機械学習を活用して、Amazonの文化破壊と闘う先住民族がいます: 数学

ラベル数学の投稿を表示しています。すべての投稿を表示

2020年6月26日金曜日

デスカ・ムトゥルー公式

なんの新しい公式か？　と思ったら、

Death Come True Official （デスカムトゥルー公式）

だった。

2020年5月23日土曜日

ブレインダイバーが次のようなマジックを披露していた。

１、電卓を用意する。
２、１から９までの好きな数字を入力する。
３、掛けるボタンを押す、
４、２と３を繰り返す。
　答えが７桁になったら（１００万以上になったら）ストップする。
５，答えの数字の桁をすべてたす。
　もし結果が２桁になればその数字の桁をたす。

たした結果は９です。

これはいわゆる数学マジックなのではと思い、次のようなHaskellのスクリプトを書いてみた。

--mag.hs
import System.Random
mkIs = do
gen <- getStdGen
let is = take 100 $ (randomRs (2,9) gen :: [Int])
return is
loop is i = do
let r = product (take i is)
if r > 1000000
then return (take i is, r)
else loop is (i+1)
sumDigits x 0 = x
sumDigits x n = f + sumDigits (x - f * 10 ^ n) (n - 1)
where f = x `div` (10^n)
main = do
is <- mkIs
(a,b) <- loop is 1
putStr $ show a
putStr $ show b
putStr "="
let rr = sumDigits b 6
print rr

--endOf mag.hs

$ runghc mag.hs

([3,6,2,3,8,9,9,4,8],2239488)=36

これは
３ｘ６ｘ２ｘ３ｘ８ｘ９ｘ４ｘ８＝２２３９４８８
2+2+3+9+4+8+8＝３６
を示していて

確かに３＋６＝９

となっている。

なおスクリプトでは１から９ではなく２から９となっている。

１は本質的ではなく演出上の都合。

このスクリプトを１００回繰り返した結果。

([9,3,8,8,8,8,7,5],3870720)=27

([7,5,7,3,8,6,2,3,9],1905120)=18

([5,6,9,6,8,6,6,4],1866240)=27

([8,5,2,6,4,4,5,6,6],1382400)=18

([5,3,5,8,7,4,5,7,8],4704000)=15

([6,5,8,3,7,6,9,6],1632960)=27

([8,4,6,7,9,7,9,7],5334336)=27

([7,5,6,2,4,3,4,5,3,6],1814400)=18

([5,7,7,5,8,2,3,3,6],1058400)=18

([5,8,7,6,2,6,8,8],1290240)=18

([2,5,4,6,7,5,2,7,2,3,7],4939200)=27

([8,9,3,2,7,2,2,4,6,6],1741824)=27

([8,7,5,6,4,5,7,3,5],3528000)=18

([9,8,7,4,7,5,3,3,3],1905120)=18

([5,8,4,6,8,2,4,6,8],2949120)=27

([6,8,6,4,2,3,7,7,3],1016064)=18

([6,6,2,7,8,5,9,4,2],1451520)=18

([2,7,2,2,6,6,7,7,8,9],7112448)=27

([4,8,3,6,2,2,8,7,8],1032192)=18

([8,7,2,3,9,4,7,2,2,2,8],5419008)=27

([6,2,2,6,2,2,9,3,8,3,6],2239488)=36

([5,5,2,4,3,7,6,2,7,7],2469600)=27

([7,7,8,3,4,5,5,9],1058400)=18

([9,4,8,6,4,2,6,2,4,8],5308416)=27

([2,4,2,4,9,7,4,6,7,2],1354752)=27

([6,4,7,7,5,3,6,4,6],2540160)=18

([6,3,2,8,7,5,8,2,7],1128960)=27

([5,5,9,5,8,3,7,3,9],5103000)=9

([8,9,4,9,4,4,8,7],2322432)=18

([5,8,5,7,2,9,9,9],2041200)=9

([7,4,8,3,8,3,3,5,3,3],2177280)=27

([6,9,4,6,9,7,6,3],1469664)=36

