Project Euler 46 is Goldbach’s other conjecture. He proposed that every odd number can be written as a sum of a prime and twice a square, i.e., for any odd number, the following is true:
N = p + 2*(i)
Where p
is a prime number, and i
is a perfect square.
It turns out this conjecture is false.
So, what is the smallest odd composite number that cannot be written as the sum of a prime and twice a square?
Out of various brute force solutions that are applicable here, one of the best and most efficient brute force solutions is as follows:
while
loop on every odd composite number (n
).n
, we will generate all primes (p
) less than n
.p
, we will calculate i
(i=(n-p)/2
) and check if i
is a perfect square.break
the loop if, for a particular n
, we find no (p,i)
satisfying n=p+2*i
.math.sqrt(n)
returns the square root of a number n
.
bisect.bisect(A,x)
returns the position in which x
should be inserted so that after insertion, the already sorted array A
remains sorted. In simpler words, it returns an index of the first element greater than x
in a sorted array A
.
gen_prime(n)
generates all prime numbers between the last element of primes
and n
.check(term)
checks if there exists any (p,i)
pair for a particular n
."""Coded by - Armaan Nougai"""from math import sqrtfrom bisect import bisectprimes = [2,3,5]def gen_prime(n):#generating primes less than n.global primesfor possiblePrime in range(primes[-1],n+1,2):i=0while i<bisect(primes,possiblePrime//(i+1)):if possiblePrime%primes[i] == 0:breaki+=1else:primes += [possiblePrime]def check(n):# checking if there exist (p,i) pairfor p in primes[:bisect(primes,n)]:i=(n-p)//2if int(sqrt(i))**2==i:# (p,i) pair foundreturn True# no (p,i) pair foundreturn Falsenum = 3while True:gen_prime(num)if num not in primes and not check(num) :print(num)breaknum += 2