Długość ciągu kolejnych liczb naturalnych

[vpprof]

Mam niby prosty problem, chcę znaleźć wzór jawny, w postaci zwartej na długość takiego ciągu:

Kod: Zaznacz cały

122333444455555...10101010101010101010...

dochodzącego do danej liczby naturalnej \(\displaystyle{ n}\). Np. jeśli \(\displaystyle{ n=100}\) to ciąg zakończy się na stu powtórzeniach liczby \(\displaystyle{ 100}\).

Problem sprawia mi to, że liczby mają coraz większą ilość cyfr. Ktoś ma pomysł?

[kerajs]

Pomysł:
\(\displaystyle{ d(n)=(\lfloor \log n \rfloor +1) \cdot \frac{n(n+1)}{2} - \sum_{k=0}^{\lfloor \log n \rfloor } \frac{10^k(10^k-1)}{2} }\)

[JakimPL]

Zanim zaczniemy od podanego ciągu, rozważmy prostszy, pomocniczy ciąg \(\displaystyle{ (b_n)_{n\in\mathbb{N}}}\):
\(\displaystyle{ \begin{array}{rcl}b_1 &=& 1 \\ b_2 &=& 22 \\ b_3 &=& 333 \\ \vdots \\ b_9 &=& 999 999 999 \\ b_{10} &=& 10101010101010101010 \\ \vdots \\b_{99} &=& \underbrace{99\ldots 9999}_{2\cdot 99 \text{ cyfr }} \\ b_{100} &=& \underbrace{100100\ldots100}_{3 \cdot 100 \text{ cyfr}}\end{array}}\)

Widać, że ciąg gwałtownie zwiększa liczbę cyfr, gdy \(\displaystyle{ n}\) też zwiększa swoją liczbę cyfr. Niech \(\displaystyle{ s(n)}\) określa liczbę cyfr \(\displaystyle{ n}\). Można wyrazić to "jawnie" jako \(\displaystyle{ s(n)=\left\lceil \log_{10} n \right\rceil + 1}\). Zatem liczba cyfr \(\displaystyle{ b_n}\) wynosi \(\displaystyle{ n\cdot s(n) = n \left(\left\lceil \log_{10} n \right\rceil + 1\right)}\). Dla \(\displaystyle{ n}\) naturalnych mniejszych od \(\displaystyle{ 10}\) zachodzi:

\(\displaystyle{ b_n = \underbrace{nn\ldots n}_{n\text{ cyfr}} = n \cdot \underbrace{11\ldots 1}_{n\text{ cyfr}}}\)

Jak zapisać inaczej liczbę złożoną z \(\displaystyle{ n}\) jedynek? Możemy zapisać to jako:

\(\displaystyle{ 11\ldots 1.(1) - 0.(1) = \frac{10^n}{9} - \frac{1}{9} = \frac{10^n - 1}{9}}\)

Stąd \(\displaystyle{ b_n = n \cdot \underbrace{11\ldots 1}_{n\text{ cyfr}} = n \frac{10^n - 1}{9}}\)

Podobnie, dla \(\displaystyle{ 10 \leqslant n \leqslant 99}\) (gdzie \(\displaystyle{ s(n) = 2}\)):
\(\displaystyle{ b_n = \underbrace{nn\ldots n}_{2n\text{ cyfr}} = n \cdot \underbrace{1010\ldots 10}_{2n\text{ cyfr}} = n\frac{10^{2n} - 1}{99}=n\frac{10^{2n} - 1}{10^2 - 1}}\)

Ogólnie:

\(\displaystyle{ b_n = n \frac{10^{s(b_n)} - 1}{10^{s(n)} - 1} = n\frac{10^{n\left(\left\lceil \log_{10} n \right\rceil + 1\right)} - 1}{10^{\left\lceil \log_{10} n \right\rceil + 1} - 1}}\)

Do określenia długości liczby wystarczy nam zsumować \(\displaystyle{ s(b_n)}\). Jeżeli się nie pomyliłem, powinien się zgadzać z wynikiem kerajsa.

[vpprof]

kerajs
Dzięki, jednak szukam postaci zwartej, czyli bez sum. Bo jeśli pozwolimy sobie na sumy, to rozwiązanie jest oczywiste: zsumować od \(\displaystyle{ k=1}\) do \(\displaystyle{ k=n}\) liczbę cyfr \(\displaystyle{ k}\) pomnożoną przez \(\displaystyle{ k}\).

\(\displaystyle{ \sum_{k=1}^{n} \left( \left\lfloor \log k \right\rfloor +1 \right) k}\)

Oczywiste, ale wymagające wielu kroków.

JakimPL, dużo dobrych pomysłów, ale mam wrażenie, że Twój pomocniczy ciąg to jest droga naokoło. Wychodzi Ci wzór z potęgami, które i tak trzeba zlogarytmować, żeby obliczyć liczbę cyfr.

Drobna sprawa:

Zatem liczba cyfr \(\displaystyle{ b_n}\) wynosi \(\displaystyle{ n\cdot s(n) = n \left(\left\lceil \log_{10} n \right\rceil + 1\right)}\).

Chodzi oczywiście o \(\displaystyle{ n\cdot s(n) = n \left( \red{ \left\lfloor \log_{10} n \right\rfloor } + 1\right)}\).

