036 – Summe der Palindrome in Basis 10 und 2

 

Die dezimale Zahl 585 ist binär 1001001001 und in beiden Basen ein Palindrom.

Finde die Summe aller Zahlen unter 1000000, die in den Basen 10 und 2 Palindrome sind. Zahlen mit führenden Nullen sind ausgeschlossen.

Lösung

Brute Force Methode:

num = 0;
for i = 1 : 2 : 999999
    a = dec2bin(i);
    lena = length(a);
    b = num2str(i);
    lenb = length(b);
    if b == b(lenb : -1 : 1)
        if a == a(lena : -1 : 1)
            num = num + i;
        end
    end
end

Ergebnis: 872187
Rechenzeit: 100 Sekunden

Stattdessen können wir auch zuerst alle Palindrome in einer Basis berechnen und dann nur noch prüfen, ob sie in der anderen Basis auch ein Palindrom sind. Dazu benutzen wir Binary Singleton Expansion Functions für bessere Performanz:

clc
clear all
tic

palindrome = [];
for ziffern = 1 : 6
    liste = (10^(ziffern-1) : 10^ziffern - 1)';
    expStellen = 10.^ (ziffern - 1 : -1 : 0);

    ziffer = mod(floor(bsxfun(@rdivide, liste, expStellen)), 10);
    rev = ziffer(:, end : -1 : 1);
    revListe = sum(bsxfun(@times, rev, expStellen), 2);
    palindromListe = (liste == revListe);

    pnum = liste(palindromListe);

    bnum = dec2bin(pnum);
    for j = 1 : size(pnum, 1),
        pos1 = find(bnum(j, : ) == '1', 1);
        temp = bnum(j, pos1 : end);
        revTemp = temp(end : -1 : 1);
        if isequal(temp, revTemp),
            palindrome = [palindrome; pnum(j)];
        end
    end
end

sum(palindrome)
toc

Ergebnis: 872187
Rechenzeit: 0.146084 Sekunden