Problems & Puzzles: Puzzles

Puzzle 425. Consecutive numbers, increasing quantity of prime factors JM Bergot sent one more nice puzzle: 421 is prime one factor 422=2x211 two factors 423=3x3x47 three factors 424=2x2x2x53 four factors Find a larger sequence like that  C. Rivera got a 6 terms sequence: 838561 838561 838562 2*419281 838563 3*11*25411 838564 2^2*29*7229 838565 5*7*13*19*97 838566 2*3^3*53*293 Q1. Get a larger sequence.

---

J. K. Andersen wrote:

An OEIS search on 838561 gives
http://www.research.att.com/~njas/sequences/A072875 :
Smallest start for a run of n consecutive numbers of which
the i-th has exactly i prime factors.
2, 3, 61, 193, 15121, 838561, 807905281, 19896463921,
3059220303001, 3931520917431241

I found term 8, 9, 10 in 2002. Factorizations for term 10:
3931520917431241 = 3931520917431241
3931520917431242 = 2*1965760458715621
3931520917431243 = 3*221477*5917124453
3931520917431244 = 2^2*23*42733923015557
3931520917431245 = 5*17*199*5557*41826179
3931520917431246 = 2*3*29*83*261799*1039837
3931520917431247 = 7^3*19*43*557*25187741
3931520917431248 = 2^4*31*59*167*804471071
3931520917431249 = 3^5*41*53*1721*4326271
3931520917431250 = 2*5^5*11*13^2*338377271

Finding the smallest start for term 11 looks too hard. It looks feasible
to find larger starts but I haven't decided whether to spend time on it.

***

Jarek Wroblewski wrote

Dear Carlos,
Here is my 10-term solution to Puzzle 425:

234592985842189760504794890446375781241=234592985842189760504794890446375781241
234592985842189760504794890446375781242=2*117296492921094880252397445223187890621
234592985842189760504794890446375781243=3*19*4115666418284030886049033165725890899
234592985842189760504794890446375781244=2^2*17*3449896850620437654482277800681996783
234592985842189760504794890446375781245=5*13^3*21355756562784684615821109735673717
234592985842189760504794890446375781246=2*3*11^3*29375530408488575069470935442821911
234592985842189760504794890446375781247=7^6*1994007478535217133208058635826703
234592985842189760504794890446375781248=2^7*1832757701892107503943710081612310791
234592985842189760504794890446375781249=3^8*35755675330313940025117343460810209
234592985842189760504794890446375781250=2*5^8*300279021878002893446137459771361

***

Frederick Schneider wrote:

I applied the chinese remainder theorem to the problem to find ranges
of numbers with certain factors (really factor counts) then it was
just a matter of running enough iterations to fill in the factor
blanks.

I doubt if these answers are minimal but they are the lowest ones I found:

1) 95787508020121 is prime
2) 95787508020122 = 2 * 47893754010061
3) 95787508020123 = 3 * 10211 * 3126938531
4) 95787508020124 = 2^2 * 16901 * 1416891131
5) 95787508020125 = 5^3 * 113 * 6781416497
6) 95787508020126 = 2 * 3 * 13 * 4751 * 11117 * 23251
7) 95787508020127 = 7 * 11^3 * 19 * 277 * 1953437

========================================================
1) 209530908168121 is prime
2) 209530908168122 = 2 * 104765454084061
3) 209530908168123 = 3 * 47 * 1486034809703
4) 209530908168124 = 2^2 * 397 * 131946415723
5) 209530908168125 = 5^4 * 335249453069
6) 209530908168126 = 2 * 3 * 73 * 107 * 5413 * 825947
7) 209530908168127 = 7^4 * 13^2 * 516379783
8) 209530908168128 = 2^6 * 67 * 48864484181

==================================================
1) 10118942649852121 is prime
2) 10118942649852122 = 2 * 5059471324926061
3) 10118942649852123 = 3 * 49681 * 67892773561
4) 10118942649852124 = 2^2 * 11 * 229975969314821
5) 10118942649852125 = 5^3 * 53 * 1527387569789
6) 10118942649852126 = 2 * 3 * 41 * 307 * 9719 * 13786057
7) 10118942649852127 = 7 * 13^3 * 163 * 1493 * 2703707
8) 10118942649852128 = 2^5 * 607 * 162269 * 3210413
9) 10118942649852129 = 3^6 * 17 * 157 * 5200666829

==================================================
1) 7849122373886781241 is prime
2) 7849122373886781242 = 2 * 3924561186943390621
3) 7849122373886781243 = 3 * 31 * 84399165310610551
4) 7849122373886781244 = 2^2 * 317 * 6190159600857083
5) 7849122373886781245 = 5 * 17 * 491 * 977257 * 192447331
6) 7849122373886781246 = 2 * 3 * 7 * 149 * 1579 * 794334474053
7) 7849122373886781247 = 13^3 * 23 * 113 * 744493 * 1846393
8) 7849122373886781248 = 2^6 * 3889 * 31535751373613
9) 7849122373886781249 = 3^6 * 53 * 10508579 * 19331863
10) 7849122373886781250 = 2 * 5^6 * 47 * 61723 * 86581717

***

Soon he added:

I found two 11 solutions close to each other (percentage-wise anyways):

