7-smooth cicli creati dalle cifre dei primi

[Studente Anonimo]

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.

[hydro1]

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

[Studente Anonimo]

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.

[hydro1]

"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$.

Ah sì certo hai ragione mi sono confuso io.

"Martino":
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.

[Studente Anonimo]

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.

[Studente Anonimo]

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.

[Studente Anonimo]

Ora che ci ripenso probabilmente per chiudere l'argomento bisogna trovare un $N$ esplicito tale che $f(n)

Cita

Segnala

[Studente Anonimo]

"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}$.

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.

[Studente Anonimo]

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

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

[Studente Anonimo]

Due problemi, che ritengo interessanti, ma che non sono riuscito a dimostrare o confutare sono i seguenti:
Possiamo definire una "sorta" di persistenza di un numero \(n\) nel seguente modo.

Definizione:
Sia \(n \geq 0 \) un intero, definiamo la persistenza \( k \in \mathbb{N} \) di \(n \) come il più piccolo intero tale che \( f^k(n) \neq n \) crea un ciclo.

Dalla definizione segue chiaramente che se \( n \) è un punto fisso di \(f\) allora la persistenza di \(n\) è uguale a 0. È anche vero che se \(n \) crea un ciclo allora la persistenza di \(n\) è \(0\) oppure \(1\). Ma il contrario (scusate non so come si dice in italiano converse) è falso, ad esempio \(4\) ha persistenza \(1\) ma non crea un ciclo.

Congettura 1:
L'unico ciclo con persistenza di \(1\) è quello generato da \(1\).

Per dimostrare o confutare questa congettura sarebbe sufficiente controllare tutti i \(7\)-smooth minori di \(10^{45} \), ma penso che sia molto dispendioso.

Congettura 2:
Per ogni intero \(k \geq 0 \) esiste un intero \(n \geq 0 \) di persistenza \(k\).

Per dimostrarlo credo sia sufficiente dimostrare che la funzione \( g: \mathbb{P} \to \mathcal{S}_7 \) definita da
\[ p_n \mapsto g(p_n) := f(n) \]
è una suriezione. Dove \( \mathbb{P} \) indica l'insieme dei primi e \( \mathcal{S}_7 \) l'insieme dei \(7\)-smooth. Ma dimostrare questo fatto mi sembra molto difficile.