La matematica in gioco: Numeri palindromi

Oggi si parla del quarto problema del Project Euler: trovare il palindromo più grande generato dal prodotto tra due numeri di tre cifre ciascuno. La risposta a tale quesito può essere trovata, come negli altri casi, sia attraverso un algoritmo specifico, sia utilizzando carta e penna. Al di là di come il problema viene risolto, ci sono alcune considerazioni preliminari che possono essere fatte, come ad esempio provare a capire come è fatto il numero palindromo cercato: \[A \cdot (10^5+1)+B \cdot (10^4+10^2)+C \cdot 1100 =\] \[= 11 \cdot (A \cdot 9091 + B \cdot 910 + C \cdot 100)\] Esso deve quindi essere divisibile per 11, ma non per il suo quadrato. Questo vuol dire che solo uno dei due moltiplicatori è divisibile per 11. A questo punto si può fare una considerazione estremamente semplice: andiamo a cercare i multipli di 11 compresi tra 900 e 1000:

902, 913, 924, 935, 946, 957, 968, 979, 990

Il massimo palindromo che cerchiamo inizia con la stessa cifra con cui finisce, quindi dovremmo cercare un numero che inizia e quindi finisce per 9. Questo esclude tutti i multipli di 11 che sono anche pari e tutti quelli che sono divisibili per 5. Dall'elenco di cui sopra restano allora: 913, 957, 979.
A questo punto, decidendo che stiamo cercando il moltiplicatore massimo, e che quindi la cifra delle centinaia è un 9 anche per il secondo moltiplicatore, facciamo alcune ulteriori considerazioni, ognuna per ogni numero considerato:

1. se il primo moltiplicatore è 913, il secondo deve necessariamente finire per 3 in modo tale da avere 9 come ultima cifra;
2. per lo stesso motivo di prima, nel caso di 957 l'ultima cifra deve essere 7;
3. e quindi per 979, l'ultima cifra del secondo moltiplicatore deve essere 1.

Per il primo numero possiamo impostare la seguente equazione: \[(900+10+3)(900+10x+3) = 824439 + 9130x\] dove $x$ è la cifra cercata.
Valutiamo $x$: (900000-824439)/9130=75561/9130=8,2761... e quindi la cifra cercata può essere solo 9. E, guarda un po', il prodotto \[913 \cdot 993 = 906609\] è palindromo.
Fatto lo stesso ragionamento anche per gli altri due numeri (957, 979) si trova che non ci sono altri numeri palindromi, e quindi 906609 è il palindromo cercato!
Dal lato programmazione ho condotto una piccola ricerca, trovando alcuni link interessanti. Ad esempio uno script per VB [link morto], o in alternativa potete consultarne uno pubblicato su Coder Profile. Su codesling, invece, ho trovato un paio di codici per i problemi 4 e 6 che possono facilmente essere adattati per qualunque linguaggio di programmazione.
Per C# eccovi un articolo su Functinal Fun sul problema #4 e infine una raccolta di codici su The Research Kitchen che possono essere utilizzati per risolvere alcuni dei problemi proposti dal Project Euler.

---

P.S.: la bellezza della matematica è che si possono trovare dimostrazioni identiche o quasi anche quando non ci si può confrontare prima: per gli iscritti al Project Euler suggerirei di controllare la dimostrazione proposta dall'utente Begoner.