您當前的位置：首頁 > 體育

請問2^2^2^2+3^3^3^3是否為素數呢？

作者：由 Ciaccona 發表于 體育時間：2022-01-20

請問2^2^2^2+3^3^3^3是否為素數呢？東城居士2022-01-22 12:23:18

以目前的數學理論和計算能力應該還沒有人能回答你這個問題！

估計你是發現

2+3=5,~2^2+3^3=31,~2^{2^2}+3^{3^3}=7625597485003

都是素數，然後才想知道

2^{2^{2^2}}+3^{3^{3^3}}

是否也為素數。 如果

2^{2^{2^2}}+3^{3^{3^3}}

也是素數，估計你還會進一步想知道

2^{2^{2^{2^2}}}+3^{3^{3^{3^3}}},~~2^{2^{2^{2^{2^2}}}}+3^{3^{3^{3^{3^3}}}},~~2^{2^{2^{2^{2^{2^2}}}}}+3^{3^{3^{3^{3^{3^3}}}}},~\cdot\cdot\cdot

是否也為素數。 其實這一問題和歷史上著名的

Cantor 猜想

有異曲同工之妙！

設

p_1=2

，當

n\geq2

時，

p_n=2^{p_{n-1}}-1

。 集合論的創始人

Cantor

猜測：當

n\geq1

時，

p_n

均為素數。 容易驗證

p_1=2,~p_2=2^2-1=3,~p_3=2^3-1=7,~p_4=2^7-1=127

都是素數，但要判斷

p_5=2^{127}-1=170141183460469231731687303715884105727

是素數卻非常困難。 而

p_6=2^{170141183460469231731687303715884105727}-1

不要說判斷是否為素數，就是將其計算出來都十分困難，因為這個數的位數為

~~~\left[ \log_{10}(2^{170141183460469231731687303715884105727}-1) \right]+1

= \left[ 170141183460469231731687303715884105727\log_{10}2 \right]+1

=51217599719369681875006054625051616350.

同樣可以計算

2^{2^{2^2}}+3^{3^{3^3}}

的位數大約為

\left[ \log_{10}3^{3^{3^3}}\right]+1=\left[3^{3^3} \log_{10}3\right]+1=3638334640025.

雖然

2^{2^{2^2}}+3^{3^{3^3}}

要遠小於

Cantor 猜想

中的

p_6=2^{170141183460469231731687303715884105727}-1,

但卻遠遠大於目前已知的最大素數

~~~~~~~~~~~~~~~M_{82589933}=2^{82589933} − 1,

因為

M_{82589933}

才

24862048

位。 故以目前的數學理論和計算機的計算能力，我們根本無法判斷

2^{2^{2^2}}+3^{3^{3^3}}

是否為素數，而對於更大的

2^{2^{2^{2^2}}}+3^{3^{3^{3^3}}},~~2^{2^{2^{2^{2^2}}}}+3^{3^{3^{3^{3^3}}}},~~2^{2^{2^{2^{2^{2^2}}}}}+3^{3^{3^{3^{3^{3^3}}}}},~\cdot\cdot\cdot

是否為素數那就更加不得而知了！

請問2^2^2^2+3^3^3^3是否為素數呢？蘇遲但到2022-01-24 11:57:16

費馬小定理：

a^{p-1}=1 \mod p(p\; is\;a\; prime).\\ a^n=a^{n \% \varphi (p)}\mod p.

2^2^2^2=65536%7=2

3^3^3=7625597484987

3^3^3^3=3^（7625597484987%6）%7=6

所以2^2^2^2+3^3^3^3=1mod7。

@MrRoach

在百度百科中關於elgamal詞條中同樣也犯了一樣的問題。

請問2^2^2^2+3^3^3^3是否為素數呢？紅岸19792022-01-24 12:48:32

是素數，我有一個美妙的證明，可惜評論區太小，寫不下

請問2^2^2^2+3^3^3^3是否為素數呢？知乎使用者2022-01-29 23:13:17

問題並不像 @東城居士 說得那樣無解，如果我們足夠幸運，還是可以做證明的：

如果已知這玩意是合數，且它的最小素因子已知，而且不算太大（比如只有幾億位）

我們還是有可能進行驗證的（藉助fermat小定理）

原理是檢查

Mod（65536，p）+Mod（3，p）^7625597484987

是否為0

但如果要我們證明它是合數

理論上可以用fermat小定理的逆命題做miller-rabin，但miller-rabin的計算時間，很可能可以跟地球壽命進行比較

（更不用說更慢的BPSW演算法）

我們只能挨個素數進行驗證

23：00：28> forprime（p=2，10^10，if（Mod（65536，p）+Mod（3，p）^7625597484987==0，print（p）））

cpu time = 6min， 26，109 ms， real time = 6min， 26，463 ms。

簡單驗證（CPU計算不到7分鐘）可知，2^2^2^2+3^3^3^3不存在小於10^10的素因子。

如果題主有耐心可以安裝一個pari/gp或者sagemath，用我或者另一個答主 @行而知之 的程式進行試算。

如果恰好這玩意是合數且有一個很小的素因子，我們還是有很大可能找到它的。

至於這玩意是素數的情形……或許上帝知道它真的是素數，但我肯定上帝給不出證明。

請問2^2^2^2+3^3^3^3是否為素數呢？何冬州楊巔楊豔華典生2022-01-30 07:43:43

一、相似題：3^a+2^（2^（。。。）），a=1，3，。。。

3+2，9+2，27+2，81+2

3+4，9+4，27+4，

3+16，，27+16

3+65536，，27+65536=65563

以上全是質數。

3+2^65536，，27+2^65536=

……

二、題目轉寫：

T［a，n］=a^（a^（。。。））［n個a］ =a^T［a，n-1］，問

T［a，n］ mod p是否有規律？

目前已知當n=1，2，3時T［2，n］+T［3，n］為素數，問n≥4時如何？

標簽： 素數  65536  27  MOD  10 

上一篇:大家天天用的千分尺是如何誕生的？

下一篇：【垂釣科普011】—魚漂

猜你喜歡