title: Project Euler Problem 233
body: <p>I've decided to tackle Project Euler <a href="http://projecteuler.net/index.php?section=problems&amp;id=233" rel="nofollow noreferrer">problem 233</a> 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:</p>
  
  <p><strong>Lemma 1</strong>:
  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.</p>
  
  <p><strong>Lemma 2</strong>:
  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).</p>
  
  <p><strong>Lemma 3</strong>:
  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:</p>
  
  <pre><code>(x+y)n = x^2+y^2
  
  (kx)^2+(ky)^2 = (kx+ky)m
  k(x^2+y^2) = (x+y)m
  m = kn
  </code></pre>
  
  <p>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.</p>
  
  <p>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 <a href="http://www.research.att.com/~njas/sequences/A046109" rel="nofollow noreferrer">A046109</a>).</p>
  
  <p>This also gives an easy method for computing the number of solutions for any n via <a href="http://www.research.att.com/~njas/sequences/A046080" rel="nofollow noreferrer">A046080</a>. 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]).</p>
  
  <p>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.</p>
  
  <p>Here's the C program:</p>
  
  <pre><code>#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 &lt; lim; i++)
      {
          prime[i] = 1;
      }
  
      for(i = 2; i &lt; lim; i++)
      {
          if(prime[i])
          {
              for(j = 2*i; j &lt; lim; j += i) prime[j] = 0;
              if((i-1)%4 == 0)
              {
                  prime[i] = 2;
                  //printf("%li\n", i);
                  primes[len++] = i;
              }
          }
  
          if(i &lt; 1000 || (i &lt; 10000 &amp;&amp; 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 &lt; len; a++)
      {
          v = primes[a]*primes[a]*primes[a];
          if(v &gt; 50000000000L) break;
  
          for(b = 0; b &lt; len; b++)
          {
              if(b == a) continue;
  
              v = primes[a]*primes[a]*primes[a]*primes[b]*primes[b];
              if(v &gt; 50000000000L) break;
  
              for(c = 0; c &lt; 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 &gt; 50000000000L) break;
  
                  for(k = 1; k*v &lt;= 50000000000L; k++)
                  {
                      if(prime[k] == 2) continue;
                      total += k*v;
                  }
              }
          }
      }
  
      for(a = 0; a &lt; len; a++)
      {
          v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a];
          if(v &gt; 50000000000L) break;
  
          for(b = 0; b &lt; 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 &gt; 50000000000L) break;
  
              for(k = 1; k*v &lt;= 50000000000L; k++)
              {
                  if(prime[k] == 2) continue;
                  total += k*v;
              }
          }
      }
  
      for(a = 0; a &lt; 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 &gt; 50000000000L) break;
  
          for(b = 0; b &lt; 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 &gt; 50000000000L) break;
  
              for(k = 1; k*v &lt;= 50000000000L; k++)
              {
                  if(prime[k] == 2) continue;
                  total += k*v;
              }
          }
      }
  
      printf("%li\n", 2*total);
  
  
      return 0;
  }
  </code></pre>
  
  <p>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?</p>
  
  <p>I'm all out of ideas!</p>
  
  <hr>
  
  <p>I'm mostly interested in how I deal with N=2k+1 since when N=2k I can do as John Feminella suggests.</p>