有沒有自然數 n，使得 n! 的前四個數字是 2020？

SarvaTathagata2021-02-05 21:41:36

其實只要把滿足

$2020\le 10^{3+\left\{\sum\limits_{i=1}^{n}\log_{10}{i}\right\}}\lt 2021$

的所有

找到就行了，所以不需要大整數運算即可在很快的時間內得出

之內滿足要求的數恰好有

個。

另外，我們可以把

的十進位制表示看成一個各位均為隨機的數（但是這一點未經證明），所以根據著名的本福特定律，滿足條件的數在全體自然數中所佔比例並不是

$\dfrac{1}{10000}$

，而是

$\log_{10}{\dfrac{2021}{2020}}\approx 0.000214944068680222$

，可以看到逼近於此比例的速度還是比較慢的。

UPD：

其實壓根就不需要用

$\log$

去算，這樣不僅引入精度誤差，而且慢。只需要在算階乘的過程之中，如果大於10000了馬上除個10，就可以保證一直在精度範圍之內了。如果說您非要使用

$\log_{10}$

去算，需要注意一些數值穩定性的小trick，然後精度開double就夠了。

在我的電腦上，使用

$\log_{10}$

計算的程式碼需要8。6s左右才能跑出

以內的答案，只需要浮點數乘除法的程式碼只需要0。33秒。（Ubuntu 20。04。2， g++ 10。2。0，編譯開關-Ofast -march=native）

並且有人提到浮點誤差的問題，我用GMP庫的高精度驗算了一下，保留200位小數的意義下也還是這個答案，可以基本排除浮點誤差的可能。

大家都喜歡貼程式碼，那麼我也貼一個C++程式碼吧：

#include

long

double

，

；

int

ans

；

int

main

（）{

for

（

int

，

；

1e8

；

）{

（

）

，

；

（

1e4

）

；

（

2020

2021

）

ans

；

}

printf

（

“%d

”

，

ans

）；

return

；

}

匿名使用者2021-02-05 23:01:23

顯然

384！ = 20205002129876021521366889509458521857103131384424164703……

8297！ = 20207983458785287090983863080884101922314442223694268578……

8795！ = 20206439534140183506320813566892771922507666440925556515……

16624！ = 20204447515212337619006649257632217013568552466164768543……

17775！ = 20201706710997231611432820358540894429946023160331657707……

故至少存在自然數n，使得n！的前四個數字是2020

證明過程如下

#！ /usr/bin/python3

sum

math

while

True

：

sum

math

sum_str

str

（

sum

）

（

sum_str

［

：

］

“2020”

）：

（

“{}！ = {}”

。

format

（

math

，

sum

））

math

#EOF

QDelta2021-02-06 20:46:20

先給個不那麼嚴謹的證明

題目等價於存在一對正整數

滿足：

$2020\times10^m\le n!<2021\times10^m \\$

簡單變形一下：

$\lg(n!)-\lg2021<m\le\lg(n!)-\lg2020 \\$

令

$f(n)=\lg(n!)-\lg2021$

，

$e=\lg\frac{2021}{2020}>0$

，上式就可以寫成：

$f(n)<m\le f(n)+e \\$

故只要存在正整數

滿足

$\{f(n)\}\ge1-e$

就可以了（這裡

$\{x\}$

表示

的小數部分）

取一個足夠大的正整數

，使得區間

$(10^{p+0.1e},10^{p+e})$

內的正整數個數大於

$\frac{1}{0.1e}$

，對於其中任一正整數

，容易知道：

$0.1e<\{\lg k\}<e \\$

假設該區間內最小的正整數為

，最大的正整數為

，那麼

$b-a+1>\frac{1}{0.1e}$

，故：

$\begin{aligned} &\sum_{k=a}^{b}\{f(k)-f(k-1)\}\\ =&\sum_{k=a}^{b}\{\lg k\}\\ >&(0.1e)(b-a+1)=1 \end{aligned} \\$

所以在

中必然存在正整數

滿足

$\{f(c)\}<1\le \{f(c)\}+\{\lg(c+1)\}<\{f(c)\}+e$

，故

$\{f(c)\}>1-e$

。

直觀上理解就是

$\{f(k)\}$

“增加”的過程中“超過”了

，而每次的“步長”又小於

，所以一定存在一個臨界的

滿足

$1-e<\{f(c)\}<1$

。

其實程式設計簡單地列舉一下就知道

是滿足條件的一個正整數，但是精確地計算階乘對於計算機來說開銷不少。 @SarvaTathagata 的回答裡說可以利用

$2020\le10^{3+\{\sum_{i=1}^n\lg i\}}<2021$

這個式子來避免大整數運算，可是在實際操作中也會遇到精度相關的問題

我們用C++來簡單測試一下，找到所有

以內滿足條件的正整數

// test。cpp

#include

template

typename

void

count_factorial

（

FILE

output

）

