OliForum Matematico

Un numero con $2^n$ divisori ha una rappresentazione in fattori primi della forma $\displaystyle p_1^{2^{\alpha_1}-1}p_2^{2^{\alpha_2}-1}\cdots p_i^{2^{\alpha_i}-1}$. Ogni $p^k$ può essere scritto univocamente come prodotto di fattori di tipo $ \displaystyle\beta_p^i=p^{2^i}$ tramite la rappresentazione binaria di $k$. Un numero con esattamente $2^n$ divisori è biunivocamente rappresentato dal prodotto di $n$ fattori $\beta_p^i$, alla condizione di non fare salti, ossia che se il fattore $\beta_p^i$ compare, allora compaiono tutti i $\beta_p^{j<i}$ (questo equivale al fatto che $2^{\alpha_i}-1 = \overbrace{111\cdots1}^{\alpha_i}$ in binario e $n=\sum\alpha_i$).

Se chiamiamo $q_n$ l'enumerazione che ordina naturalmente i $\beta_p^i$ (in teoria dovremmo giustificare l'esistenza di tale enumerazione ma si costruisce facilmente) vale quindi $f(2^k)=\prod_1^kq_i$, da qui segue $f(2^k)\mid f(2^{k+1})$.
Notare che il prodotto rispetta la condizione di non fare salti poiche i $\beta_p^i$ per un stesso $p$ sono ordinati rispetto ad $i$, e che l'espressione consente di costruire i $f(2^k)$.