Project Euler Problem 27

Problem 27

27 September 2002

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40² + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula  n² 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, 79 and 1601, is 126479.

Considering quadratics of the form:

n² + an + b, where |a| 1000 and |b| 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |4| = 4

Find the product of the coefficients, a and b, for the quadratic e-pression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

Answer: -59231

 

 

C#

 

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

namespace ConsoleApplication1 {
    class Program {
        static bool isPrime(long x) {
            if (x < 2) return false;
            for (long i = 2; i * i <= x; i++)
                if (x % i == 0) return false;
            return true;
        }

        static void Main(string[] args) {
            int max = 0;
            int maxA = 0;
            int maxB = 0;
            for (int a = -1000; a <= 1000; a++) {
                for (int b = -1000 + 1; b < 1000; b++) {                    
                    int count = 0;
                    for (int i = 0; ; i++) {                        
                        var v = i * i + a * i + b; // the quadratic formula
                        if (!isPrime(v)) break;
                        count++;
                    }
                    if (count > max) {
                        max = count;
                        maxA = a;
                        maxB = b;
                    }
                    //Console.WriteLine(a + " " + b + " " + count);
                }
            }
            Console.WriteLine(maxA + " " + maxB + " " + max + " " + maxA * maxB);
        }
    }
}

Racket

 

#lang racket
(define (prime? x)
  (let/ec break
    (when (< x 2) (break #f))
    (let loop ([i 2])
      (when (<= (* i i) x)
        (when (= 0 (modulo x i)) (break #f))
        (loop (+ 1 i))))
    #t))

(define (problem27)
  (define max 0)
  (define maxA 0)
  (define maxB 0)
  (for* ([a (in-range -999 1000)]
         [b (in-range -999 1000)])
    (define count 0)
    (let/ec break
      (let loop ([i 0])
        (define v (+ (* i i) (* a i) b)) ; the quadratic formula
        (unless (prime? v) (break))
        (set! count (+ 1 count))
        (loop (+ 1 i))))
    (when (> count max)
      (set! max count)
      (set! maxA a)
      (set! maxB b)))
  (displayln (list maxA maxB max (* maxA maxB))))
(problem27)

 

Python

 

def isPrime(x):
    if x < 2: return False
    i=2
    while i*i<=x:
        if x % i==0: return False
        i+=1
    return True

def problem27():
    max=0
    maxA=0
    maxB=0
    for a in range(-999,1000):
        for b in range(-999,1000):
            count=0
            i=0
            while True:
                v=i*i+a*i+b
                if not isPrime(v): break
                count+=1
                i+=1
            if count>max:
                max=count
                maxA=a
                maxB=b
    print(maxA, maxB, max, maxA*maxB)
problem27()