([8,7,5,3,6,6,7,4,7],5927040)=27

([7,7,4,4,6,3,7,8,3],2370816)=27

([9,7,3,6,9,8,7,8],4572288)=36

([8,4,6,3,5,9,9,7],1632960)=27

([5,5,4,2,9,3,3,7,6,3],2041200)=9

([6,3,3,2,6,8,8,4,8],1327104)=18

([2,9,2,2,9,7,9,4,3,7],3429216)=27

([7,5,2,5,3,8,7,5,5],1470000)=12

([4,4,8,3,9,5,5,9,7],5443200)=18

([4,9,6,9,9,8,3,3],1259712)=27

([7,6,4,7,7,5,3,9],1111320)=9

([7,3,8,3,5,5,4,4,7],1411200)=9

([6,4,3,8,8,3,7,8,8],6193152)=27

([3,4,5,5,7,5,5,4,8],1680000)=15

([8,6,8,7,5,4,8,2,2],1720320)=15

([3,2,4,7,5,5,5,2,4,8],1344000)=12

([3,5,3,2,9,5,9,8,3,8],6998400)=36

([4,5,3,2,5,6,9,4,3,8],3110400)=9

([9,8,3,8,3,6,3,9,3],2519424)=27

([8,2,3,7,3,6,2,4,8,2,4],3096576)=36

([2,7,5,6,4,8,6,2,8],1290240)=18

([3,4,5,9,4,2,7,8,2,9],4354560)=27

([5,8,5,3,7,4,3,2,7,9],6350400)=18

([6,4,4,8,2,3,9,6,4,8],7962624)=36

([6,5,5,3,8,4,5,6,3],1296000)=18

([6,4,9,7,5,8,4,3,5],3628800)=27

([9,7,6,6,6,9,6,8],5878656)=45

([3,8,6,4,2,5,8,3,2,5],1382400)=18

([9,8,4,7,4,6,6,3,4],3483648)=36

([6,9,2,9,7,5,3,2,4,9],7348320)=27

([3,7,2,4,9,6,4,7,7],1778112)=27

([9,7,6,5,2,8,8,6],1451520)=18

([7,8,9,7,8,2,5,6],1693440)=27

([3,4,8,5,8,3,7,5,2,3],2419200)=18

([4,8,4,6,6,5,6,4,8],4423680)=27

([6,3,8,2,6,4,8,3,9],1492992)=36

([4,6,5,3,7,8,8,7],1128960)=27

([8,9,9,6,8,2,9,3],1679616)=36

([2,4,2,3,4,8,2,7,3,3,8],1548288)=36

([6,6,2,5,3,6,9,2,7,6],4898880)=45

([4,8,2,3,8,8,8,9,5],4423680)=27

([2,6,7,8,4,5,9,5,6],3628800)=27

([2,6,9,4,9,5,2,2,2,4,2],1244160)=18

([5,9,8,7,8,5,9,5],4536000)=18

([8,5,7,9,5,2,7,5,5],4410000)=9

([3,6,3,8,3,7,5,3,9],1224720)=18

([8,5,3,2,3,3,4,9,9,7],4898880)=45

([6,7,5,6,9,2,3,9,6],3674160)=27

([8,8,9,4,9,8,9],1492992)=36

([8,8,9,5,9,2,3,9],1399680)=36

([8,8,7,6,2,2,4,6,3,2],1548288)=36

([6,3,4,2,5,9,8,4,3,3],1866240)=27

([6,3,4,4,2,4,4,6,9,3],1492992)=36

([8,4,4,3,3,4,7,2,3,7],1354752)=27

([4,5,8,8,4,2,7,7,8],4014080)=17

([9,3,7,9,3,2,8,8,6],3919104)=27

([9,7,8,5,9,6,6,3],2449440)=27

([3,2,7,6,4,5,2,2,9,4,3],2177280)=27

([4,3,3,5,7,8,5,2,9,2],1814400)=18

([4,8,9,7,9,3,2,5,7],3810240)=18

