038 – Pandigitale Vielfache

 

Wenn man die Zahl 192 mit 1, 2 und 3 multipliziert, erhält man

    \[192\cdot 1 = 192\]

    \[192\cdot 2 = 384\]

    \[192\cdot 3 = 576\]

Wenn man die Ergebnisse hintereinander schreibt, erhält man die pandigitale Zahl (alle Ziffern von 1 bis 9 kommen genau ein Mal vor) 192384576. Wir nennen dies das kombinierte Produkt von 192 und (1,2 3).

Auch wenn man 9 mit 1, 2, 3, 4 und 5 multipliziert, und die Ergebnisse hintereinander schreibt, erhält man solch ein Produkt: 918273645.

Was ist die größte pandigitale Zahl, die als das kombinierte Produkt einer natürlichen Zahl mit (1, 2, …, n) gebildet werden kann?

Lösung

Wir wissen bereits, dass das Ergebnis größer als 918273645 sein muss, die “Startzahl” muss also mit 9 beginnen und mehr als eine Ziffer haben. Die Zahlen 9[0...9] ergeben im kombinierten Produkt alle entweder zu wenige (8) oder zu viele (11) Ziffern. Die Zahlen 9[0...9][0...9] ergeben ebenfalls zu wenige (7) oder zu viele (11) Ziffern. Fünfstellige Zahlen scheiden ebenfalls aus, da sich zu viele Ziffern ergeben. Die gesuchte Startzahl liegt also zwischen 9123 und 9876.

In Matlab nutzen wir dieses Wissen, um nur den interessanten Bereich zu durchsuchen:

clc
clear all
tic

ergebnis = 0;
startZahl = 0;

for n = 9123 : 9876
    nString = num2str(n);
    nZiffern = length(nString);
    multiplikator = 1;
    while (nZiffern < 9)
        multiplikator = multiplikator + 1;
        teil = n * multiplikator;
        teilString = num2str(teil);
        nZiffern = nZiffern + length(teilString);
        nString = [nString teilString];
    end
    if (nZiffern > 9)
        continue
    else
        if (length(unique(nString))==9 && isempty(strfind(nString,'0')))
            temp = str2double(nString);
            if (temp > ergebnis)
                ergebnis = temp;
                startZahl = n;
            end
        end
    end
end

ergebnis
startZahl

toc

Ergebnis: 932718654
Rechenzeit: 0.247229 Sekunden