Zeckendorf Fibonacci representation normalization/conversion in SAGE

fibrep.sage

# https://www.reddit.com/r/baseprime/comments/id37jn/similar_number_systems/g26hq6q/?utm_source=reddit&utm_medium=web2x&context=3

# since 011 can always be change to 100 in a fib rep, we can normalize fib reps
# www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibrep.html#section4.1
# we iterate from high to low for this, so that we can handle strings of ones
# 011111 = 011000 + 111 = 100000 + 111 = 100111 = 100001 + 0110 = 100001 + 1000
# additionally, 0200 can be replaced with 1001 anywhere it occurs,
# since it is equiv to 0100 + 0100 = 0100 + 0011 = 0111 = 0110 + 1 = 0100 + 1
# and 020 in lowest end can be replaced by 101, 02 in lowest end by 10
# so this gives us a way to decrease values greater than one, as well
def normFibRep(n):
    d = True # flag to indicate we are not done
    while d or max(n) >= 2: # loop also whenever any element exceeds 1
        i = 0 # start at highest element
        d = False # assume we will be done until we discover otherwise
        while i <= len(n) - 1: # iterate through elements
            c = False # start by assuming no change has been made
            if i <= len(n) - 2 and n[i] == 1 and n[i + 1] >= 1: # 11/12/13etc
                c = True # making a change, will need to increase next-higher
                n[i] = 0 # decrease this element
                n[i + 1] -= 1 # decrease next element
            if n[i] >= 2: # element exceeds 1
                c = True # making a change, will need to increase next-higher
                n[i] -= 2 # decrease this element by 2
                if i <= len(n) - 3: # occurence of 200/300/400/etc
                    n[i + 2] += 1 # so replace with 001/101/301/etc
                elif i == len(n) - 2: # second-to-lowest element is >= 2
                    n[len(n) - 1] += 1 # so increase lowest element
            if c: # we made a change, so must increase next-higher element
                d = True # we might not be done normalizing because of change
                if i == 0: # we're at highest element in this fib rep already
                    n = [1] + n # need to prepend a higher element
                    i += 1 # shift index to account for this
                else: # general case of 011 within the fib rep
                    n[i - 1] += 1 # increase higher element
            i += 1 # move to next lower element and loop
    return n # guaranteed to be normalized Fibonacci rep
  
  def fibRepToNatNum(l):
    s = 0 # sum so far (accumulator)
    f = 2 # start with 2nd fibonacci number (=1)
    for m in reversed(l): # m is multiplier, 1 or 0 for normal Fibonacci rep
        s += fibonacci(f) * m # accumulate this element of Fibonacci rep
        f += 1 # next Fibonacci number
    return s
  
  # relies on Zeckendorf theorem where each natnum has a unique Fibonacci rep
# to guarantee uniqueness, the rep has only 0's and 1's, with no 1's adjacent
# subtract-highest-possible Fibonacci number algorithm taken from:
# codereview.stackexchange.com/questions/143544/zeckendorf-representation-of-positive-integer
def natNumToFibRep(n):
    # n decreases as we go, by subtracting the Fib nums appended to the rep
    b = [] # representation we're building, high to low
    s = False # flag: whether to skip this Fibonacci number
    for f in reversed([1] + list(fibonacci_xrange(2, n + 1))): # f is Fib num
        # fibonacci_xrange(i,j) is all Fib numbers which are >=i and <j
        # we start at 2 so f won't iterate [1,1,2,3,5,8,...]
        # (F1 isn't allowed in a Fib rep, because it's the same value as F2)
        if s: # skipping this Fibonacci number
            s = False # next number we don't need to skip
            b.append(0) # skipping this Fib num so add a zero
        else: # not skipping this Fibonacci number
            if n >= f: # we can subtract this Fibonacci num from n
                # highest possible Fib num to subtract (b/c Fibs going hi to lo)
                n -= f # decrease n by this Fibonacci num
                b.append(1) # representation will have a 1 for this Fib num
                s = True # must skip next Fibonacci number
            else:
                b.append(0) # this Fib num is greater than n, so append 0 to rep
    return b