([9,2,8,9,2,9,6,4,2],1119744)=27

([2,2,6,2,5,2,3,5,6,3,6,6],4665600)=27

([7,3,8,9,2,4,2,2,2,7,7],4741632)=27

([4,7,6,2,2,4,6,5,4,2,3],1935360)=27

([4,5,4,7,2,4,6,4,2,9],1935360)=27

([8,5,7,3,3,4,8,6,3],1451520)=18

([9,7,6,3,3,7,9,9],1928934)=36

([9,4,7,8,4,6,3,6,2],1741824)=27

５回目に１５、そのほか数回不正解が現れるが、殆どは正解となっている。

大勢で一斉に計算すれば不思議度は増すだろう。

なおなぜこのようなことがおこるのか？

案外複雑な仕組みかもしれない

答えが７桁になったら（１００万以上になったら）という条件も本質的ではなく、
入力者がわかりやすくするための演出で、
適当に大きな数になればよく、例えば５回繰り返せば、結構な確率で９もしくは、たして９になる。

[2,2,9,2,6]432=9
[7,5,8,6,2]3360=12
[7,3,9,9,4]6804=18
[6,3,5,7,6]3780=18
[3,2,8,6,9]2592=18
[8,5,5,9,7]12600=9
[8,4,9,8,3]6912=18
[2,9,8,8,2]2304=9
[2,8,7,5,2]1120=4
[3,4,9,5,3]1620=9

このマジックの前段の計算は、一般的な式で表せばこうなる。

１のA乗ｘ２のｂ乗ｘ３のｃ乗・・・ｘ９のI乗。

AからIは任意の整数で、

例えば[2,2,9,2,6]432=9のケースでは

１の０乗ｘ２の３乗ｘ３の０乗ｘ４の０乗ｘ５の０乗ｘ６の１乗ｘ７の０乗ｘ８の０乗ｘ９の１乗

で表せる。

また後段の計算は、１０のN乗での整数割り算がからんでいる。

ただそれがどんな意味をもつのかは僕の知識では不明。

2018年5月6日日曜日

2の平方根

四角数は整数nの2乗です。
2の平方根は２００に一番近い四角数を探し、そのもととなったｎの桁をずらせば求まります。
Haskellで計算しますと

*Main> takeWhile (\(a,b) -> b < 200) $ map (\x -> (x , x*x)) [1..]
[(1,1),(2,4),(3,9),(4,16),(5,25),(6,36),(7,49),(8,64),(9,81),(10,100),(11,121),(12,144),(13,169),(14,196)]
*Main>

２００に一番近い四角数は１９６でｎは１４。
桁をずらして１．４。

これは2の平方根の近似値です。
偶然ですがとてもよい近似値です。

*Main> 1.4*1.4
1.9599999999999997
*Main>

さらに２００を百倍して２００００に一番近い四角数を探しますと

*Main> last $ takeWhile (\(a,b) -> b < 20000) $ map (\x -> (x , x*x)) [1..]
(141,19881)
*Main>

ともう一桁詳しい√２が求まります。

これを関数化しますと

*Main> let f k = last $ takeWhile (\(a,b) -> b < 2*100^k) $ map (\x -> (x , x*x)) [1..]
*Main> f 3
(1414,1999396)
*Main> f 4
(14142,199996164)
*Main> f 5
(141421,19999899241)
*Main>

ただしｋを大きくとると四角数のリストを作るのに負担が増えて現実的ではありません。

少し工夫を加えたのが折り紙をつかった計算法です。

正方形の折り紙を２枚用意します。
１枚を台紙に貼ります。
もう１枚を１００等分します。

小さな折り紙が１００枚できたことになります。

最初の折り紙の下辺、右辺に沿ってこの小さな折り紙を並べていきます。

下辺に１０枚、右辺に１０枚、角に１枚、合計２１枚並べることができました。
こうしてできた図形はやはり正方形です。

まだ小さな折り紙がのこっているので同様の作業を繰り返します。

こんどは下辺に１１枚、右辺に１１枚、角に１枚、合計２３枚並べることができました。

