Questo gioco può finire?

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Vi propongo un gioco
Premessa: provate a giocare senza programmi informatici o software sofisticati, altrimenti perde di senso il gioco

Dato un numero \( N \in \mathbb{N} \), scriviamolo in base 10, \( N= n_0 = a_k 10^k + \ldots + a_0 \).
Moltiplichiamo tutte le sue cifre per ottenere \(n_1 = a_k \cdot \ldots \cdot a_0 \) e iteriamo il procedimento con \(n_1 \) finché, non arriviamo ad un numero \(n_{\ell} \in \{ 0, 1, \ldots, 9 \} \) composto di una sola cifra. Diremo allora che \(n_0 \) ha lunghezza \( \ell \). Definiamo così l'applicazione \( L : \mathbb{N} \to \mathbb{N} \), che ad un intero associa la sua lunghezza \( n \mapsto L(n)= \ell \)
Ad esempio \(N = 18 \) è di lunghezza \( L(18) = 1 \) poiché \(N=n_0 = 18 \) e \( n_1=1 \cdot 8 = 8 \).

Chi conosce il gioco si astenga dal giocare
Regole del gioco:
1) Chi propone il gioco trovo l'intero minimale di lunghezza \(0\) e il gioco può partire
2) Se qualcuno ha trovato l'intero minimale di lunghezza \(\ell \geq 0\), bisogna imperativamente cercare l'intero minimale di lunghezza \(\ell+1\).
3) Supponiamo che si siano trovati tutti gli interi minimali \(N_0,N_1,\ldots, N_{\ell} \) di lunghezza rispettivamente \(0< 1< \ldots < \ell \), il vincitore momentaneo è colui che ha trovato \(N_{\ell}\).
4) Sotto le medesime condizioni del punto 3), tutti i partecipanti - anche il vincitore momentaneo stesso - hanno al più 1 mese di tempo per trovare \(N_{\ell+1} \), altrimenti il vincitore momentaneo sarà dichiarato vincitore e il gioco termina.
[5) Sarei tentato di metterla come regola che è vietato usare programmi informatici e software, ma ad una certa forse diventa impossibile! Diremo che è vietato fino a numeri ragionevolmente bassi poi è ammesso però se riuscite senza a trovargli.. chapeau avete vinto a priori ]


Io inizio (e poi smetto di giocare perché conosco le risposte).
\( N_0 = 0 \) è minimale per \(L(n)=0 \).
Attualmente sono vincitore momentaneo, se passa più di un mese prima che qualcuno trovi un intero positivo \(N_1\) minimale tale che \( L(n)=1\) sarò vincitore. Altrimenti chi trova entro un mese questo \(N_1 \) sarà vincitore momentaneo, etc.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Per 6 non è il minimo, per 7 lo è

[axpgn]

Ne ho trovato una di lunghezza $9$

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Quale ?
E che ragionamento hai usato per quello del 7 e del 9?

Comunque se da qui in poi volete trovare il minimo, diciamo che a caso è un po' poco probabile che lo troviate. Dovreste capire come ridurre i casi di molto.

Con l'idea giusta controllando "solo" 8000 numeri, o meno se avete fortuna e/o riuscite a capire come ridurre i casi da 8000 a meno... trovate praticamente tutti i minimi fino ad un certa lunghezza.

[axpgn]

"3m0o":Quale ?

Il numero è questo $44.688.999$

"3m0o":E che ragionamento hai usato per quello del 7 e del 9?

Come ho già detto, non ho ancora capito quale sia il meccanismo, ma nemmeno vado a caso, provandoli tutti (con tre cifre, a mano si può ancora fare ma poi è improponibile ).
Ho seguito varie strade e quella che mi ha dato più risultati (cioè quelli che ho postato) è questa: in pratica, le cifre "buone" sono il $2$, il $3$ e il $7$, quindi basta mescolarne un po' ... [size=85][Lo zero non ci va, l'uno è neutro, anche se può essere utile nei conti, il $4$, il $6$, l'$8$ e il $9$ dipendono dagli altri e il $5$ non si dovrebbe scartare ma più delle volte produce "zeri"; quindi basta "mettere in fila" un po' di due, tre e sette e poi riordinarli o accorparli per ottenere il minimo con quella forma][/size]
Ho iniziato con le potenze di $2$, poi con [size=150]$2^(e_2)*3^(e_3)*7^(e_7)$[/size] ed infine con [size=150]$6^(e_6)*7^(e_7)*8^(e_8)*9^(e_9)$[/size], producendo una trentina di numeri per ciascuna.
Analizzandoli dal maggiore e saltando quelli con zero o con $5$ e un pari, già al terzo o quarto trovavo un numero "buono" (che sono poi quelli che ho postato).

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"axpgn":
[quote="3m0o"]E che ragionamento hai usato per quello del 7 e del 9?

