Goldbach's other conjecture | Project Euler | Problem #46
URL to the problem page: https://projecteuler.net/problem=46
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?
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?
#include <iostream>
using namespace std;
int power(int a, int b) {
int result = 1;
for (int i = 0; i < b; i++) {
result *= a;
}
return result;
}
int main()
{
int i, j, a, b, n, cnt, cnt2 = 0, result = 0;
for (i = 3; i < 10000; i += 2) {
cnt = 0;
for (j = 2; j <= sqrt(i); j++) {
if (i % j == 0) {
cnt++;
break;
}
}
if (cnt != 0) {
cnt2++;
}
}
int* composites = new int[cnt2];
a = 0;
for (i = 3; i < 10000; i += 2) {
cnt = 0;
for (j = 2; j <= sqrt(i); j++) {
if (i % j == 0) {
cnt++;
break;
}
}
if (cnt != 0) {
composites[a] = i;
a++;
}
}
for (i = 2; i < 10000; i++) {
cnt = 0;
for (j = 2; j <= sqrt(i); j++) {
if (i % j == 0) {
cnt++;
break;
}
}
if (cnt == 0) {
cnt2++;
}
}
int* primes = new int[cnt2];
b = 0;
for (i = 2; i < 10000; i++) {
cnt = 0;
for (j = 2; j <= sqrt(i); j++) {
if (i % j == 0) {
cnt++;
break;
}
}
if (cnt == 0) {
primes[b] = i;
b++;
}
}
for (i = 0; i < a; i++) {
cnt = 0;
for (j = 0; primes[j] <= composites[i]; j++) {
result = 0;
for (n = 0; result <= composites[i]; n++) {
result = primes[j] + (2 * power(n, 2));
if (result == composites[i]) {
cnt++;
break;
}
}
if (cnt != 0) {
break;
}
}
if (cnt == 0) {
cout << "Smallest odd composite that cannot be written as the sum of a prime and twice a square is = " << composites[i] << endl;
break;
}
}
return 0;
}
Comments
Post a Comment