Solution to Project Euler Problem 46: Goldbach's other conjecture - It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square. 9 = 7 + 2×12 15 = 7 + 2×22 21 = 3 + 2×32 25 = 7 + 2×32 27 = 19 + 2×22 33 = 31 + 2×12 It turns out that the conjecture was false. What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
Updated: Jan. 17, 2021 — Training Time: 3 minutes
Overseen by: Archangel Macsika
All Training Resources
Scroll for more menu list
Topic: Project Euler Problem 46: Goldbach's other conjecture.
Difficulty: Easy.
Objective: It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12
It turns out that the conjecture was false.
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
Input: None.
Expected Output: 5777.
Sikademy Solution in Java Programming Language
package sikademy;
/**
*
* @author Archangel Macsika
* Copyright (c) Sikademy. All rights reserved
*/
public class SikademyEulerSolution {
public String run() {
for (int i = 9; ; i += 2) {
if (!satisfiesConjecture(i))
return Integer.toString(i);
}
}
private static boolean satisfiesConjecture(int n) {
if (n % 2 == 0 || isPrime(n))
return true;
for (int i = 1; i * i * 2 <= n; i++) {
if (Library.isPrime(n - i * i * 2))
return true;
}
return false;
}
public static boolean isPrime(int x) {
if (x < 0)
throw new IllegalArgumentException("Negative number");
if (x == 0 || x == 1)
return false;
else if (x == 2)
return true;
else {
if (x % 2 == 0)
return false;
for (int i = 3, end = sqrt(x); i <= end; i += 2) {
if (x % i == 0)
return false;
}
return true;
}
}
public static int sqrt(int x) {
if (x < 0)
throw new IllegalArgumentException("Square root of negative number");
int y = 0;
for (int i = 1 << 15; i != 0; i >>>= 1) {
y |= i;
if (y > 46340 || y * y > x)
y ^= i;
}
return y;
}
public static void main(String[] args) {
SikademyEulerSolution solution = new SikademyEulerSolution();
System.out.println(solution.run());
}
}
Sikademy Solution in Python Programming Language
#
# @author Archangel Macsika
# Copyright (c) Sikademy. All rights reserved.
#
import itertools
def compute():
ans = next(itertools.filterfalse(test_goldbach, itertools.count(9, 2)))
return str(ans)
def test_goldbach(n):
if n % 2 == 0 or is_prime(n):
return True
for i in itertools.count(1):
k = n - 2 * i * i
if k <= 0:
return False
elif is_prime(k):
return True
def sqrt(x):
assert x >= 0
i = 1
while i * i <= x:
i *= 2
y = 0
while i > 0:
if (y + i)**2 <= x:
y += i
i //= 2
return y
# Tests whether the given integer is a prime number.
def is_prime(x):
if x <= 1:
return False
elif x <= 3:
return True
elif x % 2 == 0:
return False
else:
for i in range(3, sqrt(x) + 1, 2):
if x % i == 0:
return False
return True
if __name__ == "__main__":
print(compute())