Funzionale sugli interi positivi

[Gi81]

Trovare tutte le funzioni $f:NN \\{0} -> NN \\{0}$ strettamente crescenti tali che per ogni $n in NN \\{0}$
1) $f(2n) = f(n) +n$
2) se $n$ è un numero primo, allora $f(n)$ è un numero primo.

[dan952]

Solo $f(n)=n$...

Edit: avevo escluso l'identità

[Gi81]

@dan95:

In realtà una soluzione c'è. La più banale di tutte le funzioni

Hint:

aggiungiamo l'ipotesi $f(1)=1$

[otta96]

Con l'ipotesi aggiuntiva $f(1)=1$ è veramente facile, ci avevo già pensato, infatti si nota che $f$ e l'identità coincidono su un insieme chiuso per moltiplicazioni per $2$, infatti chiamando $A$ questo insieme, si ha $n\inA=>f(2n)=f(n)+n=n+n=2n=>2n\inA$.
Ora l'ipotesi $f(1)=1$ implica che tutte le potenze di $2$ stanno in $A$, ma dato che $2=f(2)3\inA$. Analogamente per induzione forte, per ogni numero dispari $2n+1$ si ha che $n,n+1\inA=>2n=f(2n)2n+1\inA$. Ma allora tutti i numeri dispari stanno in $A$, mentre per quelli pari discende dalla proprietà detta prima, quindi $A=NN$.
Immagino che si possa dimostrare che $f(1)=1$ usando le sole ipotesi iniziali, ma non so come.

[giammaria2]

Nelle soluzioni finora date, l'unica con dimostrazione è quella di otta96, in cui però manca la parte finale.

togliendo l'ipotesi $f(1)=1$ (non data), la condizione 1) è soddisfatta da
$f(n)=a+n" "$ con $" "a in NN$ (zero compreso)
Per $a=0$ è certo soddisfatta anche la 2) e probabilmente è l'unica possibilità. ma non so bene come dimostrarlo.

[dan952]

Domani scrivo la mia soluzione

[giammaria2]

Nel frattempo ho trovato il pezzo che mi mancava.

$2$ e $3$ sono numeri primi, quindi devono essere primi anche $a+2$ ed $a+3$; trattandosi di due numeri consecutivi, uno di essi è pari, e quindi può essere primo solo se vale $2$. E' facile escludere che sia $a+3=2$, quindi resta solo $a+2=2->a=0$.

[Gi81]

@otta96:

"otta96":Analogamente per induzione forte, per ogni numero dispari $2n+1$ si ha che $n,n+1\inA=>2n=f(2n)2n+1\inA$

Questa non l'ho capita. Come fai a dire che $f(2(n+1))= 2n+2$?
Cioè, mi puoi spiegare meglio cosa usi come ipotesi induttiva?

@giammaria:

Non ho capito perchè "la condizione 1) è soddisfatta da $f(n)=a+n$ con $ a in NN$ (zero compreso)"
Una volta fatto questo, l'ultima tua parte è perfetta:

"giammaria":Nel frattempo ho trovato il pezzo che mi mancava.
$ 2 $ e $ 3 $ sono numeri primi, quindi devono essere primi anche $ a+2 $ ed $ a+3 $; trattandosi di due numeri consecutivi, uno di essi è pari, e quindi può essere primo solo se vale $ 2 $. E' facile escludere che sia $ a+3=2 $, quindi resta solo $ a+2=2->a=0 $.

Anzi, per dimostrare che $f(1)=1$ ho fatto un ragionamento molto simile

[dan952]

Passo 1. Dimostriamo che se $f(n)$ è soluzione allora $f(n)=f(1)-1+n$.

Per ipotesi

$f(n)
in particolare sottraendo $f(n)$ si ha

$0< f(n+1)-f(n)
Ovvero $n-1$ numeri naturali $0

Passo 2. Dimostriamo che $f(1)=1$.

Sia $p$ primo, per ipotesi anche $f(p)$ è primo, anche $f(f(p))=f(1)-1+f(p)=2(f(1)-1)+p$ è primo, in particolare componendo la funzione $p$ volte con se stessa abbiamo $f^{(p)}(p)=p(f(1)-1)+p=pf(1)$ che deve essere primo quindi necessariamente $f(1)=1$

[Gi81]

@dan95:

Solo una cosa: nel passo 1 non dimostri che $f(n)= n+f(1)$, ma piuttosto che $f(n) = n + (f(1)-1))$
Nel punto 2 hai $f^((p)) (p) = p [f(1)- 1] + p = p * f(1)$, da cui $f(1)=1$

Comunque la strategia è corretta

[giammaria2]

Non avevo scritto la prima parte perché molto simile alla soluzione di otta96; la scrivo ora e poi, per completezza, ricopio l'ultima parte.

Posto per comodità $f(1)=a+1$ (con $a in NN$ ed $a>=0$), si ha
$f(2)=f(2*1)=f(1)+1=a+2$
$f(4)=f(2*2)=f(2)+2=a+4 " "$ eccetera, calcolando $f(8),f(16)...$
quindi per le potenze di $2$ vale la formula $f(n)=a+n$, facilmente verificabile per induzione completa.
Indicando ora con $n_k, n_(k+1)$ due successive potenze di $2$, noto che fra $a+n_k$ ed $a+n_(k+1)$ ci sono tanti posti quanti fra $n_k$ ed $n_(k+1)$; poiché la funzione è strettamente crescente deve quindi essere $f(n)=a+n$ anche per i valori di $n$ che non sono potenze di $2$.
Copio l'ultima parte: finora ho usato solo la prima ipotesi, ora uso la seconda
$2$ e $3$ sono numeri primi, quindi devono essere primi anche $a+2$ ed $a+3$; trattandosi di due numeri consecutivi, uno di essi è pari, e quindi può essere primo solo se vale $2$. E' facile escludere che sia $a+3=2$, quindi resta solo $a+2=2->a=0$.