OliForum Matematico

Trovare tutti i valori di $k$ intero tale che esiste almeno un intero positivo $n$ che verifica
\[ k=\frac{\sigma_0(n^2)}{\sigma_0(n)}\]

Ps. $\sigma_0(m)$ rappresenta il numero di divisori positivi di $m$

Sicuramente $k$ dispari, dato che $\sigma_0(n^2)$ è dispari.
Sia $f(n)=\frac{2n-1}{n}$.
Siano $a_1,a_2,\dots a_m$ gli esponenti nella fattorizzazione di $n$. Allora vale:
$ \displaystyle \frac{\sigma_0(n^2)}{\sigma_0(n)}=\prod_{i=1}^mf(a_i+1) $ (1)
Sia $I$ l'insieme dei $k\in\mathbb{Q}$ che si possono ottenere. Dimostrerò che $I\cap \mathbb{N}$ sono tutti i dispari.
Per la (1) è ovvio che $a,b\in I$ implica $ab\in I$. (2)
Dimostrerò per induzione forte su $n$ dispari che $n\in I$:

• Passo base: Facilmente $1\in I$.
• Passo induttivo (ottengo $n$ dispari): Sia $m=\upsilon_2(n+1)-1$. Sia $d=n+2-\frac{n+1}{2^m}$. Infine definisco $a_i=2^id-(2^i-1)$.
  Per le definizioni vale $\frac{n+1}{2^m}\equiv 2\pmod 4$ da cui ottengo $d\equiv n\pmod 4 \Rightarrow dn+1\equiv 2\pmod 4$.
  Facendo 2 conti si ottiene $a_m=(2^m-1)n+2^m$, inoltre per definizione vale anche $2^md\equiv 2^m-1\pmod{a_m}$. Quindi:
  $ a_m|dn+1\iff a_m|2^mdn+2^m \iff a_m|(2^m-1)n+2^m $
  E l'ultima è vera perchè vale l'identità mostrata prima, quindi $a_m|dn+1$.
  Infine $a_m\ge d$ da cui $\frac{dn+1}{2a_m}\le \frac{dn+d}{2d}\le \frac{n+1}{2}<n$.
  Quindi detto $x=\frac{dn+1}{2a_m}$ i risultati ottenuti finora dicono che è un intero dispari $<n$, allora per ipotesi induttiva $x\in I$.
  Inoltre facendo il conto vale:
  $ \displaystyle\frac nx=f\left(\frac{dn+1}2\right)\cdot f(a_{m-1}) \cdot f(a_{m-2})\cdots f(a_0)\in I $
  E perciò $x,\frac nx \in I$ e applicando la (2) ho $n\in I$ che è la tesi d'induzione.

La dimostrazione è scritta in maniera particolarmente involuta quindi aggiungo qui l'idea: io cerco un $d$ per cui ho $dn$ al numeratore e $d$ al denominatore così si semplifica; poi faccio la catena $f(a_{m-1}) \cdot f(a_{m-2})\cdots f(a_0)$ in cui tutto si semplifica tranne un $a_m$ che allora impongo divida in denominatore di $dn$... e poi sono conti attenti e fortunati.
Un bel problema

Perfetto; l'idea della costruzione induttivamente e' giusta, e credo sia anche l'unica possibile, o almeno, la piu' immediata..

Questo è il problema più figo del mondo.