View Single Post
Old 2002-10-14, 21:51   #4
ewmayer's Avatar
Sep 2002
Rep├║blica de California

32·1,303 Posts

Note: this is a continuation of a discussion started within Tony Reix's
"Goldbach Conjecture..." thread. I moved it over to this thread since
it more logically belongs here.

Originally Posted by akruppa
I just found this factorization with GMP-ECM:

s_0 = 4
s_11 = 2 * 8191 * 4194619596652733275824127 * prp1143

I haven't tried to find any factors of M(4194619596652733275824127) or M(prp1143), though.
Yep, I just found this one last Friday myself (actually, it was running on
one of my Alphas, and at the same time I was in contact with Paul
Zimmerman re. the large-integer multiply algorithms used by GMP-ECM,
and using timings for the same cofactor as an example. He fired up a
few curves on one of his machines, and a few minutes later reported
the 25-digit factor you also found, and the probable-prime cofactor.)

(I'm planning on proposing these sequences as a nice factoring challenge
in a mail to Zimmerman, Montgomery, Crandall and some others - Peter M.
has long been interested in factorizations of regular Lucas sequences,
so this is close to his normal stomping grounds, but I think of some
considerable interest by itself).

Here are some more-complete data (*= indicates an S-term divide by a
Mersenne prime):

S0 [4] = 2.2
S1 [4] *= 2.7
S2 [4] = 2.97
S3 [4] *= 2.31.607
S4 [4] = 2.708158977
S5 [4] *= 2.127.7897466719774591
S6 [4] = 2.22783.265471.592897.2543310079.220600496383
S7 [4] = 2.113210499946729046527.71510428488234435849323250891975205208728978040847871
S8 [4] = 2.12289.665972737.3867637345756894712411491994657791.PRP100
S9 [4] = 2.1049179854847.27293256153178849431531258375109421840383.C241
S10[4] = 2.C586
S11[4] *= 2.8191.4194619596652733275824127.PRP1143

Here are the first few of the S0 = 10 sequence:

S1 [10] *= 2.7.7
S2 [10] = 2.4801
S3 [10] *= 2.31.1487071
S4 [10] = 2.52609.80789839489

S5 [10] *= 2.127.769.36810112513.10050007226929279
S6 [10] = 2.1279.212542494659839.9603749795193112055306105436352550778712005121
S7 [10] = 2.3583.55782066825217.45896243081785568814275071.PRP85
S8 [10] = 2.5119.64419841.128905150832968536864331777.C217
S9 [10] = 2.51199.10162177.C498
S10[10] = 2.4906458295537663.184023456784189587457.C984
S11[10] *= 2.8191.116184333317857001473.C2015

Originally Posted by wpolly
I guess that for every positive integer n,

Indeed it does. As is well-known, for the LL test we can use starting values

4, 52, 724, ..., U{n}, ..., where U{n} =14 U{n-1} - u{n-2}


10, 970, 95050, ..., V{n}, ..., where V{n} = 98V{n-1} - V{n-2},

where we define U1 = U0 = 4 and V1 = V0 = 10.

(I'm only interested in the starting values that work for *any* Mersenne
prime, not the additional ones that give an S_(p-2) that has
M(p) as a factor, for some particular p only, by mere happenstance.)

Thus we have

S0 [52] = S0[4].13
S1 [52] *= S1[4].193
S2 [52] = S2[4].37633
S3 [52] *= S3[4].1416317953
S4 [52] = S4[4].769.314113.8304419329
S5 [52] *= S5[4].81409.49427725039504674210783029592577
S6 [52] = S6[4].310273.1674378241.31166535458340592006672641989850047959301818960703585863681
S7 [52] = S7[4].15361.C143
S8 [52] = S8[4].31252623361.261536198433160793898188046337.26315739764268897985597215805161179137.C216
S9 [52] = S9[4].3305473.3536560129.11590564601857.C557
S10[52] = S10[4].270337.21386688145268737.C1150
S11[52] *= S11[4].C2343

For the starting value V2 = 970, we have