この作業は計４回繰り返すことができます。

この４回という数字を記録しておきます。
√２の一桁目の値です。

*Main> 21+23+25+27
96

１００−９６＝４

ですので小さな折り紙が４枚あまります。

その４枚の小さな折り紙をそれぞれ、再び１００等分します。

同様の作業をしますと
こんどは下辺に１４０枚、右辺に１４０枚、角に１枚、合計２８１枚並べることができました。
数がたりないので１回だけ並べることができます。

１を記録します。√２の次の桁の値です。

余った２１９枚をさらに百等分して・・・

とこの作業を無限に繰り返せば無限に詳しい２の平方根が求まります。
StateMonadを使ってアルゴリズムに忠実に書くとこうなります。

実行例

$ runghc root2.hs
(10,100,0,0,0,1)
(10,100,21,0,1,1)
(10,100,44,21,2,1)
(10,100,69,44,3,1)
(10,100,96,69,4,1)
(10,100,125,96,5,1)
4
(140,400,0,0,0,2)
(140,400,281,0,1,2)
(140,400,564,281,2,2)
1
(1410,11900,0,0,0,3)
(1410,11900,2821,0,1,3)
(1410,11900,5644,2821,2,3)
(1410,11900,8469,5644,3,3)
(1410,11900,11296,8469,4,3)
(1410,11900,14125,11296,5,3)
4
(14140,60400,0,0,0,4)
(14140,60400,28281,0,1,4)
(14140,60400,56564,28281,2,4)
(14140,60400,84849,56564,3,4)
2
(141420,383600,0,0,0,5)
(141420,383600,282841,0,1,5)
(141420,383600,565684,282841,2,5)
1
(1414210,10075900,0,0,0,6)
(1414210,10075900,2828421,0,1,6)
(1414210,10075900,5656844,2828421,2,6)
(1414210,10075900,8485269,5656844,3,6)
(1414210,10075900,11313696,8485269,4,6)
3
(14142130,159063100,0,0,0,7)
(14142130,159063100,28284261,0,1,7)
(14142130,159063100,56568524,28284261,2,7)
(14142130,159063100,84852789,56568524,3,7)
(14142130,159063100,113137056,84852789,4,7)
(14142130,159063100,141421325,113137056,5,7)
(14142130,159063100,169705596,141421325,6,7)
5
(141421350,1764177500,0,0,0,8)
(141421350,1764177500,282842701,0,1,8)
(141421350,1764177500,565685404,282842701,2,8)
(141421350,1764177500,848528109,565685404,3,8)
(141421350,1764177500,1131370816,848528109,4,8)
(141421350,1764177500,1414213525,1131370816,5,8)
(141421350,1764177500,1697056236,1414213525,6,8)
(141421350,1764177500,1979898949,1697056236,7,8)
6
(1414213560,6712126400,0,0,0,9)
(1414213560,6712126400,2828427121,0,1,9)
(1414213560,6712126400,5656854244,2828427121,2,9)
(1414213560,6712126400,8485281369,5656854244,3,9)
2
(14142135620,105527215600,0,0,0,10)
()

計算はこちらで見れます。

２の平方根だけではなく任意の整数Nの平方根を求めるHaskellのコードが

http://hhg2the-haskell.blogspot.jp/2017/10/blog-post_26.html

さらに折り紙ではなくサイコロを１０００等分して並べる方法でNの立方根も計算します。

2018年5月3日木曜日

hanoiの塔

ハノイの塔の最小解き手順数は次のようなHaskellのコードで計算できます。

h 1 = 1
h n = h (n-1) + 1 + h (n-1)

円盤の枚数が(n-1)のときの手順数がわかれば、円盤の枚数がｎのときの手順数はいつでも計算できる、ということから再帰的に書くことができます。

計算してみます。

$ ghci

GHCi, version 8.0.1: http://www.haskell.org/ghc/ :? for help
Prelude> :l h.hs
[1 of 1] Compiling Main ( h.hs, interpreted )
Ok, modules loaded: Main.
*Main> h 1
1
*Main> h 2
3
*Main> h 3
7
*Main>

