While reading Beiler’s Recreations in the Theory of Numbers, I ran across this rather odd conjecture attributed to Goldbach: that all odd numbers are either prime, or can be expressed as the sum of a prime and twice a square. That seemed rather interesting. There were two known exceptions, in particular 5777 and 5993, which could not be so expressed. It turns out that even among primes, most primes can be written as a similar sum. Those that cannot are apparently called “Stern Primes”. I thought that I’d write a little Python gizmo to check that out.
Sure enough, one small Python script later, and 3m49s of runtime, we get….
3 is not the sum of a prime and twice a square 17 is not the sum of a prime and twice a square 137 is not the sum of a prime and twice a square 227 is not the sum of a prime and twice a square 977 is not the sum of a prime and twice a square 1187 is not the sum of a prime and twice a square 1493 is not the sum of a prime and twice a square 5777 is not the sum of a prime and twice a square 5993 is not the sum of a prime and twice a square
The first eight are all prime (in fact, the only known Stern primes). The last two are composite.
There are no other such numbers smaller than ten million (yes, the script tried them all).
You can read more about this conjecture here and the WIkipedia entry on Stern primes here.
[tags]Mathematics[/tags]
Addendum: I rewrote the program in C, and ran it up until max value = 1,073,741,824. The C version took only 1m41s on my faster workstation, and verified that there were no additional odd numbers that could not be so expressed that were smaller than 2^30th.
I’d like to look at the Python script that calculated this, does anyone know where I can find it?
Thanks!
I wasn’t able to locate my source code, but it’s pretty straightforward. For each number that you test, you simply find all the squares less than one half your test number, and then find the difference between your number and twice the square. If the remainder is prime, then your number _can_ be expressed as twice a square and a prime. If _all_ such remainders are composite, then the number can’t be so expressed. You can check a number n in about sqrt(n) trials. If you use (say) a hash map storing primes, then you can quickly find out whether a number is prime.
Thanks. I’m trying to teach myself Python, bought a Python book, and in the book it challenges the reader to create a program that does exactly what your code did. I understand code better if I can see it, and so was hoping to see your code.
The problem in the book refers to Goldbachs conjecture and asks the reader to input a number and make the program return the two prime numbers that make up that number. Still searching for answers on how to do this… if you have any input i’d appreciate it.
This exact question is on project euler (http://projecteuler.net/index.php?section=problems&id=46).
I was having trouble with my algorithm which takes about 4 minutes to solve the solution. So I did a quick google search and found your blog. I implemented your algorithm in Ruby, but I also made some modifications to the code. The total run time is 0.3 seconds on my 2.33 MBP! Although that’s up to 6,000 only…
The algorithm only looked at odd composites and simply skipped every number that was even or prime!
#include
#include
#include
#include
using namespace std;
#define SIZE 10000000
unsigned long long b;
bool IsSquare(unsigned long long a)
{
b=(int)sqrt(a);
return b*b==a;
}
int main()
{
unsigned long long i,j;
char* NPrime=(char*)calloc(SIZE,sizeof(char));
vector primes;
for(i=3;i<SIZE;i+=2)
{
if(!NPrime[i])
{
primes.push_back(i);
for(j=i*i;j<SIZE;j+=i*2)
NPrime[j]=1;
}
else
{
for(j=0;j<primes.size();j++)
if(IsSquare((i-primes[j])/2))
break;
if(j==primes.size())
{
printf(“%llu is invalid: Goldbach failed.\n”,i);
fflush(stdout);
scanf(“%llu”,&i);
}
else
{
printf(“%llu = %d + 2x%llu\n”,i,primes[j],(i-primes[j])/2);
fflush(stdout);
}
}
}
return 0;
}
the code above is pretty efficient and is in c
get rid of the else and its brackets to calculate ANY odd
the #includes didnt come out right.
so:
#include stdio.h
#include math.h
#include stdlib.h
#include vector
excuse me, but isn’t ‘1’ the smallest odd number which is not a prime yet cannot be expressed by a sum of a prime and twice a square?
From the reference given in the original post:
In the last paragraph of a letter to Leonhard Euler dated 18 November 1752,
Goldbach expressed his belief that every odd integer could be written in the form
p+2a^2, where p is a prime (or 1, then considered a prime) and and a>= 0 is an integer
[2, p. 594]. Writing in his usual mixture of German and Latin, Goldbach said:
…
So in the time of Goldbach 1 was defined to be prime. Now of course we define 1 as a unit and not as a prime so we must interpret this conjecture of Goldbach accordingly.
I think the main interest here is on the programming and less on the number theory.