mersenneforum.org Runs of factored numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2017-03-06, 20:22 #1 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 166416 Posts Runs of factored numbers Been thinking this evening about factoring consecutive numbers. Two numbers is easy: 2^74207281 and 2^74207281-1 Three numbers is also easy based upon the largest twin prime pair: 2996863034895 · 2^1290000 ± 1 and 2996863034895 · 2^1290000 Four or more numbers is a bit harder. Anyone got any ideas? It may be necessary to rely on prp cofactors beyond ECPP size.
2017-03-06, 20:59   #2
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,409 Posts

Quote:
 Originally Posted by henryzz Been thinking this evening about factoring consecutive numbers.
It is a nice problem, see here: http://www.math.uni.wroc.pl/~jwr/cons-fac/

2017-03-06, 22:49   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000101100012 Posts

Quote:
 Originally Posted by henryzz Been thinking this evening about factoring consecutive numbers. Two numbers is easy: 2^74207281 and 2^74207281-1 Three numbers is also easy based upon the largest twin prime pair: 2996863034895 · 2^1290000 ± 1 and 2996863034895 · 2^1290000 Four or more numbers is a bit harder. Anyone got any ideas? It may be necessary to rely on prp cofactors beyond ECPP size.
primes in arithmetic progressions x+1 is technically an arithmetic progression every third term will divide by 3 so find the first one that does and you already have a factor of some larger numbers by stepping. also reminds me of the longest run of composites up to a point except you want full factorizations it seems.

 2017-03-07, 03:59 #4 LaurV Romulan Interpreter     Jun 2011 Thailand 8,837 Posts You can take newpgen (or any other siever) and sieve 2^n+k for a VERY large particular n (pick one) and some k range like [-1000, +1000], then see where are the gaps. Larger gap will give your series of consecutive numbers with factors, and the factors too. Or were you talking about full factorization? Last fiddled with by LaurV on 2017-03-07 at 04:02
2017-03-07, 04:44   #5
axn

Jun 2003

22·11·107 Posts

Quote:
 Originally Posted by LaurV Or were you talking about full factorization?
I believe so.

 2017-03-07, 17:57 #6 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 10110011001002 Posts It seems the idea used for the larger runs is for many of the numbers to have algebraic factors. The run of 20 numbers has 9/20 with algebraic factors splitting them in half. I am not certain how to go about creating these polynomials or if it is possible to have a higher number with algebraic factors.
 2017-03-07, 18:47 #7 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3·3,041 Posts length 22.. "new" record Ok, I have just made it length 21 by factoring N-1 :-) Code: N-1 = 5213411917...84<303> = 2^2 · 23 · 41 · 290399 · 82049473563797795110840675341962134165303 · 5800687119043966076458093431403599342066486860130593363750638259379043892237928868657375528720659036199535857003362322259881288749204326339939518541384047634456777775176259082126086907366473591808484877382252182189655036384810428841744360051529320492751 EDIT: ...have just made it length 22 by factoring N-2 :-) Code: N-2 = 5213411917...83<303> = 3 · 1231 · 2046425585967871763903675443<28> · 125250681966946964598302585902770629381<39> · 5507654344...57<234> Last fiddled with by Batalov on 2017-03-07 at 23:25
2017-03-08, 14:46   #8
Dr Sardonicus

Feb 2017
Nowhere

DE016 Posts

Quote:
 Originally Posted by henryzz It seems the idea used for the larger runs is for many of the numbers to have algebraic factors. The run of 20 numbers has 9/20 with algebraic factors splitting them in half. I am not certain how to go about creating these polynomials or if it is possible to have a higher number with algebraic factors.
An obvious technique to use is CRT, but the number of nicely factored polynomials with small integer differences suggests more sophisticated methods have been brought to bear. Let's see here...

The expressions at Largest Consecutive Factorizations just below the first occurrence of "4178" (do a string search) yield a cornucopia of polynomial expressions involving curious substitutions.

Hmm, looking at the references, A Chinese Prouhet–Tarry–Escott solution sort of stands out...

BTW, Batalov has been credited with extending the run at the previously-referenced site.

2017-03-09, 19:24   #9
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

22×1,433 Posts

Quote:
 Originally Posted by Dr Sardonicus An obvious technique to use is CRT, but the number of nicely factored polynomials with small integer differences suggests more sophisticated methods have been brought to bear. Let's see here... [Google, Google, toil and trouble] The expressions at Largest Consecutive Factorizations just below the first occurrence of "4178" (do a string search) yield a cornucopia of polynomial expressions involving curious substitutions. Hmm, looking at the references, A Chinese Prouhet–Tarry–Escott solution sort of stands out... BTW, Batalov has been credited with extending the run at the previously-referenced site.
Not sure how he used polrootsmod currently. I will come back to this another day when I have more of a brain.

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson Operazione Doppi Mersennes 3 2014-02-16 15:19 aketilander Factoring 4 2012-08-08 18:09 hj47 Software 3 2009-10-07 15:21 koders333 Factoring 12 2006-03-31 16:06 Unregistered Software 16 2004-08-10 13:34

All times are UTC. The time now is 17:07.

Wed Oct 21 17:07:01 UTC 2020 up 41 days, 14:17, 0 users, load averages: 1.15, 1.77, 1.89