90. Quante potenze di 2! (Staffetta)

[Nabir Albar]

Per ogni intero positivo $n$, sia $f(n)$ il numero di modi di rappresentarlo come somma di potenze di 2 con esponente naturale. Rappresentazioni che differiscono solo per l'ordine degli addendi sono considerate uguali. Per chiarire $f(4)=4$, essendo $4=2^2,2+2,2+1+1,1+1+1+1$.
Mostrare che $\forall n\ge 3\ \ 2^\frac {n^2}{4} < f(2^n) < 2^\frac {n^2}{2}$.

[dario2994]

Qualcuno riesce a trovare una formula asintotica per $f(n)$ ? (non ho una soluzione, ma mi sembra carina come domanda da porsi... ) (ovviamente non è da considerarsi il problema della staffetta )

In particolare mi chiedo se esista un $\alpha$ tale che $f(n)$ è asintotica a $2^{\alpha\cdot \log_2(n)^2}$...

edit: bon... ho fatto qualche prova col pc... sono andato abbastanza in "là" e sto $\alpha$ continua a crescere... finora posso dire che dovrebbe essere $>0.36$
edit2: andando oltre ottengo anche $>0.37$

[<enigma>]

@dario2994: appurato che $ f(2n)=f(2n+1) $, allora $ \log (f(2n))=\frac 1 {2 \log 2} \left ( \log \frac {n} {\log n} \right ) ^2+\left (\frac 1 2+\frac 1 {\log 2}+\frac {\log \log 2} {\log 2}\right ) \log n-\left ( 1+\frac {\log \log 2} {\log 2} \right ) \log \log n+\Phi \left ( \frac 1 {\log 2} \log \frac n {\log n} \right ) $, dove $ \Phi $ è una certa funzione periodica di periodo 1 e valore assoluto piccolo.

[dario2994]

@dario2994: appurato che $ f(2n)=f(2n+1) $, allora $ \log (f(2n))=\frac 1 {2 \log 2} \left ( \log \frac {n} {\log n} \right ) ^2+\left (\frac 1 2+\frac 1 {\log 2}+\frac {\log \log 2} {\log 2}\right ) \log n-\left ( 1+\frac {\log \log 2} {\log 2} \right ) \log \log n+\Phi \left ( \frac 1 {\log 2} \log \frac n {\log n} \right ) $, dove $ \Phi $ è una certa funzione periodica di periodo 1 e valore assoluto piccolo.

Come l'hai ottenuto?

[<enigma>]

Vedi qui e qui. Quella riguardante il problema è, in particolare, questa.

[dario2994]

Fallo per tutti... leva l'hint

[<enigma>]

Fatto (bisognerebbe toglierlo anche dal quote, però ), anche se penso che la difficoltà non sia tanto trovare la relazione quanto darne una stima asintotica. I link rispondono alla tua domanda?

[dario2994]

