N=1<<21
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]]

# LOOK at Q around the midpoint n=3*2^k. Is the extreme a spike or a cliff?
for k in [6,7,8,9,10]:
    m=3*(1<<k)
    w=6
    print("k=%d, n=3*2^%d=%d:"%(k,k,m))
    print("   n:      ", [m+d for d in range(-w,w+1)])
    print("   Q(n):   ", [Q[m+d] for d in range(-w,w+1)])
    print("   e(n):   ", [round(Q[m+d]-(m+d)/2,1) for d in range(-w,w+1)])
# Q value AT the midpoint vs simple formulas
print("\nQ(3*2^k) vs candidates:")
for k in range(4,17):
    m=3*(1<<k)
    q=Q[m]
    print("  k=%2d  Q=%8d   2^(k+1)=%8d   diff=%d"%(k,q,1<<(k+1),q-(1<<(k+1))))