Zeckendorf

Télécharger le projet
Commenter

Description

La suite de Bonifacci 1170-1250 est définie par F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, ... selon la relation F(n) = F(n-1) + F(n-2). Cette suite infinie est : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Édouard Zeckendorf 1901-1983 est un médecin belge qui s'est intéressé aux mathématiques et qui a démontré que tout entier positif a une représentation unique comme somme de nombres de Fibonacci non consécutifs. Exemple : 123 = 89 + 34. Le programme ci-joint zeckendorf.py écrit en langage Python calcule et affiche la représention Zeckendorf de tout nombre de l'ensemble N des entiers naturels. C'est une modification simple de la publication : https://kylekizirian.github.io/zeckendorf-and-hypothesis.html Cette représention Zeckendorf de tout entier naturel a diverses utilisations en théorie des nombres. Pour l'utiliser : lancer python.exe et faire la 1-ère fois : exec(open("zeckendorf.py").read()) et pour les fois suivantes : main(). 

    
from typing import List

def fibonacci_numbers_up_to(num: int) -> List[int]:
    """Returns a sorted list of fibonacci numbers up to a given number"""
    fibonacci_nums = [0, 1]
    next_fibonacci = fibonacci_nums[-2] + fibonacci_nums[-1]
    while next_fibonacci < num:
        fibonacci_nums.append(next_fibonacci)
        next_fibonacci = fibonacci_nums[-2] + fibonacci_nums[-1]

    return fibonacci_nums

assert fibonacci_numbers_up_to(6) == [0, 1, 1, 2, 3, 5]
assert fibonacci_numbers_up_to(13) == [0, 1, 1, 2, 3, 5, 8]

def largest_element_lte(list_: List[float], num: int) -> int:
    """Returns the largest element in a list less than or equal to given number

    Raises ValueError if no elements in the list are less than or equal
    """
    for element in sorted(list_, reverse=True):
        if element <= num:
            return element
    else:
        raise ValueError(f"No element found less than or equal to {num}")

fibonaccis_up_to_twenty = fibonacci_numbers_up_to(20)
assert largest_element_lte(fibonaccis_up_to_twenty, 6) == 5
assert largest_element_lte(fibonaccis_up_to_twenty, 13) == 13

def zeckendorf_representation(num: int) -> List[int]:
    """Returns a sorted list of fibonacci numbers that sum to a given number"""
    if num < 0:
        raise ValueError("Negative integers don't have a Zeckendorf representation")

    fibonaccis = fibonacci_numbers_up_to(num+1)

    zeckendorf_numbers = []
    if num == 0: return zeckendorf_numbers
    while num > 0:
        next_zeckendorf = largest_element_lte(fibonaccis, num)
        zeckendorf_numbers.append(next_zeckendorf)
        num -= next_zeckendorf

#   return list(reversed(zeckendorf_numbers))
    return zeckendorf_numbers

def main():
    n = int(input("Entrez n : "))
    x = zeckendorf_representation(n) 
    print(n,":", x)
    if n > 0:
        y = fibonacci_numbers_up_to(x[0]+1)
        y = list(reversed(y))
        m = 1
        while len(y) > 3:
            y = y[1:]
            if y[0] in x: m = m*10+1
            else: m = m*10
    else: m = 0
    print("mot :", m)

if __name__ == '__main__':
    main()
Télécharger le projet

Codes Sources

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (pgl10)