Project Euler Forum

I have written a code for the problem 341 (http://projecteuler.net/index.php?secti ... ems&id=341). It correctly reproduces all the numbers stated in the problem, like Sum[ G[n^3], {n, 1, 10^3 -1}] and G[10^6]. But my answer is being rejected

I have spent considerable time debugging my code and believe that it works correctly. I would appreciate it if somebody could confirm some more of the sequence values quoted below for verification. Specifically, I am getting

G[(10^6-1)^3] == 160113493649

G[(10^5-1)^3] == 2240166964

Thank you for you help.

Both of those values are correct.

Should I be able to solve this with considerably less memory than G[max_n], where for our purposes max_n = (10^6-1)^3? If this were the case, I would need something like 100ish more times memory than I have available. It feels silly even asking the question, but after much research, it seems that a closed form to the recurrence relation is not possible to get at, and while generating the sequence is reasonably fast my method, while slightly cleverer than simply storing each value of G, still requires memory on the order of G[max_n]. Am I even going down the right track here?

As with all Project Euler problems, a correct solution does not need to use excessive time or memory.

Should I be able to solve this with considerably less memory than G[max_n]

For your information, it can be done with less than 400 bytes of memory.

I am a PE newbie with less than 50 problems solved. I use Visual Basic with Excel. I've been solving them in order, but thought I would try to jump to a recent problem, so that's how I got here. I've solved the problem, I think, as I am able to duplicate all the results posted here, except for G(999,999^3). It seems I need 18 digits of precision, for this, but Excel only offers 15 with Double Precision. Can any one point me to a method to achieve more precision in Excel? Thanks!

mahartman wrote:I am a PE newbie with less than 50 problems solved. I use Visual Basic with Excel. I've been solving them in order, but thought I would try to jump to a recent problem, so that's how I got here. I've solved the problem, I think, as I am able to duplicate all the results posted here, except for G(999,999^3). It seems I need 18 digits of precision, for this, but Excel only offers 15 with Double Precision. Can any one point me to a method to achieve more precision in Excel? Thanks!

Please don't post the same question in more than one topic.

[snip] confused ramblings... [/snip]

::EDIT::

... and the penny drops.

So G(1) = 1.
G(2) cannot equal 1 otherwise G(1) would equal 2 therefore G(2) has to equal 2 which means that G(3) also has to equal 2 to make G(2) true.
So G(2) = 2.
G(3) = 2.
G(4) and G(5) have to both equal 3 in order to satisfy G(3) = 2.
Now G(6), G(7) and G(8) have to equal 4 to satisfy G(4) = 3.

Ahhhhhh... I get it now

Thanks!