Witam!
Zamieściłem już post w dziale informatyka, ale pomyślałem że może ktoś z matematyków pomoże mi a i dzial bardziej odpowiedni
Mianowicie chciałbym policzyć pierwszą cyfrę liczby n! (bez liczenia silni i dochodzenia co jest pierwszą cyfrą). Czy jest jakiś sprytny sposób pozwalający policzyć tę pierwszą cyfrę?
Pierwsza cyfra n!
-
Przemas O'Black
- Użytkownik
- Posty: 744
- Rejestracja: 7 lut 2009, o 18:30
- Płeć: Mężczyzna
- Podziękował: 69 razy
- Pomógł: 58 razy
-
Sylwek
- Użytkownik
- Posty: 2716
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 160 razy
- Pomógł: 657 razy
Pierwsza cyfra n!
Jako że mam chwilę czasu, to rozwinę poprzednią myśl.
Dobierzmy takie \(\displaystyle{ k \in \mathbb{Z}}\) i \(\displaystyle{ \alpha \in \langle 0,1 )}\), żeby: \(\displaystyle{ \sum_{i=1}^n \log_{10} (i) = k+\alpha}\) - oczywiście istnieją, gdyż te składniki to odpowiednio część całkowita i część ułamkowa tej długiej sumy. Przyda nam się też, że wówczas: \(\displaystyle{ 1 \le 10^{\alpha}<10}\), czyli w zapisie dziesiętnym: \(\displaystyle{ 10^{\alpha}=\overline{a_0,a_1a_2\ldots}}\)
Wróćmy do problemu:
\(\displaystyle{ n! = 10^{ \log_{10} (n!) } = 10^{ \sum_{i=1}^n \log_{10} (i)}=10^{k+\alpha}=10^k \cdot 10^{\alpha} = \\ = 1 \underbrace{00 \ldots 0}_{k} \cdot \overline{a_0,a_1a_2\ldots} = \overline{a_0a_1a_2\ldots}}\)
Zatem pierwszą cyfrą \(\displaystyle{ n!}\) w zapisie dziesiętnym jest \(\displaystyle{ a_0}\), małe przypadki (tzn. \(\displaystyle{ n!<10}\) do zapamiętania oddzielnie w programie ). Jak widać ten sposób działa też dla wyznaczania kolejnych cyfr \(\displaystyle{ n!}\).
Wszystko łatwe do zaimplementowania i algorytm pracuje w O(n). Własność równości logarytmu iloczynu z sumą logarytmów upewnia nas, że nie pojawią się zaskakująco wielkie liczby. Teraz wystarczy z tej sumy wyciągnąć część ułamkową \(\displaystyle{ \alpha}\), obliczyć \(\displaystyle{ 10^{\alpha}}\) i z tej liczby wyciągnąć z tego część całkowitą \(\displaystyle{ a_0}\)
Dobierzmy takie \(\displaystyle{ k \in \mathbb{Z}}\) i \(\displaystyle{ \alpha \in \langle 0,1 )}\), żeby: \(\displaystyle{ \sum_{i=1}^n \log_{10} (i) = k+\alpha}\) - oczywiście istnieją, gdyż te składniki to odpowiednio część całkowita i część ułamkowa tej długiej sumy. Przyda nam się też, że wówczas: \(\displaystyle{ 1 \le 10^{\alpha}<10}\), czyli w zapisie dziesiętnym: \(\displaystyle{ 10^{\alpha}=\overline{a_0,a_1a_2\ldots}}\)
Wróćmy do problemu:
\(\displaystyle{ n! = 10^{ \log_{10} (n!) } = 10^{ \sum_{i=1}^n \log_{10} (i)}=10^{k+\alpha}=10^k \cdot 10^{\alpha} = \\ = 1 \underbrace{00 \ldots 0}_{k} \cdot \overline{a_0,a_1a_2\ldots} = \overline{a_0a_1a_2\ldots}}\)
Zatem pierwszą cyfrą \(\displaystyle{ n!}\) w zapisie dziesiętnym jest \(\displaystyle{ a_0}\), małe przypadki (tzn. \(\displaystyle{ n!<10}\) do zapamiętania oddzielnie w programie ). Jak widać ten sposób działa też dla wyznaczania kolejnych cyfr \(\displaystyle{ n!}\).
Wszystko łatwe do zaimplementowania i algorytm pracuje w O(n). Własność równości logarytmu iloczynu z sumą logarytmów upewnia nas, że nie pojawią się zaskakująco wielkie liczby. Teraz wystarczy z tej sumy wyciągnąć część ułamkową \(\displaystyle{ \alpha}\), obliczyć \(\displaystyle{ 10^{\alpha}}\) i z tej liczby wyciągnąć z tego część całkowitą \(\displaystyle{ a_0}\)