Problem Description

Given the positive integers, x, y, and z, are consecutive terms of an arithmetic progression, the least value of the positive integer, n, for which the equation, x² − y² − z² = n, has exactly two solutions is n = 27:

34² − 27² − 20² = 12² − 9² − 6² = 27

It turns out that n = 1155 is the least value which has exactly ten solutions.

How many values of n less than one million have exactly ten distinct solutions?

Analysis

Concept code. More later.

Solution

Runs < 1 second in Python.

from Euler import is_prime
 
nmax = 55992
s = 0
inc=3
for n in range(3, nmax , 4):
  if is_prime(n): s += inc
  if is_prime(n+2): s += (inc-1)
  if n>nmax//16: inc=2
  if n>nmax//4: inc=1
 
print "Answer to PE135 = ", s

Comments