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