Primi troncabili
Navigando per il sito "eulerProject" ho trovato il seguente problema:
{The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.}
Quello che non riesco a capire è come si dimostra (matematicamente) perché ne esistono solo 11.
{The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.}
Quello che non riesco a capire è come si dimostra (matematicamente) perché ne esistono solo 11.
Risposte
EDIT. Temo di aver scambiato fra loro destra e sinistra, seguendo un mio strano ragionamento; confido che riusciate comunque a capire.
Non ho avuto la pazienza di arrivare fino in fondo e non mi è chiaro se gli 11 numeri possono avere un qualsiasi numero di cifre o debbono averne proprio 4; ti dico come imposterei la soluzione nella seconda ipotesi, accennando poi brevemente a come modificarla nella prima.
Cominciamo con i seguenti punti fermi:
- non possono esserci le cifre $0,4,6,8$ perché troncando da sinistra arriverei ad un numero non primo;
- le cifre $2,5$ possono esserci solo al primo posto per lo stesso motivo;
- le cifre $1,9$ non possono essere all'ultimo posto perché troncando da destra fino ad un numero di una sola cifra non otterrei un numero primo. Per lo stesso motivo non possono neanche essere al primo posto, ma questo mi interesserà solo quando penserò al primo posto.
Consideriamo ora le ultime due cifre: la prima di esse può essere solo $1,3,7,9$ e la seconda solo $3,7$. Scartando le combinazioni che danno origine a numeri non primi, ci resta che le ultime due cifre possono essere solo $13,17,37,73,97$.
Consideriamo le ultime tre cifre: la prima di esse può essere solo $1,3,7,9$, seguita da uno dei precedenti gruppi; di nuovo scartiamo le combinazioni che originano numeri non primi.
Qui io ho smesso e quindi non so dirti i risultati.
Per le quattro cifre farei un ragionamento analogo, a parte il fatto che la prima cifra può essere $2$ o $5$ mentre non può essere né $1$ né $9$ (quindi sarà una fra $2,3,5,7$).
Una volta ottenuti i risultati possibili bisogna controllarne la troncabilità da destra e quasi certamente ne dovremo scartare parecchi.
Se i numeri da trovare possono avere un qualsiasi numero di cifre (anche una sola?) il ragionamento di base è lo stesso ma, per ogni numero di cifre, devi aggiungere quelli inizianti con $2$ o $5$ e scartare quelli che iniziano con $1$ o $9$.
Non ho avuto la pazienza di arrivare fino in fondo e non mi è chiaro se gli 11 numeri possono avere un qualsiasi numero di cifre o debbono averne proprio 4; ti dico come imposterei la soluzione nella seconda ipotesi, accennando poi brevemente a come modificarla nella prima.
Cominciamo con i seguenti punti fermi:
- non possono esserci le cifre $0,4,6,8$ perché troncando da sinistra arriverei ad un numero non primo;
- le cifre $2,5$ possono esserci solo al primo posto per lo stesso motivo;
- le cifre $1,9$ non possono essere all'ultimo posto perché troncando da destra fino ad un numero di una sola cifra non otterrei un numero primo. Per lo stesso motivo non possono neanche essere al primo posto, ma questo mi interesserà solo quando penserò al primo posto.
Consideriamo ora le ultime due cifre: la prima di esse può essere solo $1,3,7,9$ e la seconda solo $3,7$. Scartando le combinazioni che danno origine a numeri non primi, ci resta che le ultime due cifre possono essere solo $13,17,37,73,97$.
Consideriamo le ultime tre cifre: la prima di esse può essere solo $1,3,7,9$, seguita da uno dei precedenti gruppi; di nuovo scartiamo le combinazioni che originano numeri non primi.
Qui io ho smesso e quindi non so dirti i risultati.
Per le quattro cifre farei un ragionamento analogo, a parte il fatto che la prima cifra può essere $2$ o $5$ mentre non può essere né $1$ né $9$ (quindi sarà una fra $2,3,5,7$).
Una volta ottenuti i risultati possibili bisogna controllarne la troncabilità da destra e quasi certamente ne dovremo scartare parecchi.
Se i numeri da trovare possono avere un qualsiasi numero di cifre (anche una sola?) il ragionamento di base è lo stesso ma, per ogni numero di cifre, devi aggiungere quelli inizianti con $2$ o $5$ e scartare quelli che iniziano con $1$ o $9$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo