prog

frontpage - thread list - new thread - preferences - ?

LISP Puzzles

36 2020-04-13 00:02

[2/4]
With these explanations the code should be easy to follow:

def seq2_next (levels, level):
   if level < len (levels):
      state = levels [level]
      start, count, used, S = state

      if used < count:
         length = start + (used - 1)
         state [2] = used + 1
         state [3] = S + (length + 1)
         return (S, length)
      else:
         start, count = seq2_next (levels, level + 1)
         length = start - 1
         state [0] = start
         state [1] = count
         state [2] = 1
         state [3] = S + (length + 1)
         return (S, length)
   else:
      levels.append ([4, 3, 2, 13])
      return (8, 4)

def seq3_sum1sc (s, c):
   # start, count
   return (c - 1 + s + s) * c // 2

def seq3_covered (s, c):
   # start, count
   return (c - 3 + s + s) * c // 2

def seq3_inc (s, c, S):
   # start, count, S

   # incS   = (c - 1 + s + s) * c // 2
   # countS = (c - 3 + s + s) * c // 2
   cm1    = c - 1
   incS   = (cm1 + s + s) * c // 2
   countS = incS - c

   overR = (incS - 1) * incS // 2
   # backR = (s - 1) * c + s * (c - 1) * c // 2 + (c - 1) * c * (c + 1) // 6
   cm1c  = cm1 * c
   backR = (s - 1) * c + s * cm1c // 2 + cm1c * (c + 1) // 6
   incR  = overR - backR + S * countS
   return (incR, incS)

def work_seq3 (n):
   seq3covered = seq3_covered
   seq3inc     = seq3_inc
   seq3next    = seq2_next
   seq3sum1sc  = seq3_sum1sc

   levels       = []
   R, S         = 3, 4
   start, count = 4, 3
   advance      = seq3covered (start, count)
   covered      = 2 + advance

   while covered <= n:
      incR, incS = seq3inc (start, count, S)
      R += incR
      S += incS
      start, count = seq3next (levels, 0)
      advance      = seq3covered (start, count)
      covered     += advance

   print ("levels:", len (levels))
   covered     -= advance
   fakelevels   = [[start, count, 0, S]]
   start, count = seq3next (fakelevels, 0)
   covered     += count

   while covered < n:
      R += seq3sum1sc (start, count)
      start, count = seq3next (fakelevels, 0)
      covered     += count

   R += seq3sum1sc (start, count - (covered - n))
   return R

The first integer k for which R(10^k) overflows an u64 is k=10. The value of R(10^10) is
50000940106333921296
and, while this computation took about 70 milliseconds in >>18, it now takes about 850 microseconds in vanilla python:

$ g 10
k 10 index 10000000000
levels: 4
10000000000 -> 50000940106333921296 0x2B5E7061C419DA010 66
$ python3 -m timeit -s 'import flake.hofs as mod' 'mod.work_seq3 (10000000000)'
1000 loops, best of 3: 841 usec per loop

The first integer k for which R(10^k) overflows an u128 is k=20. The value of R(10^20) is
5000000000942800098290022420982686040347
and it is computed in 300 milliseconds in vanilla python:

$ g 20
k 20 index 100000000000000000000
levels: 5
100000000000000000000 -> 5000000000942800098290022420982686040347 0xEB194F8ED94AC565124861C3B7D0C411B 132
$ python3 -m timeit -s 'import flake.hofs as mod' 'mod.work_seq3 (100000000000000000000)'
10 loops, best of 3: 300 msec per loop

As you can see, the algorithmic improvements made possible by the application of a small amount of math effort tend to outweigh the differences between languages. I propose that we use the timing for computing R(10^20) to compare implementations with this runtime order of growth.

157