032 – Pandigitale Zahlen und Produkte

 

Eine pandigitale Zahl ist eine dezimale ganze Zahl, die jede der zehn Ziffern von 0 bis 9 genau einmal enthält. Die erste Ziffer darf dabei nicht 0 sein.

Wir definieren hier eine n-stellige Zahl als pandigital, wenn sie alle Ziffern von 1 bis n genau ein Mal enthält. Zum beispiel ist die die Zahl 15234 pandigital, da alle Ziffern von 1 bis 5 genau ein Mal vorkommen.

Das Produkt 7254 ist ungewöhnlich, da die Gleichung 39\cdot 186=7254 mit Faktoren und Produkt gemeinsam betrachtet neunstellig pandigital ist.

Finde die Summe aller Produkte, für die eine solche pandigitale Gleichung aufgestellt werden kann.

Lösung

Wir brauchen in der gewünschten Gleichung 9 Ziffern. Dies kann auf zwei unterschiedliche Arten erreicht werden: entweder xx * xxx = xxxx oder x * xxxx = xxxx. Wir testen vom kleinstmöglichen Produkt 1234 bis zum größtmöglichen 9876. Die Ziffern werden zunächst aufgeteilt. Wir prüfen, ob jede Ziffer nur ein Mal vorkommt und ob alle Ziffern größer als 0 sind.
Anschließend testen wir zuerst die Möglichkeit xx * xxx = xxxx, indem wir für den ersten Faktor 12 bis 98 testen. für jeden Kandidaten testen wir, ob das gewünschte Produkt durch diesen Faktor teilbar ist. Ist dies der Fall, testen wir, ob der Quotient noch größer oder gleich 100 ist, da wir noch drei Ziffern benötigen. Danach werden die Ziffern der beiden Faktoren in das Feld zu den Ziffern des Produktes gespeichert. Erneut wird geprüft, ob keine Ziffer doppelt vorkommt und ob alle Ziffern größer als 0 sind.

Nur wenn alle Tests erfolgreich sind, haben wir ein neues ungewöhnliches Produkt gefunden.

Im zweiten Schritt verfahren wir ähnlich mit der Möglichkeit x * xxxx = xxxx.

Matlab-Code:

tic
anzahl = 0;
summe = 0;
res = [];

% entweder xx * xxx = xxxx oder x * xxxx = xxxx
for produkt = 1234 : 9876
    ziffer = ones(1, 9);
    ziffer(6) = floor(produkt / 1000);
    ziffer(7) = floor(mod(produkt, 1000) / 100);
    ziffer(8) = floor(mod(produkt, 100) / 10);
    ziffer(9) = mod(produkt, 10);
    if (length(unique(ziffer(6 : 9))) == 4 && min(ziffer(6 : 9)) > 0 )
        for q = 12 : 98    % xx * xxx = xxxx ?
            if (mod(produkt, q) == 0)
                d = produkt / q;
                if (d < 100)
                    % es ergibt sich nur xx * xx = xxxx, nicht pandigital
                    continue
                end

                ziffer(1 : 2) = [floor(q / 10), mod(q, 10)];
                ziffer(3 : 5) = [floor(d / 100), ...
                    floor(mod(d, 100) / 10), mod(d, 10)];
                if (length(unique(ziffer)) == 9 && min(ziffer) > 0)
                    anzahl = anzahl + 1;
                    res(anzahl, : ) = ziffer;
                    disp([produkt d q]);
                    summe = summe + produkt;
                    break
                end
            end
        end

        for q = 2 : 9
            if (mod(produkt, q) == 0)
                d = produkt / q;
                if (d < 1000)   % 1 x 3 = 4 Ziffern
                    continue
                end
                ziffer(1) = q;
                ziffer(2 : 5) = [floor(d / 1000), ...
                    floor(mod(d, 1000) / 100), ...
                    floor(mod(d, 100) / 10), mod(d, 10)];
                if (length(unique(ziffer)) == 9 && min(ziffer) > 0)
                    anzahl = anzahl + 1;
                    res(anzahl, : ) = ziffer;
                    disp([produkt d q]);
                    summe = summe + produkt;
                    break
                end
            end
        end
    end
end
disp(summe)
toc

Ergebnis: 45228
Rechenzeit: 0.507799 Sekunden