Problems & Puzzles: Puzzles

Puzzle 1069 Follow up to Puzzle 1066 Fred Schneider send the following follow uo to Puzzle 1066: Here's a (complete) set of 6 consecutive triangular numbers (based on 7 consecutive numbers, from 146444713841 to 146444713847) which all have 9 distinct prime factors:   10723027106059410843561 = 3 * 7 * 19 * 127 * 151 * 263 * 887 * 4943 * 1215329 10723027106205855557403 = 3 * 7 * 19 * 37 * 151 * 229 * 491 * 35201 * 1215329 10723027106352300271246 = 2 * 11 * 13 * 17 * 37 * 229 * 491 * 35201 * 15060131 10723027106498744985090 = 2 * 3 * 5 * 11 * 13 * 17 * 79  * 15060131 * 123582037 10723027106645189698935 = 3 * 5 * 59 * 79 * 97 * 157 * 227 * 359 * 123582037 10723027106791634412781 = 59 * 89 * 97 * 113 * 157 * 179 * 227 * 359 * 81349   Q. Can you find a complete set of 6 consecutive triangular numbers which all have n distinct prime factors (where n > 9)?

---

During the week 25-31, Dec 2021, contributions came from Giorgos Kalogeropoulos, Oscar Volpatti

***

Giorgos wrote:

Here is my answer:   

 

n=10

(based on 7 consecutive numbers from 10615645066757491577 to 10615645066757491583)

 

56345960091686333905511328359991719253 = 3 * 23 * 127 * 263 * 887 * 2657 * 4943 * 560797 * 51626189 * 72489097
56345960091686333916126973426749210831 = 3 * 7 * 13 * 23 * 41 * 79 * 2657 * 560797 * 51626189 * 36015881535671
56345960091686333926742618493506702410 = 2 * 5 * 7 * 13 * 41 * 79 * 277 * 45161 * 42430004207 * 36015881535671
56345960091686333937358263560264193990 = 2 * 3 * 5 * 31 * 277 * 2677 * 45161 * 47569 * 896377709 * 42430004207
56345960091686333947973908627021685571 = 3 * 31 * 43 * 61 * 2677 * 8641 * 47569 * 152293 * 1537709 * 896377709
56345960091686333958589553693779177153 = 43 * 61 * 137 * 317 * 1237 * 3347 * 8641 * 152293 * 1537709 * 59039293
 

 

n=11

(based on 7 consecutive numbers from 96166724366466386929 to 96166724366466386935)
 

 

4624019437687959954275240332581004218985 = 5 * 11 * 127 * 263 * 887 * 4943 * 13669 * 25589 * 31153 * 80231 * 656675969
4624019437687959954371407056947470605915 = 3 * 5 * 11 * 19 * 953 * 13669 * 25589 * 31153 * 80231 * 1953949 * 906032639
4624019437687959954467573781313936992846 = 2 * 3 * 13 * 19 * 137 * 139 * 953 * 545089 * 1953949 * 178163483 * 906032639
4624019437687959954563740505680403379778 = 2 * 13 * 43 * 89 * 137 * 139 * 4801 * 12611 * 545089 * 178163483 * 415035389
4624019437687959954659907230046869766711 = 3 * 7 * 43 * 89 * 317 * 4801 * 7297 * 12611 * 274471 * 3606413 * 415035389
4624019437687959954756073954413336153645 = 3 * 5 * 7 * 241 * 317 * 7297 * 23399 * 274471 * 413129 * 3606413 * 8255717

 

***

Oscar wrote:

Dear Carlos,

This week I didn't attempt an exhaustive search: I used a nice construction to generate many solutions.

I'll show it with a simple example for n = 4.

Let's search for a number x = 72*y+1 satisfying the following constraints:

72*y+1 = 11*q1

72*y+2 = 2*5*q2

72*y+3 = 3*q3

72*y+4 = 2*2*q4

72*y+5 = 7*q5

72*y+6 = 2*3*q6

72*y+7 = 5*q7

If q1,...,q7 are all prime, then T(x)...T(x+5) is a solution for the case n = 4.

All relations hold for y = 385*z+64 and x = 27720*z+4609, so:

q1 = 2520*z+419

q2 = 2772*z+461

q3 = 9240*z+1537

q4 = 6930*z+1153

q5 = 3960*z+659

q6 = 4620*z+769

q7 = 5544*z+923

These polynomials are simultaneously prime for (infinitely?) many arguments z, starting from z = 2345,

