# Floor 0: build it and watch.
N=1<<20
Q=[0,1,1]+[0]*(N-2)
for n in range(3,N+1):
    Q[n]=Q[n-Q[n-1]]+Q[n-Q[n-2]]
print("first 30:", Q[1:31])
print("Q(n)/n at n=2^k:", [(1<<k, round(Q[1<<k]/(1<<k),4)) for k in range(4,21,4)])

# error signal
e=[Q[n]-n/2 for n in range(1,N+1)]
# Floor 1 test: generation structure aligned to powers of 2?
import math
print("\nper-octave stats of e(n)=Q(n)-n/2   [2^k, 2^(k+1)):")
print(" k    max|e|      std(e)     max|e|/sqrt(2^k)")
for k in range(4,20):
    lo=1<<k; hi=1<<(k+1)
    blk=e[lo-1:hi-1]
    mx=max(abs(x) for x in blk)
    mean=sum(blk)/len(blk)
    sd=math.sqrt(sum((x-mean)**2 for x in blk)/len(blk))
    print(" %2d  %9.1f  %9.2f      %6.3f"%(k,mx,sd,mx/math.sqrt(lo)))