Project Euler Problem 233

Question

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.

Elevenses

To confirm your answer, login to the Euler site, goto problem 233 and check your answer! – Bureaucratic

I know, but that is only part of the answer so I can't check it! I don't have the full answer. – Elevenses

Answer 1

Hint 1: The circle has radius n/√2, which is never an integer for integer n, so A046080 never applies.

Hint 2: Don't bother sliding the circle around. Pick it up off the graph paper and just think about it, the square that defines it, and the as yet unknown points of interest on the circumference in relation to each other.

Hint 3: The angle inscribed in a half circle is always 90 degrees.

Hint 4: How many ways can a number be written as the sum of two squares?

Bonus hint to be used liberally throughout: symmetry!

---

SPOILER ALERT!

---

Don't read further until you try to work it out from the hints above

If those hints aren't sufficient, here are some of the missing steps to interleave with the hints above:

Hint 1.5: You're going to have to change your way of looking at the problem since the approach you were using is based on a flawed premise.

Hint 2.5: Think about a lattice point on the left side of the arc between the top corners of the square. By symmetry there is another such point directly to the right of it and a third directly below. What can you say about the distance between these points and about the trangle they form?

Hint 3.5: How can you determine how many lattice points there are on the left side of the arc between the top corners of the square for any given n?

Leveller

Thanks; I appreciate the reply! I'm afraid I still can't see how to proceed. I've brainstormed for ages and think (x, y) points may lie in a sort of pattern to roots of unity. IE: the relation between some pairs may be a constant distance along the circumference. – Elevenses

Thanks again! :) For hint 2.5: Call the top-left lattice point A, the right hand side one B and the lower point C. The angle at A is 90 degrees. If x is x-coordinate of A, then length AB = N-2x and AC = √(n^2+4nx-4x^2). We also know BC = √2 n. I don't think I've caught your line of thought though... – Elevenses

You've almost got it. Pull up a level of abstraction. It's a right triangle, the corners are all lattice points, and the length of the hypotenuse is known. What can you say about the length of the other two legs right off the bat without doing any algebra? – Leveller

Thanks yet again! Obviously we can use the Pythagorean theorem. If x > 0, AB < AC < BC. The lengths AB and AC are also integer but BC is never integer. I don't see the significance yet. – Elevenses

BC isn't an integer, but BC^2 is, since it's the sum of the squares of two integers. In fact, we know that it's 2*N^2. Now move on to hints 3.5 and 4... – Leveller

We need to find A with integer coordinates and for each 1 <= x <= N/2 we could see if √(N^2/4+Nx-x^2)+N/2 is integer too. However, I'm sure at some point I need to stop referring to x and deal with just N. – Elevenses

Better still, and relating it to r(), 1+(r(2, 2*N^2)-4)/8 lattice points I think... Is this right? – Elevenses

@Elevenses -- do you need to find the "A"s, or just determine how many there are? As for the r() comment, I'm not sure about you expression (it doesn't look like what I got though it might be equivalent) but yes, you're on the right track. – Leveller

I've got it! Thanks loads! :D My above formula is wrong but I got the generally idea and have the answer. – Elevenses

No problem. Thanks for a question with a bit more meat to it than the typical "I don't know how to code and I"m using .net" question! – Leveller

Answer 2

Hint #1. Your lemma #2 is not quite right. Are you sure that's the radius?

Hint #2. The answer is closely related to the sum of squares function, r(k, n). This gives the number of ways to represent n using k different squares, allowing zeroes and distinguishing between order. For example, r(2, 5) is 8, because there are 8 ways to represent 5 using 2 squares:

(-2)^2 + (-1)^2
(-2)^2 + 1^2
2^2    + (-1)^2
2^2    + 1^2
... (and the 4 additional expressions produced by reversing these 2 terms)

You can see that a circle of radius p centered at the origin has r(2, p^2) lattice points. For example, a circle with radius 5 has:

(-4)^2 + (-3)^2
... and 7 others like this

5^2    + 0^2
(-5)^2 + 0^2
0^2    + 5^2
0^2    + (-5)^2

for a total of 12. What sorts of numbers would have 420 circle lattice points? Now what if they weren't centered at the origin? I'll let you take it from here.

If you want a much much bigger hint, I've rot-13'd (http://rot13.com) something you should check out here:

uggc://zngujbeyq.jbysenz.pbz/FpuvamryfGurberz.ugzy

Appellant

Thanks for the pointers. I still can't see how to proceed. The problem occurs when the center is (1/2, 1/2) instead... I can't see how to transform it to something easily solvable. Can I have a another hint please? :) – Elevenses

Answer 3

You can refer to http://oeis.org/A046109/b046109.txt to check up to 1000. I installed PARI/GP and used one of the PARI scripts here: http://oeis.org/A046109 to check numbers higher.

Polydipsia