[1/14]
Here is the upgraded version of >>76 using stacked self-generation >>35 of the S sequence and layered >>81 partial >>72 fourth-order S-groups >>35 to achieve O(log(log(n))) space consumption and O(n^(1/16)) runtime >>86. Fourth-order S-group formulas were obtained from the general procedure for incrementing the S-group order. To avoid shifting in the main loop the Svec of >>83 is reversed so the 's' value is at index 0. The new Slist is [s, S1, S2 ...] and holds the starting values of the S-groups from the one with the highest order, which is furthest from the base S sequence, to the one with the lowest order, which is closest to the base S sequence, and ending with the S sequence itself. With layers numbered from 1, the first equation that defines the general procedure is:
layer[N+1].count(c,Slist) = layer[N].inc(c,Slist')
where Slist' is Slist with the value at index N-1 decremented. The [N+1].inc equation can be obtained by expressing the [N+2].count both in terms of [N+1].inc and as a sum of the component [N+1].counts:
layer[N+1].inc(c,Slist') = sum(for j in [1...c] of layer[N+1].count(s-2+j,h(j,Slist)))
where h advances the values of Slist[k in 0...N-1] for subgroup j:
h[k](j,Slist) = Slist[k+1]+layer[k+1].inc(j-1,Slist)
One thing that saves on computations is to note that Slist[N] need not be included in the final h because it is a foregone conclusion that in the final result it will appear as a linear term, and its factor will be the full count in the same layer. Implementing these as well as the previous observations yields:
class Layer:
@ classmethod
def count (cls, c, Slist, counts, incs):
pass
@ classmethod
def increment (cls, c, Slist, counts, incs):
pass
class ChainedLayers:
class Layer1 (Layer):
@ classmethod
def count (cls, c, Slist, counts, incs):
counts [0] = c
@ classmethod
def increment (cls, c, Slist, counts, incs):
s = Slist [0]
incs [0] = (c - 1 + s + s) * c // 2
def _access (setasup):
def fun (cls):
cls.up = setasup.increment
return cls
return fun
@ _access (Layer1)
class Layer2 (Layer):
@ classmethod
def count (cls, c, Slist, counts, incs):
s = Slist [0]
# Slist [0] = s - 1
# cls.up (c, Slist, counts, incs)
# Slist [0] = s
# counts [1] = incs [0]
counts [1] = (c - 3 + s + s) * c // 2
@ classmethod
def increment (cls, c, Slist, counts, incs):
countS = counts [1]
incS = countS + c
s = Slist [0]
overR = (incS - 1) * incS // 2
cm1c = (c - 1) * c
backR = (s - 1) * c + (c + 1 + 3 * s) * cm1c // 6
incR = overR - backR + Slist [1] * countS
incs [0] = incS
incs [1] = incR
@ _access (Layer2)
class Layer3 (Layer):
@ classmethod
def count (cls, c, Slist, counts, incs):
S = Slist [1]
Slist [1] = S - 1
cls.up (c, Slist, counts, incs)
Slist [1] = S
counts [2] = incs [1]
@ classmethod
def increment (cls, c, Slist, counts, incs):
# names from seq4_inc
countS1 = counts [1]
countS0 = counts [2]
incS0 = countS0 + countS1
overR = (incS0 - 1) * incS0 // 2
s = Slist [0]
s20 = 20 * s
s30 = 30 * s
s60 = s30 + s30
backR = c*(((((5*c + (s30 - 29))*c + ((s60 - 130)*s + 45))*c + (((s20 + s20 - 140)*s + 90)*s + 85))*c + ((250 - s60)*s - 290))*c + (s20 - 160)*s + 184) // 240
backR = countS1 * (countS1 + 1) // 2 * Slist [1] - countS1 + backR
incR = overR - backR + Slist [2] * countS0
incs [1] = incS0
incs [2] = incR