7-smooth cicli creati dalle cifre dei primi

[3m0o]

Sia \( f: \mathbb{N} \to \mathbb{N} \) la funzione definita nel seguente modo
\[ 0 \mapsto f(0) = 0 \]
e se \( n > 0 \) allora
\[ n \mapsto f(n) = \prod_{j=0}^{\ell} a_j \]
dove \[ p_n = \sum_{j=0}^{\ell} a_j \cdot 10^{j} \]
è l' \(n\)-esimo numero primo (inizio con \(p_1=2\)) e \( a_j \in \{0,1,\ldots,9\} \) per ogni \(0 \leq j \leq \ell \), i.e. la sua rappresentazione in base 10. Inoltre scriviamo per semplicità \( f^k = \underbrace{f \circ \ldots \circ f}_{k-\text{volte}} \).
Diciamo che \(n \) crea un ciclo se esiste un intero \(k \) tale che
\[ f^k(n) = n \]

i) Verifica che \(n=0,1,2,3,5,7 \) creano dei cicli. Riuscite a trovare altri cicli con \(k > 1 \) ? (Io non sono riuscito)
ii) Dimostra che per ogni intero \(n\) allora \( f(n) \) è \(7\)-smooth, i.e. se \(p\) è un divisore primo di \(f(n)\) allora \( p \leq 7 \).
iii) Dimostra che esiste \(M > 0 \) tale che \( n \leq M \), per ogni \( n \) che crea un ciclo, i.e. ci sono un numero finito di interi positivi che creano un ciclo.
iv) Dimostra che se \(n\) non crea un ciclo, allora esistono \(k \) ed \( m \geq 0 \) tale che
\[ f^k(n) = m \]
dove \(m\) crea un ciclo.

[dissonance]

A me questi problemi possono anche interessare, anzi, mi interessano davvero. Ma non saprei proprio da dove cominciare.

[hydro]

Non mi sembra che 1,2,3 creino dei cicli. Secondo la tua definizione per esempio $f(1)=2$ e $f(2)=2$.

[Martino]

A me sembra di capire che $f(2)=$ il prodotto delle cifre del secondo primo $=3$, $f(3)=5$, $f(5)=1$, $f(1)=2$.

Il fatto che $f(n)$ sia "$7$-smooth" mi sembra chiaro, è un prodotto di numeri tra $0$ e $9$ e quindi tutti i fattori primi di $f(n)$ sono uguali a $2$, $3$, $5$ oppure $7$.

Sul fatto che un numero finito di interi produca cicli ci devo pensare.

[hydro]

A me sembra di capire che $f(2)=$ il prodotto delle cifre del secondo primo $=3$, $f(3)=5$, $f(5)=1$, $f(1)=2$.

Ah sì certo hai ragione mi sono confuso io.

Il fatto che $f(n)$ sia "$7$-smooth" mi sembra chiaro, è un prodotto di numeri tra $0$ e $9$ e quindi tutti i fattori primi di $f(n)$ sono uguali a $2$, $3$, $5$ oppure $7$.

Sì tra l'altro $0$ non è $7$-smooth, quindi bisognerebbe specificare questa cosa.

[Martino]

Un paio di idee che secondo me risolvono il problema (modulo pensare a come formalizzarlo):

1. Congettura. Per ogni $n in NN$ esiste $k$ tale che $f^k(n) in {0,2,7}$.

2. La congettura sopra implica in modo immediato che solo un numero finito di numeri produce cicli.

3. Per dimostrare la congettura si può procedere per induzione. Basta mostrare che $f(n) < n$ da un certo $n$ in poi.

Ora, per il punto 3 userei come minimo il teorema dei numeri primi. Mi sembra un'idea ragionevole.

[Martino]

Per mostrare che $f(n) < n$ da un certo $n$ in poi farei così.

Ricordando che ci sono $x/log(x)$ primi tra $1$ e $x$ (asintoticamente), è facile vedere che l'$n$-esimo primo $p_n$ soddisfa $p_n le n^(1+epsilon)/10$ per $n$ abbastanza grande (per qualsiasi $epsilon$ positivo fissato in precedenza).

Ora è chiaro che $x$ ha al massimo $log_(10)(x)+1$ cifre decimali, e siccome nel caso peggiore sono tutte uguali a $9$, il prodotto delle cifre decimali di $x$ è minore o uguale di $9^(log_(10)(x)+1) = 9 x^(log_(10)(9))$. Il numero $log_(10)(9)$ è fortunatamente minore di $1$.

$f(n) le 9 p_n^(log_(10)(9)) le n^((1+epsilon) log_(10)(9))$

e quindi basta scegliere $epsilon$ minore di $log_9(10)-1 > 0$ per dedurre che $f(n) < n$ per $n$ grande.

A rigore, questo dimostra che esiste un insieme finito $X$ tale che

Per ogni $n in NN$ esiste $k in NN$ tale che $f^k(n) in X$.

Molto probabilmente si può prendere $X={0,2,7}$, ma per dimostrare questo bisogna conoscere moltissimi numeri primi e fare paginate di conti

Non ho formalizzato bene ma mi sembra che funzioni.

[Martino]

Ora che ci ripenso probabilmente per chiudere l'argomento bisogna trovare un $N$ esplicito tale che $f(n)<n$ per ogni $n ge N$, e controllare a mano i numeri sotto $N$, altrimenti l'induzione non parte.

[3m0o]

Un paio di idee che secondo me risolvono il problema (modulo pensare a come formalizzarlo):

1. Congettura. Per ogni $n in NN$ esiste $k$ tale che $f^k(n) in {0,2,7}$.

Questo è falso, ad esempio \( f(21)=7 \cdot 3 = 21 \), che è un' altro ciclo

Ma sull'idea dopo sei praticamente ad un passo dal dimostrarlo, ma l'induzione non è necessaria perché
supponendo che \(n \), con \(p_n > 17 \), sia tale che
\[ f(n) \geq n = \pi(p_n) > \frac{p_n}{\log p_n} \]
allora basta trovare un limite superiore \(A(\ell) \) ( che dipende dal numero di cifre, i.e \( \ell+1 \) ) per \(f(n) \) ed un limite inferiore \(B(\ell)\) per \( p_n \) , ricordandosi che
\[ p_n = \sum_{j=0}^{\ell} a_j 10^j \]
e che
\[ f(n) = \prod_{j=0}^{\ell} a_j \]
così riesci a ottenere
\[ A(\ell) \geq \frac{ B(\ell)}{\log B(\ell)} \ \ \ \ \ (1) \]
e poi dimostrare che questa cosa è valevole solo per un numero finito di \( \ell \), qui hai bisogno l'induzione ma senza farla su tutti i numeri ma solo su \( \ell \), trovi facilmente un \( L \) tale per cui per ogni \( \ell \geq L \) hai che
\[ A(\ell) < \frac{ B(\ell)}{\log B(\ell)} \]
E lo fai trasformando (1) in qualcosa della forma
\[ \text{lineare} \geq \text{esponenziale} \]
Tra l'altro \( X \neq \{ 0,2,7,21 \} \) perché, ora non ricordo quale, ma c'è almeno un' altro numero che crea un ciclo.

[3m0o]

Sì tra l'altro $0$ non è $7$-smooth, quindi bisognerebbe specificare questa cosa.

Sì, dovrei specificare in effetti che è \( 7\)-smooth oppure \(0\).