2022-07-02 / Bartłomiej Kurek
Project Euler #4: Largest palindrome product

Problem 4: Largest palindrome product

A palindromic number reads the same both ways.
The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Repozytorium git.


Python

#!/usr/bin/env python


def is_palindrome(n):
    return str(n) == str(n)[::-1]


def find_max_palindrome(bottom, top):
    max_palindrome = 0
    b = t = 0
    for i in range(top, bottom - 1, -1):
        for j in range(bottom, top + 1):
            n = i * j
            if n > max_palindrome and is_palindrome(n):
                max_palindrome = n
                b = i
                t = j
    return (max_palindrome, b, t)


if __name__ == "__main__":
    import sys

    digits = int(sys.argv[1]) if len(sys.argv) > 1 else 3
    bottom = 10 ** (digits - 1)
    top = 10 ** digits - 1
    print(find_max_palindrome(bottom, top))

Czytamy od sekcji __main__:

  • digits: ile cyfr mają mieć liczby będące czynnikami produktu, dla którego poszukujemy
    najwyższej liczby palindromicznej
  • bottom, top: dolny i górny zakres; dla liczb trzycyfrowych bottom = 100, top = 1000 - 1 = 999
  • uruchamiamy algorytm (find_max_palindrome) przekazując dolną i górną wartość przedziału

find_max_palindrome():
Iterujemy po obu zakresach (od góry lub od dołu) i dla każdego produktu sprawdzamy czy wynik
jest liczbą palindromiczną. Tę ostatnią część w Pythonie łatwo wykonać po prostu sprawdzając czy liczba w postaci stringa wygląda taka samo jak jej postać odwrócona (is_palindrome()).

C

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

/*
 * Quick benchmarks show that is_palindrome_naive()
 * is faster than is_palindrome(). Maybe because
 * naive exits early in non-palindrome case (although it does
 * the same amount of divisions to fill the array).
 */

int is_palindrome_naive(unsigned long n)
{
    int digits[64];
    int length = 0;

    // make an array of digits
    while(n) {
        digits[length] = n % 10;
        length++;
        n /= 10;
    }

    // check if it's a palindrome
    int i;
    for(i = 0; i <= length - 1; i++, length--) {
        if(digits[i] != digits[length - 1]) {
            return 0;
        }
    }

    return 1;
}


int is_palindrome(unsigned long n)
{
    unsigned long original = n;
    unsigned long reversed = 0;
    unsigned long remainder = 0;

    while(n) {
        remainder = n % 10;
        reversed = reversed * 10 + remainder;
        n /= 10;
    }

    return (original == reversed);
}


int main(int argc, char** argv)
{
    unsigned long digits = (argc > 1 ? strtoul(argv[1], 0, 10) :  3);

    if(digits < 1) {
        fprintf(stderr, "Invalid amount of digits: %ld\n", digits);
        return -1;
    }

    unsigned long start = pow(10, digits - 1);
    unsigned long end = pow(10, digits) - 1;

    printf("# Looking for palindromes in range (%ld, %ld)\n", start, end);

    unsigned long i;
    unsigned long j;
    unsigned long product = 0;

    unsigned long max_palindrome = 0;
    unsigned long product_0 = 0;
    unsigned long product_1 = 0;

    unsigned long min_product = 0;

    /* the outer loop starts from top, the inner from bottom.
     * if we get to the largest known factor within inner/bottom loop range
     * it means that (i * end) can't get greater than known max_palindrome
     *
     */
    for(i = end; i >= start; i--) {

        if((max_palindrome && i <= min_product))
            break;

        for(j = start; j <= end; j++) {
            product = i * j;
            if(is_palindrome_naive(product)) {
#ifdef DEBUG
                printf("# %ld * %ld = %16ld\tMAX: %ld, (min product: %ld)\n",
                       i, j, product, max_palindrome, min_product);
#endif
                if(product > max_palindrome) {
                    min_product = j;
                    max_palindrome = product;
                    product_0 = i;
                    product_1 = j;
                }
            }

        }
    }

    printf("Digits: %ld, Palindrome: %ld (%ld * %ld)\n",
           digits, max_palindrome, product_0, product_1);


    return 0;
}

Uruchamiamy:

$ time ./prog
# Looking for palindromes in range (100, 999)
Digits: 3, Palindrome: 906609 (993 * 913)

real    0m0.002s
user    0m0.002s
sys 0m0.000s

Dla liczb pięciocyfrowych:

$ time ./prog 5
# Looking for palindromes in range (10000, 99999)
Digits: 5, Palindrome: 9966006699 (99979 * 99681)

real    0m0.588s
user    0m0.588s
sys 0m0.000s

Uwagi:
W przypadku kompilacji bez optymalizacji funkcja is_palindrome_naive() (z tablicą) jest nieznacznie szybsza od wersji, która odwraca liczbę arytmetycznie. Jednak po włączeniu optymalizacji kompilatora mamy sytuację odwrotną: is_palindrome() jest nieco szybsza.

Przykładowo - dla produktu liczb sześciocyfrowych, przy optymalizacji O2:

  • is_palindrome()
$ time ./prog 6
# Looking for palindromes in range (100000, 999999)
Digits: 6, Palindrome: 999000000999 (999999 * 999001)

real    0m17.639s
user    0m17.628s
sys 0m0.000s
  • is_palindrome_naive()
$ time ./prog 6
# Looking for palindromes in range (100000, 999999)
Digits: 6, Palindrome: 999000000999 (999999 * 999001)

real    0m21.159s
user    0m21.141s
sys 0m0.000s