prog

frontpage - thread list - new thread - preferences - ?

LISP Puzzles

67 2020-05-03 00:01

[1/2]
The improved version of >>36 uses stacked self-generation of the S sequence and third-order S-groups to achieve O(log(log(n))) space consumption and O(n^(1/8)) runtime. As explained in >>35 a third-order S-group is a group of second-order S-groups, and this is folded into the R value in one step. The constant factor that results from the more complex S-group folding step is considerably higher than in >>36.

def seq4_covered (s, c, S1):
   # start, count
   incR, incS = seq3_inc (s, c, S1 - 1)
   return incR

def seq4_inc (s, c, S0, S1, covered):
   # start, count
   incS1   = seq3_sum1sc (s, c)
   countS1 = incS1 - c

   incS0   = countS1 * S1 + seq3_inc (s, c, 0) [0]
   countS0 = covered
   overR   = (incS0 - 1) * incS0 // 2
   backR   = (
      countS1 * (countS1 + 1) // 2 * S1
      - countS1 + seq4_backR (s, c)
   )
   incR    = overR - backR + S0 * countS0
   return (incR, incS0, incS1)

def seq4_backR (s, c):
   # start, count
   return c*(((((5*c + (30*s - 29))*c + ((60*s - 130)*s + 45))*c + (((40*s - 140)*s + 90)*s + 85))*c + ((-60*s + 250)*s - 290))*c + (20*s - 160)*s + 184) // 240

def work_seq4 (n):
   seq3covered = seq3_covered
   seq3inc     = seq3_inc
   seq4next    = seq2_next
   seq3sum1sc  = seq3_sum1sc
   seq4covered = seq4_covered
   seq4inc     = seq4_inc

   levels       = []
   R, S0, S1    = 3, 4, 4
   start, count = 4, 3
   advance      = seq4covered (start, count, S1)
   covered      = 2 + advance

   while covered <= n:
      incR, incS0, incS1 = seq4inc (start, count, S0, S1, advance)
      R  += incR
      S0 += incS0
      S1 += incS1
      start, count = seq4next (levels, 0)
      advance      = seq4covered (start, count, S1)
      covered     += advance

   print ("levels:", len (levels))

   covered     -= advance
   fakelevels   = [[start, count, 0, S1]]
   start, count = seq4next (fakelevels, 0)
   advance      = seq3covered (start, count)
   covered     += advance

   while covered <= n:
      incR, incS0 = seq3inc (start, count, S0)
      R  += incR
      S0 += incS0
      start, count = seq4next (fakelevels, 0)
      advance      = seq3covered (start, count)
      covered     += advance

   covered     -= advance
   fakelevels   = [[start, count, 0, S0]]
   start, count = seq4next (fakelevels, 0)
   covered     += count

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

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

The timing for R(10^20) is down to about 80 milliseconds in vanilla python from the previous 300 milliseconds:

$ python3 -m timeit -s 'import flake.hofs as mod' 'mod.work_seq4 (100000000000000000000)'
10 loops, best of 3: 81.2 msec per loop

The timing for R(10^30) is about 14 seconds in vanilla python:

$ python3 -m timeit -s 'import flake.hofs as mod' 'mod.work_seq4 (1000000000000000000000000000000)'
10 loops, best of 3: 14.3 sec per loop

The first integer k for which R(10^k) overflows an u256 is k=39. The value of R(10^39) is
500000000000000000029814239694953305682145634502486118475654808671411192582303

$ g4 39
k 39 index 1000000000000000000000000000000000000000
levels: 5
1000000000000000000000000000000000000000 -> 500000000000000000029814239694953305682145634502486118475654808671411192582303 0x4516DF8A16FE63D603196794A678455A328B511811E5818CC6F66DDCD067DD09F 259

157