[ prog / sol / mona ]

prog


LISP Puzzles

34 2020-04-10 11:46

>>33

precalculate sum(1...N)

The final S value is not equal to N. You would need the actual value of S(N-1).

substract the S-group to S-Group transition points(R's)

No. That is a great idea, but would require visiting every R value that is used as an S gap, one at a time. That would run in O(sqrt(n)). That runtime was already achieved in >>18 with the complement of your method, although your way will give a better constant factor. My new technique is much faster than O(sqrt(n)) and is a descendant of the one I used in >>18. I will post an explanation and the code when I finish the write-up, it's just that doing write-ups is boring compared to writing code so it's slow going.

If you have an implementation of the technique in your question, please post the value of R(10^10) and the timing to compute it, so I can compare it with >>18. If you are willing, please link/post the code as well.

157


VIP:

do not edit these