I've decided to tackle Project Euler problem 233 next but I'm having some major problems! I've done some analysis and have made some quite nice progress but I've become stuck now. Here's my working:
Lemma 1: Since the circle goes through the 4 corner points there are at least 4 solutions for any n. But for each point on the circumference there are 7 others found with reflection. Therefore there are always 8k+4 lattice points.
Lemma 2: The circle has radius (√2)n and center (n/2, n/2) so its equation is (x-n/2)^2 + (y-n/2)^2 = [n/√2]^2. This reduces down to x^2+y^2 = n(x+y).
Lemma 3: If a solution of x^2+y^2 = n(x+y) is written (x, y, z) then another solution is (kx, ky, kz). The proof of that is:
(x+y)n = x^2+y^2
(kx)^2+(ky)^2 = (kx+ky)m
k(x^2+y^2) = (x+y)m
m = kn
This was as much as I did with that line of thought - I couldn't see anywhere to go from there but it's included because it well may be useful.
My next thought was to move the center of the circle. There will be the same number of solutions moving it in any dimension a whole integer. So when n/2 is integer, so n=2k, x^2+y^2 = 2*k^2. And it also turns out that there are just as many solutions to this equation as there are to the equation x^2+y^2=k^2 (see Sloane A046109).
This also gives an easy method for computing the number of solutions for any n via A046080. If the powers on the primes in n of the form 4k+1 are f[0]...f[m], then the number of solutions is 4*product(2f[i]+1 | i in [0...m]).
This allowed me to work backwards: 4.product(2f[i]+1 | i in [0...m]) = 420, so product(2f[i]+1 | i in [0...m]) = 105 = 3*5*7. I was able to come up with this program which I think finds the sum of all n, in the form 2k and less than 10^11, which have 420 circle lattice points. The answer (I hope!) is 257199853438240692.
Here's the C program:
#include "stdlib.h"
#include "stdio.h"
#include "math.h"
#include "string.h"
#define lim 1000000000L
char prime[lim];
long primes[50000000];
long len = 0;
int main(void)
{
long i, j;
for(i = 0; i < lim; i++)
{
prime[i] = 1;
}
for(i = 2; i < lim; i++)
{
if(prime[i])
{
for(j = 2*i; j < lim; j += i) prime[j] = 0;
if((i-1)%4 == 0)
{
prime[i] = 2;
//printf("%li\n", i);
primes[len++] = i;
}
}
if(i < 1000 || (i < 10000 && i%1000 == 0) || i%10000 == 0) printf("%li, %li\n", i, len);
}
printf("primes!\n");
long a, b, c, v, total = 0, k;
for(a = 0; a < len; a++)
{
v = primes[a]*primes[a]*primes[a];
if(v > 50000000000L) break;
for(b = 0; b < len; b++)
{
if(b == a) continue;
v = primes[a]*primes[a]*primes[a]*primes[b]*primes[b];
if(v > 50000000000L) break;
for(c = 0; c < len; c++)
{
if(c == a) continue;
if(c == b) continue;
v = primes[a]*primes[a]*primes[a]*primes[b]*primes[b]*primes[c];
if(v > 50000000000L) break;
for(k = 1; k*v <= 50000000000L; k++)
{
if(prime[k] == 2) continue;
total += k*v;
}
}
}
}
for(a = 0; a < len; a++)
{
v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a];
if(v > 50000000000L) break;
for(b = 0; b < len; b++)
{
if(b == a) continue;
v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[b]*primes[b]*primes[b];
if(v > 50000000000L) break;
for(k = 1; k*v <= 50000000000L; k++)
{
if(prime[k] == 2) continue;
total += k*v;
}
}
}
for(a = 0; a < len; a++)
{
v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a];
if(v > 50000000000L) break;
for(b = 0; b < len; b++)
{
if(b == a) continue;
v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[b]*primes[b];
if(v > 50000000000L) break;
for(k = 1; k*v <= 50000000000L; k++)
{
if(prime[k] == 2) continue;
total += k*v;
}
}
}
printf("%li\n", 2*total);
return 0;
}
We just need to add on the values of n that have 420 circle lattice points and are in the form 2k+1! However, that seems harder than for n=2k and I can't see any method for it. I'm also a little unsure whether my answer for even n is correct since the method is quite convoluted... Can anyone confirm it? Is there a neat method without involving treating different n differently?
I'm all out of ideas!
I'm mostly interested in how I deal with N=2k+1 since when N=2k I can do as John Feminella suggests.