Project Euler Problem 46

Problem 46

20 June 2003

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 21²
15 = 7 + 22²
21 = 3 + 23²
25 = 7 + 23²
27 = 19 + 22²
33 = 31 + 21²

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Answer: 5777

 

 

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Euler {
    static class Program {
        /// <summary>
        /// Returns primes under limit using sieve.
        /// </summary>
        /// <param name="limit">An integer to limit.</param>
        /// <returns>Primes under limit.</returns>
        static HashSet<int> primesUnder(int limit) {
            var p = new bool[limit];
            if (limit >= 3) p[2] = true;
            for (int i = 3; i < limit; i += 2) p[i] = true;
            for (int i = 3; i * i < limit; i += 2) {
                if (!p[i]) continue;
                for (int j = i + i; j < limit; j += i)
                    p[j] = false;
            }
            var r = new HashSet<int>();
            for (int i = 2; i < limit; i++)
                if (p[i]) r.Add(i);
            return r;
        }

        static void Main(string[] args) {
            int max = 1000000;
            var primes = primesUnder(max);

            for (var i = 3; i < max; i += 2) {
                if (primes.Contains(i)) continue;
                var p2 = primes.TakeWhile(x => x <= i - 2);
                foreach (var p in p2) {
                    var r = i - p;
                    var r2 = Math.Sqrt((double)r / 2.0);
                    if (r2 == Math.Floor(r2)) {
                        //Console.WriteLine("{0}={1} + 2*{2}^2", i, p, r2);
                        //Console.ReadKey(true);
                        goto Found;
                    }
                }
                Console.WriteLine(i);
                break;
            Found: ;
            }

        }
    }
}