Lukas' Weblog

Sehr fasziniert am Känguru-Wettbewerb 2009 (Kategorie: Student) dieses Jahr hat mich das Beispiel #30. Direkt danach postete ich es in den Kommentaren vom BRGblog, allerdings mit falscher Angabe. Die Angabe lautet korrekt:

Eine Folge von Zahlen ist definiert durch a₀ = 1, a₁ = 2 und a_n+2 = a_n + (a_n+1)² für n ≥ 0. Der Rest von a₂₀₀₉ bei Division durch 7 beträgt

A) 0     B) 1     C) 2     D) 5     E) 6

Das folgende Skript berechnet die Lösung. Der Trick dabei ist die Tatsache, dass die Einerstellen der Summanden nur die Einerstellen (!) der Summe beeinflusst. Also muss man nur die Einerstelle in der Liste speichern. Sonst wäre bereits die 7. Zahl über Billionen hinaus. Skript … ganz schön. Aber wie berechnet man sowas am Papier? Dafür hatte ich dann keine Idee mehr. Vorschläge?

#!/usr/bin/env python

def func(index, a):
    if index < 0:
        raise 'ImplementationError', 'n must be greater or equal 0'
    return (a[index-2] + (a[index-1])**2) % 10

a = [1, 2]
for i in xrange(2, 2010):
    tmp = func(i, a)
    a.append(tmp)
    print i, tmp

print
print 'answer: %d ' % (a[2009] % 7)