Projecteuler (282) Ackermann function - 拼圖

Table of Contents

Problem 282 The Ackermann function

http://projecteuler.net/index.php?section=problems&id=282

對於非負整數 m, n

A(m, n)被定義如下:


A(m,n) = n+1 當m=0
A(m-1, 1) 當m>0且 n=0
A(m-1, A(m, n-1)) 當m>0且n>0

例如 A(1,0)=2, A(2,2)=7, A(3,4)=125

6
Σ A(n,n) 除以14^8 之餘數為何?
n=0

------------------------

看起來只是要求A(0,0)~A(6,6)這7項之和除以14^8之餘數
似乎很簡單,不過.....

聽說這是計算機科學中非常有名的艾克曼函數
不過,我到現在才知道有這函數(汗)

附註: 經過24小時的時候,只有22人解出來,這題似乎比螞蟻搬種子那一題更難
--

All Comments

Kristin avatarKristin2010-03-19
A(5,5)= 2的65536層"層狀次方"2^(2^(2^(2^(2^....
James avatarJames2010-03-21
我賭看過A(6,6) 這個數長怎樣的人全世界不超過50個
James avatarJames2010-03-26
↑gooooooooooooo...ooooooooooogle A(6,6): 哼,嫩B
Lauren avatarLauren2010-03-28
應該全世界沒人看過吧XD 因為這個數的位數已經是天文數字
Edith avatarEdith2010-04-01
不過A(6,6)除以14^8之餘數卻是可以確定的
Andy avatarAndy2010-04-03
算是一種數學上的小技巧吧
Suhail Hany avatarSuhail Hany2010-04-04
照U大說的A(6,6)mod14^8有解的話 其他是否也有解
Jacob avatarJacob2010-04-07
話說這題出來的那早好像xmk就解出來了
Genevieve avatarGenevieve2010-04-10
本來看到題目還天真的手算 合理範圍只到A(4,1)=A(5,0)
A(4,2)搭配小算盤合理 其他...
Hazel avatarHazel2010-04-13
我是用2^(3*14^8)≡ 1 mod (7^8) 去推的
Annie avatarAnnie2010-04-16
這樣A(4,x)的次方塔的每一層除14^8的餘數就可以求出來
Isabella avatarIsabella2010-04-19
因為除以14^8的餘數只有14^8個 最後會有一個循環
Irma avatarIrma2010-04-23
A(4,?) 不管?是多少 都可以求出其除14^8之餘數
A(5,?)跟 A(6,?) 也用類似的方法去解
Sandy avatarSandy2010-04-24
其實最難解的是A(4,?) A(4,?)解出以後
Oscar avatarOscar2010-04-25
就會發現 A(5,?)跟A(6,?)根本就迎刃而解了
Skylar DavisLinda avatarSkylar DavisLinda2010-04-26
感謝U大的指點 我想再來我得研究的是怎麼寫程式XD
靠紙筆跟小算盤應該到了個極限了- -
Connor avatarConnor2010-04-28
utomaya的那行式子很關鍵...
Odelette avatarOdelette2010-04-29
是說這讓我想起某次 ACM 的比賽的題目也是類似問題
然後也發現到和這題一樣的情形 XDrz
(那個題目沒有出 Ackermann function 這麼狠啦
Hamiltion avatarHamiltion2010-05-02
只是用和 Ackermann 類似的形式把指數推廣出去而已)