I didn't really search. I just added odd squares to primes congruent to 3 mod 4. Such sums always give you multiples of 4. (Primes like 5, which are congruent to 1 mod 4, don't give multiples of 4 when added to odd squares.) Then I checked the (bit vector) list of results to see if any nonsquare multiples of 4 had not been hit.
I did my largest test last night. It took 12 hours on my new iMac to verify that 3676 is the only nonsquare multiple of 4 less than 100,000,000 that does not have a square plus prime decomposition. My guess is that 3676 is the only nonsquare multiple of 4 that has no such decomposition, period.
I got into this problem when I went to a regional meeting of the Mathematical Association of America. I presented a talk on "How to beat the market and sleep well at night" (see my signature) at the meeting, but I also went to listen to Charles McCracken talk about this square plus prime problem. Charles had done a lot of computations, and every nonsquare multiple of 4 he had tested had always had a square plus prime decomposition. I figured that looking for counterexamples would be a good test of Perl on my new machine. At that point I had run exactly one Perl script on my iMac: I had printed "hello world" on the screen.
I'll send you the code in a separate letter, Ken. If anyone else is interested in this application of "Bit::Vector", let me know. I'll sent you the code as well.
Regards,
Vic
At 1:55 PM +1100 11/3/02, Ken Williams wrote:
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
-- *---* http://vic.norton.name/finance/btm | How to beat the market and sleep well at night | or | How optimizing a weighted Sharpe ratio | can lead to an effective investment strategy *---* mailto:vic@;norton.name
