20060918, 05:01  #1 
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 nth 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? 
20060918, 11:35  #2 
"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_{10}(37634) = 4.57558..., and in each step the log size doubles, so after p1 steps we'd have a number n so that log_{10}(n) = ~4.57558 * 2^{p5}. Now 2^{p5} 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 20060920 at 20:56 
20060919, 17:31  #3  
Einyen
Dec 2003
Denmark
2·3·13·41 Posts 
Quote:
7,11,67,34549,127541 no other factors below 10^10. 

20060919, 22:07  #4 
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 
20060921, 01:38  #5  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Quote:


20060923, 01:34  #6  
Einyen
Dec 2003
Denmark
2×3×13×41 Posts 
Quote:
The LLtest comes from the Lucas Sequences . and are roots of the polynomial with P=2 and Q=2 so and . Now is given by: can be ignored since so it goes towards zero very quickly. Using base10 Log: so for M44: Last fiddled with by ATH on 20060923 at 01:59 

20060923, 01:54  #7 
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:
and For M44 approximating with overestimates by a factor of: just by skipping 2 :) Last fiddled with by ATH on 20060923 at 01:58 
20060923, 03:38  #8 
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 everlarger 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 
20060923, 03:55  #9  
"Phil"
Sep 2002
Tracktown, U.S.A.
2137_{8} Posts 
Quote:


20060923, 11:40  #10  
Einyen
Dec 2003
Denmark
2×3×13×41 Posts 
Quote:
Compared to: Actually: instead of . I can't help thinking how amazing this sequence S_{n} really are. We now know that a 9808358digit 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. Last fiddled with by ATH on 20060923 at 11:54 

20060923, 12:01  #11 
Jun 2003
2^{6}×3^{4} Posts 
That would be incorrect. Each M(p) divides a different S(p2).
