Probleemstelling

Een palindroomgetal leest van links naar rechts hetzelfde als van rechts naar links. Het grootste palindroom dat het product is van twee tweecijferige getallen is

Bepaal het grootste palindroom dat geschreven kan worden als het product van twee driecijferige getallen.

Eerste analyse

Er zijn 900 driecijferige getallen. Zelfs wanneer we alle unieke paren onderzoeken, zijn er hoogstens 405450 producten. Deze zoekruimte is klein genoeg voor brute force.

We doorlopen de factoren in dalende volgorde, zodat grote producten eerst worden onderzocht. Zodra verdere producten niet meer groter kunnen zijn dan het beste gevonden palindroom, stoppen we de betreffende lus.

Gekozen programmeeraanpak

We maken eerst een afzonderlijke, algemene functie is_palindroom(uitdrukking). Ze zet haar argument indien nodig om naar tekst en vergelijkt die tekst met haar omgekeerde. De functie is dus niet speciaal geschreven voor producten van driecijferige getallen.

Door de palindroomtest los te koppelen van de zoeklussen krijgt elk programmadeel één duidelijke taak. De functie kan afzonderlijk worden getest en hergebruikt, terwijl het hoofdalgoritme overzichtelijk blijft.

Daarna daalt de eerste factor van 999 tot 100. De tweede factor daalt telkens van 999 tot de eerste factor, zodat elk ongeordend factorpaar hoogstens eenmaal wordt onderzocht.

Alleen producten die groter zijn dan het tot dan toe gevonden maximum blijven interessant. Wanneer een product in de dalende binnenste lus niet meer groter is, mogen we die lus afbreken. Voor ieder nog interessant product gebruiken we is_palindroom(); bij een positief resultaat bewaren we het product en beide factoren.

De functie is_palindroom()

def is_palindroom(uitdrukking) -> bool:
    tekst = str(uitdrukking)
    return tekst == tekst[::-1]

str(uitdrukking) maakt een tekstvoorstelling van de ontvangen waarde. De uitdrukking tekst[::-1] levert dezelfde tekst in omgekeerde volgorde. Zijn beide teksten gelijk, dan geeft de functie True terug; anders geeft ze False terug. Zo werkt de functie bijvoorbeeld voor het getal 9009, maar ook voor een tekst zoals "lepel".

Algoritme

1. Initialiseer het grootste palindroom met 0.
2. Doorloop de eerste factor dalend van 999 tot en met 100.
3. Doorloop de tweede factor dalend van 999 tot en met de eerste factor.
4. Bereken het product.
5. Breek de lus af wanneer geen groter product meer mogelijk is.
6. Test het product met de algemene functie is_palindroom().
7. Bewaar elk groter gevonden palindroom en zijn factoren.
8. Druk het antwoord, de factoren en de uitvoeringstijd af.

Python-programma

import time


# Controleer of een uitdrukking een palindroom is
def is_palindroom(uitdrukking) -> bool:
    tekst = str(uitdrukking)
    return tekst == tekst[::-1]


# Start van de tijdsmeting
starttijd = time.perf_counter()


# Zoek dalend naar het grootste palindroomproduct
grootste_palindroom = 0
eerste_factor = 0
tweede_factor = 0

for factor_a in range(999, 99, -1):
    if factor_a * 999 <= grootste_palindroom:
        break

    for factor_b in range(999, factor_a - 1, -1):
        product = factor_a * factor_b

        if product <= grootste_palindroom:
            break

        if is_palindroom(product):
            grootste_palindroom = product
            eerste_factor = factor_a
            tweede_factor = factor_b


# Stop de tijdsmeting
eindtijd = time.perf_counter()
uitvoeringstijd = eindtijd - starttijd


# Toon het resultaat
print(f"Het grootste palindroom is: {grootste_palindroom}")
print(f"Factoren: {eerste_factor} en {tweede_factor}")
print(f"Uitvoeringstijd: {uitvoeringstijd:.8f} seconden")

Complexiteit en eenvoudige optimalisaties

Met mogelijke driecijferige factoren onderzoeken de twee geneste lussen in het ongunstigste geval een kwadratisch aantal paren. De tijdscomplexiteit is daarom wanneer de cijferlengte vast is. De tekstvergelijking in is_palindroom() kost voor een getal met cijfers tijd, zodat de algemene notatie is. Het geheugengebruik blijft .

De code vermijdt dubbele factorparen, doorloopt grote producten eerst en breekt een lus af zodra geen verbetering meer mogelijk is. Men zou ook de deelbaarheid van zescijferige palindromen door 11 in de lussen kunnen verwerken, maar die extra optimalisatie is voor deze kleine zoekruimte niet nodig.

Wiskundige achtergrond

Een zescijferig palindroom heeft de vorm . De waarde ervan is

Ieder zescijferig palindroom is dus deelbaar door 11. Bij een product dat zo’n palindroom vormt, moet minstens een van beide factoren deelbaar zijn door 11. De Python-oplossing hoeft deze extra eigenschap niet te gebruiken, omdat de gewone afkappingen de zoekruimte al voldoende beperken.

Resultaat

Het grootste palindroomproduct is

Uitvoeringstijd: ongeveer 0,00121165 seconden.

Besluit

De dalende brute-force aanpak onderzoekt een beperkte zoekruimte en slaat dankzij de afkappingen veel onnodige producten over. Zo vinden we met duidelijke Python-code snel het correcte antwoord 906609.