Teilbarkeit durch 11 (Divide by 11)

Als Problem 2 beim HP Codewars-Wettbewerb 2011 galt es einen Algorithmus zu implementieren, der eine gegebene Zahl n dahin überprüft, ob die Zahl durch 11 teilbar ist. Ursprünglich wurde der Algorithmus 1897 durch Charles Dodgson (a.k.a. Lewis Carroll) entwickelt.

Der Algorithmus:

• Solange die Zahl mindestens aus zwei Ziffern besteht, soll eine neue Zahl gebildet werden,
• wobei die Einer-Zahl entfernt wird
• und von der gekürzten Zahl subtrahiert wird.
• Falls die verbleibende zweistellige Zahl durch 11 teilbar ist, dann ist auch die ursprüngliche Zahl durch 11 teilbar.

Seine Implementierung in Python:

def teste_teilbarkeit_11(n):
    '''Der Algorithmus prueft, ob eine Zahl
    durch 11 teilbar ist. Entwickelt wurde das
    Verfahren durch Reverend Charles Dodgson 1897

    '''
    print(n)
        
    while len(str(n)) >= 2:

        if n < 11:
            return False
        elif len(str(n)) == 2 and str(n)[0] == str(n)[1]:
            return True
        else:
            n = int(str(n)[:-1]) - int(str(n)[-1])
            print(n)


n = 161408196180

liste = [11,33,121,143,144,161408196180, 195024706980990699675294451800000]

for item in liste:
    if teste_teilbarkeit_11(item) == True:
        print("\nThe number {} is divisible by 11.\n".format(item))
    else:
        print("\nThe number {} is not divisible by 11.\n".format(item))

Es funktioniert. Alternativ eine Umsetzung, die ganz auf Modulo, größer/kleiner als und damit eben nicht auf Umwandlung der Zahl in Strings setzen muss.

def teste_teilbarkeit_11(n):
    '''Der Algorithmus prueft, ob eine Zahl
    durch 11 teilbar ist. Entwickelt wurde das
    Verfahren durch Reverend Charles Dodgson 1897
 
    '''
    print(n)
         
    while n >= 11:
 
        if 11 <= n <= 99 and n % 11 == 0:
            return True
        else:
            n = n // 10 - n % 10
            print(n)
            
    return False

Auch das geht, was die Konsolenausgabe zeigt:

161408196180
16140819618
1614081953
161408192
16140817
1614074
161403
16137
1606
154
11

The number 161408196180 is divisible by 11.

Der Algorithmus war mir bislang nicht bekannt.