枚数が多くなると非常に時間がかかるようになります。

*Main> map h [1..64]

[1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535,131071,262143,524287,1048575,^CInterrupted.

*Main>

これはこのコードの構造がHanoiの塔を解くプログラムと同じだからです。
（円盤を動かすたびにカウントしているのと同じ）

このようなときはfold系の関数を利用します。

*Main> scanl (\x _ -> x + 1 + x) 0 [1..64]

[0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535,131071,262143,524287,1048575,2097151,4194303,8388607,16777215,33554431,67108863,134217727,268435455,536870911,1073741823,2147483647,4294967295,8589934591,17179869183,34359738367,68719476735,137438953471,274877906943,549755813887,1099511627775,2199023255551,4398046511103,8796093022207,17592186044415,35184372088831,70368744177663,140737488355327,281474976710655,562949953421311,1125899906842623,2251799813685247,4503599627370495,9007199254740991,18014398509481983,36028797018963967,72057594037927935,144115188075855871,288230376151711743,576460752303423487,1152921504606846975,2305843009213693951,4611686018427387903,9223372036854775807,18446744073709551615]

(0.02 secs, 709,992 bytes)

*Main>

最初のコードが非効率だったのは二股再帰しているからです。

次のように書き換えればよい。

h2 1 = 1

h2 n = h2 (n-1) * 2 + 1

*Main> h2 64

18446744073709551615

(0.02 secs, 112,688 bytes)

*Main>

円盤の数がN枚のときのハノイの塔は、２のN乗マイナス１回の動きで解けることが知られています。

Prelude> 2^64-1

18446744073709551615

「最初に一番下にあった円盤はただ１回、元の位置から目的地に移動しているだけ」ということが関係しています。つまり円盤が何枚積まれていても一番下の円盤が持ちうる状態は２つ。です。すべての円盤についてそうですので、N枚の円盤が持ちうる状態をすべて数え上げれば２のN乗になります。一番最初の状態を加えていないので２のN乗マイナス１です。

64枚の円盤に上から順番に番号をつけます。一番上が1番一番下が６４番です。６４番はただ一回A塔からB塔に移動しているだけです。つまり６４番の持ちうる状態は２つ。つぎに６３番から１番までの動きををみてみますと、６４番を移動させるために、一旦全部C塔に移動しています。このとき６３番だけをみますと、ただ一回A塔からC塔に移動しているだけです。つまり６３番の持ちうる状態は２つ。で６４番がB塔に移動したあと、すべてB塔に移動するのですが、やはり６３番はただ一回C塔からB塔に移動しているだけです。このとき、６３番の持ちうる状態は２つです。つまり６４番の持ちうる状態それぞれについて６３番が持ちうる状態は２つづつ。つまり２ｘ２、２の２乗です。６２番については面倒なので省略しますが、同じことが言えます。ハノイの塔のルールにしたがって(最小手順で）動かした場合、自分より下の円盤が持ちうる全ての状態それぞれについて２つづつの状態を持ちうるということです。６４番と６３番が持ちうる状態が２ｘ２でしたので、２ｘ２ｘ２、２の３乗。一般に
ハノイの塔のルールにしたがって（最小手順で）円盤を動かした場合、 N番目までの円盤が持ちうる状態は２の（Nマイナス１）乗　かける　２つまり　２のN乗です。１番の円盤は下から数えて６４枚目ですので、２の６４乗最初の状態を勘定にいれないので、２の６４乗マイナス１

（これは６４bitのメモリーが０〜18446744073709551615までの整数を表わせることと等価です。）

さてソロリ新左衛門がなぜ大金持ちになったかですが、

決して「戦場でサンタフェを売った。」からではありません。

有名なのは将棋盤と米粒の話しです。

最初のマスに１粒、次に２倍の２粒、さらに２倍の４粒・・・米粒をのせていきます。

将棋盤は９ｘ９の８１マスなので、

*Main> scanl (\x _ -> x * 2) 1 [2..(9*9)]

[1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904,9223372036854775808,18446744073709551616,36893488147419103232,73786976294838206464,147573952589676412928,295147905179352825856,590295810358705651712,1180591620717411303424,2361183241434822606848,4722366482869645213696,9444732965739290427392,18889465931478580854784,37778931862957161709568,75557863725914323419136,151115727451828646838272,302231454903657293676544,604462909807314587353088,1208925819614629174706176]

(0.03 secs, 1,033,184 bytes)

ソロリ新左衛門が求めたのはその合計ですので

*Main> sum it

2417851639229258349412351

(0.01 secs, 109,800 bytes)

*Main>

2杼4178垓5163京9229兆2583億4941万2351粒です。

ある方の計算によると１俵は2666666粒なのだそうです。

とすると2杼4178垓5163京9229兆2583億4941万2351粒は約９０京俵。

日本の現在の年間生産量は１億数千万俵。

同様の話しがインドの王様とチェスの発明者の話しとして伝わっています。

こちらはチェス盤と麦です。

*Main> scanl (\x _ -> x * 2) 1 [2..(8*8)]

(0.02 secs, 685,632 bytes)

*Main> sum it

18446744073709551615

1844京6744兆737億955万1615粒

なぜかハノイの塔の解き手順と一致しました。

将棋盤やチェス盤ですのでこの程度の数でおさまっていますが、これが囲碁の盤だったらどうなるでしょうか。

*Main> sum $ scanl (\x _ -> x * 2) 1 [2..(18*18)]

34175792574734561318320347298712833833643272357706444319152665725155515612490248800367393390985215

(0.02 secs, 276,408 bytes)

*Main>

34,175,792,574,734,561,318,320,347,298,712,833,833,643,272,357,706,444,319,152,665,725,155,515,612,490,248,800,367,393,390,985,215

サイエンティフィック・ノーテーションでは

3.417579257473456e97

３のあとに０が９７個並びます。

実際にハノイの塔を解くHaskellのプログラムは

http://hhg2the-haskell.blogspot.jp/2017/10/blog-post_9.html

参考

Emacsにはテキストベースながらグラフィカルにハノイの塔の動きをシミュレートするマクロが搭載されています。（有名です。）

多分そのソースコードとおもわれるLispプログラムが

http://www.opensource.apple.com/source/emacs/emacs-51/emacs/lisp/play/hanoi.el

に公開されています。（かなり複雑）

またVimのマクロもあり（これは初耳）、

Kona　３．０では

/usr/share/vim/vim74/macros/hanoi

にありました。（使用法は同ディレクトリーのClick.meというファイルを開いてください。）

ユニクスの塔

プリンストンという所にある「ユニクス寺院（和名『宦官寺』）には３本の塔が立っており、

３２枚のシリコンでできた円盤がささっている。

この寺院の僧には円盤をすべて別の塔に移し替えることが修行として課せられている。

その修行は,1970年1月1日午前0時0分0秒に始まっており、

計算では2038年1月19日3時14分7秒に３１枚の円盤を移し終え、最後の１枚にとりかかったところでタイムオーバーとなり、

その瞬間システムはリブートするといわれている。（hanoi.elの注釈より）

＊＊＊＊＊という所にある「＊＊＊の塔」には３本の塔が立っており、世界中から集められたコインでできた32枚の円盤がささっている。
この円盤はなにやら怪しげな動きを繰り返しているが
(なんと「ユニクスの塔」の１０００倍のスピードで)
「黒い箱」で覆われているため、その動きは小さな「窓」を通してしか、うかがい知ることができない。
どうやら円盤は隣の塔に移動しようとしているようだ。
そしてすべて移動し終わったとき、システムはフリーズする。

登録: 投稿 (Atom)

2020年6月26日金曜日

デスカ・ムトゥルー公式

2020年5月23日土曜日

ブレインダイブ

2018年5月6日日曜日

2の平方根

2018年5月3日木曜日

hanoiの塔