{

int

count

；

log_sum

；

for

（

int

；

100000000

；

）

{

log_sum

std

：：

log10

（（

）

）；

tmp

std

：：

pow

（（

）

，

（

）

log_sum

std

：：

floor

（

log_sum

））；

（

tmp

2020

tmp

2021

）

{

count

；

fprintf

（

output

，

“%d

”

，

）；

}

printf

（

“%d

”

，

count

）；

}

int

main

（）

{

count_factorial

float

（

fopen

（

“float。txt”

，

“w”

））；

count_factorial

double

（

fopen

（

“double。txt”

，

“w”

））；

count_factorial

long

double

（

fopen

（

“ldouble。txt”

，

“w”

））；

return

；

}

編譯執行，檢視輸出，結果令人驚訝：使用float型別（4byte）時一個也沒找著，使用double（8byte）時有21456個，而使用long double型別（16byte）時則有21488個。

這表明在實際運算的過程中，各種近似誤差的疊加最終超過閾值，影響到了最終結果。

利用GMP庫，我們來做個測試。計算

的前16位數字

// gmp_check。c

#include

int

main

（）

{

mpz_t

fact

，

base

；

mpz_init_set_ui

（

base

，

）；

mpz_fac_ui

（

fact

，

99999999

）；

size_t

digits

mpz_sizeinbase

（

fact

，

）；

mpz_pow_ui

（

base

，

base

，

digits

）；

mpz_t

result

；

mpz_div

（

result

，

fact

，

base

）；

gmp_printf

（

“%Zd

”

，

result

）；

return

；

}

輸出

16172037949214623863

使用C++標準庫，用三種浮點型別分別計算這個結果

// test2。cpp

#include

template

typename

test

（）

{

log_sum

；

for

（

int

；

100000000

；

）

{

log_sum

std

：：

log10

（（

）

）；

}

return

std

：：

pow

（（

）

，

（

）

log_sum

std

：：

floor

（

log_sum

））；

}

int

main

（）

{

using

namespace

std

；

auto

test

float

（）；

auto

test

double

（）；

auto

test

long

double

（）；

cout

setprecision

（

）；

cout

endl

；

return

；

}

得到

1617。089863098135

1617。203354540494

（float， float你在幹什麼啊float）

過載float型別的庫函式可能實現略有不同，兩次測試都顯現出巨大的差異。（事實上，這裡float型別計算出的對數之和僅在1。3e8左右，與實際值7。6e8差距巨大）

對比正確數值1617。2037949214623863，可以發現double型別在第5位出現不同，而long double型別在第8位出現差異。

BTW，雖然在第一個測試中使用long double型別僅比double型別多找到32個數，但是對比輸出檔案可知並情況沒有看上去這麼簡單

comm -3 <

（

sort double。txt

）

（

sort ldouble。txt

）

> diff。txt

這個diff。txt

僅

有2048行，非常的巧

在dalao @SarvaTathagata 的提點下做了一些改進，取得了顯著的效果。

// test_opt。cpp

#include

const

long

double

SUP

std

：：

log10

（

2。021

）；

const

long

double

INF

std

：：

log10

（

2。020

）；

template

typename

void

count_factorial

（

FILE

output

）

{

int

count

；

log_sum

；

for

（

int

；

100000000

；

）

{

log_sum

std

：：

log10

（（

）

）；

log_sum

std

：：

floor

（

log_sum

）；

（

log_sum

INF

log_sum

SUP

）

{

count

；

fprintf

（

output

，

“%d

”

，

）；

}

printf

（

“%d

”

，

count

）；

}

int

main

（）

{

count_factorial

float

（

fopen

（

“float2。txt”

，

“w”

））；

count_factorial

double

（

fopen

（

“double2。txt”

，

“w”

））；

count_factorial

long

double

（

fopen

（

“ldouble2。txt”

，

“w”

））；

return

；

}

// 個數分別為21658， 21486 和 21486double與long double所得數字完全相同

（我確實太菜了

環境：x86_64，gcc10。2。0 on archlinux

mathe2021-04-17 14:22:08

2021年了，該換2021開頭的了，第一個以2021開頭的n！為16979！

由於Sterling公式的存在，尋找某個特點模式開頭的階乘還是比較容易的，比如以圓周率的前若干位開始的最小階乘數n！有：

d = 3， n = 9

d = 31， n = 62

d = 314， n = 62

d = 3141， n = 10044

d =31415， n = 50583

d = 314159， n = 1490717

d = 3141592， n = 5573998 開始數字是3141592381

d = 31415926， n = 65630447 開始數字是3141592602

d = 314159265， n = 688395641 開始數字3141592651957527

d = 3141592653， n = 5777940569 起始數字314159265301

d = 31415926535， n = 77773146302，開始數字314159265353488

d = 314159265358， n = 1154318938997開始數字3141592653584138

d = 3141592653589， n = 1544607046599開始數字31415926535899498

另外還有

927877657573029！ = 3。141 592 653 589 793 763154362168869644108970257452834353669890 * 10^13485028080082190

當然如果不要求求最小結果，構造性的尋找結果，會很簡單。

比如我們想找20210417開頭的階乘數，我們先找一個充分大的10的冪，由於目標8位數，我們選擇從

$10^{24}$

開始，計算得到

$\lg(10^{24}!)=23565705518096748172348859.4801733290967631277766999611$

而目標

$\lg(20210417)=7.305575274372831021327701525754$

為此我們需要讓小數部分增長0。825401945276067893551001564，這個數字乘以

$\ln10$

轉化為1。9005582149209609973521088。

現在假設目標為

$(10^{24}+k)!$

，k相對

$10^{24}$

不大，那麼小數部分增長取自然對數後為

$\sum_{h=1}^k\ln(1+\frac{h}{10^{24}})\approx \sum_{h=1}^k \frac{h}{10^{24}}=\frac{k(k+1)}{2\times10^{24}}\approx 1.9005582149209609973521088$

可以求得

$k\approx1949645206144$

經檢驗，這個資料略小，可以調整為k=1949645206145

得出

$(10^{24}+1949645206145)!=2021041700001755193997\cdots$

在補充一個結果

$\left[\frac{100000000014070649876!}{10^{1956570552091087814759}}\right]=5201314$

零點不是點2021-08-15 22:15:58

問題：

$\varphi：\exists x_{0}\in \mathbb{Z}_{\geqslant 0} ，x_{0}!$

前四位為

若

$n\in \mathbb{Z}$

，

現兩邊取自然對數得：

$\log n!=\log 1+\log 2+\log 3+\cdots \cdots + \log n= \sum^{n}_{i=1} \log i$

根據尤拉-麥克勞林公式

$\sum_{k=1}^nf(k)=\int_1^nf(x)\mathrm{d}x+{f(n)+f(1)\over2}+\sum_{k=1}^\infty{B_{2k}\over(2k)!}\left[f^{(2k-1)}(n)-f^{(2k-1)}(1)\right]$

可得：

$\log n!= n\log n-n+1+ \frac{\log n}{2} +誤差項\\$

觀察影象（圖1）：

圖1

可見近似效果不太好，但夠數值計算。

現在我們定義符號

$\mathcal E\left[ h(x) \right]$

表示：

若

$x\in\left[ a,b\right],f(x)\leq g(x)+h(x)$

則稱

$在[a,b]上，f(x)=g(x)+\mathcal E\left[h(x ) \right]$

所以我們要找到一個較好的

使得

$\sum_{k=1}^\infty{B_{2k}\over(2k)!}\left[f^{(2k-1)}(n)-f^{(2k-1)}(1)\right]= \mathcal E[h(x)]$

現置

$\mathcal S= \sum_{k=1}^\infty{B_{2k}\over(2k)!}\left[f^{(2k-1)}(n)-f^{(2k-1)}(1)\right]$

計算

$f^{\left( 2k+1\right) }(x)=\frac{\left( 2k-2\right) !}{x^{2k-1}}$

$\therefore \mathcal S= \sum_{k=1}^\infty{B_{2k}\over(2k)!} [\frac{\left( 2k-2\right) !}{n^{2k-1}} -\left( 2k-2\right) !]= \sum^{\infty }_{k=1} \frac{B_{2k}}{2n^{2k-1}} -\sum^{\infty }_{k=1} \frac{B_{2k}}{2}$

接下來計算

$\sum^{\infty }_{k=1} \frac{B_{2k}}{2}$

事實上，

$B_{2k}=2 \left( 2\pi \right)^{-2k} \left( 2k\right) !\zeta \left( 2k\right)$

由：

$\zeta \left( 2k\right) =\frac{1}{\left( 2k-1\right) !} \int^{\infty }_{0} \frac{x^{2k-2}}{\mathrm{e}^{x} -1} \mathrm{d} x$

知：

好像有點麻煩，翻下書

所以

$\sum^{\infty }_{k=1} \frac{B_{2k}}{2} =\frac{1}{2} \sum^{\infty }_{k=1} B_{2k}=$

選擇比較多，我選

$\zeta \left( 2n\right) =-\frac{1}{2} \frac{\left( 2\pi \mathrm{i} \right)^{2n} }{(2n)!} B_{2n}$

所以

$\sum^{\infty }_{k=1} B_{2k}= \sum^{\infty }_{k=1} -\frac{2\left( 2k\right) !\zeta \left( 2k\right) }{\left( 2\pi \mathrm{i} \right)^{2k} }$

先放結論：

$\log n!=\left(n+\frac12\right)\log n-n+\frac12\log2\pi+\int_n^\infty{\overline B_1(x)\over x}\mathrm dx= \mathcal E \Large{[}\left( n+\frac{1}{2} \right) \log n-n+\log 2\pi \Large]$

再換底就行，坑我慢慢填

仍未完待續

（釋出於8。15下午，算是挖這個老問題，預計接下來算常數

留坑

小蜜蜂問答

小蜜蜂問答

有沒有自然數 n，使得 n! 的前四個數字是 2020？

推薦文章

小蜜蜂問答

小蜜蜂問答

有沒有自然數 n，使得 n! 的前四個數字是 2020？

相關文章

excel對多個工作表中的同一單元格求和兩種方法？

第四期中國有嘻哈TT和誰battle？

MySql那些事兒（三）：InnoDB架構介紹之磁碟篇

丁克族什麼意思

推薦文章