Wu Yudong's Blog

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×1²
15 = 7 + 2×2²
21 = 3 + 2×3²
25 = 7 + 2×3²
27 = 19 + 2×2²
33 = 31 + 2×1²

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?

哥德巴赫的另一个猜想

克里斯蒂安·哥德巴赫曾经猜想，每个奇合数可以写成一个素数和一个平方的两倍之和。

9 = 7 + 2×1²
15 = 7 + 2×2²
21 = 3 + 2×3²
25 = 7 + 2×3²
27 = 19 + 2×2²
33 = 31 + 2×1²

最终这个猜想被推翻了。

最小的不能写成一个素数和一个平方的两倍之和的奇合数是多少？

//（Problem 46）Goldbach's other conjecture
// Completed on Fri, 26 Jul 2013, 16:58
// Language: C11
//
// 版权所有（C）wu yudong
// 博客地址：http://www.wuyudong.com
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#include<stdbool.h>

bool issquare(int n)  //判断一个自然数是否为一个平方数
{
	if (ceil(sqrt(n)) * ceil(sqrt(n)) == n)
		return true;
	else
		return false;
}

bool isprim(int n)				//素数判断
{
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)
			return false;
	}
	return true;
}

bool judge(long long n)
{
	int i = 1;
	long long t;
	while ((t = (n - 2 * (i * i))) > 0) {
		if (isprim(t))
			return true;
		i++;
	}
	return false;
}

int main()
{
	for (long long i = 1001; i < 100000000; i = i + 2) {
		if (!isprim(i) && !judge(i)) {
			printf("%lld\n", i);
			break;
		}
	}
	return 0;
}

Answer:5777

Completed on Fri, 26 Jul 2013, 23:58