90. Quante potenze di 2! (Staffetta)
-
- Messaggi: 62
- Iscritto il: 22 nov 2010, 19:09
- Località: Sto ca... Stoccarda!
90. Quante potenze di 2! (Staffetta)
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}$.
Mostrare che $\forall n\ge 3\ \ 2^\frac {n^2}{4} < f(2^n) < 2^\frac {n^2}{2}$.
Re: 90. Quante potenze di 2! (Staffetta)
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$
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$
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Re: 90. Quante potenze di 2! (Staffetta)
@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.
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Re: 90. Quante potenze di 2! (Staffetta)
Come l'hai ottenuto?<enigma> ha scritto:@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.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Re: 90. Quante potenze di 2! (Staffetta)
Ultima modifica di <enigma> il 05 gen 2011, 22:24, modificato 1 volta in totale.
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Re: 90. Quante potenze di 2! (Staffetta)
Fallo per tutti... leva l'hint
Ultima modifica di dario2994 il 05 gen 2011, 22:28, modificato 1 volta in totale.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Re: 90. Quante potenze di 2! (Staffetta)
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?
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Re: 90. Quante potenze di 2! (Staffetta)
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
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
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Re: 90. Quante potenze di 2! (Staffetta)
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).
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Re: 90. Quante potenze di 2! (Staffetta)
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
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Re: 90. Quante potenze di 2! (Staffetta)
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}} $.
$ \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}} $.
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Re: 90. Quante potenze di 2! (Staffetta)
E' la prima cosa che ho pensato, ma di fatto non sono riuscito a cavarci niente..<enigma> ha scritto: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}} $.
Elenchiamo per iniziare i primi valori di $ f(n) $:Nabir Albar ha scritto: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}$.
$ 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?
The only goal of science is the honor of the human spirit.
Re: 90. Quante potenze di 2! (Staffetta)
Miseria, ci avevamo tanto discusso che avevo dimenticato che era ancora da risolvere
IMO '97
IMO '97
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Re: 90. Quante potenze di 2! (Staffetta)
Addirittura? A meno di una via più veloce, mi pareva abbastanza difficile da scrivere per bene in un'ora e mezza..<enigma> ha scritto:IMO '97
The only goal of science is the honor of the human spirit.