2017年11月19日日曜日

171119

A generalized Euler transform

定理 数列{f(n)} および{g(n)} を用いて、新たな数列{a(n)} を次のように定義する。

Product_{n>0} (1 - g(n)*x^n)^(-f(n)) = a(0) + a(1)*x + a(2)*x^2 + ... .

このとき、
 a(n) = (1/n) * Sum_{k=1..n} b(k)*a(n-k). 
(ただし、b(n) = Sum_{d|n} d*f(d)*g(d)^(n/d))

証明. Product_{n>0} (1 - g(n)*x^n)^(-f(n)) = exp(Sum_{n>0} (Sum_{d|n} d*f(d)*g(d)^(n/d)) * x^n/n)
を示せばよいが、これは
- Sum_{n>0} f(n) * log(1 - g(n)*x^n)
= Sum_{n>0} f(n) * (Sum_{m>0} (g(n)*x^n)^m/m)
= Sum_{n>0} (Sum_{d|n} d*f(d)*g(d)^(n/d)) * x^n/n
より明らか。Q.E.D.

g(n) = 1 としたのが、Euler transform である。

2017年11月18日土曜日

171118

Ruby


Expansion of Product_{k>=1} (1 ± k*x^k))^(±k)

それぞれ計算してみた。

def s(f_ary, g_ary, n)
  s = 0
  (1..n).each{|i| s += i * f_ary[i] * g_ary[i] ** (n / i) if n % i == 0}
  s
end

def A(f_ary, g_ary, n)
  ary = [1]
  a = [0] + (1..n).map{|i| s(f_ary, g_ary, i)}
  (1..n).each{|i| ary << (1..i).inject(0){|s, j| s + a[j] * ary[-j]} / i}
  ary
end

n = 50
ary1 = (0..n).map{|i| -i}
ary2 = (0..n).to_a
p A(ary1, ary1, n)
p A(ary1, ary2, n)
p A(ary2, ary1, n)
p A(ary2, ary2, n)

出力結果
[1, 1, 4, 13, 29, 81, 188, 456, 1030, 2405, 5295, 11611, 25246, 53552, 113332, 235685, 486011, 990840, 2006567, 4018010, 7992003, 15768511, 30875424, 60060509, 116042548, 222817961, 425200270, 806991037, 1522748592, 2858792520, 5339457208, 9924370365, 18359901997, 33812646935, 61999124321, 113204234852, 205862337221, 372878429033, 672835402816, 1209588044793, 2166753852049, 3867809679344, 6881037028716, 12201406676888, 21566414247820, 38000774004995, 66755792351581, 116923614457354, 204203782318876, 355635202391775, 617666801739931]
[1, -1, -4, -5, -3, 23, 44, 104, 70, -93, -465, -1155, -1882, -1904, 804, 6195, 18755, 33296, 47327, 35198, -28493, -176199, -453792, -805453, -1126396, -1028297, -18994, 2946491, 8248080, 16444480, 25436984, 30736635, 22263981, -16098311, -102681575, -256880020, -472968099, -714186361, -843996976, -644815585, 298761545, 2421641832, 6222259508, 11789810688, 18381745764, 23559771093, 22274637285, 6320449894, -36301921428, -117867266775, -248604757661]
[1, -1, -3, -6, 2, 9, 41, 46, 91, -110, -210, -713, -574, -1152, 792, 1066, 9317, 8553, 21302, 745, 8051, -82940, -76750, -276022, -82369, -404100, 381095, -38110, 2427272, 1126260, 6527840, 198507, 9754305, -14320206, 2879362, -60271740, -5154261, -143468194, 45076661, -234052476, 368886604, -247381667, 1282501567, -391275933, 3098609545, -1922335739, 5751247293, -8041862590, 10176770846, -25557378946, 18952181107]
[1, 1, 5, 14, 42, 103, 289, 690, 1771, 4206, 10142, 23449, 54786, 123528, 279480, 619206, 1366405, 2969071, 6425534, 13727775, 29187555, 61439660, 128620370, 267044222, 551527679, 1130806020, 2306746335, 4676096006, 9432394144, 18920266428, 37776372312, 75041364413, 148416537369, 292180587654, 572826984930, 1118261849716, 2174572373811, 4211951389306, 8128298517165, 15628368778820, 29944800382236, 57177924889211, 108820805664983, 206435020380189, 390397024961585, 736033705364187, 1383595389367133, 2593344028747990, 4847245569040526, 9035118348679538, 16796348691066595]

