Bill Gosper wrote:
Ah, an obbortunity to refustigate with this Mathematica malpractice:
OddPrimeQ[n_]:= Block[{$RecursionLimit=Infinity},n+1==Odd4[(n-1)/2,0,4]]
Odd4[n_,t_,k_]:=If[k==0,KroneckerDelta[0,n], If[t>n,0,Odd4[n-t,0,k-1]+Odd4[n,1/2+t+Sqrt[2*t+1/4],k]]]
It's not so bad. (I mean, not so difficult to see how it works. Of course it's terrible when considered as a primality test.) ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... Odd4[n,t,k] is the number of partitions of n into k parts chosen from {0,1,3,6,10,15,...}. So the crucial theorem (assuming it to be one) is: The number of ways to write (n-1)/2 = t+t+t+t where each t is a triangular number (0 included) is n+1 iff n is an odd prime. Triangular numbers are n(n+1)/2 = [(n+1/2)^2-1/4]/2, so this is the same as: The number of ways to write (n-1)/2 = (sum of four odd squares)/8 - 1/2 is n+1 iff n is an odd prime or, rearranging a bit: The number of ways to write 4n = sum of four odd squares is n+1 iff n is an odd prime. Now, the sum of four odd squares is always 4 (mod 8), so if n is even then the number of such representations is 0, and n+1 isn't, so all is as it should be when n is even. What about odd n? Ah, well, it turns out that Lagrange proved this (note: I didn't know this beforehand, but once we've got this far we're in "if true then surely already well known" territory): 8n+4 is the sum of four odd squares in exactly sigma(2n+1) ways, where sigma is the sum-of-divisors function. In other words: if n is odd then the number of ways to write 4n as the sum of four odd squares is sigma(n). Which means all we need to show is sigma(n) = n+1 <==> n prime, which is trivial. -- g