mersenneforum.org > Math Blöde Fragen über die LL Primalitätsprüfung
 Register FAQ Search Today's Posts Mark Forums Read

 2006-09-18, 05:01 #1 brunoparga     Feb 2006 Brasília, Brazil 3·71 Posts Blöde Fragen über die LL Primalitätsprüfung Hi, everyone. I hope someone might help me with this. If I understand the way LL test is done, what Lucas had discovered is that there's this sequence, obtained by taking a first member (like 4), squaring it, subtracting two and repeating the process. If the n-th member of the sequence divides M(n+1), then M(n+1) is prime. The first question is: I've read somewhere that the first member needs not be 4, it may take other values, like 10. When does this happen? Is it useful for the tests we do? The second question. Again if I understand it correctly, the way Lehmer contributed to the test was using "modular arithmetics" or, to put it the way I understand it, whenever the value of Lucas' sequence gets larger than the Mersenne number (not the exponent, the number itself) you're testing, divide the former by the latter, discard the result and take only the residue as the current value for the sequence. It's this that makes GIMPS possible, because otherwise the values used would get too large too early (if for some weird reason I'm not wrong, then the sequence would get way larger than M44 by the 25th iteration). The question is: if we didn't do the modulo operation, i.e. dividing and taking only the residue, how large would the Lucas sequence be for, say, M44? I know this will probably be so large it cannot even be represented in a reasonable way, but I'd be content with an analogy (like, you'd need a computer as big as the Solar System to store the number or something like that). All I want is a way of thinking about that number. Thanks a lot, Bruno PS: By the way, this is just the second time I post here in the Math forum. Remembering my first post, perhaps someone could please find a small factor for 2^32582656 * M32582657 + 1, that is, the number following the 44th perfect number?
 2006-09-18, 11:35 #2 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts As for the size: the first four terms in the LL sequence are 4, 14, 194, 37634. From here on the subtraction of 2 in each step has very little effect on the size of the numbers, so we can pretend that the number is simply squared in each remaining step. log10(37634) = 4.57558..., and in each step the log size doubles, so after p-1 steps we'd have a number n so that log10(n) = ~4.57558 * 2p-5. Now 2p-5 is about as large as Mp itself, so if you wanted to write down the number of digits in the final LL value for M44, you'd get a large poster full in tiny font, just like the new M44 poster will be. That final LL value is far too great to compare it to anything that physically exists. Alex Last fiddled with by akruppa on 2006-09-20 at 20:56
2006-09-19, 17:31   #3
ATH
Einyen

Dec 2003
Denmark

2·3·13·41 Posts

Quote:
 perhaps someone could please find a small factor for 2^32582656 * M32582657 + 1, that is, the number following the 44th perfect number?
Some small factors of 2^32582656*M44+1:

7,11,67,34549,127541

no other factors below 10^10.

 2006-09-19, 22:07 #4 brunoparga     Feb 2006 Brasília, Brazil 3·71 Posts Well, thanks a lot both of you guys I'd also like to know when does the first number in the LL sequence need not be 4 - I've read somewhere that it can be, say, 10. Thanks again, Bruno
2006-09-21, 01:38   #5

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts

Quote:
 Originally Posted by brunoparga I'd also like to know when does the first number in the LL sequence need not be 4 - I've read somewhere that it can be, say, 10.
See the "Initial Values of LLT" section on the "Lucas-Lehmer test" page of Mersennewiki at http://www.mersennewiki.org/index.ph..._Values_of_LLT.

2006-09-23, 01:34   #6
ATH
Einyen

Dec 2003
Denmark

2×3×13×41 Posts

Quote:
 The second question. Again if I understand it correctly, the way Lehmer contributed to the test was using "modular arithmetics" or, to put it the way I understand it, whenever the value of Lucas' sequence gets larger than the Mersenne number (not the exponent, the number itself) you're testing, divide the former by the latter, discard the result and take only the residue as the current value for the sequence. It's this that makes GIMPS possible, because otherwise the values used would get too large too early
I found a more accurate way of finding the size of $S_{n-2}$:

The LL-test comes from the Lucas Sequences $V_n=\alpha^2+\beta^2$. $\alpha$ and $\beta$ are roots of the polynomial $X^2-PX+Q$ with P=2 and Q=-2 so $\alpha=\frac{2+\sqrt{12}}{2}=2.7320508...$ and $\beta=\frac{2-\sqrt{12}}{2}=-0.7320508....$.

Now $S_{n-2}$ is given by:
$\Large S_{n-2} = \frac{v_{2^{n-1}}}{2^{(2^{n-2})}}=\frac{\alpha^{(2^{n-1})}}{2^{(2^{n-2})}}$
$\beta^{(2^{n-1})}$ can be ignored since $\middle|\beta\middle|<1$ so it goes towards zero very quickly. Using base-10 Log:

$Log(S_{n-2}) = Log(\alpha^{(2^{n-1})})-Log(2^{(2^{n-2})}) = (2^{n-1})*Log(\alpha)-(2^{n-2})*Log 2=2^{n-2}*(2*Log(\alpha)-Log2)=2^{n-2}*0.5719475475$

$LogLog(S_{n-2}) = (n-2)*Log 2+Log(0.5719475475)=(n-2)*Log2-0.2426437$

so for M44:

$LogLog(S_{32582655}) = 32582655*Log2-0.2426437 = 9808356.2507271$

$\Large S_{32582655}=10^{(10^{9808356.2507271})}$