2017年11月9日木曜日

171109

Ruby


Product_{k=1..n} (1 - k^k*x^k) 等(2)

簡単な計算方法を見つけた。

def s(k, n)
  s = 0
  (1..n).each{|i| s += i ** (1 + k * n) if n % i == 0}
  s
end

def A(k, l, n)
  a_ary = [1]
  a = [0] + (1..n).map{|i| s(k, i)}
  (1..n).each{|i| a_ary << l * (1..i).inject(0){|s, j| s + a[j] * a_ary[-j]} / i}
  a_ary
end

p A(1, -1, 50)
p A(1,  1, 50)

出力結果
[1, -1, -4, -23, -229, -2761, -42615, -758499, -15702086, -365588036, -9516954786, -273061566624, -8575969258607, -292418459301779, -10762887030763337, -425243370397722674, -17953905924215881215, -806666656048846472309, -38431184040433830671913, -1935181289882115032490348, -102696392415846742681733803, -5728632608276744273452117182, -335107577316074301942345694886, -20512630873623057901876906465743, -1311322803795912839879249103895553, -87390960343889620272724433296491880, -6061384949468492645254259961399089464, -436878303197147196764997753948315233462, -32675044025947179003139330924063144267098, -2532599985989370726380519904538079256177793, -203178927579931810874025726965036433479741952, -16852125986543066536028316042434581330055228156, -1443540661889085555907194401730450877441654520045, -127574820869143586595809496206091343218785221447959, -11621234125615831378564183221418512234993617429041058, -1090196183005328639647915061369295772435373168383752681, -105234462011765494539519684733251330682780002215401072539, -10444032619061859497835254098020641143844512837807387209711, -1064902631219112666269332993851683972378340828286166920131461, -111474276281159827251053377800414613365575724197083049385370429, -11972088595272475908579728804082619667947506111569023902379561582, -1318310476289005221139456767233891094537237273824409848278526461933, -148748832043264334406644872125794105595871324181527240036587485159754, -17188011557131984039753154446985789282791436973154624682540639685440653, -2032795780843366162329190289675591210400612525094020643226076694024657889, -245939698538743537478667846250646039337163770333022466134040568157902292494, -30423641976898894071689041552479607626257428359671512045193457871897137467696, -3846200040360747504396179827366602271408814708121940123440320482354684713335810, -496695201984715682948564922534938106524773540501514053768423580824529347786758831, -65492741914370653035591205743688113605561186820898464463643223003610278456267562995, -8813674657487816832612715981635867854914273624507153623639538458830834786224586856770]
[1, 1, 5, 32, 304, 3537, 52010, 895397, 18016416, 410889848, 10523505770, 298220329546, 9274349837081, 313761671751672, 11474635626789410, 450964042480390679, 18954785687060988578, 848386888530723146912, 40285405287225043910550, 2022698192735125064374800, 107067613600574960842869576, 5958957516540411012538481312, 347874804978251035491293556717, 21255282815702806741512542156320, 1356552811381527011063310886545470, 90269224251818008284503526617607078, 6252407532636283837248750189467023717, 450077403312833906134664153832793562364, 33623078468794716158752737057969922475976, 2603279113832594183853952144206489719837940, 208641020463859049059313644666998258355430174, 17289127397779339597455206628731138571029463388, 1479694518137323492518182330267555690966057710386, 130664405112427023669744020431578357644166585768834, 11893676637179710201515160431837573422707677490346506, 1114962549339627610139884413141761124617651310248910807, 107553299717906401134057923370737862686988012597837335428, 10667456623847661239614784713395895708825315080311903974842, 1087038281322044541723912129364763989898375730124545587816420, 113727624541296280610995388843934779805112107590089608738821866, 12207607672244566843332717756498509768573329189287764690816378001, 1343567949879928688576883932845039142064874998015038262382867301310, 151526235731705276942576654565683947618697905104015802013110682919256, 17500984254427353429088809491108129599200863753155515140181675937796866, 2068914981048485504735305132601459341359908002379365151497580784456356578, 250206395748750271585510108940161076975800606600455914501836198285139561506, 30939269917163886094342998721746598367612901564113128379988190173340349015884, 3909916438944027445264015931163420219796204883134594411865752491610605996942362, 504742036355325700420716147919073362233829975908395870482808863420263975649192158, 66530881888898978050425464434805233005142718980300319762710280722182219337819485262, 8950431855499888765825807120133883814986861716725771387614680145772266006338061859966]

