import math
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]]
e=[Q[n]-n/2 for n in range(1,N+1)]

# WHERE is the octave max? relative position within [2^k, 2^{k+1})
print("argmax position within octave (0=start,1=end):")
for k in range(6,20):
    lo=1<<k; hi=1<<(k+1)
    blk=[abs(x) for x in e[lo-1:hi-1]]
    am=blk.index(max(blk))
    print("  k=%2d  relpos=%.4f  max=%.1f"%(k, am/ (hi-lo), max(blk)))

# FLOOR 2: self-similarity of generation profiles.
# profile = |e| averaged into 64 bins across the octave, normalized.
def profile(k,bins=64):
    lo=1<<k; hi=1<<(k+1)
    blk=[abs(x) for x in e[lo-1:hi-1]]
    m=len(blk)//bins
    p=[sum(blk[i*m:(i+1)*m])/m for i in range(bins)]
    mu=sum(p)/bins; sd=math.sqrt(sum((x-mu)**2 for x in p)/bins) or 1
    return [(x-mu)/sd for x in p]
def corr(a,b):
    n=len(a); return sum(a[i]*b[i] for i in range(n))/n
print("\ncorrelation of successive octave profiles (floor 2):")
for k in range(8,19):
    print("  r(gen %d, gen %d) = %.3f"%(k,k+1,corr(profile(k),profile(k+1))))

# FLOOR 3: does the FIRST HALF of a generation mirror the WHOLE previous
# generation (nesting), or is similarity only sibling-to-sibling?
def half_profile(k,which,bins=64):
    lo=1<<k; mid=lo+(1<<(k-1)); hi=1<<(k+1)
    seg = e[lo-1:mid-1] if which==0 else e[mid-1:hi-1]
    blk=[abs(x) for x in seg]
    m=len(blk)//bins
    p=[sum(blk[i*m:(i+1)*m])/m for i in range(bins)]
    mu=sum(p)/bins; sd=math.sqrt(sum((x-mu)**2 for x in p)/bins) or 1
    return [(x-mu)/sd for x in p]
print("\nnesting test: r(first-half of gen k, WHOLE gen k-1):")
for k in range(10,19):
    print("  k=%2d  r=%.3f"%(k, corr(half_profile(k,0), profile(k-1))))