90. Quante potenze di 2! (Staffetta)

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Nabir Albar
Messaggi: 62
Iscritto il: 22 nov 2010, 19:09
Località: Sto ca... Stoccarda!

90. Quante potenze di 2! (Staffetta)

Messaggio da Nabir Albar » 05 gen 2011, 00:31

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
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: 90. Quante potenze di 2! (Staffetta)

Messaggio da dario2994 » 05 gen 2011, 20:37

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 :roll: )

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

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: 90. Quante potenze di 2! (Staffetta)

Messaggio da <enigma> » 05 gen 2011, 21:55

@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.)

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: 90. Quante potenze di 2! (Staffetta)

Messaggio da dario2994 » 05 gen 2011, 22:09

<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.
Come l'hai ottenuto?
...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

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: 90. Quante potenze di 2! (Staffetta)

Messaggio da <enigma> » 05 gen 2011, 22:22

Vedi qui e qui. Quella riguardante il problema è, in particolare, questa.
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.)

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: 90. Quante potenze di 2! (Staffetta)

Messaggio da dario2994 » 05 gen 2011, 22:23

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

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: 90. Quante potenze di 2! (Staffetta)

Messaggio da <enigma> » 05 gen 2011, 22:26

Fatto (bisognerebbe toglierlo anche dal quote, però :P ), 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.)

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: 90. Quante potenze di 2! (Staffetta)

Messaggio da dario2994 » 05 gen 2011, 22:35

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 :o )
Il problema è che dalla formula che hai piazzato non riesco neppure a capire quanto vale $\alpha$ :lol: :lol:
Bon comunque sapere che non è una congettura aperta fa sempre piacere :roll: :D
...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

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: 90. Quante potenze di 2! (Staffetta)

Messaggio da <enigma> » 05 gen 2011, 22:40

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.)

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: 90. Quante potenze di 2! (Staffetta)

Messaggio da <enigma> » 05 gen 2011, 23:12

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 :x
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: 90. Quante potenze di 2! (Staffetta)

Messaggio da <enigma> » 06 gen 2011, 15:50

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}} $. :wink:
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 90. Quante potenze di 2! (Staffetta)

Messaggio da jordan » 26 feb 2011, 17:39

<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}} $. :wink:
E' la prima cosa che ho pensato, ma di fatto non sono riuscito a cavarci niente..
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}$.
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?
The only goal of science is the honor of the human spirit.

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: 90. Quante potenze di 2! (Staffetta)

Messaggio da <enigma> » 26 feb 2011, 18:34

Miseria, ci avevamo tanto discusso che avevo dimenticato che era ancora da risolvere :shock:
IMO '97 :wink:
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 90. Quante potenze di 2! (Staffetta)

Messaggio da jordan » 26 feb 2011, 18:36

<enigma> ha scritto:IMO '97 :wink:
Addirittura? :? A meno di una via più veloce, mi pareva abbastanza difficile da scrivere per bene in un'ora e mezza..
The only goal of science is the honor of the human spirit.

Rispondi