Come ho già detto, non ho ancora capito quale sia il meccanismo, ma nemmeno vado a caso, provandoli tutti (con tre cifre, a mano si può ancora fare ma poi è improponibile ).
Ho seguito varie strade e quella che mi ha dato più risultati (cioè quelli che ho postato) è questa: in pratica, le cifre "buone" sono il $2$, il $3$ e il $7$, quindi basta mescolarne un po' ... [size=85][Lo zero non ci va, l'uno è neutro, anche se può essere utile nei conti, il $4$, il $6$, l'$8$ e il $9$ dipendono dagli altri e il $5$ non si dovrebbe scartare ma più delle volte produce "zeri"; quindi basta "mettere in fila" un po' di due, tre e sette e poi riordinarli o accorparli per ottenere il minimo con quella forma][/size]
Ho iniziato con le potenze di $2$, poi con [size=150]$2^(e_2)*3^(e_3)*7^(e_7)$[/size] ed infine con [size=150]$6^(e_6)*7^(e_7)*8^(e_8)*9^(e_9)$[/size], producendo una trentina di numeri per ciascuna.
Analizzandoli dal maggiore e saltando quelli con zero o con $5$ e un pari, già al terzo o quarto trovavo un numero "buono" (che sono poi quelli che ho postato).

Cordialmente, Alex[/quote]

Direi ottimo! Così trovi un numero della forma \( \underbrace{2\ldots 2}_{e_2-\text{volte}}\underbrace{3\ldots 3}_{e_e-\text{volte}}\underbrace{7\ldots 7}_{e_7-\text{volte}} \) oppure della forma \( \underbrace{3\ldots 3}_{e_3-\text{volte}} \underbrace{5\ldots 5}_{e_5-\text{volte}} \underbrace{7\ldots 7}_{e_7-\text{volte}} \) che è di una certa lunghezza, diciamo \( \ell \geq 3 \), evidentemente tutti gli altri numeri che danno lunghezza \( \ell \) è formato da cifre diverse che sono tutte divisibili per almeno uno di questi 3 numeri oppure ci metti gli 1. Infatti se un numero è composto dalle cifre \( a_0 , \ldots, a_n \) ed è di lunghezza \( \ell \geq 3 \) esse sono tutte scomponibili in fattori primi (oppure sono primi oppure sono \(1\) ). E dunque ponendo
\[ a_j = \prod_{k=1}^{A_j} p_{k,j}^{\alpha_{k,j}} \]
Abbiamo che \( p_{k,j} \in \{ 2,3,7 \} \) oppure \( p_{k,j} \in \{ 3,5,7 \} \) (poiché abbiamo supposto \( \ell \geq 3 \), e si ci fossero un 2 ed un 5 contemporaneamente allora \( 2\cdot 5 = 10 \) e dunque contiene uno zero).
Da cui
\[ \prod_{j=0}^{n} \prod_{k=1}^{A_j} p_{k,j}^{\alpha_{k,j}} = 2^{e_2} \cdot 3^{e_3} \cdot 7^{e_7} \]
oppure
\[ \prod_{j=0}^{n} \prod_{k=1}^{A_j} p_{k,j}^{\alpha_{k,j}} = 3^{e_3} \cdot 5^{e_5} \cdot 7^{e_7} \]

A questo punto considera il numero \( \underbrace{2\ldots 2}_{e_2-\text{volte}}\underbrace{3\ldots 3}_{e_e-\text{volte}}\underbrace{7\ldots 7}_{e_7-\text{volte}} \), per ipotesi è un numero di lunghezza \( \ell \geq 3 \).
Costruisci un algoritmo di packing che ti permetto di trovare il numero più piccolo tra quelli di lunghezza \( \ell \).

Analogalmente costruisci un algoritmo che ti trova il minimale se il numero di lunghezza \( \ell \) è \( \underbrace{3\ldots 3}_{e_3-\text{volte}} \underbrace{5\ldots 5}_{e_5-\text{volte}} \underbrace{7\ldots 7}_{e_7-\text{volte}} \). Chiamo questo algoritmo \( \operatorname{Pack}(e_k,e_3,e_7) \) dove \( k=2 \text{ oppure } 5 \).
Ad esempio sia \( 2233\) che \(333 \) sono numeri di lunghezza \( \ell = 3 \).
L' algoritmo che devi costruire restituisce \( \operatorname{Pack}(2,2,0) = 49 \) e \( \operatorname{Pack}(0,3,0) = 39 \).

