026 – Perioden von Stammbrüchen

 

Der Stammbruch bezeichnet einen Bruch mit einer 1 im Zähler und einer beliebigen natürlichen Zahl im Nenner. Somit ergeben sich Stammbrüche als Kehrwert natürlicher Zahlen.

Als Dezimalbruch dargestellt sind die Stammbrüche mit den Nennern 2 bis 10:

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

Dabei meint 0.1(6) den periodischen Bruch 0.16666… und hat die 1-ziffrige sich wiederholende Periode 6. 1/7 hat eine 6-ziffrige Periode.

Finde den Wert von d unter 1000, für den 1/d die längste Periode hat.

Lösung

Es gibt hier verschiedene Lösungsmöglichkeiten. Im Folgenden werden zwei davon vorgestellt.

Möglichkeit 1

Wie bei den meisten Problemen können wir mit Brute Force zur Lösung kommen. Dazu gehen wir alle Zahlen von 1 bis 1000 durch, führen manuell die Berechnung des Kehrwertes durch und schreiben diesen in einen String. Anschließend suchen wir in diesem String nach der längsten Periode.

Matlab-Code:

function d = e026
    maxPeriode = 0;
    maxD = 0;
    for i = 1 : 1000
        periode = perDivision(1,i);
        if length(periode) > maxPeriode
            maxPeriode = length(periode);
            maxD = i;
        end
    end
    d = maxD;
end

function periode = perDivision(a, b)

    bs = num2str(b);
    ziffernB = length(bs);
    y = char(zeros(1,10000));
    letzterEintrag = 0;
    periode = [];

    done = 0;
    while (done == 0)     

        a = a * 10;
        while (a < b)
            a = a * 10;
            letzterEintrag = letzterEintrag + 1;
            y(letzterEintrag) = '0';
        end

        teiler = floor(a / b);
        teilerS = num2str(teiler);

        letzterEintrag = letzterEintrag + 1;
        if length(teilerS) == 1
            y(letzterEintrag) = teilerS;
        else
            y(letzterEintrag : letzterEintrag + 1) = teilerS;
        end

        letzterEintrag = letzterEintrag + length(teilerS)-1;

        a = a - teiler * b;
        if (a == 0)
            break
        end

        periodeGefunden = 0;

        if (letzterEintrag > 2 * ziffernB)
            snippet = y(letzterEintrag - ziffernB + 1 : letzterEintrag);
            teiler = strfind(y(1 : letzterEintrag), snippet);
            lTeiler = length(teiler);
            if (lTeiler == 3)
                  if (teiler(3) - teiler(2) == teiler(2) - teiler(1))
                        periodeGefunden = strcmp(y(teiler(1) : ...
                            teiler(2)), y(teiler(2) : teiler(3)));
                  end
            end
        end

        if (periodeGefunden)
            periode = y(teiler(2) : teiler(3) - 1);
            done = 1;
        end

        if (letzterEintrag > 10000)
            done = 1;
        end
    end
end

Ergebnis: 983
Rechenzeit: 9.558173 Sekunden

Möglichkeit 2

Alternativ können wir uns folgendes vor Augen führen. Der Dezimalbruch 0.(1) ist bekanntlich gleich dem Bruch 1/9. Gleiches gilt für 0.(2) = 2/9, …, 0.(8) = 8/9, 0.(9) = 9/9 = 1.
Dies funktioniert auch mit mehrstelligen Zahlen, z.B. 1/7 = 0.(142857) = 142857/999999.

Für eine gegebene Zahl d können wir die Länge der Periode von 1/d finden, indem wir die kleinste Zahl bestimmen, die nur aus 9en besteht (9999…) und die ohne Rest durch d teilbar ist.

Die Zahl 10n-1 – 1 ist 999… mit n 9en. Wir können herausfinden, ob diese Zahl ganzzahlig durch d teilbar ist, indem wir den Modulo berechnen: mod(10n-1 – 1, d). Dieser ist dann gleich 0.
Vereinfachend kann man das kleinste n bestimmen, so dass mod(10n-1, d) = 1.

Matlab Code:

function d = e026
    numMax = 0;
    for i = 901 : 2 : 999
        num = 1;
        while mod(sym(10)^sym(num), sym(i)) ~= 1 && num < 1000
            num = num + 1;
        end
        if num ~= 1000
            if (numMax < num)
                numMax = num;
                d = i;
            end
        end
    end
end

Leider kann Matlab nicht gut mit großen genauen Zahlen umgehen, daher müssen wir sym() verwenden. Dadurch dauern alle Rechenoperationen sehr sehr lange. In einer anderen Programmiersprache wäre dieser Ansatz wohl schneller, in Matlab ist er langsamer als Möglichkeit 1. Wir haben hier vorausgesetzt, dass die gesuchte Zahl ungerade und größer als 900 ist.