1) 1452591346605212407096281241 = 1452591346605212407096281241
2) 1452591346605212407096281242 = 2 * 726295673302606203548140621
3) 1452591346605212407096281243 = 3 * 53 * 9135794632737184950291077
4) 1452591346605212407096281244 = 2^2 * 1447 * 250966023946995923824513
5) 1452591346605212407096281245 = 5 * 47 * 661 * 2901323 * 3223131688902289
6) 1452591346605212407096281246 = 2 * 3 * 13 * 109 * 1441361 *
118535813663970893
7) 1452591346605212407096281247 = 7^3 * 17 * 29 * 367 * 23406493050855258259
8) 1452591346605212407096281248 = 2^5 * 1193 * 1952169019 * 19491067003367
9) 1452591346605212407096281249 = 3^6 * 59 * 11953 * 2825445881066020603
10) 1452591346605212407096281250 = 2 * 5^6 * 1249 * 347227 * 107180925913547
11) 1452591346605212407096281251 = 11^8 * 57679 * 1465487 * 80168227

1) 1569237900729469390846281241 = 1569237900729469390846281241
2) 1569237900729469390846281242 = 2 * 784618950364734695423140621
3) 1569237900729469390846281243 = 3 * 70749671 * 7393381380432941711
4) 1569237900729469390846281244 = 2^2 * 4079 * 96177856136888293138409
5) 1569237900729469390846281245 = 5 * 13 * 17 * 1917274867 * 740699636491007
6) 1569237900729469390846281246 = 2 * 3 * 307 * 6607 * 188311 * 684729701246719
7) 1569237900729469390846281247 = 7^3 * 43 * 1861 * 2111059 * 27081921124597
8) 1569237900729469390846281248 = 2^5 * 61 * 56393 * 14255543400426665693
9) 1569237900729469390846281249 = 3^6 * 19 * 486181 * 233028841969597879
10) 1569237900729469390846281250 = 2 * 5^6 * 691 * 57739739 * 1258594713769
11) 1569237900729469390846281251 = 11^8 * 313 * 587 * 39844177737841

I tried to find a set of consecutive numbers given the following
limitations. Some of these are necessary in order to satisfy the
earlier numbers in the list:

1) prime
2) 2 * prime
3) 3 * (product of 2 primes)
4) 2^2 * (product of 2 primes)
5) 5 * (product of 4 primes)
6) 2 * 3 * (product of 4 primes)
7) 7^a * (product of 7-a primes) (Note: 7 can be among the remaining primes)
8) 2^b * (product of 8-b primes) (Note: 2 is not allowed to be among
the remaining primes)
9) 3^c * primes (9-c) (Note: 3 can be among the
remaining primes)
10) 2 * 5*d * primes(9-d) (Note: 5 can be among the remaining primes)
11) 11^e * primes(11-f) (Note: 11 can be among the
remaining primes)

I picked a, b, c, d and e such that there were 3 remaining prime
factors to be found by chance. Given the magnitude of the numbers
checked and their lack of low factors excluding the "Notes" in 7), 9),
10) and 11), I figured that the average number had this many factors
roughly. I did this to try maximize my chance of finding a set of
numbers that fit these constraints.

n = -6 (mod 7^3)
n = (-7-32) (mod 2^6) (So, the 8th number in the term would have 2^5
as a factor but not 2^6)
n = -8 (mod 3^6)
n = -9 (mod 5^6)
n = -10 (mod 11^8)

Using the Chinese remainder theorem, I found that numbers of the form: b*x + m
(where
x is an integer and >=0,
b = 2^6 * 3^6 * 5^6 * 7^3 * 11^ 8 = 53599795117407000000
m= 22264441931080281241
[m and b are both 20 digit numbers]
)
meet these 5 modulo constraints.

Then, it's just a matter of incrementing x and checking for a solution
set. Running this over night, I found two "11" solutions where (x=
27100688 and 29276938 respectively).

***

On Dec 23 Schneider added:

These are 34-digit numbers. I used the same technique as before just
forcing the 12th term to have 8 of its factors accounted (leaving 4 to
be found)

1) 5841309494645985646073875051281241 is prime
2) 5841309494645985646073875051281242 = 2 * 2920654747322992823036937525640621
3) 5841309494645985646073875051281243 = 3 * 401 *
4855618865042382083186928554681
4) 5841309494645985646073875051281244 = 2^2 * 95798851 *
15243683597640397707050461
5) 5841309494645985646073875051281245 = 5 * 307 * 1121357 * 2778079 *
1221555905408485169
6) 5841309494645985646073875051281246 = 2 * 3 * 241 * 7908653 *
201287631773 * 2537595020029
7) 5841309494645985646073875051281247 = 7^4 * 17 * 984648595783 *
145340908341643577
8) 5841309494645985646073875051281248 = 2^5 * 6097109 * 1748058119359
* 17126965071569
9) 5841309494645985646073875051281249 = 3^6 * 89 * 1391731113671 *
64690029021259399
10) 5841309494645985646073875051281250 = 2 * 5^6 * 79 * 1907 *
1240744650479389993391197
11) 5841309494645985646073875051281251 = 11^8 * 131 * 1049055521 *
198289157151521
12) 5841309494645985646073875051281252 = 2^2 * 3 * 13^5 * 19 * 366103
* 355265189 * 530521106039

***