E poi trova un modo \( \operatorname{MinimalPacking} \). (c'è un imprecisione in questo algoritmo, nel senso che la terna deve esistere per ipotesi.)
Prende una lunghezza \( \ell \geq 3 \), e restituisce la terna di interi \( \operatorname{MinimalPacking}(\ell)= (e_k,e_3,e_7) \) se \( L(k^{e_k} \cdot 3^{e_3} \cdot 5^{e_5} ) = \ell -1 \) e se \( \operatorname{Pack}(e_k,e_3,e_7) \leq \operatorname{Pack}(x,y,z) \) per ogni \( (e_k,e_3,e_7) \neq (x,y,z) \) tale che \(L( 2^x \cdot 3^y \cdot 7^z )= \ell -1 \) oppure \(L( 3^y\cdot 5^x \cdot 7^z )= \ell -1 \).
Ad esempio \( \operatorname{MinimalPacking}(3)=(0,3,0) \).

Per quanto rigurada:

"axpgn":[quote="3m0o"]Quale ?

Il numero è questo $44.688.999$

[/quote]

Il tuo numero \( 44.688.999 \) è ottenibile dalla terna \( (11,7,0) \) infatti \( 4\cdot 4 \cdot 6 \cdot 8 \cdot 8 \cdot 9 \cdot 9 \cdot 9= 2^{11} \cdot 3^7 \) e ti dirò di più
\( \operatorname{MinimalPacking}(9)=(11,7,0) \), i.e. hai beccato la terna giusta ma
\( \operatorname{Pack}(11,7,0) < 44.688.999 \)

[axpgn]

"3m0o":Direi ottimo!

Bontà tua!
Devo ancora chiarirmi diverse cose ... e digerire quello che hai scritto

Siamo d'accordo che i numeri da trovare sono di quelle forme (in qualche modo c'ero arrivato pure io ), ed anche il discorso sull'impacchettamento è chiaro (è la parte più semplice a mio parere anche se ... vedi in fondo ) ma come fai a dire, a priori cioè senza calcoli successivi, quale sia la lunghezza a cui giungerai?

Un'idea potrebbe essere questa: una specifica terna individua un ben preciso numero, del quale si può facilmente (in modo relativo) verificare se è delle due forme necessarie, se non lo è si scarta, se lo è lo si compatta e si prosegue ripetendo ... dovrebbe funzionare ...

"3m0o":\( \operatorname{MinimalPacking}(9)=(11,7,0) \), i.e. hai beccato la terna giusta ma
\( \operatorname{Pack}(11,7,0) < 44.688.999 \)