Podobnie, dla \(\displaystyle{ 10 \leqslant n \leqslant 99}\) (gdzie \(\displaystyle{ s(n) = 2}\)):
\(\displaystyle{ b_n = \underbrace{nn\ldots n}_{2n\text{ cyfr}} = n \cdot \underbrace{1010\ldots 10}_{2n\text{ cyfr}} = n\frac{10^{2n} - 1}{99}=n\frac{10^{2n} - 1}{10^2 - 1}}\)

\(\displaystyle{ b_n = \underbrace{nn\ldots n}_{2n\text{ cyfr}} = n \cdot \underbrace{\red{0101\ldots 01}}_{2n\text{ cyfr}} }\) wszak jeśli chcemy uzyskać np. \(\displaystyle{ 22}\), to mnożymy \(\displaystyle{ 22 \cdot 01}\) a nie razy dziesięć.

Ogólnie:

\(\displaystyle{ b_n = n \frac{10^{s(b_n)} - 1}{10^{s(n)} - 1} = n\frac{10^{n\left(\left\lceil \log_{10} n \right\rceil + 1\right)} - 1}{10^{\left\lceil \log_{10} n \right\rceil + 1} - 1}}\)

Do określenia długości liczby wystarczy nam zsumować \(\displaystyle{ s(b_n)}\).

No właśnie, a \(\displaystyle{ s()}\) usuwa te dziesiątki z powrotem.

[kerajs]

kerajs
Dzięki, jednak szukam postaci zwartej, czyli bez sum. Bo jeśli pozwolimy sobie na sumy, to rozwiązanie jest oczywiste: zsumować od \(\displaystyle{ k=1}\) do \(\displaystyle{ k=n}\) liczbę cyfr \(\displaystyle{ k}\) pomnożoną przez \(\displaystyle{ k}\).

\(\displaystyle{ \sum_{k=1}^{n} \left( \left\lfloor \log k \right\rfloor +1 \right) k}\)

Oczywiste, ale wymagające wielu kroków.

Twój wymaga wielu kroków, ale mój tylko kilku.
Przykłady:
Ilość twoich postów to 459
\(\displaystyle{ d(459)=3 \cdot \frac{459 \cdot 460}{2} -(0+ \frac{10 \cdot 9}{2}+\frac{100 \cdot 99}{2} )}\)
Ilość moich postów to 7527
\(\displaystyle{ d(7527)=4 \cdot \frac{7527\cdot 7528}{2} -(0+ \frac{10 \cdot 9}{2}+\frac{100 \cdot 99}{2}+\frac{1000 \cdot 999}{2} )}\)
Policzenie tego pisemnie jest szybkie, a jak się ma kalkulator to błyskawiczne.

Ale to tylko chybiony pomysł. Jak znajdziesz postać bez sum, to ją tutaj zamieść, proszę.

[Gosda]

\(\displaystyle{ \sum_{k=0}^{m} 10^k (10^k - 1) = \frac {10}{99} (10^{2m+1} - 11 \cdot 10^m + 1 }\),

zatem dla \(m = \lfloor \log n \rfloor\) mamy chyba rozwiązanie bez sumy?

[arek1357]

Widzę możliwość skrócenie tej sumy , wystarczy zacząć od \(\displaystyle{ k=1}\) a nie od \(\displaystyle{ k=0}\)

To już jest jakiś pomysł...

[kerajs]

Widzę możliwość skrócenie tej sumy , wystarczy zacząć od \(\displaystyle{ k=1}\) a nie od \(\displaystyle{ k=0}\)

To już jest jakiś pomysł...

Wiem, że liczenie od k=0 jest trochę sztuczne, skoro i tak daje składnik sumy równy zero , jednak wprowadziłem je specjalnie aby uniknąć dziwacznego sumowania \(\displaystyle{ \sum_{k=1}^{0} .......}\) dla \(\displaystyle{ n<10}\)

\(\displaystyle{ \sum_{k=0}^{m} 10^k (10^k - 1) = \frac {10}{99} (10^{2m+1} - 11 \cdot 10^m + 1) }\),

Touché!

[vpprof]

kerajs, nie doceniłem Twojego pomysłu. Jak widzę, polega na obliczaniu sum kolejnych liczb naturalnych, które wyrażają się prostym wzorem \(\displaystyle{ (n^2+n)/2}\) o ile zaczynają się od jedynki. Więc wymyśliłeś żeby policzyć wszystkie liczby tak, jak gdyby miały tyle cyfr co \(\displaystyle{ n}\), a potem odejmować wkłady kolejnych nadmiarowych, nieistniejących cyfr. Przykładowo dla \(\displaystyle{ n=1000}\) liczymy sumę liczb do tysiąca i mnożymy przez cztery, potem odejmujemy wkład w sumę od czwartej cyfry dla wszystkich liczb mniejszych niż czterocyfrowe, potem odejmujemy wkład od trzeciej cyfry dla wszystkich liczb mniejszych niż trzycyfrowe itd. — Świetne! I rzeczywiście rozwiązując to za pomocą np. funkcji tworzących uzyskuje się postać podaną przez Gosda. Dziękuję!