mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-09-18, 05:01   #1
brunoparga
 
brunoparga's Avatar
 
Feb 2006
Brasília, Brazil

3·71 Posts
Default 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?
brunoparga is offline   Reply With Quote
Old 2006-09-18, 11:35   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2006-09-19, 17:31   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2·3·13·41 Posts
Default

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.
ATH is offline   Reply With Quote
Old 2006-09-19, 22:07   #4
brunoparga
 
brunoparga's Avatar
 
Feb 2006
Brasília, Brazil

3·71 Posts
Default

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
brunoparga is offline   Reply With Quote
Old 2006-09-21, 01:38   #5
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by brunoparga View Post
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.
cheesehead is offline   Reply With Quote
Old 2006-09-23, 01:34   #6
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×3×13×41 Posts
Default

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
ATH is offline   Reply With Quote
Old 2006-09-23, 01:54   #7
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×3×13×41 Posts
Default

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
ATH is offline   Reply With Quote
Old 2006-09-23, 03:38   #8
brunoparga
 
brunoparga's Avatar
 
Feb 2006
Brasília, Brazil

3×71 Posts
Default 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
brunoparga is offline   Reply With Quote
Old 2006-09-23, 03:55   #9
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

21378 Posts
Default

Quote:
Originally Posted by brunoparga View Post
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.
philmoore is offline   Reply With Quote
Old 2006-09-23, 11:40   #10
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×3×13×41 Posts
Default

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
ATH is offline   Reply With Quote
Old 2006-09-23, 12:01   #11
axn
 
axn's Avatar
 
Jun 2003

26×34 Posts
Default

Quote:
Originally Posted by ATH View Post
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).
axn is offline   Reply With Quote
Reply

Thread Tools


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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.