Rozkład na potęgi dwójki

Santiago A · Post autor: **Santiago A** » 19 sie 2016, o 16:29

Niech $\displaystyle{ f(n)}$ oznacza liczbę sposobów na które można zapisać liczbę jako sumę potęg 2, przy czym każda potęga może być użyta co najwyżej dwa razy. Na przykład $\displaystyle{ f(6) = 3}$, bo $\displaystyle{ 6=4+2=4+1+1=2+2+1+1}$. Co ciekawego można powiedzieć o ciągu

$\displaystyle{ a_n = \frac{f(n)}{f(n+1)}}$?

kropka+ · Post autor: **kropka+** » 24 sie 2016, o 11:14

Może chodzi o to, że

$\displaystyle{ \forall _{k \in N} \ a _{2 ^{k} }=1}$

Santiago A · Post autor: **Santiago A** » 24 sie 2016, o 12:06

Nie do końca. $\displaystyle{ f(8) = 4}$, $\displaystyle{ f(9) = 3}$.

kropka+ · Post autor: **kropka+** » 24 sie 2016, o 12:26

$\displaystyle{ 8=4+4=4+2+2=4+2+1+1}$ Jaka jest czwarta możliwość?

Santiago A · Post autor: **Santiago A** » 24 sie 2016, o 12:28

$\displaystyle{ 8 = 8}$

dec1 · Post autor: **dec1** » 24 sie 2016, o 12:29

A co powiecie na coś takiego:
$\displaystyle{ 8=4+2+1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\ldots}$

$\displaystyle{ 8=8}$ nie spełnia warunków zadania, bo $\displaystyle{ 0}$ nie jest potęgą dwójki, więc nie jest to suma

Santiago A · Post autor: **Santiago A** » 24 sie 2016, o 12:31

Standardowo definiuje się, że suma po pustym zbiorze indeksów to zero, nie widzę więc przyczyn, dla których mielibyśmy nie uznawać sumy po singletonie. Nie zaznaczyłem tego wcześniej, ale dopuszczam jedynie rozkłady na całkowite składniki.

kropka+ · Post autor: **kropka+** » 24 sie 2016, o 12:35

Dla mnie liczba nie jest sumą. Suma jest wynikiem dodawania, a tu trzeba by dodać zero, które nie jest potęgą dwójki.

dec1 · Post autor: **dec1** » 24 sie 2016, o 12:44

$\displaystyle{ \displaystyle\mathop{\mbox{\Large $\mathsurround0pt\forall$}}_{k\in\mathbb{N}_+} a_{2^k-2}=k}$

$\displaystyle{ \displaystyle\mathop{\mbox{\Large $\mathsurround0pt\forall$}}_{k\in\mathbb{N}_+} a_{2^k-1}=\frac1k}$

$\displaystyle{ \displaystyle\mathop{\mbox{\Large $\mathsurround0pt\forall$}}_{k\in\mathbb{N}_+} a_{2^k}=\frac{k}{k-1}}$

A co można powiedzieć o ciągach
$\displaystyle{ b_n=\frac{a_n}{a_{n+1}}=\frac{f(n)f(n+2)}{f^2(n+1)}}$,

$\displaystyle{ c_n=\frac{b_n}{b_{n+1}}=\frac{f(n)f^2(n+2)}{f^3(n+1)f(n+3)}}$,
... ?

arek1357 · Post autor: **arek1357** » 25 sie 2016, o 10:20

A dyskusje typu czy 8=8 jest przedstawione jako suma czy nie jest bezsensowna, bo to takie czcze
dywagacje dobre w klubie studenckim typu Żaczek zaraz po obiedzie.
Przychylam się tu do opinii Santiago że to też jest rozwiązanie jak najbardziej.

Przyszło mi coś innego do głowy ale to już jest raczej trafione mianowicie:

Zróbmy rozkłady poszczególnych liczb na potęgi dwójki, i jest tych samych potęg nie więcej niż dwie.

$\displaystyle{ 1=1 \\
f(1)=1}$

$\displaystyle{ 2=2 \\
2=1+1 \\
f(2)=2}$

$\displaystyle{ 3=2+1 \\
f(3)=1}$

$\displaystyle{ 4=2^2 \\
4=2+2 \\
4=2+1+1 \\
f(4)=3}$

$\displaystyle{ 5=2^2+1 \\
5=2+2+1 \\
f(5)=2}$

itd.....

niech $\displaystyle{ a}$ będzie liczbą naturalną, szukamy $\displaystyle{ f(a)}$

niech $\displaystyle{ k}$ będzie tają liczbą że: $\displaystyle{ 2^k \le a, 2^{k+1}>a}$

łatwo zauważyć, że szukamy liczby rozwiązań równania w naturalnych:

(1) $\displaystyle{ x_{0}+2^1x_{1}+2^2x_{2}+...+2^kx_{k}=a}$

ale muszą być założenia:

$\displaystyle{ 0 \le x_{i} \le 2}$, dla $\displaystyle{ i=0,1,2,...,k-1}$

natomiast:

$\displaystyle{ x_{k}=0,1}$

Wielomianem charakterystycznym tego równania jest:

$\displaystyle{ w(x)=(1+x+x^{2^1})(1+x^{2^1}+x^{2^2})(1+x^{2^2}+x^{2^3})...(1+x^{2^k})}$

współczynnik przy $\displaystyle{ x^a}$ określa ilość rozwiązań równania (1)

Przykład znajdźmy$\displaystyle{ f(10), a=10}$

$\displaystyle{ k=3}$

równanie:

$\displaystyle{ x_{0}+2x_{1}+4x_{2}+8x_{3}=10}$

wielomian charakterystyczny:

$\displaystyle{ w(x)=(1+x+x^2)(1+x^2+x^4)(1+x^4+x^8)(1+x^8)}$

lub:

$\displaystyle{ w(x) = x^{22}+x^{21}+2 x^{20}+x^{19}+3 x^{18}+2 x^{17}+3 x^{16}+x^{15}+4 x^{14}+3 x^{13}+5 x^{12}+2 x^{11}+5 x^{10}+3 x^9+4 x^8+x^7+3 x^6+2 x^5+3
x^4+x^3+2 x^2+x+1}$

Odczytujemy, że:

$\displaystyle{ f(10)=5}$ co się zgadza z doświadczeniem bo:

$\displaystyle{ 10=2^3+2}$

$\displaystyle{ 10=2^3+1+1}$

$\displaystyle{ 10=2^2+2^2+2}$

$\displaystyle{ 10=2^2+2^2+1+1}$

$\displaystyle{ 10=2^2+2+2+1+1}$

Oczywiście w tym wielomianie charakterystycznym możemy znaleźć wszystkie rozwiązania

od $\displaystyle{ f(8)}$ do $\displaystyle{ f(15)}$ bo tylko dla nich $\displaystyle{ k=3}$,

i jak widać też zgadza się z doświadczeniem.

Pokazałem jak łatwo się szuka $\displaystyle{ f(a)}$

Wzór jawny pewnie by wyglądał bardzo brzydko bo jak widać mamy tu do czynienia z partycjami liczby $\displaystyle{ a}$ do tego z ograniczeniami.

Łatwo zauważyć, że zadanie opiera się na trójkowym zapisie liczby...

A co do ciągu $\displaystyle{ a_{n}}$ mogę powiedzieć, że jest on ilorazem kolejnych współczynników wielomianu charakterystycznego jak widać nic mądrzejszego nie powiem...