Uhm sisi (pure troppo) ma volevo una dimostrazione (tra l'altro quel risultato non ho capito bene di chi è... ma pare che ad averlo scritto su OEIS è stato flajolet )
Il problema è che dalla formula che hai piazzato non riesco neppure a capire quanto vale $\alpha$
Bon comunque sapere che non è una congettura aperta fa sempre piacere

[<enigma>]

Il lato curioso è che il problema è stato risolto solo nel 2008, anche se versioni meno precise si conoscevano già in precedenza. L'articolo mi sembra che sia di de Bruijn, ora cerco un po' su internet (anche se trovare articoli gratis è sempre un calvario perché c'è arXiv e poco altro).

[<enigma>]

Mi pare che $ \displaystyle \alpha \rightarrow \frac 1 2 $ per $ n \rightarrow \infty $, e dunque $ \displaystyle \alpha = \frac 1 2 $. Domani ci ripenso perché ora mi serve qualche ora di sonno

[<enigma>]

Ecco la derivazione che ho fatto. Prendendo per buona la formula asintotica citata prima (di cui prima o poi troverò la dimostrazione da qualche parte! ), possiamo scrivere (le uguaglianze sono da ritenersi approssimate e valide solo asintoticamente), fermandoci all'ordine di magnitudine $ (\log n )^2 $,
$ \displaystyle e^{\frac 1 {2 \log 2} (\log n)^2}=2^{\alpha \frac {(\log n)^2} {(\log 2)^2}} $
$ \displaystyle e^{\frac 1 {2 \log 2} (\log n)^2}=e^{\alpha \log 2 \frac {(\log n)^2} {(\log 2)^2}} $
$ \displaystyle \frac 1 {2 \log 2}=\alpha \frac 1 {\log 2} $
$ \displaystyle \alpha=\frac 1 2 $.

E' più illuminante troncare la formula al termine $ \log n \log \log n $ (poi si può fare anche con termini più piccoli dell'espansione ma son conti in più):
$ \displaystyle e^{\frac 1 {2 \log 2} (\log n)^2}=2^{\alpha \frac {(\log n)^2} {(\log 2)^2}} $ (ricordando che $ \displaystyle \left (\log \frac n {\log n} \right )^2=\log n -2 \log n \log \log n $ se togliamo il termine in $ \displaystyle (\log \log n)^2 $che non c'interessa)
da cui $ \displaystyle \alpha=\frac 1 2 \frac {\log n-2 \log \log n} {\log n} $. Questo spiega perché hai ottenuto un valore così piccolo per $ \alpha $ provando col computer: il secondo fattore tende a 1 abbastanza lentamente.

Ciò mostra, tra l'altro, che l'upper bound del problema è ottimale.

PS. A te che piacciono queste cose: $ \displaystyle F(x):=\sum _{n \in \mathbb N} f(n) x^n=\prod _{n \in \mathbb N} \frac 1 {1-x^{2^n}} $.

[jordan]

PS. A te che piacciono queste cose: $ \displaystyle F(x):=\sum _{n \in \mathbb N} f(n) x^n=\prod _{n \in \mathbb N} \frac 1 {1-x^{2^n}} $.

E' la prima cosa che ho pensato, ma di fatto non sono riuscito a cavarci niente..

Per ogni intero positivo $n$, sia $f(n)$ il numero di modi di rappresentarlo come somma di potenze di 2 con esponente naturale. Rappresentazioni che differiscono solo per l'ordine degli addendi sono considerate uguali. Per chiarire $f(4)=4$, essendo $4=2^2,2+2,2+1+1,1+1+1+1$.
Mostrare che $\forall n\ge 3\ \ 2^\frac {n^2}{4} < f(2^n) < 2^\frac {n^2}{2}$.

Elenchiamo per iniziare i primi valori di $ f(n) $:
$ f(1)=1 $
$ f(2)=f(3)=2 $
$ f(4)=f(5)=4 $
$ f(6)=f(7)=6 $
$ f(8)=f(9)=10 $...
E' immediato vedere che la funzione è crescente, e che:
- se $ n $ è dispari allora $ f(n)=f(n-1) $,poichè nella sua rappresentazione dovrà obbligatoriamente comparire almeno un 1;
- se $ n $ è pari allora $ \displaystyle f(n)=f(n-1)+f\left(\frac{n}{2}\right) $, data dalla somma del numero di combinazioni in cui compare almeno un 1 e da quelle in cui tutti i numeri della rappresentazione valgono almeno 2.

Da quanto detto possiamo quindi dedurre che:
$ \displaystyle f(2^{n+1})=f(2^{n+1}-1)+f(2^n)=f(2^{n+1}-2)+f(2^n)=f(2^{n+1}-3)+f(2^n-1)+f(2^n)=\ldots $ $ \displaystyle =\sum_{1\le i\le 2^n}{ f(i) } $.
In particolare:
$ f(16)=f(8)+2f(6)+2f(4)+2f(2)+f(1)=35 $
$ \displaystyle 2^{\frac{3^2}{4}}<f(2^3)=10<2^{\frac{3^2}{2}} $
$ \displaystyle 2^{\frac{4^2}{4}}<f(2^4)=35<2^{\frac{4^2}{2}} $
Dobbiamo quindi verificare la tesi per ogni $ n\ge 5 $:

1. Upper bound

Supponiamo che la tesi sia verificata per $ f(2^3), f(2^4), \ldots, f(2^n) $. Definiamo $ e(\cdot):\mathbb{Z}\to \{0,1\} $ tale che:
- $ e(x)=1 $ se $ x $ è dispari;
- $ e(x)=0 $ se $ x $ è pari.
Allora $ \displaystyle f(2^{n+1})=\sum_{1\le i\le 2^n}{ f(i) } < \sum_{1\le i\le 8}{ f(i) } +\sum_{4\le j\le n}{ f(2^j) 2^{j-1}}= $
$ \displaystyle =f(2^4)+\sum_{4\le j\le n}{ f(2^j) 2^{j-1}}< $
$ \displaystyle < 2^0+2^1+2^2+2^3+2^4+2^5+\sum_{4\le j\le n}{2^{\frac{(j+1)^2-3}{2}} }< $
$ \displaystyle < 2^0+2^1+2^2+2^3+2^4+2^5+\sum_{4\le j\le n}{2^{\frac{(j+1)^2-3+e(j)}{2}} }< $
$ \displaystyle <2^{\frac{(n+1)^2}{2}} $.
Infatti dati interi non negativi $ a_0<a_1<\ldots <a_k $ risulta sempre verificata $ \displaystyle \sum_{1\le i\le k}{2^{a_i}}\le 2^{a_k+1}-1<2^{a_k+1} $.


2. Lower bound

Supponiamo anche qui che la tesi sia verificata per $ f(2^3), f(2^4), f(2^5), \ldots, f(2^n) $. E osserviamo che per ogni intero $ k>0 $ vale la disuguaglianza:
$ f(2^n+2k)\ge f(2^n)+kf(2^{n-1}) $.
Per $ k=1 $ infatti otteniamo un'identità, e supposta che sia vera per un generico $ k>0 $ allora:
$ f(2^n+2k+2)=f(2^n+2k)+f(2^{n-1}+k+1) \ge f(2^n+2k)+f(2^{n-1}) \ge f(2^n)+(k+1)f(2^{n-1}) $.
Tornando alla tesi originale, abbiamo che:
$ \displaystyle f(2^{n+1})= \sum_{1\le i\le 2^n}{f(i)} > \sum_{2^{n-2}\le i\le 2^n}{ f(i) }= $
$ \displaystyle =f(2^n)+[f(2^n-1)+f(2^n-2)+\ldots+f(2^{n-1})]+[f(2^{n-1}-1)+f(2^{n-1}-2)+\ldots+f(2^{n-2})]> $
$ \displaystyle >f(2^n)+[2^{n-1}f(2^{n-1})+2f(2^{n-2})\sum_{1\le i\le 2^{n-2}-1}{i}]+2^{n-2}f(2^{n-2})> $
$ \displaystyle > 2^{\frac{n^2}{4}}+[2^{\frac{n^2+2n-3}{4}}+2^{n-2}(2^{n-2}-1)2^{\frac{(n-2)^2}{4}}]+2^{n-2}2^{\frac{(n-2)^2}{4}} $
$ \displaystyle > 2^{\frac{n^2}{4}}+2^{\frac{n^2+2n-3}{4}}+2^{\frac{n^2+4n-12}{4}}-2^{n-2}2^{\frac{(n-2)^2}{4}}+2^{n-2}2^{\frac{(n-2)^2}{4}}= $
$ \displaystyle = 2^{\frac{n^2}{4}}+2^{\frac{n^2+2n-3}{4}}+2^{\frac{n^2+4n-12}{4}}> $
$ \displaystyle >2^{\frac{(n+1)^2}{4}} $. []

Ps. Dove l'hai preso?

[<enigma>]

Miseria, ci avevamo tanto discusso che avevo dimenticato che era ancora da risolvere
IMO '97

[jordan]

IMO '97

Addirittura? A meno di una via più veloce, mi pareva abbastanza difficile da scrivere per bene in un'ora e mezza..