... ma neanche da sottovalutare, visto che in 4 ore e mezza non credo che l'avrei finito
(sì, ho dormito poco stanotte)
Ciònonostante la soluzione non è complicata, anzi, si arriva quasi ad una formula esplicita per n.
Cominciamo: fattorizzando n come $ ~ n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} $, osserviamo che per trovare un divisore di n, basta che scegliamo gli esponenti di ciascun primo che divide n, in modo tale che siano nonnegativi e minore dell'esponente che divide n. In poche parole:
$ ~ \tau(n) = (a_1+1)(a_2+1)\cdots (a_k+1) $
e anche:
$ ~ \tau(n^2) = (2a_1+1)(2a_2+1)\cdots (2a_k+1) $
Osserviamo che in queste formule abbiamo tenuto solo gli esponenti, e dimenticato che primi c'erano sotto. Infatti questi non centrano una cippa. Anzi, visto che i primi sono infiniti, per ogni k-upla $ ~ (a_i) $ possiamo trovare un n per cui $ ~ \tau(n) = (a_1+1)(a_2+1)\cdots (a_k+1) $.
Quindi il problema diventa: trovare tutti gli interi positivi m che si possono scrivere come:
$ \displaystyle m = \frac{(2a_1-1)(2a_2-1)\cdots (2a_n-1)}{a_1a_2\cdots a_n} $
per opportuni interi positivi $ ~n, a_1,\ldots,a_n $. (sì, ho sostituito $ ~ a_i+1 $ con $ ~ a_i $, ed ora ho il sospetto che questo mi abbia in fondo aggiunto difficoltà al problema, ma non posso più farne a meno).
Chiaramente il numeratore è dispari. Quindi gli $ ~ a_i $ sono tutti dispari, e anche m, proprio lui, è dispari. Il claim è: tutti gli m dispari si scrivono in questo modo.
Cominciamo con un lemmino. Detta $ ~ f(x) = 2x-1 $, allora $ ~ f^n(x) = 2^n(x-1) + 1 $, e detta $ ~ f^{-1}(x) = \frac{x+1}2 $, si ha $ ~ f^{-n}(x) = \frac{x-1}{2^n} + 1 $.
Diomostrazione: una volta azzeccate le formule giuste, l'induzione deve funzionare.
Ora siamo pronti per scrivere ogni m dispari. Il passo "furbo" è scrivere $ ~ m = 2^kd - 1 $, con d dispari. Ora, posto $ ~ r = d(2^k-1) $, calcoliamo quanto fa la frazione legale:
$ \displaystyle \frac{f(r)}{r} \cdot \frac{f^2(r)}{f(r)} \cdots \frac{f^k(r)}{f^{k-1}(r)} $.
Si semplifica di nuovo tutto, e basta calcolare $ ~ \frac{f^k(r)}{r} $, cioè, sviluppando r ed usando la formula, $ ~ \frac{2^k(2^kd - d -1) + 1}{d(2^k-1)} = \frac{2^kd(2^k-1) - (2^k-1)}{d(2^k-1)} $$ \displaystyle = \frac{2^kd-1}{d} = \frac{m}{d} $.
Quindi, per riuscire a fare $ ~ m = 2^kd-1 $ mi basta fare d. Ma anche d è dispari, e ovviamente $ ~ d < 2^kd -1 $, quindi il problema è risolto grazie all'induzione
(commento: questa soluzione era moltissimo "calata dall'alto", come ci sono arrivato è una storia molto lunga
)
