A partial proof sketch for Gosper's conjectural obfuscated prime test. Gosper's first code is checking if the number of representations of (N-1)/2 as the sum of 4 triangular numbers is N+1. The second code is checking if the number of representations of N-1 as the sum of 8 triangular numbers is N^3+1. The open conjucture is whether (s4t((N-1)/2)-1)^3 = s8t(N-1)-1 implies that N is prime. As another poster has already noted, we can convert sum-of-triangle questions into sum-of-odd-square questions: Multiply each triangluar number by 8 and add 1. triangle = K(K+1)/2; times 8, plus 1 -> 4K^2 + 4K + 1 = (2K+1)^2. So s4t((N-1)/2) also is the number of representations of 4N as the sum of 4 odd squares, and s8t(N-1) is the number of representations of 8N as the sum of 8 odd squares. Gosper's prime test is asking if s4os(4N) = N+1, and if s8os(8N) = N^3+1, and (conjecturally) if (s4os(4N)-1)^3 = s8os(8N)-1. Theorem 386 of Hardy & Wright gives the number of representations of X as the sum of 4 squares s4s(X) = 8 * (sum of divisors d of X, excluding 4|d), but they count the squares of -k and k as distinct. Gosper's s4t & s8t, and my s4os & s8os, don't double count -k and k, so corrections of 2^4 and 2^8 are needed wrt the H&W s4s and s8s. For 8 squares, H&W states s8s(X) = 16 * (-1)^X * sum ((-1)^d * d^3) over d|X. Some versions of s4s and s8s are multiplicative functions. If we make the guess that, when N is odd, s4os(4N) = sigma(N) = sum of divisors of N, and s8os(8N) = sigma_3(N) = sum of cubes of divisors of N, and recall that sigma & sigma_3 are both multiplicative functions, then Gosper's conjectural test follows: If N is an odd composite, sigma(N)-1 is the sum of all the divisors of N>1, including at least one divisor between 1 and N; while sigma_3(N)-1 is the sum of the cubes of all the divisors of N>1. The cube of the LHS includes the cubes of all the individual terms (divisors of N>1), plus cross terms. So the LHS equals or exceeds the RHS, with equality only when there are no cross terms. This is just when N has no divisors between 1 and N, i.e., when N is prime. Rich ------------- Quoting rwg@sdf.lonestar.org:
I entered the obfuscated C contest one year with a program that computed a prime sieve in an incredibly slow and non-intuitive manner. I don't think anyone ever figured out what it did ---- it was so slow and ugly that no one would look at it.
Hilarie
____________________________________________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]]]
Absolutely useless hint:
OddPrimeQ[n_]:= Block[{$RecursionLimit=Infinity},n^3+1==Odd4[n-1,0,8]]
gets the same answers, only more slowly.
The only Funster to come close to explaining this was Joshua Zucker, who stopped short of totally cooking it, but correctly indicated the final steps. (Marc LeBrun is disqualified--he helped misbeget it.) --rwg For a modicum of speed: Odd4[n_,t_,k_]:=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]]]
I don't know whether
OddPrimeQ[n_]:=Block[{$RecursionLimit=Infinity}, (Odd4[(n-1)/2,0,4]-1)^3==Odd4[n-1,0,8]-1]
can give a false positive. It's too slow to test beyond a few thousand. But I see how, with Macsyma, to test its conjecture out to a few million.
DAZ> it was a *positive* "No".
As opposed to a positive, definite "No".
DDyer>I've had waxy paper ... burst into flames while the tamale was still cold.
Isn't "cold tamale" an oxymoron?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun