What is Project Euler 46?
Problem statement
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?
Solution approach
Out of various brute force solutions that are applicable here, one of the best and most efficient brute force solutions is as follows:
- We will run a
whileloop on every odd composite number (n). - For every
n, we will generate all primes (p) less thann. - Then for every
p, we will calculatei(i=(n-p)/2) and check ifiis a perfect square. - We will then
breakthe loop if, for a particularn, we find no(p,i)satisfyingn=p+2*i.
Solution implementation
The following two functions are imported:
-
math.sqrt(n)returns the square root of a numbern. -
bisect.bisect(A,x)returns the position in whichxshould be inserted so that after insertion, the already sorted arrayAremains sorted. In simpler words, it returns an index of the first element greater thanxin a sorted arrayA.
The other two functions are:
gen_prime(n)generates all prime numbers between the last element ofprimesandn.check(term)checks if there exists any(p,i)pair for a particularn.
"""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