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]]
print("the quoting-clock derivation, checked exactly:")
print(" k   m=3*2^k  plateau?(Q[m-1]==Q[m-2]==3*2^(k-1))  Q[m]  2*Q[m/2]  equal")
for k in range(2,12):
    m=3*(1<<k)
    plat = Q[m-1]==Q[m-2]==3*(1<<(k-1))
    print(" %2d  %7d      %s        %6d  %6d   %s"%(
        k, m, str(plat).ljust(5), Q[m], 2*Q[m//2], Q[m]==2*Q[m//2]))