Reprezentacja Zeckendorfa

Każda liczba naturalna posiada reprezentację jako suma różnych (niesąsiadujących) liczb Fibonacciego.

Zadanie: napisać algorytm generujący te liczby wchodzące w skład sumy.

Zadanie: zaobserwuj, że reprezentacja liczby \([m\cdot (1+\sqrt{5})/2]\) w postaci Zeckendorfa i liczby \(m\) dla \(m\) dużych jest zbliżona do operacji ‘’shiftu’’ na indeksach.

def Zeck(m):
    n=1
    li=[]
    fibli=[]
    fp,f=0,1
    # budowanie listy liczb Fibonacciego nie większych niż m
    while f<=m:
        fibli.insert(0,[n,f])
        n+=1
        f,fp=f+fp,f 
    
    #zgrupowanie liczb, z listy fibli, które dodają się do m (od góry)
    zeckind=[]
    zeckval=[]
    while m>0:
        i,f=fibli.pop(0)
        if m>=f:
            m=m-f
            zeckind.append(i)
            zeckval.append(f)
    return zeckind,zeckval

print(Zeck(999999999)[0])
print(Zeck(99999999)[0])
print(Zeck(9999999)[0])
print(Zeck(999999)[0])
print(Zeck(99999)[0])
print(Zeck(9999)[0])

[44, 42, 37, 34, 29, 27, 25, 23, 17, 13, 11, 7, 5]
[39, 37, 35, 32, 30, 28, 23, 21, 15, 13, 11, 9, 3]
[35, 29, 27, 24, 21, 19, 14, 7, 3]
[30, 26, 24, 12, 9, 7, 5, 3]
[25, 22, 20, 14, 11, 8, 6, 4]
[20, 18, 15, 9, 5, 2]

#reprezentacja nie jest krótsza niż pozycyjna!
len(''.join(map(str,Zeck(10**300)[0])))

1291

f=lambda m: Zeck(int(m*((1+sqrt(5))/2)))[0]
N=100000000000000000001
print(f(N))
print(Zeck(N)[0])

[98, 94, 91, 89, 85, 82, 70, 67, 63, 61, 58, 48, 38, 34, 28, 26, 22, 20, 16, 14, 12, 9, 6]
[97, 93, 90, 88, 84, 81, 69, 66, 62, 60, 57, 47, 37, 33, 27, 25, 21, 19, 15, 13, 11, 8, 5]