Blöde Fragen über die LL Primalitätsprüfung

brunoparga · 2006-09-18, 05:01

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?

akruppa · 2006-09-18, 11:35

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. log₁₀(37634) = 4.57558..., and in each step the log size doubles, so after p-1 steps we'd have a number n so that log₁₀(n) = ~4.57558 * 2^p-5. Now 2^p-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

ATH · 2006-09-19, 17:31

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.

brunoparga · 2006-09-19, 22:07

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

cheesehead · 2006-09-21, 01:38

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.

ATH · 2006-09-23, 01:34

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})}$

ATH · 2006-09-23, 01:54

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 :)

brunoparga · 2006-09-23, 03:38

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

philmoore · 2006-09-23, 03:55

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.

ATH · 2006-09-23, 11:40

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 S_n really are. We now know that a 9808358-digit number M44 is a factor of an unimaginably huge number S_32582655 with 10^9808356.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 S_100000000 once and for all, and then test all Mersenne numbers up to 2^100000002-1, just by 1 division for each.

axn · 2006-09-23, 12:01

Quote:

Originally Posted by ATH

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

That would be incorrect. Each M(p) divides a different S(p-2).

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. log₁₀(37634) = 4.57558..., and in each step the log size doubles, so after p-1 steps we'd have a number n so that log₁₀(n) = ~4.57558 * 2^p-5. Now 2^p-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-23, 01:54	#7
ATH Einyen Dec 2003 Denmark 3159₁₀ 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-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