# How can I use NestWhileList instead of While in this case?

OK, the problem occurred when I challenged with Project Euler No. 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million.

My code is:

ClearAll[primelist, i]
primelist = {}; i = 1
While[Prime[i] < 2*10^6, AppendTo[primelist, Prime[i]];i++]
Plus @@ primelist


And I get the answer correct. I think using While is not a good habit in functional programming, but I can not modify my code to NestWhileList(or others FP-like functions). One of the proper manner is:

Plus @@ (Prime /@ NestWhileList[# + 1 &, 1, (Prime[# + 1] < 2*10^6 &)])


But I think it is not efficient, because when evaluating the NestWhileList, Prime[1],Prime[2],Prime[3],... ran the first time(in order to compare with 2*10^6), and then when mapping Prime to the list which was the result of NestWhileList, the same thing went once again! MMA evaluate Prime[1],Prime[2],Prime[3],... one more time.

1. Is there any method (or SOP) that can always change While to NestWhile or NestWhileList?
2. And I found that the second code above run faster much more than code 1, unbelievable.

When using advanced functionality to deal with primes it is highly recommended not using any of NestList or FoldList or whatever similar.
PrimePi is especially designed to find how many primes are below of a given number, then Prime roughly inverse of PrimePi is Listable, therefore I'd suggest this approach yielding the result almost immediately:

Total @ Prime @ Range @ PrimePi @ 2000000

142913828922


See closely related Generate PrimePower counting function.
If you are to examine something related to nesting see e.g. this NestList with a list inside?.

• +1 - Probably the fastest solution available – eldo Jul 9 '14 at 16:57
• @eldo Thanks, when I started to play with Mathematica I used to test something like Select[ range, PrimeQ] just to be convinced that there are better ways, however sometimes one can find another interesting solutions, see e.g. this approach – Artes Jul 9 '14 at 17:12

I like to use Sum for such things, when possible, as it conserves memory and is usually reasonably fast:

Sum[Prime @ i, {i, PrimePi[2*^6]}]

142913828922


Performance (still in v7, for now...) compared to Artes's fully vectorized code, with a larger search space:

Sum[Prime @ i, {i, PrimePi[2*^7]}] // Timing
MaxMemoryUsed[]

{1.857, 12272577818052}
15904176

(* in a fresh kernel *)
Total @ Prime @ Range @ PrimePi[2*^7] // Timing
MaxMemoryUsed[]

{1.716, 12272577818052}
138293008


So Sum is only slightly slower and uses a fraction of the memory that Total does.

The performance comparison performed in 10.0.2 under Windows:

Sum[Prime @ i, {i, PrimePi[2*^7]}] // Timing
MaxMemoryUsed[]

{2.308815, 12272577818052}

41744320

(* in a fresh kernel *)
Total @ Prime @ Range @ PrimePi[2*^7] // Timing
MaxMemoryUsed[]

{2.199614, 12272577818052}

157160592


Both methods are slower now and use more memory, but Sum remains a good option.

• i = 0; NestWhile[(++i; # + Prime[i]) &, 0, Prime[i + 1] < 2000000 &] // AbsoluteTiming I just figure out this code! It seems elegant. And it is much more fast than Build-in functions! – Eric Aug 9 '14 at 13:01
• The algorithm is while(Prime[i]<2*10^6){sum=sum+Prime[i]; i++;} – Eric Aug 9 '14 at 13:06
First @ NestWhile[
With[{p = Prime[#[[3]]]},
{#[[1]] + #[[2]], p, #[[3]] + 1}
] &,
{0, 2, 2}, #[[2]] <= 2 10^6 &
]


EDIT: this is a faster version:

Total[
NestWhileList[
{Prime@#[[2]], #[[2]] + 1} &,
{0, 1},
#[[1]] <= 2 10^6 &][[;;-2, 1]]
]

• I have found a better(not sure) solution based on your second solution. NestWhile[{#[[1]] + Prime[#[[2]]], #[[2]] + 1} &, {0, 1}, Prime[#[[2]]] < 2000000 &] // Timing – Eric Aug 9 '14 at 13:39
• The first entry of the list is recorded as a sum, the second the counter(is going to be the argument of Prime) – Eric Aug 9 '14 at 13:42
• @Eric, my second solution runs a bit faster (in my computer) than your proposal. – ecoxlinux Aug 15 '14 at 16:06