mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2017-03-06, 20:22   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

7·811 Posts
Default 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.
henryzz is offline   Reply With Quote
Old 2017-03-06, 20:59   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

25238 Posts
Default

Quote:
Originally Posted by henryzz View Post
Been thinking this evening about factoring consecutive numbers.
It is a nice problem, see here: http://www.math.uni.wroc.pl/~jwr/cons-fac/
R. Gerbicz is offline   Reply With Quote
Old 2017-03-06, 22:49   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-03-07, 03:59   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

3·2,861 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2017-03-07, 04:44   #5
axn
 
axn's Avatar
 
Jun 2003

23·3·193 Posts
Default

Quote:
Originally Posted by LaurV View Post
Or were you talking about full factorization?
I believe so.
axn is offline   Reply With Quote
Old 2017-03-07, 17:57   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

7·811 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2017-03-07, 18:47   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

2·7·647 Posts
Cool 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
Batalov is offline   Reply With Quote
Old 2017-03-08, 14:46   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

63078 Posts
Default

Quote:
Originally Posted by henryzz View Post
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...

[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.
Dr Sardonicus is offline   Reply With Quote
Old 2017-03-09, 19:24   #9
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

7·811 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
henryzz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
short runs or long runs MattcAnderson Operazione Doppi Mersennes 3 2014-02-16 15:19
Factored vs. Completely factored aketilander Factoring 4 2012-08-08 18:09
Who runs prime95 ECM? hj47 Software 3 2009-10-07 15:21
Same team factored RSA challenge numbers in recent time koders333 Factoring 12 2006-03-31 16:06
My CPU Runs at 100% Unregistered Software 16 2004-08-10 13:34

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

Thu Jul 9 07:33:13 UTC 2020 up 106 days, 5:06, 0 users, load averages: 1.51, 1.51, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.