Search the web
Sign In
New User? Sign Up
primeform · User group for PFGW & PrimeForm programs
? Already a member? Sign in to Yahoo!

Yahoo! Groups Tips

Did you know...
Want to share photos of your group with the world? Add a group photo to Flickr.

Best of Y! Groups

   Check them out and nominate your group.
Click here for the latest updates on Groups Message search

Messages

  Messages Help
Advanced
Update on search for consecutive factored titanics   Topic List   < Prev Topic  |  Next Topic >
Reply  | 
[primeform] Re: Update on search for consecutive factored titanics

In 2002 Jack Brennen asked in
http://groups.yahoo.com/group/primenumbers/message/9879 :
> For a given n>=2, what is the largest n-tuple of
> consecutive integers for which the prime factorization
> of each member is known?

This is now answered at the new record page
"Largest Consecutive Factorizations" at
http://hjem.get2net.dk/jka/math/consecutive_factorizations.htm
Only cases with at least 500 digits are listed. This currently means n<=7.
(I call it k instead of n).

Jack also wrote:
> So I'm curious, what is the longest titanic factorized n-tuple?
> The above-mentioned 5-tuple is titanic. Can someone give me
> 6 consecutive titanic numbers along with their prime factorizations?

It took 5 years but then he gets one more than requested:
m to m+6 for m = 21247003564*2411#-1 with 1037 digits.
Prime factorizations where pN is an N-digit prime:

