On Saturday, November 2, 2002, at 03:02 PM, Vic Norton wrote:
So here is the answer to your homework exercise. There is exactly one nonsquare multiple of 4 less than or equal to 10,000,000 that is not the sum of a square and a prime. That nonsquare multiple of 4 is 3,676.Interesting, where did you find this problem? Is it conjectured that 3,676 is the only such number, or are there other known ones above 10M?
Note that all small, nonsquare multiples of 4 do have a square plus prime decomposition:
8 = 1 + 7, 12 = 1 + 11, 20 = 1 + 19 = 9 + 11,
24 = 1 + 23, 28 = 9 + 19 = 25 + 3, ...
The exercise with the 10,000,000 upper limit took 26 minutes and 53 seconds on my new iMac. I don't think I'll try it on my Power Computing tower. When I set the upper limit at 2,000,000 rather than 10,000,000, the comparative computation times were
Power Computing 240 MHz: 8 minutes, 43 seconds,
iMac 800 MHz: 2 minutes, 53 seconds.
So far, no matter which machine I use, the answer is always the same: 3,676.
Also, how did you use Bit::Vector to search? Want to post your code?
-Ken