so we have the solution x = 65008009.

 

For larger n, the strategy doesn't change.

Choose x=72*y+1 or x=72*y+65, otherwise at least one number between T(x) and T(x+5) will be divisible by 4 or by 9.

Express each number from x to x+6 as the product of suitable fixed small primes and an unknown factor.

Solve all congruences, obtaining a relation of the form x = a*z+b.

Use it to express unknown factors as linear functions of argument z.  

Find the smallest value z which makes the polynomials simultaneously prime (infinitely many such values are conjectured to exist).

 

The drawback of this approach is that solutions are very large.

Here are my "smallest" results for 5<=n<=15:

 

n=5   

x=27493265

 

n=6

x=1582000002929

 

n=7

x=102680561669606489

 

n=8

x=17973285151137752532665

 

n=9

x=4271707046774786911741272665

 

n=10

x=1119120048145603254199164646029185

 

n=11

x=2191155070726816094680948994929950965689

 

n=12

x=1474273034541658310537728680013376311596120785

 

n=13

x=61921247734541959586398101040506977562355825509185

 

n=14

x=8113638595709703351532026851379194559720103929901997692729

 

n=15

x=975891275708805924498015621987504452206477389544371807091575737209

Later he added on my request:

here is the factorization of my solution for n=10, starting from index

x = 1119120048145603254199164646029185.

 

T(x) = 3*5*17*23*29*31*43*67*p1*p2

T(x+1) = 3*11*17*23*29*31*43*67*p2*p3

T(x+2) = 2*11*37*41*53*71*79*83*p3*p4

T(x+3) = 2*3*37*41*53*71*79*83*p4*p5

T(x+4) = 3*5*7*13*19*47*61*73*p5*p6

T(x+5) = 5*7*13*19*47*59*61*73*p6*p7

where:
 

p1 = 223824009629120650839832929205837

p2 = 184181378053313107634239

p3 = 101738186195054841290833149639017

p4 = 7474664458767634344851

p5 = 373040016048534418066388215343063

p6 = 309265253870763705104021

p7 = 18968136409247512783036688915749

 

And here is a more detailed exposition of my approach.

 

We need to find 7 consecutive numbers x,...,x+6 such that triangular numbers T(x),...,T(x+5) all have n=10 distinct prime factors.

If 8 divides m, then 4 divides T(m-1) and T(m).

Hence 8 can't divide x,...,x+6 and it must be x == 1 mod 8. 

If 9 divides m, then 9 divides T(m-1) and T(m) too.

Hence 9 can't divide x,...,x+6 and it must be x == 1 or 2 mod 9.

So it must be x=72*y+1 or x=72*y+65.

In order to have the correct number of prime factors in T(x),...,T(x+5):

each of the odd numbers x, x+2, x+4, x+6 must be the product of k distinct primes;

each of the even numbers x+1, x+3, x+5 must be twice the product of 10-k distinct primes.

Hence the factorizations of x,...,x+6 involve N = 4*k + 3*(11-k) = 33+k primes, counted with multiplicity.

It can't be k=1, as there are no four consecutive odd primes; I chose k=2, N=35.

Let's assign N-7=28 primes, keeping one prime factor per number undetermined. 

Having 7 consecutive integers, we must use small primes 2 (four times), 3 (twice), 5 (once or twice), and 7 (once).

We also need 19 or 20 larger primes (depending on how many 5 were placed), each to be used once; I chose next 19 primes, between 11 and 83.

The given solution comes from the following assignments:

x = 5*p1,

x+1 = 2*3*17*23*29*31*43*67*p2

x+2 = 11*p3

x+3 = 2*2*37*41*53*71*79*83*p4

x+4 = 3*p5

x+5 = 2*5*7*13*19*47*61*73*p6

x+6 = 59*p7

In this case, it must be x=72*y+65.

All constraints are satisfied by numbers of the form x=a*z+b, with:

a = 3204774188271310216267488215913480 = 12*(83#)

b = 1119120048145603254199164646029185

The integer coefficients a and b were computed by repeatedly apply Bezout's identity.

We obtain similar linear functions pi = ai*z+bi for the undetermined factors.

According to Dickson's conjecture, there are infinitely many values z for which p1,...,p7 are simultaneously prime.

For this lucky assignment, the first such value is z=0, so x=b is a solution.

 

I actually checked several assignments before finding this lucky one.

In my first attempt, the first suitable value was z = 62319722, providing the much larger solution:

x = 199720637621689169988490888429408970509385

 

***