Last fiddled with by ATH on 2006-09-23 at 01:59

 2006-09-23, 01:54 #7 ATH Einyen     Dec 2003 Denmark 2×3×13×41 Posts Comparing for fun to the approximated value skipping the "-2" step in each iteration, let me call the this sequence T: $T_0=4$ and $T_{n-2}=4^{(2^{n-2})}$ $Log(T_{n-2}) = 2^{n-2}*Log 4=2^{n-2}*0.60205999$ $\Large \frac{T_{n-2}}{S_{n-2}}=\frac{10^{(2^{(n-2)}*0.60205999)}}{10^{(2^{(n-2)}*0.57194755)}}=10^{(2^{(n-2)}*(0.60205999-0.57194755))}=10^{(2^{(n-2)}*0.03011244)}$ For M44 approximating $S_{n-2}$ with $T_{n-2}$ overestimates by a factor of: $\Large 10^{(2^{32582655}*0.03011244)} = 10^{(10^{9808354.97})}$ just by skipping -2 :) Last fiddled with by ATH on 2006-09-23 at 01:58
 2006-09-23, 03:38 #8 brunoparga     Feb 2006 Brasília, Brazil 3×71 Posts Even more questions Wait a minute; if I understand your last post correctly, you're telling me T(32582655) is almost S(32582655) times bigger than S(32582655) itself, that is, it'd be something like [S(32582655)]^2 ? Wow. For someone as ignorant in math as me, it seems a way too large effect for just adding 2 to each term of the sequence. But then I compare the first members of the sequences (4 vs. 4, 14 vs. 16, 194 vs. 256, 37634 vs. 65536 and so on) and it doesn't seem strange anymore. Now, a more historical question. Since the explanation in the Mersennewiki page cheesehead pointed to, regarding Lucas' formulation of the test, uses the concept of modulo, I'm not sure anymore if something I had assumed in my first post is right. I had thought that Lucas had conceived the test without using modulo, and thus the only way he'd have to actually test a number would be by dividing some term of his ever-larger sequence by the corresponding Mersenne number. Then came Lehmer and showed modular arithmethics (which I had supposed wasn't fully developed by Lucas' times) could be used to cut down those numbers to manageable sizes. Is this right or not or something like that? And, finally: since the numbers grow so fast, is there any practical use for the fact that the initial term can have more than one value? Or does it work just the same by using always 4 (or 10)? Thanks a lot you guys for your knowledge and your patience. Bruno
2006-09-23, 03:55   #9
philmoore

"Phil"
Sep 2002
Tracktown, U.S.A.

21378 Posts

Quote:
 Originally Posted by brunoparga The second question. Again if I understand it correctly, the way Lehmer contributed to the test was using "modular arithmetics" or, to put it the way I understand it, whenever the value of Lucas' sequence gets larger than the Mersenne number (not the exponent, the number itself) you're testing, divide the former by the latter, discard the result and take only the residue as the current value for the sequence.
Modular arithmetic was actually originally employed by Lucas in his computations showing that M127 was prime, and was not a later contribution of Lehmer. Lehmer generalized Lucas sequences in a way that extended their applicability. Lucas' original tests required a starting element of 3 when the exponent was congruent to 3 mod 4, and a starting element of 4 when the exponent was congruent to 1 mod 4; Lehmer showed that one could take the starting element to be 4 in both cases. Lehmer also clarified that Lucas' test was both a necessary and sufficient condition for the primality of Mersenne numbers, a point on which Lucas seemed to have some confusion, and also that the intermediate residues were irrelevant; i.e., one only needed to examine the final residue to determine whether Mp was prime or composite. For a good book with some details on this, look at Hugh Williams' "Edouard Lucas and Primality Testing", Wiley-Interscience, 1998.

2006-09-23, 11:40   #10
ATH
Einyen

Dec 2003
Denmark

2×3×13×41 Posts

Quote:
 Wait a minute; if I understand your last post correctly, you're telling me T(32582655) is almost S(32582655) times bigger than S(32582655) itself, that is, it'd be something like [S(32582655)]^2 ?
No not as much as $(S_{n-2})^2$, the huge numbers are misleading. I never wrote $T_{n-2}$ itself:

$\Large T_{n-2}=10^{(2^{(n-2)}*Log2+LogLog4)}$

$\Large T_{32582655}=10^{(10^{9808356.2730108})}$ Compared to: $\Large S_{32582655}=10^{(10^{9808356.2507271})}$

Actually:

$\Large \frac{Log T_{n-2}}{Log S_{n-2}}=\frac{2^{n-2}*Log4}{2^{n-2}*(2*Log(\alpha)-Log2)}=1.05264896$

$\Large T_{n-2}=(S_{n-2})^{1.05264896}$

instead of $(S_{n-2})^2$.

I can't help thinking how amazing this sequence Sn really are. We now know that a 9808358-digit number M44 is a factor of an unimaginably huge number S32582655 with 109808356.25 digits, and because of that we know that M44 is prime.

Think about if these numbers weren't so impossibly big we could calculate the entire series up to say S100000000 once and for all, and then test all Mersenne numbers up to 2100000002-1, just by 1 division for each.

Last fiddled with by ATH on 2006-09-23 at 11:54

2006-09-23, 12:01   #11
axn

Jun 2003

26×34 Posts

Quote:
 Originally Posted by ATH Think about if these numbers weren't so impossibly big we could calculate the entire series up to say S100000000 once and for all, and then test all Mersenne numbers up to 2100000002-1, just by 1 division for each.
That would be incorrect. Each M(p) divides a different S(p-2).

All times are UTC. The time now is 21:40.

Thu Dec 2 21:40:04 UTC 2021 up 132 days, 16:09, 0 users, load averages: 1.23, 1.43, 1.36