Beh, sì, $26.888.999$ è minore ... ricostruire il numero più piccolo partendo dalla fila di due e tre è la parte più facile ma meno banale di quello sembra (infatti anche facendolo a mano, ho sbagliato e un algoritmo non l'ho ancora trovato)

@3m0o
[ot]Ma dove trovi il tempo per fare TUTTO? Dormi talvolta? [/ot]


Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Non lo puoi dire a priori purtroppo. Ma comunque puoi ridurre in modo considerevole il numero di interi da controllare.

Per l'algoritmo \( \operatorname{Pack} \) ti lascio qualche spunto se vuoi farlo.
Fact 1: Considera \(n\), \(m\) due interi, e \(m\) possiede più cifre (in base 10) di \(n\), allora \( n < m \).

- Priorità 1: Eliminare più cifre possibili impacchettandole (per moltiplicazione) in una singola cifra (questo restringe già notevolmente le moltiplicazioni che puoi fare)
- Priorità 2: Se hai due cifre \(a - Consideriamo un intero \(n = \sum_{j=0}^{k} a_j 10^j \), e sia \( \sigma \in S_{k+1} \) una permutazione dell'insieme \( \{0,1,\ldots, k \} \). Con un abuso di notazione diremo \( \sigma(n) := \sum_{j=0}^{k} a_{\sigma(j)} 10^j \). Abbiamo allora \( L(n) = L(\sigma(n)) \). Inoltre tra tutti i possibili \( \sigma(n) \) quello minimale è quello con i coefficienti \( a_j \) scritti in modo ascendente, ovvero dove \( a_{\sigma(k)} \leq a_{\sigma(k-1)} \leq \ldots \leq a_{\sigma(0)} \).

Se tiri fuori un algoritmo più preciso dovrebbe risultare abbastanza chiaro quanto segue:
Dall'algoritmo di Packing si deduce chiaramente:
Se
\[ L(5^{n_1} 3^{k_1} 7^{m_1}) = L(5^{n_2} 3^{k_2} 7^{m_2}) \]

Siano inoltre \( \tilde{r}_j \equiv k_j \mod 2 \) qui per \(j =1,2\).
Se \[ n_1 + \left \lfloor \frac{k_1}{2} \right \rfloor + \tilde{r}_1 + m_1 < \left \lfloor \frac{k_1}{2} \right \rfloor + \tilde{r}_2 + n_2 +m_2 \] allora risulta \[ \operatorname{Pack}(n_1,k_1,m_1) \leq \operatorname{Pack}(n_2,k_2,m_2) \]


Se
\[ L(2^{n_1} 3^{k_1} 7^{m_1}) = L(5^{n_2} 3^{k_2} 7^{m_2}) \]

Siano inoltre \( r_1 \equiv n_1 \mod 3 \) e \( \tilde{r}_j \equiv k_j \mod 2 \) qui per \(j =1,2\).
E definiamo per semplificarci la vita \[ f_1(r_1,\tilde{r}_1) = \left\{\begin{matrix}
r_1 + \tilde{r_1} -1 & \text{se} & r_1 =2 \\
r_1 & \text{se} & r_1 = 1 \\
\tilde{r}_1 & \text{se} & r_1 =0
\end{matrix}\right. \]
Se \[ \left \lfloor \frac{n_1}{3} \right \rfloor + \left \lfloor \frac{k_1}{2} \right \rfloor + f_1(r_1,\tilde{r}_1) + m_1 < \left \lfloor \frac{k_1}{2} \right \rfloor + \tilde{r}_2 + n_2 +m_2 \] allora risulta \[ \operatorname{Pack}(n_1,k_1,m_1) \leq \operatorname{Pack}(n_2,k_2,m_2) \]

Mentre se \[ \left \lfloor \frac{k_1}{2} \right \rfloor + \tilde{r}_2 + n_2 +m_2 < \left \lfloor \frac{n_1}{3} \right \rfloor + \left \lfloor \frac{k_1}{2} \right \rfloor + f_1(r_1,\tilde{r}_1) + m_1 \] allora risulta \[ \operatorname{Pack}(n_1,k_1,m_1) \leq \operatorname{Pack}(n_2,k_2,m_2) \]


Se invece
\[ L(2^{n_1} 3^{k_1} 7^{m_1}) = L(2^{n_2} 3^{k_2} 7^{m_2}) \]

Definiamo in modo analogo \( r_j \equiv n_1 \mod 3 \) e \( \tilde{r}_j \equiv k_j \mod 2 \). E definiamo in modo analogo \[ f_j(r_j,\tilde{r}_j) = \left\{\begin{matrix}
r_j + \tilde{r_j} -1 & \text{se} & r_j =2 \\
r_j & \text{se} & r_j = 1 \\
\tilde{r}_j & \text{se} & r_j =0
\end{matrix}\right. \]
Qui tutto per \(j =1,2\)!

Se \[ \left \lfloor \frac{n_1}{3} \right \rfloor + \left \lfloor \frac{k_1}{2} \right \rfloor + f_1(r_1,\tilde{r}_1) + m_1 < \left \lfloor \frac{n_2}{3} \right \rfloor + \left \lfloor \frac{k_2}{2} \right \rfloor + f_2(r_2,\tilde{r}_2) + m_2 \] allora risulta \[ \operatorname{Pack}(n_1,k_1,m_1) \leq \operatorname{Pack}(n_2,k_2,m_2) \]


Da queste considerazioni dovrebbe essere chiaro che chiamando con \( N_{\ell} \) l'intero minimale tale che \( L(N_{\ell})=\ell \), allora \( N_0 < N_1 < N_2 < \ldots \)



Pertanto trovata una terna che è di lunghezza \( \ell \), e conoscendo \(N_{\ell-1} \), per verificare che è minimale basta verificare gli esponenti che soddisfano queste relazione.

Pertanto l'algoritmo di \( \operatorname{MinimalPacking} \), e da qui l'imprecisione a cui facevo riferimento, ti dice se c'è un Packing più piccolo semplicemente di lunghezza \( \ell \) se gli dai \( (n_2,k_2,m_2) \) che sai essere già di lunghezza \( \ell \) per ipotesi. E poi semplicemente controlli tutte le terne \( (n_1,k_1,m_1) \) che soddisfano quelle disuguaglianze (a seconda dei casi), se ne trovi una di lunghezza \( \ell \) allora forse è minimale.

Ad esempio tu prima avevi beccato 67788 che è equivalente a \( (7,1,2)_2 \) di lunghezza \(6\), ma non sapevi se era minimale. Beh ti era sufficiente controllare tutte le terne di interi che verificano a seconda dei casi quelle disuguaglianze. Inoltre sappiamo che la \(N_5\) il minimale di lunghezza \( 5 \) è associata alla terna \((1,3,1)_2 \) da cui basta checkare tutte le terne di interi \((n,k,m)_2 \) che verificano
\[ 3= 0+1+1+1 \leq \left \lfloor \frac{n}{3} \right \rfloor + \left \lfloor \frac{k}{2} \right \rfloor + f(r,\tilde{r}) + m < 2 +0+1+1=5 \]
Oppure tutte le terne di interi \( (n,k,m)_5 \) che verificano
\[ 3 \leq n + \left \lfloor \frac{k}{2} \right \rfloor + \tilde{r} + m < 5 \]
Da cui deduciamo che è un numero di \(4\) cifre. Ora non ho voglia di trovare tutte le terne da dover verificare (che è comunque un numero molto piccolo rispetto ai 67109 numeri compresi tra 679 e 67788) ma la terna \( (7,1,1)_2 \) la verifica, infatti \( 2 + 0+1+1 = 4 \) quindi calcoliamo la sua lunghezza e troviamo che è di lunghezza \(6\). Pertanto la tua terna non è minimale. Ora facciamo lo stesso procedimento applicato alla terna \( (7,1,1)_2 \) scoprendo che tutte le terne di verificano la disuguaglianza \( 3 \leq \text{qualcosa} < 4 \) non sono di lunghezza 6. Ciò implica che \( (7,1,1)_2 \) è minimale. Ora fai il \( \operatorname{Pack}(7,1,1) = 6788 \).

Detto ciò non c'è un modo per trovare un numero che è di una certa lunghezza.
Il titolo invece arriva da quanto segue. Ma non volevo dirlo subito
Infatti quella che ho chiamato "lunghezza" si chiama in realtà persistenza moltiplicativa ed è congetturato (un problema ancora aperto) che non esiste \( N \in \mathbb{N} \) con persistenza \( > 11 \).
Si sa che se questo \(N\) esiste allora deve avere più di 20 mila cifre (o qualcosa così).

@axpgn
[ot]Cosa intendi per "TUTTO" ?
Dormire... certo, anche se con dei ritmi tutti miei [/ot]

[axpgn]

@3m0o
[ot]

"3m0o":Cosa intendi per "TUTTO" ?

Hai capito benissimo!
Come, per esempio, scrivere un papiro alle due di notte che adesso mi ci vorranno anni per digerirlo [/ot]


Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

@axpgn
[ot]Mah... oddio non ho capito benissimo, ho solo intuito un pochettino
Però anni no! Al massimo qualche giorno dai.. [/ot]

Algoritmo di \( \operatorname{Pack} \)

Per farti "digerire" in meno tempo il "papiro" ecco l'algoritmo di \( \operatorname{Pack} \)
Dato un numero della forma \( \underbrace{ 2 \ldots 2 }_{ n_2-fois } \ \ \underbrace{3 \ldots 3}_{ n_3-fois } \ \ \underbrace{5 \ldots 5}_{ n_5-fois } \ \ \underbrace{7 \ldots 7}_{ n_7-fois } \) troviamo il minimale in questo modo

Step 1: Raggruppiamo quanti più 2 possibile per formare degli \(8\), quindi restiamo con \(r_2\) 2, dove \(r_2 \equiv n_2 \mod 3 \).
Step 2: Raggruppiamo quanti più 3 possibile per formare dei \(9\), quindi restiamo con \(r_3 \) 3, dove \( r_3 \equiv n_3 \mod 2 \).
Step 3: Raggruppiamo ciascuna coppia di 2 e 3 con un 6.
Step 4: Raggruppiamo ciascuna coppia di 2 con un 4.
Step 5: Ordiniamo le cifre con in modo crescente.

Ad esempio: \( \operatorname{Pack}( 22222222333337777)=677778899 \) restituisce
Step 1: \( 22222222333337777 \rightsquigarrow 8822333337777 \)
Step 2: \( 8822333337777 \rightsquigarrow 88229937777 \)
Step 3: \( 88229937777 \rightsquigarrow 6882997777 \)
Step 4: non fa nulla
Step 5: \( 2688997777 \rightsquigarrow 2677778899 \)

[axpgn]

I tuoi passi son gli stessi che avevo in mente ma non ho una dimostrazione che quest'algoritmo sia sempre il migliore (non so se mi sono spiegato )


Cordialmente, Alex