Hi, yesterday night, 31 Dec. 2009, 01:00am, I was thinking that let's see if there is something special about the new year date 1.1.2010, and after figuring out some very common observations, I found out at 09:14pm, on 1.1.2010 that the number 112010 (hundred and twelve thousand ten) is a sum of two primes which are 111997 and 13!!. What's big deal! Clearly not. But it is.
I came to this conclusion after running my code for 30 minutes(total time). Yesterday, at the same time, I was working out a problem on arrays, the problem was "Given a sorted array of integers and a target value t, find if there exists a pair (x, y) such that x + y = t and if yes, report these numbers." I solved this problem using 2 counters, first at start i = 0 and second at end, j = n-1, where n is the length of the array, if sum of a[i] and a[j] is greater than target value t, then I would decrement j, else increment i, so by following this greedy approach, I would eventually reach to the pair which sum to t (if at all), otherwise I would report that there is no such pair. I implemented this algorithm in C and run my code first for 10 numbers which worked fine and then I ran the code on 1 million numbers which also worked fine.
So, how does it relates with primes? It does so in that if I can find primes up to a certain number n in sorted order (non decreasing) then if I now run my above code then I will be able to find if a given number (even) hopefully is a sum of two primes or not, this is a powerful result in finding out if any given even number is a sum of two primes or not, and has a very good practical application (Goldbach's conjecture).
Now, what I did is that I found out primes up to 112010 and ran my code over this sorted array of primes up to 112010 and I found out that this number is indeed a sum of two primes (111997 and 13)!
Code available on request! Any queries, suggestions or comments are welcome!
Cheers!
Rajendra
