[QUOTE=xilman;420808]Countably infinite.[/QUOTE]

okay then what's the absolute fastest way you can code it.

[QUOTE=science_man_88;420843]okay then what's the absolute fastest way you can code it.[/QUOTE]

If by 'fast' you are referring to execution speed of the tests, several of us have been working on that for many years, and continue to do so. You are welcome to compare timings of your efforts to ours.

If OTOH by 'fast' you mean 'speed of coding it up', then you got us beat, hands-down. (But only if you neglect the coding time others put into the bignum package you are using.)

[QUOTE=ewmayer;420926]If by 'fast' you are referring to execution speed of the tests, several of us have been working on that for many years, and continue to do so. You are welcome to compare timings of your efforts to ours.

If OTOH by 'fast' you mean 'speed of coding it up', then you got us beat, hands-down. (But only if you neglect the coding time others put into the bignum package you are using.)[/QUOTE]

mine are all PARI/gp and suck even compared to the lucas example.

I've thought about the fact that in the squaring version if[TEX] s_n=a{M_n}[/TEX] then [TEX]s_{n+1}=a^2{M_n}^2-2[/TEX] which mod the next mersenne number is [TEX]a^22^{n-1}-2[/TEX] but that's not all that helpful when a's value is the larger part of that typically and in the [TEX]s_n=2{s_{n-1}}^2-1[/TEX] version(s) of the test you can find the relation that the next value is also [TEX]2{s_{n-1}-1}^2+4{s_{n-1}-1}+1[/TEX] which is like the way mersenne numbers that have exponents in a cunningham chain of the first kind follow but I have a hard time finding a useful relationship to use to mod that one.

Here's another crappy version:
[CODE]LL(p)=my(s=Mod(2,2^p-1));for(x=1,p-2,s=vecprod([2,s-1,s+1])+1);s[/CODE]

Crappy-performing but functional bc code:
[code]define lltest(p) {
auto i,m,r; i = p-2; m = 2^p-1; r = 4;
while(i--) {
r = (r^2-2)%m;
}
return(r==0);
}[/code]

In Ruby....

[CODE]def LL(p)
s, n = 4, 2**p-1
3.upto(p) { s=(s**2-2)%n }
s==0
end

print "LL exponent : "
p = gets.to_i
puts LL(p)
[/CODE]

Earlier in the thread someone mentioned the Rosetta Code page, with dozens of languages. None particularly efficient, though.

[url]http://rosettacode.org/wiki/Lucas-Lehmer_test[/url]

[QUOTE=GP2;494490]Earlier in the thread someone mentioned the Rosetta Code page, with dozens of languages. None particularly efficient, though.

[url]http://rosettacode.org/wiki/Lucas-Lehmer_test[/url][/QUOTE]

Ah! I did not handle exponent 2. Also [c](p-2).times[/c] maybe neater then [c]3.upto(p)[/c].

I guess the linked page is too small for George's source :wink:

[QUOTE=paulunderwood;494491]Ah! I did not handle exponent 2.[/QUOTE]

No need - LL assumes p an odd prime.