S1 [970]*= S1[10].9601
S2 [970] = S2[10].92198401
S3 [970]*= S3[10].193.3457.12740606401
S4 [970] = S4[10].7998337.178600862593.50583668732161
S5 [970]*= S5[10].453889.6326017.1818474177246611367987147117589497752930980982885377
S6 [970] = S6[10].103356618801671002199041.PRP105
S7 [970] = S7[10].147457.23789569.5161326615565677037332776796681217.C209
S8 [970] = S8[10].132408306782587129755649.PRP487
S9 [970] = S9[10].12289.285922099201.2203263382290433.2369699936274268446721.C968
S10[970] =S10[10].356671489.389603329.883184938795009.C2007

Similarly, we have that S_j[4] divides S_j[724] (and so on), and that
S_j[10] divides S_j[970] and so on. When we divide out this "primitive part"
of any S_j[U,V{n}] it keeps the remaining cofactor from growing too large
with increasing starting values of the LL sequence, which is desirable for
a sequence that is to be used as a benchmark factoring challenge. That is,
even though for a given starting value the S-terms get large very quickly,
for any index j we have a decent number of not-too-huge numbers to factor,
e.g. S_j[U1], S_j[U2]/S_j[U1], etc.

Now, I don't believe there is any correlation between factors of these
and Mersenne prime exponents - 607 and 1279 appear as factors for a different reason,
which follows from the first of the following claims, which I leave to the interested readers to
prove for themselves.

Define: For the (j)th term of the sequence with starting value S_0
(where S_0 = U{n} or V{n}), call S_j[U,V{1}] the primitive part
of S_j[S_0] and call S_j[S_0]/S_j[U,V{1}] the nonprimitive part.
(E.g. S1[970] has primitive part = S1[10] and nonprimitive part = 9601.)

(1) For any of the aforementioned starting values of the sequence and n > 2,
odd factors of S_(n-2) have one of the two forms given by q = k*2^n +- 1.


The smallest possible odd factor of S_(n-2) is q = 2^n-1,
and this minimum is achieved when q is (by definition) a Mersenne prime.

(I'd long wondered about the possibility of odd factors
of S_(n-2) smaller than 2^n-1, and this neatly rules that possibility out).
Clearly, if this minimum factor occurs, it must divide the primitive part of S_(n-2).

In addition, there appear to be further restrictions on the factors, depending
on which term in either of the starting sequences one uses for the LL sequence.
The following rules appear to hold:

For S_0 = U2 (52) or V2 (970):

Factors of the nonprimitive part must == +1 modulo 2^n, and have k == 0 modulo 2*3.

For S_0 = U3 (724) or V3 (95050):

All factors of the nonprimitive part of form p = k.2^n + 1 have k == 0 mod 2*3*5;
All factors of the nonprimitive part of form p = k.2^n - 1 have k == 0 mod 5;

For S_0 = U4 (10084) or V4 (9313930):

All factors of the nonprimitive part of form p = k.2^n + 1 have k == 0 mod 2*3*7;
All factors of the nonprimitive part of form p = k.2^n - 1 have k == 0 mod 7;

The one exception is that S1[10084] has the factor 7 in both its primitive part
(as expected) and its nonprimitive part (which violates the second of the above,
i.e. this repeated factor is of p = k.2^n - 1 with k = 1, which is not a multiple of 7).

Other Notes:

In addition to the fact that S_j[U_(k-1)] | S_j[U_k] (similarly for the
V-sequence of starting values), we have that

S_j[U_k] = S_j[U_(k-1)]*{ S_(j+1)[U_(k-1)] - 1 } .

(For example, S3[52] = S3[4].1416317953 = S3[4]*{ S4[4] - 1 }. )
Note, however, that this identity does not
make trivial the problem of factoring the nonprimitive part S_j[U_k]/S_j[U_(k-1)],
since e.g. if S_(j+1)[U_(k-1)] factors as 2*q1*q2*...*qk, in order to factor
we still have to factor S_j[U_k]/S_j[U_(k-1)] = 2*q1*q2*...*qk - 1.

This is fun,
ewmayer is offline   Reply With Quote