m = 12906420959*p1027
m+1 = 2^2*103*51570397*2411#, where 2411# = 2*3*5*7*...*2411
m+2 = 2524541*p1031
m+3 = 2*5002841*6245491249*p1020
m+4 = 3*485475518243*p1025
m+5 = 2^2*(5311750891*2411#+1)
m+6 = 5*3691*23063^2*2961991*19076087*3778442561*p1001

PrimeForm/GW made prp tests and Marcel Martin's Primo proved
p1027, p1031, p1020, p1025, p1001.

(m+5)/4 = 5311750891*2411#+1 = p1037 was found by Markus Frind
and Paul Underwood with NewPGen and PrimeForm/GW in 2003
during an AP8 search:
http://tech.groups.yahoo.com/group/primenumbers/message/12734
They found more than 10 million prp's and kindly gave me access
to 7278744 stored ones so I could search for 7 consecutive titanic
factorizations with limited computing power.

Each of the prp's are of form x+1 = k*2411#+1 for small k, so x
is trivially factored. If x and x+1 are both factored then so are nx
and nx+n for small n, so (x,x+1) can potentially be used for
7 consecutive factorizations in 21 ways:
6 ways around (x,x+1), 5 ways around (2x,2x+2) if 2x+1 is also
factored, 4 ways around (3x,3x+3), 3 around (4x,4x+4),
2 around (5x,5x+5), and 1 last way from 6x to 6x+6.

The x values are part of the same arithmetic progression k*2411#.
This made it possible to sieve all possibilities to 10^12 in the same
sieve run with my APTreeSieve. It stored found factors and after
dividing by them, the cofactors of x-1 and 2x+1 were prp tested.
If one of them is prp then there are 3 consecutive factorizations
(x-1,x,x+1) or (2x,2x+1,2x+2), giving 9 possibilities of extending to 7.
If x-1 and 2x+1 remained unfactored then that x was skipped in
order to spare further cofactor prp tests which would give much
smaller chance of extending to 7 numbers.

The single solution with 7 numbers is 4x-1 to 4x+5 for
x = 5311750891*2411#.
There were many with 6 numbers out of 7, and lots with 5.
Limited GMP-ECM found many factors above 10^12 but no
complete factorizations to reach 7.
k=8 would be reached if any of these 5 composites were complete factored:

(21247003564*2411#-2)/(2*63501029*1676569836074094735760183)
(21247003564*2411#+6)/(2*3^3*44041*50036011*18714589754509974127923506831749)
(9902172078*2411#+3)/3
(10520194890*2411#+3)/(3*137809990746376231)
(9988354978*2411#+3)/(3*31850135205297880082057*623786556972123391792124611*1426\
15599612981064331297)

All 5 have had the recommended GMP-ECM work for 30-digit factors:
453 curves with B1=250000.
The first 2 are at the ends of the k=7 record. The last 3 are holes
in cases with 7 of 8 factored. All 3 happen to be of form 2x+3.

The search for k=7 was originally planned for June 2005 together
with Décio Luiz Gazzoni Filho after discussion at
http://tech.groups.yahoo.com/group/primeform/message/5975?l=1
In fact, this post is a delayed follow-up to that post.
Décio did not have time and I did it alone after getting a faster
computer this year.

The records for k=2 and k=3 are the Mersenne and twin prime records.
The records for k=4 and k=5 were found by starting with known
Cunningham chains in The Prime Pages database and factoring a
single additional number.
If (p, 2p+1, 4p+3) is a CC3 with p+1 factored by construction,
then (4p, 4p+2, 4p+3, 4p+4) is factored, and only 4p+1 is missing for k=5.
For k=4 there is both a 2063-digit record with proven prime factors
(the same as k=5), and a 4187-digit record with a prp factor
(240819405*2^13879+3)/(3*13*43*358877).
A certification of that would give shared record credit.
The record for k=6 is the same as k=7.

The record page is mentioned at
http://mersenneforum.org/showthread.php?p=111804#post111804
where some people object to prime numbers being allowed as
their own prime factorization.

--
Jens Kruse Andersen




Tue Aug 7, 2007 3:55 am

jkand71
Offline Offline
Send Email Send Email

 | 
Expand Messages Author Sort by Date

OK, so I've been unsuccessfully trying to solve Jack Brennen's problem of finding 6 consecutive fully factored titanic integers. Turns out that (as usual) Jens...
Décio Luiz Gazzoni...
deciogazzoni
Offline Send Email
May 28, 2005
10:06 pm

Decio: I have a feeling that there ought to be a meta-theorem: no smart method to solve Jack's problem can possibly be better than the dumbest method of making...
David Broadhurst
djbroadhurst
Offline Send Email
May 28, 2005
10:39 pm

... I have to disagree. First, you're making an assumption that factoring is inherently hard, which we don't know that it is. I believe if factoring were...
Décio Luiz Gazzoni...
deciogazzoni
Offline Send Email
May 28, 2005
11:46 pm

... Just for kicks, here's an heuristic for a simple-minded strategy that finds 5 fully-factored integers (somehow the 6th is given, either by my method or...
Décio Luiz Gazzoni...
deciogazzoni
Offline Send Email
May 29, 2005
6:42 pm

Decio: I hoped that you would disgaree! ... I always do assume that :-) ... Yes that would be neat. In effect, 2/6 would be doable by SIQS, after 4/6 came from...
David Broadhurst
djbroadhurst
Offline Send Email
May 28, 2005
11:56 pm

... In that case, your meta-theorem depends on an unproven hypothesis -- and I don't see much of a chance of proving a lower bound on the complexity of...
Décio Luiz Gazzoni...
deciogazzoni
Offline Send Email
May 29, 2005
12:14 am

... But as you are not in process, I'm suggesting that that you _may_ be tilting at windmills. Can there exist two polynomials P(x) and P(x)+c with c in [1,5] ...
David Broadhurst
djbroadhurst
Offline Send Email
May 29, 2005
12:59 am

... Yes. ... No, I don't. But I was just arguing that it may be fallacious to think that Mertens supports your meta-theorem, when one of the avenues of attack...
Décio Luiz Gazzoni...
deciogazzoni
Offline Send Email
May 29, 2005
1:40 am

Interesting to see so much effort put into something which I just sort of threw off as a random thought a few years back. :) My personal opinion is that you...
Jack Brennen
jbrennen
Offline Send Email
May 29, 2005
2:04 am

... Yes, the approach that I initially used is a dead-end. However, I changed my focus to algebraic factorizations such that the second largest factor is...
Décio Luiz Gazzoni...
deciogazzoni
Offline Send Email
May 29, 2005
4:28 am

... Yes. ... I know little of algebraic factors and don't want to judge between David and Décio. Décio's estimates of 148e6 and 170e6 values looks right with...
Jens Kruse Andersen
jkand71
Offline Send Email
May 30, 2005
11:58 am

Jens, If my values are correct, then that approach is hopeless. I was expecting something an order of magnitude or two smaller. Right now I've barely sieved an...
Décio Luiz Gazzoni...
deciogazzoni
Offline Send Email
May 30, 2005
1:29 pm

In 2002 Jack Brennen asked in ... This is now answered at the new record page "Largest Consecutive Factorizations" at ...
Jens Kruse Andersen
jkand71
Offline Send Email
Aug 7, 2007
4:00 am

... Call me impressed. :)...
Jack Brennen
jbrennen
Offline Send Email
Aug 7, 2007
5:07 am

... means n<=7. How about the largest 8 consecutive integers with known factorization? It is interesting to know the largest example for the least n which ...
jarek372000
Offline Send Email
Aug 7, 2007
8:30 pm

... That's neat! Given that we can factorize 111 digit numbers, without too much trouble, a 9th-order poly would be even neater. (8th order would do for Sean...
David Broadhurst
djbroadhurst
Offline Send Email
Aug 7, 2007
11:01 pm

... I am not aware of any published result for 8 numbers, but I might consider lowering the 500-digit limit if I heard a non-trivial result. Of course, there...
Jens Kruse Andersen
jkand71
Offline Send Email
Aug 7, 2007
11:59 pm

... 11 or 12 factorizatons at 125 digits may be reduced to 8, by setting x = -13860*y^2, since then the remainder are trivial, at only half that size: ...
David Broadhurst
djbroadhurst
Offline Send Email
Aug 8, 2007
2:21 pm

... Sextic deconstruction: P(c,x) = prod(k=1,length(c),x - c[k]^2) Q(c,x) = P(c,x) - P(c,0) a = [22, 61, 86, 127, 140, 151]; b = [35, 47, 94, 121, 146, 148]; ...
David Broadhurst
djbroadhurst
Offline Send Email
Aug 12, 2007
7:18 am

... Wow! Congrats to Jens for 5 years work :-) ... whereas sane people know that primes are completely factorized. Best regards from David...
David Broadhurst
djbroadhurst
Offline Send Email
Aug 7, 2007
10:51 pm
Advanced

Copyright © 2010 Yahoo! Inc. All rights reserved.
Privacy Policy - Terms of Service - Guidelines - Help