2017年11月6日月曜日

171106

Ruby


8765432 * 8 = 70123456

数遊びをしてみる。

def show(ary, k, n)
  ary.each{|i| puts "#{i} * #{k} = #{i * k}"}
end

n = 20
ary = (0..n).map{|i| ((9 * i + 8) * 10 ** i - 8) / 81}
show(ary, 8, n)
show(ary, 9, n)
ary = (0..n).map{|i| ((-9 * i + 82) * 10 ** i - 1) / 81}
show(ary, 8, n)
show(ary, 9, n)

出力結果
0 * 8 = 0
2 * 8 = 16
32 * 8 = 256
432 * 8 = 3456
5432 * 8 = 43456
65432 * 8 = 523456
765432 * 8 = 6123456
8765432 * 8 = 70123456
98765432 * 8 = 790123456
1098765432 * 8 = 8790123456
12098765432 * 8 = 96790123456
132098765432 * 8 = 1056790123456
1432098765432 * 8 = 11456790123456
15432098765432 * 8 = 123456790123456
165432098765432 * 8 = 1323456790123456
1765432098765432 * 8 = 14123456790123456
18765432098765432 * 8 = 150123456790123456
198765432098765432 * 8 = 1590123456790123456
2098765432098765432 * 8 = 16790123456790123456
22098765432098765432 * 8 = 176790123456790123456
232098765432098765432 * 8 = 1856790123456790123456
0 * 9 = 0
2 * 9 = 18
32 * 9 = 288
432 * 9 = 3888
5432 * 9 = 48888
65432 * 9 = 588888
765432 * 9 = 6888888
8765432 * 9 = 78888888
98765432 * 9 = 888888888
1098765432 * 9 = 9888888888
12098765432 * 9 = 108888888888
132098765432 * 9 = 1188888888888
1432098765432 * 9 = 12888888888888
15432098765432 * 9 = 138888888888888
165432098765432 * 9 = 1488888888888888
1765432098765432 * 9 = 15888888888888888
18765432098765432 * 9 = 168888888888888888
198765432098765432 * 9 = 1788888888888888888
2098765432098765432 * 9 = 18888888888888888888
22098765432098765432 * 9 = 198888888888888888888
232098765432098765432 * 9 = 2088888888888888888888
1 * 8 = 8
9 * 8 = 72
79 * 8 = 632
679 * 8 = 5432
5679 * 8 = 45432
45679 * 8 = 365432
345679 * 8 = 2765432
2345679 * 8 = 18765432
12345679 * 8 = 98765432
12345679 * 8 = 98765432
-987654321 * 8 = -7901234568
-20987654321 * 8 = -167901234568
-320987654321 * 8 = -2567901234568
-4320987654321 * 8 = -34567901234568
-54320987654321 * 8 = -434567901234568
-654320987654321 * 8 = -5234567901234568
-7654320987654321 * 8 = -61234567901234568
-87654320987654321 * 8 = -701234567901234568
-987654320987654321 * 8 = -7901234567901234568
-10987654320987654321 * 8 = -87901234567901234568
-120987654320987654321 * 8 = -967901234567901234568
1 * 9 = 9
9 * 9 = 81
79 * 9 = 711
679 * 9 = 6111
5679 * 9 = 51111
45679 * 9 = 411111
345679 * 9 = 3111111
2345679 * 9 = 21111111
12345679 * 9 = 111111111
12345679 * 9 = 111111111
-987654321 * 9 = -8888888889
-20987654321 * 9 = -188888888889
-320987654321 * 9 = -2888888888889
-4320987654321 * 9 = -38888888888889
-54320987654321 * 9 = -488888888888889
-654320987654321 * 9 = -5888888888888889
-7654320987654321 * 9 = -68888888888888889
-87654320987654321 * 9 = -788888888888888889
-987654320987654321 * 9 = -8888888888888888889
-10987654320987654321 * 9 = -98888888888888888889
-120987654320987654321 * 9 = -1088888888888888888889