2016年2月28日日曜日

160228(3)

Ruby


Borwein integral

https://en.wikipedia.org/wiki/Borwein_integral
を見ると、ボールウェイン積分は
1 / 3 + 1 / 5 + … + 1 / (2k + 1) > n (n = 1, 2)
となるとき、規則性が崩れるらしい。

このような奇数については、
オンライン整数列大辞典の
A056053(http://oeis.org/A056053/list)
を見れば詳しく載っているが、
自分で確かめてみた。

def f(n)
  i = 3
  s = 1r / i
  while s < n
    i += 2
    s += 1r / i
  end
  i
end

# 和が0, 1, 2, … を超える
def A056053(n)
  (0..n - 1).map{|i| f(i)}
end

p A056053(3)

出力結果
[3, 15, 113]

160228(2)

Ruby


Ei(1) - γ

160227 分で
e - 1 + γ - Ei(1) = 1 / (0! + 1! + 2!) + 1 / (1! + 2! + 3!) + 1 / (2! + 3! + 4!) + …
となることを確認した。

今回は
Ei(1) - γ = 1 / (1 1!) + 1 / (2 2!) + 1 / (3 3!) + …
を確認する。
(厳密には近似値の比較なのですが…。)

まず、WolframAlpha でEi(1) - γ の値を確認してみる。
http://www.wolframalpha.com/input/?i=Ei(1)+-+%CE%B3
によると、
1.317902151454403894860008844249231837974901245792783992840…
となる。

一方、1 / (1 1!) + 1 / (2 2!) + 1 / (3 3!) + … は以下の計算により、
1.317902151454403894860008844249231837974901245792783992840…
となる。

よって、両辺は一致する。

require 'bigdecimal'

def f(n)
  return 1 if n == 0
  (1..n).inject(:*)
end

def g(n)
  n * f(n)
end

def h(n)
  (1..n).inject(0){|s, i| s += 1r / g(i)}
end

(1..100).each{|i| p BigDecimal(h(i), 100).to_s("F")}

出力結果
"1.0"
"1.25"
"1.305555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555556"
"1.315972222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222"
"1.317638888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888889"
"1.31787037037037037037037037037037037037037037037037037037037037037037037037037037037037037037037037"
"1.317898715041572184429327286470143613000755857898715041572184429327286470143613000755857898715041572"
"1.317901815239984882842025699168556311413454270597127739984882842025699168556311413454270597127739985"
"1.317902121432420704907477394249881022367794854567341339828112314884801657288429775202261974748747235"
"1.317902148989739928893368046807200246353685507124660563814002967442120881274320427759581198734637888"
"1.317902151267204327569887935448301008666569032129397689763250128810494370859931225491591051956612322"
"1.317902151441177302468788760275051761343247634733926220217706509192800679092165383651675137966624258"
"1.31790215145353041311249769458227666685875144083602292060500518708976917435125893334351542809751268"
"1.317902151454349752083764103490408931000085876955039538487836221848241574547015138170015039177622626"
"1.317902151454400733175309568933581605213324464091333905822767930677657635003639968692552792755940578"
"1.317902151454403720348642311049392504093006412556351153908799085491881232296020329855982739254670146"
"1.317902151454403885728480801962378574619217177869293285290724685758412642526740349851189933524496004"
"1.3179021514544038944058180067325043869616418167900340761348380660193108955326731904064940147053202"
"1.317902151454403894838483019712732266801430302941206747146455907694369534186708622899556268060596753"
"1.317902151454403894859034607829293091093820256033387449019507755173934819522775305942976725094972389"
"1.317902151454403894859966652641835532104812997670221040941188111068699685070896243949481054212177633"
"1.317902151454403894860007092602710307437934583567686961251839531469092375518232069772077316425940671"
"1.317902151454403894860008774415827972952733590920700666822414826835460313495247926422544457765643482"
"1.31790215145440389486000884157156010195766480128375503353790654869904792212974682347629574986774967"
"1.317902151454403894860008844150340215711454159761696321219781430818609686301311581123159799484470548"
"1.317902151454403894860008844245709302758561754379963380675472069950250284088721520385247966999881822"
"1.317902151454403894860008844249110669374782327027528460985277223060569427494033809028340274757633117"
"1.317902151454403894860008844249227808276106249810033891046966941343705418402124921009671259846229143"
"1.317902151454403894860008844249231708263308473160699945793372782142668328919873495487052077423495123"
"1.31790215145440389486000884424923183392956276702422140755742363701285713381433428288687879265654036"
"1.317902151454403894860008844249231837852546772035569632170245203762186649055576555126207410197634384"
"1.317902151454403894860008844249231837971308983124780369438797419161824554302137600477202710142726098"
"1.317902151454403894860008844249231837974798781797741566493520716584036136458143067374568963217329344"
"1.317902151454403894860008844249231837974898404078198071253733405870310342523150143851742913348351755"
"1.317902151454403894860008844249231837974901169104757680365445431532133463344546258627435904617294418"
"1.317902151454403894860008844249231837974901243777542854994233950743679612440803098146841193733353826"
"1.3179021514544038948600088442492318379749012457411807412518207927390161072307704072941739843894372"
"1.317902151454403894860008844249231837974901245791495562437091369715350906612507796794486528194336843"
"1.317902151454403894860008844249231837974901245792752605964402534689118639930394726972666591747647945"
"1.317902151454403894860008844249231837974901245792783246400380744335354228430018220895759730796759903"
"1.317902151454403894860008844249231837974901245792783975500582486385234908703655900703566825122735203"
"1.317902151454403894860008844249231837974901245792783992446788989460090412043349293488215402711944379"
"1.317902151454403894860008844249231837974901245792783992831721749400135804763883161793761773863240639"
"1.317902151454403894860008844249231837974901245792783992840271392312027308837737994612531657106786992"
"1.317902151454403894860008844249231837974901245792783992840457162330853593370700766288593817532819604"
"1.317902151454403894860008844249231837974901245792783992840461113016509161803585135251459033609932774"
"1.317902151454403894860008844249231837974901245792783992840461195285200948199199748638644094696192261"
"1.317902151454403894860008844249231837974901245792783992840461196963425129605707512019372262174948422"
"1.317902151454403894860008844249231837974901245792783992840461196996975633857066267805409310087893152"
"1.317902151454403894860008844249231837974901245792783992840461196997633223740392899418815636226986869"
"1.3179021514544038948600088442492318379749012457927839928404611969976458648377271291691694679482305"
"1.317902151454403894860008844249231837974901245792783992840461196997646103260790755543898774685576441"
"1.317902151454403894860008844249231837974901245792783992840461196997646107674460854714951079402679321"
"1.317902151454403894860008844249231837974901245792783992840461196997646107754681881894671851744931191"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756113926677384222556991224"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139042258713680591003757"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139475152697814062811914"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482487702895991436487"
"1.31790215145440389486000884424923183797490124579278399284046119699764610775613948260991786144729981"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611920828936715347"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953126181908826"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953638703229534"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646709357496"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646832498625"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834363958"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834391792"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392201"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"
"1.317902151454403894860008844249231837974901245792783992840461196997646107756139482611953646834392207"

160228

φ(n) / (x^n - 1) の和(2)

φ(1) = 1 より、
先程の式を次のように変形する。
x / (x - 1)^2 = φ(1) / (x^1 - 1) + φ(2) / (x^2 - 1) + φ(3) / (x^3 - 1) + … (ただし、|x| > 1)
q = 1 / x とおくと、
q / (1 - q)^2 = φ(1) q / (1 - q^1) + φ(2) q^2 / (1 - q^2) + φ(3) q^3 / (1 - q^3) + …
この式は、
https://en.wikipedia.org/wiki/Lambert_series
に載っている。
書籍では、例えば
岩波数学公式 II 級数・フーリエ解析§12
に載っている。

2016年2月27日土曜日

160227(3)

Ruby


φ(n) / (x^n - 1) の和(1)

数学発想ゼミナールの5.2.6 を言い換えることで以下のことが言える。

|x| > 1 とする。このとき、
(1 / (x - 1))^2 = φ(2) / (x^2 - 1) + φ(3) / (x^3 - 1) + φ(4) / (x^4 - 1) + …

証明は次の通り。
(p, q) = 1, p + q = n を満たす(p, q) がφ(n) 個あるので、
φ(2) / (x^2 - 1) + φ(3) / (x^3 - 1) + φ(4) / (x^4 - 1) + …
= Σ(p, q) 1 / (x^(p + q) - 1) (ただし、(p, q) = 1)
また、
Σ(p, q) 1 / (x^(p + q) - 1) (ただし、(p, q) = 1)
= Σ(p, q) (1 / x^(p + q) + 1 / x^(2p + 2q) + 1 / x^(3p + 3q) + …) (ただし、(p, q) = 1)
= ΣΣ 1 / x^(i + j) ({(np, nq) | (p, q) = 1, n は自然数} = {(i, j) | i, j は自然数} を利用)
= (1 / (x - 1))^2

このことを確認してみた。

def phi(n)
  (1..n).count{|i| i.gcd(n) == 1}
end

def f(x, n)
  s = 0
  ary = []
  # mは2以上
  (2..n).each{|m|
    s += phi(m).to_r / (x ** m - 1)
    ary << s
  }
  ary
end

(2..11).each{|i| p f(i, 15)}

出力結果
[(1/3), (13/21), (79/105), (2869/3255), (8917/9765), (1191049/1240155), (20578541/21082635), (1520304323/1539032355), (16789542493/16929355905), (34537487042221/34654391537535), (449427387314429/450507089987955), (3686665814572343399/3690103574091339405), (158584741893919291187/158674453685927594415), (23952145775426455461197/23959842506575066756665)]
[(1/8), (21/104), (59/260), (7659/31460), (27109/110110), (29960467/120350230), (4925551611/19737437720), (3733197362847/14941240354040), (227786779796287/911415661596440), (20180315525204510651/80726819394581480120), (1473207388735201025589/5893057815804448048760), (1174418833558436411447845389/4697715861504489610997570360), (642410325457742053171036613673/2569650576242955817215670986920), (2930040028807106686854654805314713/11720176278244121482320675371342120)]
[(1/15), (31/315), (569/5355), (201169/1826055), (875597/7912905), (4797461027/43212374205), (411208441701/3701860056895), (5134172652055553/46210319090220285), (1052541530773316201/9473115413495158425), (1471590943767082471129051/13244372132722994489150925), (118218059484889671444570557/1063964561328747223961790975), (2644497441890682492018461715012797/23800483994355331804827382591970475), (8666019860381680780534706315495770559/77994186049502422324419332753887246575), (1299409103057383018169917200017414308044737/11694682238820541710590408011116115413195225)]
[(1/24), (43/744), (295/4836), (235231/3776916), (1237501/19828809), (48398750489/774552937158), (60605165778089/969740277321816), (954638889087324443/15274379108095923816), (497370120791770489759/7957951515317976308136), (6071432377857675208314065869/97142960843983511650681704216), (3648931815638219269371510870755/58382919467234090502059704233816), (1113565791801899980681971715311759886103/17817053045473267478790752348183804410296), (14499740403113737813854294481157989403318117/231995847705107415841334386325701317226464216), (4569172714734103591681577878983892427079997916069/73106763524681153987337133153341324785720630210136)]
[(1/35), (57/1505), (439/11137), (3457773/86590175), (107306033/2684295425), (6010964024081/150285647959475), (7796684542006677/194920485403439075), (365459434178932090251/9136507912315399762475), (406026102866255183166409/10150660290582409136109725), (29461035175921469031070024244549/736525931945748453877140477371975), (5307195294785902673992542021229347/132679885740512685762724877423722925), (13863131083041005729347823776800932877986661/346578277920399575594559303331925325113158775), (3880803333421651855290854924692256338761424139547/97020083386202895993214147696829179736202327997175), (5457849267149117256084869282436863874484766683758490889/136446231691937553040872574110537350334782604227715001925)]
[(1/48), (73/2736), (941/34200), (2658541/95794200), (4766137/171631275), (654357297484/23557593912675), (4191481309901571/150894241541987600), (1483704304399834621409/53413392726791228660400), (3117264332660818182542009/112221538118988371415500400), (1027308541511400166303977681518113/36983108058508014131149555705282800), (805752341108212294866787598989106309/29007084420556452416864968191510142800), (13011424551729575942680458844104482425243827509/468411284045169099754678958834014204433957662800), (1339435078055280063621486777471460777383479738344037/48219662813461842636045916059249924247044903681620400), (1048143408423116818241640109915856361410487809642437192469/37733162703659953510434662531930318497622966793318060634800)]
[(1/63), (13/657), (6061/298935), (28542361/1399314735), (232503301/11394419985), (487662896715361/23895819265962735), (1997978229302434469/97901171532649325295), (524784117298408504680203/25714428011251073834008815), (1910739319868400890524411543/93626232388965159829626095415), (2344732387769102038146063591342334009/114891887460425199016335551943082142895), (9456305746843831033145461450278446210621/463358982127894827632881280986450282295535), (742665581111536213806675594978940850161586038034321/36390613477367529727321746610221873308920392941584935), (173053705725435103925981965130153452653554984740055251247/8479631580655749674471331429874070252824703202069296798895), (2545488663486864852054954069925439556905824319673012037038732287/124728944511076359997470361592892298999729490152708985315475088695)]
[(1/80), (111/7280), (2321/149240), (17205921/1101540440), (628167427/40206226060), (187796621208731/12019068290359130), (4929315028287479481/315476504485346444240), (2623241107999857166068231/167887446868471302577645040), (15490239880033878611909171347/991375373758323041720993961200), (60762518866414456420373552741504032997/3888801212226651794795797800178154901200), (393801885130182303012979684015840268733867/25203320656440930282071565542954621914677200), (125123944405749824204878182253902289084200553089713847/8007932442125052244980092329577261637208377789841965200), (59846407238441479722721412614131480869534890279204772387649/3830170063271086113617243220959815509291855471748042429264400), (2293132452151182328974366845052801892581129339828453920449065291089/146760476937725739043113477425031633436731163728606343588469273488400)]
[(1/99), (133/10989), (13655/1109889), (152213989/12331976679), (4617905807/374069959263), (5131255319094419/415633246506671193), (1555086385339056959/125962063585249048521), (4669931350019075330796499/378264454832693648455708563), (466997820063987052757732662247/37826823747724197539219312008563), (5188864709355549436994583840459487491487/420298041637176992241578555924120076443493), (1556816651635599352021175081477753884397455/126102148795445133338905129763779178086879521), (1729796279763073609900606312832486580673158042573128533/140113498661591692360028428056050319526559047869101457831), (17297964527511083969683438804723773275311254899914643434381547/1401135126729415585191976640588931251315910005250062447411457831), (4675172299701990466589192004979871259522638909132846842838333136016727/378688956275890916762370302398522920185761159319379986097550862248501563)]
[(1/120), (157/15960), (971/97356), (78384487/7839591900), (4350830231/435097350450), (8478797893673897/847881603476872650), (248293580841626988203/24829364876216738682600), (440198063431226969906280599/44019807183490522493210761800), (5907898300420519275273058095751/590789832209626302381381634117800), (168559233979485634204812569303611949375611/16855923400713006805622901539012129153785800), (2447648636928069408960397815141711525100884341/244764863701753571824450153247995127442123601800), (8449946932508755159902810607113000554046108238672855842173/844994693252389928766019879162951091907166846608893160707400), (13722130772077556071023915236349958931506735062219725071681696673/1372213077208046829410931428388970329631897364380426479360728789400), (140846435394735573677517666529787382906712878478021416485606326104601259/14084643539473849124923274023881501276336755777412846491922492940073406600)]

160227(2)

Ruby


隣り合う階乗の和(5)

1 / ((0 + 2)^(k - 1) 0!) + 1 / ((1 + 2)^(k - 1) 1!) + 1 / ((2 + 2)^(k - 1) 2!) + … の和を求めてみた。

require 'bigdecimal'

def f(n)
  return 1 if n == 0
  (1..n).inject(:*)
end

# 階乗の和で表現
def g(k, n)
  return f(n - 1) if k == 1
  return f(n - 1) + f(n) if k == 2
  return f(n - 1) + f(n) + f(n + 1) if k == 3
  return f(n - 1) + f(n)            +     f(n + 2) if k == 4
  return f(n - 1) + f(n) + f(n + 1) - 2 * f(n + 2) + f(n + 3) if k == 5
end

def h(k, n)
  (1..n).inject(0){|s, i| s += 1r / g(k, i)}
end

def i(k, n)
  (1..n).map{|i| g(k, i)}
end

n = 40
(1..5).each{|k| p i(k, n)}

(1..5).each{|k|
  (1..n).each{|i|
    p BigDecimal(h(k, i), 40).to_s("F")
  }
}

出力結果
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000, 51090942171709440000, 1124000727777607680000, 25852016738884976640000, 620448401733239439360000, 15511210043330985984000000, 403291461126605635584000000, 10888869450418352160768000000, 304888344611713860501504000000, 8841761993739701954543616000000, 265252859812191058636308480000000, 8222838654177922817725562880000000, 263130836933693530167218012160000000, 8683317618811886495518194401280000000, 295232799039604140847618609643520000000, 10333147966386144929666651337523200000000, 371993326789901217467999448150835200000000, 13763753091226345046315979581580902400000000, 523022617466601111760007224100074291200000000, 20397882081197443358640281739902897356800000000]
[2, 3, 8, 30, 144, 840, 5760, 45360, 403200, 3991680, 43545600, 518918400, 6706022400, 93405312000, 1394852659200, 22230464256000, 376610217984000, 6758061133824000, 128047474114560000, 2554547108585472000, 53523844179886080000, 1175091669949317120000, 26976017466662584320000, 646300418472124416000000, 16131658445064225423360000, 418802671169936621568000000, 11292160911544957796352000000, 315777214062132212662272000000, 9146650338351415815045120000000, 274094621805930760590852096000000, 8488091513990113876361871360000000, 271353675587871452984943575040000000, 8946448455745580025685412413440000000, 303916116658416027343136804044800000000, 10628380765425749070514269947166720000000, 382326474756287362397666099488358400000000, 14135746418016246263783979029731737600000000, 536786370557827456806323203681655193600000000, 20920904698664044470400288964002971648000000000, 836313165329095177704251551336018791628800000000]
[4, 9, 32, 150, 864, 5880, 46080, 408240, 4032000, 43908480, 522547200, 6745939200, 93884313600, 1401079680000, 22317642547200, 377917892352000, 6778983923712000, 128403161542656000, 2560949482291200000, 53645489280294912000, 1177524571957493760000, 27027108408834293760000, 647424419199902023680000, 16157510461803110400000000, 419423119571669861007360000, 11307672121588288782336000000, 316180505523258818297856000000, 9157539207801834167205888000000, 274399510150542474451353600000000, 8496933275983853578316414976000000, 271618928447683644043579883520000000, 8954671294399757948503137976320000000, 304179247495349720873304022056960000000, 10637064083044560957009788141568000000000, 382621707555326966538513718098001920000000, 14146079565982632408713645681069260800000000, 537158363884617358023791203129806028800000000, 20934668451755270815446604943584552550400000000, 836836187946561778816011558560118865920000000000, 34288839778492902285874313604776770456780800000000]
[8, 27, 128, 750, 5184, 41160, 368640, 3674160, 40320000, 482993280, 6270566400, 87697209600, 1314380390400, 21016195200000, 357082280755200, 6424604169984000, 122021710626816000, 2439660069310464000, 51218989645824000000, 1126555274886193152000, 25905540583064862720000, 621623493403188756480000, 15538186060797648568320000, 403937761545077760000000000, 10905001108863416386191360000, 305307147282883797123072000000, 8853054154651246912339968000000, 265568637026253190848970752000000, 8231985304516274233540608000000000, 263404931555499460927808864256000000, 8691805710325876609394556272640000000, 295504152715192012300603553218560000000, 10342094414841890509692336749936640000000, 372297242906559633495342584954880000000000, 13774381471991770795386493851528069120000000, 523404943941357399122404890199562649600000000, 20412017827615459604904065718932629094400000000, 816452069618455561802417592799797549465600000000, 33473447517862471152640462342404754636800000000000, 1405842430918208993720846857795847588728012800000000]
[16, 81, 512, 3750, 31104, 288120, 2949120, 33067440, 403200000, 5312926080, 75246796800, 1140063724800, 18401325465600, 315242928000000, 5713316492083200, 109218270889728000, 2196390791282688000, 46353541316898816000, 1024379792916480000000, 23657660772610056192000, 569921892827426979840000, 14297340348273341399040000, 372916465459143565639680000, 10098444038626944000000000000, 283530028830448826040975360000, 8243292976637862522322944000000, 247885516330234913545519104000000, 7701490473761342534620151808000000, 246959559135488227006218240000000000, 8165552878220483288762074791936000000, 278137782730428051500625800724480000000, 9751637039601336405919917256212480000000, 351631210104624277329539449497845760000000, 13030403501729587172336990473420800000000000, 495877732991703748633913778655010488320000000, 19365982925830223767528980937383818035200000000, 775656677449387464986354497319439905587200000000, 31841630715119766910294286119192104429158400000000, 1338937900714498846105618493696190185472000000000000, 57639539667646568742554721169629751137848524800000000]
"1.0"
"2.0"
"2.5"
"2.666666666666666666666666666666666666667"
"2.708333333333333333333333333333333333333"
"2.716666666666666666666666666666666666667"
"2.718055555555555555555555555555555555556"
"2.718253968253968253968253968253968253968"
"2.71827876984126984126984126984126984127"
"2.718281525573192239858906525573192239859"
"2.718281801146384479717813051146384479718"
"2.71828182619849286515953182619849286516"
"2.71828182828616856394634172411950189728"
"2.718281828446759002314557870113425668981"
"2.71828182845822974791228759482727736696"
"2.718281828458994464285469576474867480158"
"2.718281828459042259058793450327841862233"
"2.718281828459045070516047795848605061179"
"2.718281828459045226708117481710869683343"
"2.718281828459045234928752728335199400299"
"2.718281828459045235339784490666415886146"
"2.718281828459045235359357431729807147377"
"2.718281828459045235360247110869052204706"
"2.718281828459045235360285792570758511546"
"2.718281828459045235360287404308329607665"
"2.718281828459045235360287468777832451509"
"2.718281828459045235360287471257428714"
"2.718281828459045235360287471349265613372"
"2.718281828459045235360287471352545502609"
"2.718281828459045235360287471352658602238"
"2.718281828459045235360287471352662372226"
"2.718281828459045235360287471352662493838"
"2.718281828459045235360287471352662497639"
"2.718281828459045235360287471352662497754"
"2.718281828459045235360287471352662497757"
"2.718281828459045235360287471352662497757"
"2.718281828459045235360287471352662497757"
"2.718281828459045235360287471352662497757"
"2.718281828459045235360287471352662497757"
"2.718281828459045235360287471352662497757"
"0.5"
"0.8333333333333333333333333333333333333333"
"0.9583333333333333333333333333333333333333"
"0.9916666666666666666666666666666666666667"
"0.9986111111111111111111111111111111111111"
"0.9998015873015873015873015873015873015873"
"0.9999751984126984126984126984126984126984"
"0.9999972442680776014109347442680776014109"
"0.9999997244268077601410934744268077601411"
"0.9999999749478916145582812249478916145583"
"0.9999999979123243012131901020789909678799"
"0.9999999998394095616317838540060762282985"
"0.9999999999885292544022702752861483020213"
"0.9999999999992352836268180183524098868014"
"0.9999999999999522052266761261470256179251"
"0.9999999999999971885427456544792368010544"
"0.9999999999999998438079303141377353778364"
"0.999999999999999991779364753375670283044"
"0.9999999999999999995889682376687835141522"
"0.9999999999999999999804270589366087387692"
"0.9999999999999999999991103208607549426713"
"0.9999999999999999999999613182982936931596"
"0.9999999999999999999999983882624289038817"
"0.9999999999999999999999999355304971561553"
"0.9999999999999999999999999975204037367752"
"0.999999999999999999999999999908163101362"
"0.9999999999999999999999999999967201107629"
"0.9999999999999999999999999999998869003711"
"0.9999999999999999999999999999999962300124"
"0.9999999999999999999999999999999998783875"
"0.9999999999999999999999999999999999961996"
"0.9999999999999999999999999999999999998848"
"0.9999999999999999999999999999999999999966"
"0.9999999999999999999999999999999999999999"
"1.0"
"1.0"
"1.0"
"1.0"
"1.0"
"1.0"
"0.25"
"0.3611111111111111111111111111111111111111"
"0.3923611111111111111111111111111111111111"
"0.3990277777777777777777777777777777777778"
"0.4001851851851851851851851851851851851852"
"0.4003552532123960695389266817838246409675"
"0.4003769546012849584278155706727135298564"
"0.4003794041407715349514291313233112174911"
"0.4003796521566445508244450043391842333641"
"0.400379674931288537589643890750191856493"
"0.4003796768449912614775529638444501359364"
"0.4003796769932285892020601755311490021225"
"0.4003796770038799958285234913368684359598"
"0.4003796770045937311101600075412858749452"
"0.4003796770046385387101511392784493581404"
"0.4003796770046411847875669938862264865598"
"0.400379677004641332302299474978365296381"
"0.4003796770046413400902697086224671334972"
"0.4003796770046413404807498828371227950526"
"0.4003796770046413404993907790879716152724"
"0.400379677004641340500240018266341897268"
"0.4003796770046413405002770181549305385936"
"0.400379677004641340500278562736769505707"
"0.4003796770046413405002786246274922357979"
"0.4003796770046413405002786270117194119756"
"0.4003796770046413405002786271001549439974"
"0.4003796770046413405002786271033176943331"
"0.4003796770046413405002786271034268939748"
"0.4003796770046413405002786271034305382961"
"0.4003796770046413405002786271034306559857"
"0.4003796770046413405002786271034306596673"
"0.400379677004641340500278627103430659779"
"0.4003796770046413405002786271034306597822"
"0.4003796770046413405002786271034306597823"
"0.4003796770046413405002786271034306597823"
"0.4003796770046413405002786271034306597823"
"0.4003796770046413405002786271034306597823"
"0.4003796770046413405002786271034306597823"
"0.4003796770046413405002786271034306597823"
"0.4003796770046413405002786271034306597823"
"0.125"
"0.162037037037037037037037037037037037037"
"0.169849537037037037037037037037037037037"
"0.1711828703703703703703703703703703703704"
"0.1713757716049382716049382716049382716049"
"0.1714000670373969693697584854047439081453"
"0.1714027797110080804808695965158550192564"
"0.1714030518820621445390488810325880956602"
"0.1714030766836494461263504683341753972475"
"0.1714030787540716267413685489169942720774"
"0.1714030789135468537320276383415157953644"
"0.1714030789249497250954512700097234004556"
"0.1714030789257105398544843639958462171583"
"0.1714030789257581222065934650761407130906"
"0.1714030789257609226815929108097134307903"
"0.1714030789257610783332056081395826736385"
"0.1714030789257610865284685237558126075175"
"0.1714030789257610869383616939476074410499"
"0.1714030789257610869578857026583402241277"
"0.1714030789257610869587733643845711203287"
"0.1714030789257610869588119661654061331466"
"0.1714030789257610869588135748562143349434"
"0.1714030789257610869588136392137909585731"
"0.1714030789257610869588136416894198677768"
"0.1714030789257610869588136417811209130144"
"0.1714030789257610869588136417843963030892"
"0.1714030789257610869588136417845092584584"
"0.1714030789257610869588136417845130239633"
"0.1714030789257610869588136417845131454406"
"0.1714030789257610869588136417845131492371"
"0.1714030789257610869588136417845131493521"
"0.1714030789257610869588136417845131493555"
"0.1714030789257610869588136417845131493556"
"0.1714030789257610869588136417845131493556"
"0.1714030789257610869588136417845131493556"
"0.1714030789257610869588136417845131493556"
"0.1714030789257610869588136417845131493556"
"0.1714030789257610869588136417845131493556"
"0.1714030789257610869588136417845131493556"
"0.1714030789257610869588136417845131493556"
"0.0625"
"0.07484567901234567901234567901234567901235"
"0.07679880401234567901234567901234567901235"
"0.07706547067901234567901234567901234567901"
"0.07709762088477366255144032921810699588477"
"0.07710109166083919080355750261807922967625"
"0.07710143074504057969244639150696811856514"
"0.07710146098626880903224408978660512705446"
"0.07710146346642753919097424851676385721319"
"0.07710146365464773742870316493338375492499"
"0.07710146366793733967792475571876054853224"
"0.07710146366881448362895734277016113353926"
"0.07710146366886882754031684948345562044659"
"0.07710146366887199969712412288880858684208"
"0.07710146366887217472681158824715688169831"
"0.07710146366887218388278880573714919010115"
"0.07710146366887218433808118993805085309442"
"0.07710146366887218435965451468498742328034"
"0.07710146366887218436063071512052406243423"
"0.07710146366887218436067298472653505749142"
"0.07710146366887218436067473935293664898314"
"0.07710146366887218436067480929601526645257"
"0.07710146366887218436067481197758095910381"
"0.07710146366887218436067481207660611547195"
"0.07710146366887218436067481208013307875032"
"0.07710146366887218436067481208025438949384"
"0.07710146366887218436067481208025842361416"
"0.07710146366887218436067481208025855345916"
"0.07710146366887218436067481208025855750841"
"0.07710146366887218436067481208025855763087"
"0.07710146366887218436067481208025855763447"
"0.07710146366887218436067481208025855763457"
"0.07710146366887218436067481208025855763457"
"0.07710146366887218436067481208025855763457"
"0.07710146366887218436067481208025855763457"
"0.07710146366887218436067481208025855763457"
"0.07710146366887218436067481208025855763457"
"0.07710146366887218436067481208025855763457"
"0.07710146366887218436067481208025855763457"
"0.07710146366887218436067481208025855763457"

160227

隣り合う階乗の和(4)

n!
(n + 2)n! = n! + (n + 1)!
(n + 2)^2 n! = n! + (n + 1)! + (n + 2)!
より、
e = 1 / 0! + 1 / 1! + 1 / 2! + …
1 = 1 / (0! + 1!) + 1 / (1! + 2!) + 1 / (2! + 3!) + …
e - 1 + γ - Ei(1) = 1 / (0! + 1! + 2!) + 1 / (1! + 2! + 3!) + 1 / (2! + 3! + 4!) + …
となる。

なお、WolframAlpha でe - 1 + γ - Ei(1) の値を確認すると、
以前計算した1 / (0! + 1! + 2!) + 1 / (1! + 2! + 3!) + 1 / (2! + 3! + 4!) + … の値と一致している。
http://www.wolframalpha.com/input/?i=exp(1)+-+1+%2B+%CE%B3+-+Ei(1)

2016年2月25日木曜日

160225(3)

Ruby


隣り合う階乗の和(3)

e = 1 / 0! + 1 / 1! + 1 / 2! + …
1 = 1 / (0! + 1!) + 1 / (1! + 2!) + 1 / (2! + 3!) + …
? = 1 / (0! + 1! + 2!) + 1 / (1! + 2! + 3!) + 1 / (2! + 3! + 4!) + …

以下の計算により、
? はおよそ
0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422
くらいだとわかる。
(実際は、
0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077421…
である。)

require 'bigdecimal'

def f(n)
  return 1 if n == 0
  (1..n).inject(:*)
end

def g(n)
  f(n - 1) + f(n) + f(n + 1)
end

def h(n)
  (1..n).inject(0){|s, i| s += 1r / g(i)}
end

(1..100).each{|i| p BigDecimal(h(i), 100).to_s("F")}

出力結果
"0.25"
"0.3611111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111"
"0.3923611111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111"
"0.3990277777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777778"
"0.4001851851851851851851851851851851851851851851851851851851851851851851851851851851851851851851851852"
"0.4003552532123960695389266817838246409674981103552532123960695389266817838246409674981103552532123961"
"0.400376954601284958427815570672713529856386999244142101284958427815570672713529856386999244142101285"
"0.4003794041407715349514291313233112174911116710058509000307942106883905825704767503709302651101592901"
"0.4003796521566445508244450043391842333641275440217239159038100837042635984434926233868032809831751631"
"0.400379674931288537589643890750191856492962794069095175396281697387998494299600600706901813202919504"
"0.4003796768449912614775529638444501359364274227189090103953018815933678848541763404678267593130507993"
"0.4003796769932285892020601755311490021224730959440694150428860163569898279632989367699102408837118572"
"0.4003796770038799958285234913368684359598207654912854475196894682171310305081295995144051849251411594"
"0.4003796770045937311101600075412858749451609853994065902087333918289558769008772268299337350215924904"
"0.4003796770046385387101511392784493581403902123746653114992007140423098362865826442813829325025360031"
"0.4003796770046411847875669938862264865597624573817394136100103183068123999781029642046980408197497376"
"0.4003796770046413323022994749783652963809813190343328579599377827420827010789612536448674208937610743"
"0.4003796770046413400902697086224671334971740697554409361690589328931381968515990385199879812887390233"
"0.4003796770046413404807498828371227950525831785068742717570440350048786182368660163449766649418761121"
"0.4003796770046413404993907790879716152724380112435461101906511529001759291992847764750632472859809976"
"0.4003796770046413405002400182663418972679913150903304367143309813084224285933371187495847537750047843"
"0.4003796770046413405002770181549305385935694768566319592669874793685170640876859650598618632484666182"
"0.4003796770046413405002785627367695057069873152068823937232970822310320626811605972961415815969089564"
"0.4003796770046413405002786246274922357979319186774732980882942531005144027987147808208787723982100198"
"0.4003796770046413405002786270117194119756217841341497844805602313915293474839632623730829602834918963"
"0.4003796770046413405002786271001549439973566729708418725354942122598270760220827670934829619850255341"
"0.400379677004641340500278627103317694333102588098488484201116605904498830540542790589419559377118255"
"0.4003796770046413405002786271034268939747648419171380171004801482754603250375028759560824515405656806"
"0.400379677004641340500278627103430538296139363959260408257954939510935666976865710551057193298877557"
"0.4003796770046413405002786271034306559856595142997071466426019419908211242141338777309157195316982785"
"0.4003796770046413405002786271034306596672880580652400019677206193795961868575262836117700178295414007"
"0.400379677004641340500278627103430659778961615599998307718866136890366815849701224327490116216845271"
"0.400379677004641340500278627103430659782249150855062964805884883337415615994934748074230470540584834"
"0.4003796770046413405002786271034306597823431617580896746040937558394017239224026504477921736846353704"
"0.4003796770046413405002786271034306597823457753055707866116919282435169422913920336269772927467146621"
"0.400379677004641340500278627103430659782345845996534691884818240075630754730215162930957756365716118"
"0.4003796770046413405002786271034306597823458478581830757398295882000183318544985744425218771470029177"
"0.4003796770046413405002786271034306597823458479059507297776538572031921979342019212133642921728248012"
"0.4003796770046413405002786271034306597823458479071457067808040334063801494195181842139967150881911677"
"0.4003796770046413405002786271034306597823458479071748707888737154016073603650253765262804881272031445"
"0.4003796770046413405002786271034306597823458479071755655833403414706829972924544806968721692847793794"
"0.4003796770046413405002786271034306597823458479071755817505162589525894915548769495298197576392223146"
"0.4003796770046413405002786271034306597823458479071755821181509041639241667306347607369247371117154889"
"0.4003796770046413405002786271034306597823458479071755821263247849922806861809967144836597958571504218"
"0.4003796770046413405002786271034306597823458479071755821265025658467812656607933178125945193272430681"
"0.40037967700464134050027862710343065978234584790717558212650635020660343985906553362310732929517945"
"0.4003796770046413405002786271034306597823458479071755821265064290831399659649304125173312007967190358"
"0.4003796770046413405002786271034306597823458479071755821265064306935641700301506902471095006180660562"
"0.4003796770046413405002786271034306597823458479071755821265064307257860743131556393040194814336581745"
"0.4003796770046413405002786271034306597823458479071755821265064307264181291798671268217110674958397553"
"0.4003796770046413405002786271034306597823458479071755821265064307264302887561120719329057111004827605"
"0.4003796770046413405002786271034306597823458479071755821265064307264305182669572288276255563898325024"
"0.400379677004641340500278627103430659782345847907175582126506430726430522518671669352826490529181607"
"0.4003796770046413405002786271034306597823458479071755821265064307264305225960020876192945143804234095"
"0.4003796770046413405002786271034306597823458479071755821265064307264305225973834445924147062511126955"
"0.4003796770046413405002786271034306597823458479071755821265064307264305225974076866555261806723694828"
"0.4003796770046413405002786271034306597823458479071755821265064307264305225974081047508158506039701671"
"0.400379677004641340500278627103430659782345847907175582126506430726430522597408111839283847044042866"
"0.4003796770046413405002786271034306597823458479071755821265064307264305225974081119574589289195595952"
"0.4003796770046413405002786271034306597823458479071755821265064307264305225974081119593967636311682854"
"0.4003796770046413405002786271034306597823458479071755821265064307264305225974081119594280274317314832"
"0.4003796770046413405002786271034306597823458479071755821265064307264305225974081119594285238116651698"
"0.4003796770046413405002786271034306597823458479071755821265064307264305225974081119594285315695562547"
"0.4003796770046413405002786271034306597823458479071755821265064307264305225974081119594285316889375711"
"0.4003796770046413405002786271034306597823458479071755821265064307264305225974081119594285316907468071"
"0.4003796770046413405002786271034306597823458479071755821265064307264305225974081119594285316907738168"
"0.4003796770046413405002786271034306597823458479071755821265064307264305225974081119594285316907742141"
"0.4003796770046413405002786271034306597823458479071755821265064307264305225974081119594285316907742199"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"
"0.40037967700464134050027862710343065978234584790717558212650643072643052259740811195942853169077422"

160225(2)

Ruby


隣り合う階乗の和(2)

1 / (0! + 1!) + 1 / (1! + 2!) + 1 / (2! + 3!) + … + 1 / ((n - 1)! + n!) = 1 - 1 / (n + 1)! ①
が成り立つ。
証明は次の通り。

n = 1 のとき、1 / 2 = 1 - 1 / 2!
より、①は正しい。
n = k のとき、①が正しいと仮定すると、
1 / (0! + 1!) + 1 / (1! + 2!) + … + 1 / (k! + (k + 1)!)
= (1 - 1 / (k + 1)!) + 1 / ((k + 2)k!)
= 1 + (- (k + 2) + (k + 1)) / (k + 2)!
= 1 - 1 / (k + 2)!
となり、n = k + 1 のときも①が正しい。
よって、①が成り立つ。

さて、Ruby で計算すると次のようになる。

def f(n)
  return 1 if n == 0
  (1..n).inject(:*)
end

def g(n)
  f(n - 1) + f(n)
end

def h(n)
  (1..n).inject(0){|s, i| s += 1r / g(i)}
end

(1..20).each{|i| p h(i)}

出力結果
(1/2)
(5/6)
(23/24)
(119/120)
(719/720)
(5039/5040)
(40319/40320)
(362879/362880)
(3628799/3628800)
(39916799/39916800)
(479001599/479001600)
(6227020799/6227020800)
(87178291199/87178291200)
(1307674367999/1307674368000)
(20922789887999/20922789888000)
(355687428095999/355687428096000)
(6402373705727999/6402373705728000)
(121645100408831999/121645100408832000)
(2432902008176639999/2432902008176640000)
(51090942171709439999/51090942171709440000)

160225

Ruby


隣り合う階乗の和(1)

オンライン整数列大辞典の
A001048(http://oeis.org/A001048/list)
と比較し、答え合わせしてみる。

def f(n)
  return 1 if n == 0
  (1..n).inject(:*)
end

def g(n)
  f(n - 1) + f(n)
end

def A001048(n)
  (1..n).map{|i| g(i)}
end
ary = A001048(20)

# OEIS A001048のデータ
ary0 =
[2,3,8,30,144,840,5760,45360,403200,3991680,
 43545600,518918400,6706022400,93405312000,
 1394852659200,22230464256000,376610217984000,
 6758061133824000,128047474114560000,
 2554547108585472000]
# 一致の確認
p ary == ary0

2016年2月23日火曜日

160223(2)

Number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0(5)

n が4000 以下の場合を2回求めたが、
比較したら、一致した。
https://www.diffchecker.com/qwaae69k

160223

Ruby


Number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0(4)

まず、n が4000 以下の場合を5時間半かけて求めた。
(データの容量が1MB を超えているので、
https://sites.google.com/site/manyamanobuwu/201602230001
に添付しています。)
そしてもう一回、n が4000 以下の場合を5時間半かけて求め、
さらに、以下のコードでn が4000 のときの値を5時間半かけて求めてみた。

=begin
1~nまでの和がn(n + 1) / 2なので、
1~nの中からいくつか選び、和がn(n + 1) / 4
となるものを数えればよい。
=end
 
def A063865(n)
  ary = [1]
  m = n * (n + 1) / 4
  a = Array.new(m + 1){0}
  a[0] = 1
  (1..n).each{|i|
    b = a.clone
    (0..[(i - 1) * i / 2, m - i].min).each{|k| b[k + i] += a[k]}
    a = b
    i * (i + 1) % 4 == 0 ? ary << a[i * (i + 1) / 4] : ary << 0
  }
  ary
end

p A063865(4000)[-1]

出力結果
71988492379520999128249554426154581015291162663671572693079317490501671952439341913581770187175201211036073750576661260789144040611195986123603335736134428477266374720430458902973948122489987121193650881632464039185888492976917812137525865723628284363474812215388436258130149465369928595748642085797004549989847304722675831846802658041877155022294706883010316527350806366775299036272657281664834832822654950774530751416630242972046114884262990945180426106270677181107671565139805177586222813051792763936917726321820816501410579507955349798468140704472383598040510041704675040518022006750403480472327386246730717625429721425300449588300444061820168372181794496655723711960469407449893343144449618343187464932501498523740489078321964441381954785886825780941777869204494691212583389243770699088932295443311178506666405371750138742130494941718968478581141296325202458078708773243605791737578190646587968003753863162455122176416551554120678092826070090678734355966067889054222589927684372473193312663627864520451588087161180439657477125986345961497749102968303731402709536949905145427036889747009374141404530359939293397818378788311806751915442925817101510044249965430490308744023360879418563308731401524

2016年2月21日日曜日

160221(4)

Ruby


Number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0(3)

DP の方が速い。
オンライン整数列大辞典の
A063865(http://oeis.org/A063865/list)
と比較し、答え合わせしてみる。

=begin
1~nまでの和がn(n + 1) / 2なので、
1~nの中からいくつか選び、和がn(n + 1) / 4
となるものを数えればよい。
=end
 
def A063865(n)
  ary = [1]
  m = n * (n + 1) / 4
  a = Array.new(m + 1){0}
  a[0] = 1
  (1..n).each{|i|
    b = a.clone
    (0..[(i - 1) * i / 2, m - i].min).each{|k| b[k + i] += a[k]}
    a = b
    i * (i + 1) % 4 == 0 ? ary << a[i * (i + 1) / 4] : ary << 0
  }
  ary
end
ary = A063865(46)

# OEIS A063865のデータ
ary0 =
[1,0,0,2,2,0,0,8,14,0,0,70,124,0,0,722,1314,0,0,
 8220,15272,0,0,99820,187692,0,0,1265204,2399784,0,
 0,16547220,31592878,0,0,221653776,425363952,0,0,
 3025553180,5830034720,0,0,41931984034,81072032060,
 0,0]
# 一致の確認
p ary == ary0

160221(3)

Ruby


Number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0(2)

少し速くしてみた。

def mul(f_ary, b_ary)
  s1, s2 = f_ary.size, b_ary.size
  ary = Array.new(s1 + s2 - 1, 0)
  (0..s1 - 1).each{|i|
    (0..s2 - 1).each{|j|
      ary[i + j] += f_ary[i] * b_ary[j]
    }
  }
  ary
end

def A063865(n)
  ary = [1]
  ary0 = [1]
  (1..n).each{|k|
    ary1 = Array.new(2 * k + 1, 0)
    ary1[0] = 1
    ary1[-1] = 1
    ary0 = mul(ary0, ary1)
    ary << ary0[k * (k + 1) / 2]
  }
  ary
end

p A063865(100)

出力結果
[1, 0, 0, 2, 2, 0, 0, 8, 14, 0, 0, 70, 124, 0, 0, 722, 1314, 0, 0, 8220, 15272, 0, 0, 99820, 187692, 0, 0, 1265204, 2399784, 0, 0, 16547220, 31592878, 0, 0, 221653776, 425363952, 0, 0, 3025553180, 5830034720, 0, 0, 41931984034, 81072032060, 0, 0, 588491482334, 1140994231458, 0, 0, 8346638665718, 16221323177468, 0, 0, 119447839104366, 232615054822964, 0, 0, 1722663727780132, 3360682669655028, 0, 0, 25011714460877474, 48870013251334676, 0, 0, 365301750223042066, 714733339229024336, 0, 0, 5363288299585278800, 10506331021814142340, 0, 0, 79110709437891746598, 155141342711178904962, 0, 0, 1171806326862876802144, 2300241216389780443900, 0, 0, 17422684839627191647442, 34230838910489146400266, 0, 0, 259932234752908992679732, 511107966282059114105424, 0, 0, 3890080539905554395312172, 7654746470466776636508150, 0, 0, 58384150201994432824279356, 114963593898159699687805154, 0, 0, 878552973096352358805720000, 1731024005948725016633786324]

160221(2)

Ruby


Number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0(1)

「プラス・マイナス・ゼロ」問題のしえるさんのコードで知った解き方を
真似して解いてみた。
オンライン整数列大辞典の
A063865(http://oeis.org/A063865/list)
と比較し、答え合わせしてみる。

def mul(f_ary, b_ary)
  s1, s2 = f_ary.size, b_ary.size
  ary = Array.new(s1 + s2 - 1, 0)
  (0..s1 - 1).each{|i|
    (0..s2 - 1).each{|j|
      ary[i + j] += f_ary[i] * b_ary[j]
    }
  }
  ary
end

def A063865(n)
  ary = [1]
  ary0 = [1]
  (1..n).each{|k|
    ary1 = Array.new(n + k + 1, 0)
    ary1[n - k] = 1
    ary1[n + k] = 1
    ary0 = mul(ary0, ary1)
    ary << ary0[k * n]
  }
  ary
end
ary = A063865(46)

# OEIS A063865のデータ
ary0 =
[1,0,0,2,2,0,0,8,14,0,0,70,124,0,0,722,1314,0,0,
 8220,15272,0,0,99820,187692,0,0,1265204,2399784,0,
 0,16547220,31592878,0,0,221653776,425363952,0,0,
 3025553180,5830034720,0,0,41931984034,81072032060,
 0,0]
# 一致の確認
p ary == ary0

160221

Ruby


Number of smooth weakly unimodal compositions of n into positive parts such that the first and last part are 1(5)

第10 ** i 項を求めてみた。
(実行時間は7~8時間くらい。)

def A001522(n)
  a = []
  m = Math.sqrt(2 * n).to_i
  (m + 1).times{a << Array.new(n + 1){0}}
  a[0][0] = 1
  (1..n).each{|x|
    b = Marshal.load(Marshal.dump(a))
    (1..m).each{|i| (0..n - x).each{|j| b[i][j + x] += a[i - 1][j]}}
    a = b
  }
  # 1, 1, … , 1の真っ平らなもの
  s = 1
  # 山型
  (1..n - 1).each{|i|
    # k + 1 <= m
    (1..m - 1).each{|k|
      s += a[k][i] * a[k + 1][n - i]
      break if a[k][n] == 0
    }
  }
  s
end

(0..4).each{|i| p A001522(10 ** i)}

出力結果
1
19
92377832
11910553732718752974456751586469
18025910585317110305980655794157479897788811117151181916744879563021342251768216899112133590826921698849578

2016年2月20日土曜日

160220(3)

Ruby


Number of smooth weakly unimodal compositions of n into positive parts such that the first and last part are 1(4)

さらに速くしてみた。
(実行時間は5分くらい。)

def A001522(n)
  ary = [1]
  a = []
  m = Math.sqrt(2 * n).to_i
  (m + 1).times{a << Array.new(n + 1){0}}
  a[0][0] = 1
  (1..n).each{|x|
    b = Marshal.load(Marshal.dump(a))
    (1..m).each{|i| (0..n - x).each{|j| b[i][j + x] += a[i - 1][j]}}
    a = b
    # 1, 1, … , 1の真っ平らなもの
    s = 1
    # 山型
    (1..x - 1).each{|i|
      # k + 1 <= m
      (1..m - 1).each{|k|
        s += a[k][i] * a[k + 1][x - i]
        break if a[k][x] == 0
      }
    }
    ary << s
  }
  ary
end

p A001522(2000)

160220(2)

Ruby


Number of smooth weakly unimodal compositions of n into positive parts such that the first and last part are 1(3)

さらに速くし、もっと調べてみた。
(実行時間は35分くらい。)

def A001522(n)
  ary = [1]
  a = []
  (n + 1).times{a << Array.new(n + 1){0}}
  a[0][0] = 1
  (1..n).each{|x|
    b = Marshal.load(Marshal.dump(a))
    (1..n).each{|i| (0..n - x).each{|j| b[i][j + x] += a[i - 1][j]}}
    a = b
    # 1, 1, … , 1の真っ平らなもの
    s = 1
    # 山型
    (1..x - 1).each{|i|
      (1..i).each{|k|
        s += a[k][i] * a[k + 1][x - i]
        break if a[k][x] == 0
      }
    }
    ary << s
  }
  ary
end

p A001522(2000)

出力結果
[1, 1, 1, 1, 2, 3, 5, 7, 10, 14, 19, 26, 35, 47, 62, 82, 107, 139, 179, 230, 293, 372, 470, 591, 740, 924, 1148, 1422, 1756, 2161, 2651, 3244, 3957, 4815, 5844, 7075, 8545, 10299, 12383, 14859, 17794, 21267, 25368, 30207, 35902, 42600, 50462, 59678, 70465, 83079, 97800, 114967, 134956, 158205, 185209, 216546, 252859, 294902, 343518, 399680, 464487, 539205, 625246, 724247, 838042, 968726, 1118660, 1290541, 1487389, 1712659, 1970221, 2264473, 2600357, 2983481, 3420118, 3917392, 4483279, 5126785, 5858008, 6688344, 7630529, 8698935, 9909619, 11280641, 12832196, 14586967, 16570260, 18810493, 21339363, 24192369, 27409105, 31033879, 35116025, 39710717, 44879358, 50690487, 57220370, 64554052, 72786034, 82021639, 92377832, 103984768, 116986932, 131544972, 147837027, 166061023, 186436302, 209206271, 234640552, 263038106, 294729764, 330082125, 369500620, 413434038, 462378446, 516882557, 577552386, 645057814, 720138225, 803610203, 896374566, 999425489, 1113858868, 1240883427, 1381830778, 1538168452, 1711512298, 1903641945, 2116515550, 2352288440, 2613330788, 2902249590, 3221910173, 3575462224, 3966365363, 4398420368, 4875799726, 5403084414, 5985300779, 6627964097, 7337122322, 8119408068, 8982090692, 9933137585, 10981276611, 12136068505, 13407980851, 14808474162, 16350089673, 18046550696, 19912867307, 21965455962, 24222263215, 26702907394, 29428825009, 32423437435, 35712324713, 39323421809, 43287223612, 47637016715, 52409121310, 57643163457, 63382361133, 69673844302, 76568991529, 84123806825, 92399315881, 101462008094, 111384303557, 122245071599, 134130179128, 147133099710, 161355557401, 176908239895, 193911555100, 212496466196, 232805378126, 254993115975, 279227963489, 305692806742, 334586351164, 366124458109, 400541567901, 438092262433, 479052928555, 523723581303, 572429808511, 625524897652, 683392105041, 746447136977, 815140796679, 889961874362, 971440234557, 1060150181193, 1156714053255, 1261806142717, 1376156880379, 1500557391432, 1635864367436, 1783005361285, 1942984450651, 2116888391019, 2305893196147, 2511271280479, 2734399102923, 2976765453900, 3239980324902, 3525784521090, 3836059948141, 4172840751685, 4538325243851, 4934888806335, 5365097705219, 5831724031676, 6337761696275, 6886443714745, 7481260718503, 8125980944068, 8824671638261, 9581722165709, 10401868749151, 11290221161267, 12252291308167, 13294024047247, 14421830186724, 15642622052899, 16963851569589, 18393551279148, 19940378265174, 21613661441237, 23423452179922, 25380578804722, 27496704921371, 29784392170791, 32257167405782, 34929594924193, 37817353785002, 40937320918825, 44307660072067, 47947917377861, 51879123632893, 56123904146670, 60706596283009, 65653375667880, 70992391211653, 76753910032966, 82970472495100, 89677058547376, 96911265647600, 104713499605793, 113127178679475, 122198952417857, 131978935680652, 142520959480878, 153882839180063, 166126661889154, 179319093696670, 193531708796403, 208841341282340, 225330461900753, 243087580684818, 262207678045233, 282792665395260, 304951878190333, 328802602679322, 354470639559798, 382090906075091, 411808080140060, 443777288275252, 478164841366785, 515149020358757, 554920916341908, 597685327505713, 643661717970053, 693085241338216, 746207834592411, 803299385657065, 864648980888417, 930566236353322, 1001382719929531, 1077453468658140, 1159158609233039, 1246905086769652, 1341128510646583, 1442295123354393, 1550903902232083, 1667488800877179, 1792621141310599, 1926912164721806, 2071015753168879, 2225631331220775, 2391506961444324, 2569442643982646, 2760293835821165, 2964975201500249, 3184464612708230, 3419807410204551, 3672120947655828, 3942599432684810, 4232519087101609, 4543243643803942, 4876230204923081, 5233035481151493, 5615322439852124, 6024867384578153, 6463567496966674, 6933448866786347, 7436675044793324, 7975556147703767, 8552558554189085, 9170315225100529, 9831636691565035, 10539522748676155, 11297174903639833, 12108009621161388, 12975672420908876, 13904052875446815, 14897300570137024, 15959842079856624, 17096399031390158, 18312007313576263, 19612037512457879, 21002216641545844, 22488651253804652, 24077852014657585, 25776759832985125, 27592773639706129, 29533779922685526, 31608184119001144, 33824943986446450, 36193605068337595, 38724338388068883, 41427980502077499, 44316076064151547, 47400923045987928, 50695620785333705, 54214121025048904, 57971282134858504, 61982926699760053, 66265902689920836, 70838148419005258, 75718761531505770, 80928072252003522, 86487721165540037, 92420741791088628, 98751648249525285, 105506528320473303, 112713142225364960, 120401027467619768, 128601610107256145, 137348322841668104, 146676730314810844, 156624662072025765, 167232353632860160, 178542596150315081, 190600895184620517, 203455639117172036, 217158277795271169, 231763511997046108, 247329494376930102, 263918042552656895, 281594865071737557, 300429800998301009, 320497073945177823, 341875561381149834, 364649080135118266, 388906689026941187, 414743009654466977, 442258566377895289, 471560146651562643, 502761182868342610, 535982157001081924, 571351029345129768, 609003692795803573, 649084454119694381, 691746543820610756, 737152656231466413, 785475521618824263, 836898512124131937, 891616283535120982, 949835454926160386, 1011775328391808037, 1077668651151363403, 1147762422505509142, 1222318748189705166, 1301615744890981095, 1385948497769966870, 1475630074073202042, 1570992596008144778, 1672388376320107345, 1780191120112238511, 1894797196741418860, 2016626985741495945, 2146126301045224898, 2283767897912557181, 2430053067324169045, 2585513322756169435, 2750712184636493112, 2926247067964226699, 3112751278995185495, 3310896127103212290, 3521393158390366257, 3744996517854771479, 3982505447433130037, 4234766927503896464, 4502678469995333094, 4787191071547729099, 5089312335792697135, 5410109774158938220, 5750714295287087604, 6112323893529478500, 6496207547750562628, 6903709342087696492, 7336252821145776396, 7795345592601023624, 8282584191082747184, 8799659217768776156, 9348360771112819169, 9930584184759766185, 10548336089786062490, 11203740819120373216, 11899047173187652075, 12636635566627863054, 13419025577247450081, 14248883919268193076, 15129032864376519663, 16062459135093881853, 17052323296570185872, 18101969674043886815, 19214936824952717261, 20394968595956542314, 21646025797049925208, 22972298526372177019, 24378219181430134869, 25868476194049395455, 27448028528689682390, 29122120985547297703, 30896300352422317045, 32776432451324628913, 34768720128603736122, 36879722239616529185, 39116373682042052102, 41486006534437268435, 43996372360036217381, 46655665738565469715, 49472549092599806450, 52456178878069908087, 55616233212664298344, 58962941019304389060, 62507112766420701786, 66260172890583483222, 70234193992048265203, 74441932898033226650, 78896868694059367675, 83613242828414887217, 88606101400878342648, 93891339752092669094, 99485749476667460089, 105407067988928614198, 111674030777596326485, 118306426492156624259, 125325155011799454345, 132752288654993736393, 140611136696694945381, 148926313368167673525, 157723809524233373550, 167031068171608808765, 176877064062823141003, 187292387570019401621, 198309333064858981468, 209961992041629934719, 222286351233776046396, 235320395986116559117, 249104219159468025812, 263680135857728587819, 279092804283380160219, 295389353042144475174, 312619515235026940981, 330835769692337461484, 350093489723540066693, 370451099774879292083, 391970240407929857614, 414715942032233877213, 438756807848521607334, 464165206481142718447, 491017474804014455974, 519394131488857914143, 549380101832748684324, 581064954449047018664, 614543150436864070089, 649914305674089880645, 687283466913220322201, 726761402392211939348, 768464907710228599781, 812517127754576978577, 859047895506530556839, 908194088593957858986, 960100004504216158393, 1014917755415158088329, 1072807683652189499069, 1133938798828295684041, 1198489237779043800590, 1266646748458594999043, 1338609199023345719696, 1414585113389402376669, 1494794234616708303274, 1579468117538344775022, 1668850752126770396425, 1763199219161187329845, 1862784379840746897728, 1967891601068129185656, 2078821518216542607592, 2195890837281148341366, 2319433178413202525532, 2449799962932103923897, 2587361346017461034926, 2732507197390016150267, 2885648132407760647920, 3047216596121103462476, 3217668002960060893239, 3397481934855824342731, 3587163400740912807944, 3787244160514542896069, 3998284116715672882158, 4220872777302926562814, 4455630793111766153107, 4703211573731751057972, 4964302985734714748388, 5239629137374426898749, 5529952254084754691032, 5836074649312032204682, 6158840795444039622206, 6499139499827487844440, 6857906191114803506510, 7236125321433338735687, 7634832890143365905409, 8055119095228608091259, 8498131118662983704591, 8965076052402115312420, 9457223971977345152398, 9975911165005026957155, 10522543522285118759320, 11098600099531206636239, 11705636858170494704551, 12345290594056660235656, 13019283063373401398428, 13729425315450635048727, 14477622242692424050071, 15265877358303442923696, 16096297813024149977224, 16971099662620335898290, 17892613398446732309184, 18863289753992234055200, 19885705800943765297736, 20962571348951079258990, 22096735663965010781127, 23291194520729818785908, 24549097605767015744942, 25873756287965071558971, 27268651774718962212449, 28737443672415965466747, 30283978970973425494526, 31912301473069238812078, 33626661689702419470814, 35431527224746591448308, 37331593672251371653031, 39331796051371141234435, 41437320804997353820165, 43653618389403462199537, 45986416483522585018374, 48441733847829629743374, 51025894864235752928868, 53745544789884500725419, 56607665759312032497365, 59619593571057370708700, 62789035296531422522463, 66124087750732521440137, 69633256866282780391990, 73325478014208622604635, 77210137316954473951860, 81297094001253668363180, 85596703840742042104064, 90119843740538188502497, 94877937518489807637931, 99882982940346534965033, 105147580068829089014685, 110684960989368714639091, 116509020978256117015129, 122634351182009091243756, 129076272880012752944756, 135850873405846907884482, 142975043806265221795194, 150466518320469075516887, 158343915766202829049943, 166626782923222521064755, 175335640008938408030417, 184492028345436289160078, 194118560321729168276330, 204238971759909623658209, 214878176798954821203344, 226062325415207490435164, 237818863704112719937555, 250176597053556121273639, 263165756345224124174533, 276818067326712639996410, 291166823303751860454102, 306246961308809872290804, 322095141909597501540284, 338749832828535280089197, 356251396552178003127516, 374642182117833341553157, 393966621273282114329051, 414271329214515676189607, 435605210115880794919133, 458019567676867204444373, 481568220920125046670654, 506307625486057529267560, 532297000680643147805925, 559598462544896510447094, 588277163226729794087019, 618401436948818837183231, 650042952879569677996029, 683276875228309365269409, 718182030900558776873178, 754841085064566911908513, 793340724996374568176157, 833771852587408009246803, 876229785916168755131609, 920814470303856903622566, 967630699292941425041145, 1016788346007639799775373, 1068402605376201104568790, 1122594247716664634954598, 1179489884210611772317326, 1239222244813200588493119, 1301930469172704357706591, 1367760411158720188192791, 1436864957625419035734790, 1509404362064521965333172, 1585546593832369936070062, 1665467703666349015440401, 1749352206238314654557266, 1837393480526365648644317, 1929794188821640869441492, 2026766715223582897619482, 2128533624515638679721738, 2235328142353476156233142, 2347394657739811200715883, 2464989248803683733436836, 2588380232947837512590126, 2717848742475562362930889, 2853689326858311727538404, 2996210582857424737402727, 3145735813767742422397691, 3302603719107619351729334, 3467169116139198583208731, 3639803694664641590860637, 3820896806608712523410848, 4010856291965505091834933, 4210109342757621977238602, 4419103406729563437297708, 4638307132573931162492283, 4868211358569093602446988, 5109330146590694870156548, 5362201863546604856061187, 5627390312376137813654417, 5905485914849390244807771, 6197106948501932052770933, 6502900840143604051761437, 6823545518488428689736380, 7159750828565402429665614, 7512260010687841755032142, 7881851246881770537045401, 8269339277802236079849579, 8675577093300192905054120, 9101457699942408527906284, 9547915968932490905320206, 10015930568033366809631664, 10506525981250119938213555, 11020774620197826114783424, 11559799031251666553524546, 12124774202757005743205851, 12716929976765055054404110, 13337553569956104978236347, 13987992208616866798702250, 14669655882752171232794193, 15384020224633899402297313, 16132629517322581065218232, 16917099838939363057842676, 17739122348719100143627709, 18600466721138933472726376, 19502984734692037291806909, 20448614022163022865399732, 21439381989560998576641981, 22477409911178296765559292, 23564917208568675114668379, 24704225921578194548487611, 25897765379916330709300514, 27148077084124017456089786, 28457819805180697712355784, 29829774912393910988172961, 31266851939634018660972252, 32772094400413218148286420, 34348685862763663315000836, 35999956295344173872875301, 37729388696700422694852372, 39540626020119545456754504, 41437478407058674689862520, 43423930742687897855802167, 45504150547673547803776477, 47682496220937525418714400, 49963525648764626251308160, 52352005196292604835930691, 54852919098111195898695022, 57471479265416572842443139, 60213135527919139167806818, 63083586329485218767653281, 66088789897309669323048085, 69234975905266844602049684, 72528657652974375386330995, 75976644783028141009860859, 79586056559830440324456592, 83364335734437026898646289, 87319263020895414025821543, 91458972210637041239204863, 95791965952622794573316229, 100327132228125432717740427, 105073761550267176809771164, 110041564919716612391724117, 115240692569289846759011369, 120681753531597207310512855, 126375836065332625053807081, 132334528977318981135586627, 138569943879003338544796808, 145094738417742023322977784, 151922140524931480814830301, 159065973724827741147010015, 166540683549760012402140279, 174361365109383563682715762, 182543791863638820060131029, 191104445651188823242826995, 200060548027301424121119717, 209430092967427310885800017, 219231880995106125795807362, 229485554795312236887864008, 240211636376935499416736578, 251431565850782546294561335, 263167741892287512562205711, 275443563961039856931108570, 288283476352278285422739485, 301713014158666213174495003, 315758851223963411945418728, 330448850173643289283753817, 345812114611083857837115337, 361879043571686015700353428, 378681388331154074209279913, 396252311668214033936242793, 414626449686254343459577849, 433839976302755669271501966, 453930670519940641976904683, 474937986594825944718362866, 496903127231808269898608104, 519869119926067380527797681, 543880896591435332134535771, 568985376611966144974882528, 595231553462257243325108294, 622670585047628663587257002, 651355887921571636619027238, 681343235544441146728266839, 712690860754201667010794607, 745459562627148608942853972, 779712817913935325920436502, 815516897243944641147445368, 852940986299071145012015704, 892057312166334579731503184, 932941275087442987313430332, 975671585832476454353988644, 1020330408934286990991146214, 1067003512030017779132470491, 1115780421566355818808173849, 1166754585135757354162190450, 1220023540721946928737319536, 1275689093144501071731822412, 1333857498004309572049700825, 1394639653444174823554817977, 1458151300051787623427093222, 1524513229245821147145030373, 1593851500499940214478858950, 1666297667774146888907357795, 1741989015538104464404975442, 1821068804786918013059990996, 1903686529466331528314408953, 1989998183741448993154415525, 2080166540560932306746036580, 2174361441987194418630671190, 2272760101782426533317722414, 2375547420760397323844679265, 2482916315434877610520406220, 2595068060517301511352746876, 2712212645838915320007044518, 2834569148296216213898349477, 2962366119442988000914187131, 3095841989377730875810463607, 3235245487601803461067700764, 3380836081551181356441638585, 3532884433533437364763450179, 3691672876831400537723345646, 3857495911766008266198455353, 4030660722543167040163544053, 4211487715743041301605320093, 4400311081345138662953907914, 4597479377218916048034018402, 4803356138047441408939676987, 5018320509690976595376002174, 5242767910038249107235698997, 5477110717435725843087075936, 5721778987829445328321900135, 5977221201799983618897081771, 6243905042718982607430267133, 6522318207305440918126834352, 6812969249911721541584516500, 7116388461923056135631463879, 7433128787710293592078498970, 7763766778633846007846194187, 8108903586657304652655968852, 8469165999192135022605282833, 8845207516860296102145716919, 9237709475929675359892673570, 9647382217247977230410062632, 10074966303574268002560740835, 10521233787283861124593662945, 10986989530501751972951517049, 11473072579802485222719812714, 11980357597700298712302904780, 12509756353242748998199977475, 13062219274113933561035749191, 13638737062750006219910660032, 14240342379070094731772952855, 14868111592530106402605122884, 15523166606315419729744319522, 16206676756601252288818788484, 16919860789926751001288953185, 17663988921850727163544480977, 18440384980183652692131690096, 19250428636222215414944401874, 20095557727549612243283620008, 20977270676107023064885381913, 21897129005389583467260345934, 22856759960773859304033438518, 23857859237143566053192390300, 24902193818146285435010829500, 25991604931586474687224698883, 27128011125639372237737482285, 28313411470756760912760348927, 29549888892329207100952828209, 30839613639370656407356536438, 32184846894700404406533068135, 33587944532314802998801441295, 35051361027866901608651576718, 36577653528406910527216609942, 38169486087780227719016230303, 39829634074333169354558185245, 41560988757839830267236337311, 43366562082837080908474032291, 45249491635838951686904363259, 47213045814197001879570835090, 49260629204680117656992501351, 51395788180166003131049307854, 53622216723167850631661483097, 55943762485263807989572784403, 58364433091854366688146273971, 60888402702044219724300330262, 63520018833830984113383893795, 66263809465184035445116020738, 69124490422013102813580811416, 72106973064458851016577179809, 75216372283387018126821316407, 78458014819434456832946137660, 81837447917440278535675058817, 85360448329598947292494730396, 89033031681195297313408196104, 92861462213324834630362835832, 96852262917567065373632980403, 101012226078165810257071335389, 105348424237879309698298337038, 109868221604295299986774283218, 114579285914063002493840815803, 119489600773176086357413606477, 124607478492149061686370825690, 129941573435665279188082579143, 135500895907038746544647720441, 141294826588625444160680666795, 147333131560143803884054809461, 153625977917719710353057623467, 160183950017359949944254109013, 167018066367480763617949530266, 174139797196076301219000890032, 181561082719106719789087481125, 189294352137718757672459188527, 197352543392984347748673598364, 205749123707956651370132339602, 214498110947999409667569709895, 223614095831546276937683861725, 233112265024693552368256071759, 243008425154324137720972075506, 253319027775804479631908540186, 264061195332691511530005232397, 275252748147335190586105743886, 286912232482766074276694192848, 299058949717818647071026395859, 311712986679061884654654175581, 324895247174791139274108999331, 338627484778082100250434626147, 352932336907720808912275910371, 367833360257705915066653809651, 383355067627973218009023959503, 399522966211020652779302336371, 416363597391217125840269976424, 433904578115763787219182512301, 452174643898544525619540106168, 471203693520456717517979001294, 491022835492256857032562415674, 511664436348491899704320186254, 533162170843719522425920397144, 555551074124952541039541081471, 578867595957098252825472557722, 603149657081106257354136357381, 628436707787592455715233455800, 654769788791876495672970485956, 682191594499659322982005588416, 710746538755981085550016097539, 740480823173642148319994491123, 771442508140946112122277367528, 803681586612438571129024380519, 837250060790273945809086749950, 872202021807950549887635686953, 908593732532416527449942544836, 946483713604972292742282223387, 985932832845984467246749500110, 1027004398153188332944165688273, 1069764254028296794683945299071, 1114280881871760530741448005224, 1160625504190843169436359532860, 1208872192871694223501970214799, 1259097981671828411322499009153, 1311382983095360694081425737783, 1365810509819509674502225275391, 1422467200847276310859244771298, 1481443152567838599377921314444, 1542832054913084961507779061958, 1606731332805848568989595376330, 1673242293102811404581342222455, 1742470277242730194267135807902, 1814524819818606824535938676976, 1889519813300693905412642346586, 1967573679145802886358502325425, 2048809545537278785758372281189, 2133355432009234104311617214445, 2221344441218206901468934879652, 2312914958135337149406769731786, 2408210856942454280767378787317, 2507381715926151084177353091207, 2610583040674998677571842990419, 2717976495896548984120439641204, 2829730146182689883961811231142, 2946018706064279881841805902066, 3067023799708809759177920804130, 3192934230628135296869941372043, 3323946261777114994511500150874, 3460263906438288047688864665784, 3602099230302559185771612719595, 3749672665171237930901440165695, 3903213334720730291537239880109, 4062959392787721898395507998568, 4229158374649844472137589532430, 4402067561794604866542078854400, 4581954360687800678569069893828, 4769096696071772793109919020953, 4963783419343677845363702120272, 5166314732584528441856095608423, 5377002628831072504448385822416, 5596171349204693190816575441353, 5824157857534435865818361825564, 6061312333135038484609103869332, 6307998682425486950782919121748, 6564595070099169644542270139958, 6831494470583198062737203073748, 7109105240551927824466224697450, 7397851713288191255514962301291, 7698174815715276326807922584124, 8010532708953294539021983683156, 8335401453285312056838019068661, 8673275698451514410266745895070, 9024669400223777913869068626649, 9390116564248373969922798350658, 9770172018181181219502507529302, 10165412213177771615362299670623, 10576436055840118818444544102259, 11003865771762500789911380730963, 11448347801861485510776212587002, 11910553732718752974456751586469, 12391181262210974207406763517102, 12890955201748096542526538000415, 13410628516490234009867773617149, 13950983404963994162393381460516, 14512832419551552589502136779678, 15097019629380179910509237461156, 15704421827196302521508115829774, 16335949781866608715350871103367, 16992549538209270345175161768866, 17675203765921113024329310263104, 18384933159431614647711799116953, 19122797890582024360548797928490, 19889899116097757428985984874882, 20687380541894623267078020561196, 21516430046334475734409413235991, 22378281364623630549030444247460, 23274215836627972435650590320504, 24205564220462175038342295732455, 25173708574296984898906344168340, 26180084208918184786440432002715, 27226181713663764144495445461560, 28313549058462101026812888355920, 29443793774793721496440186540871, 30618585218502573023697681125939, 31839656917489857476579671064040, 33108809007434449732516174459654, 34427910758798918572446280699406, 35798903198499309782073715001240, 37223801829740296036035202959273, 38704699453645196846694992639366, 40243769096442884013709226942991, 41843267046110877239507653060539, 43505536002516171662704688101209, 45233008345242699365960043376215, 47028209523446993414371942359318, 48893761572241783598353993656468, 50832386760271103822955426897923, 52846911373310233378187886191496, 54940269638899638148540110815912, 57115507797204238949849235405447, 59375788323478037583299574103914, 61724394307709608061561286383097, 64164733997226451767808912177628, 66700345508245968749761198514172, 69334901712578071042267198035031, 72072215305909523213804694335427, 74916244064333216700398555675666, 77871096296027052193456171426770, 80941036495237214470933149605740, 84130491205979681109797068705896, 87444055103142127583154327634894, 90886497298946302491890073083712, 94462767883018787677879619839309, 98178004704616178056326949218765, 102037540405859478810944767800562, 106046909715152297263461104606291, 110211857010288592616525023432347, 114538344161098739563419161296300, 119032558661837878352552887838841, 123700922063888393375043233097220, 128550098719729331062348653466509, 133587004849520095308026304595887, 138818817942054322631298882853219, 144252986502262931858103808492524, 149897240157883475789465480438588, 155759600138366621912446569535707, 161848390139560403330929311300703, 168172247588199373710209899473907, 174740135320729557361118488930354, 181561353691521711390368187387251, 188645553126065538593449133316020, 196002747135296753786275746941573, 203643325807787984169171659092898, 211578069797134067942509322814408, 219818164822483123548076844149921, 228375216700807535139467313152091, 237261266930174507458606733284709, 246488808843964877836435251224070, 256070804356702257784045696569659, 266020701322893159910224235034822, 276352451531043428643231584913101, 287080529355807943316462981930508, 298219951092050142257305344046100, 309786294995436398143902856707901, 321795722055068666700650002852185, 334264997524568172426869571425551, 347211513238964265667969878614645, 360653310745717097380485239862749, 374609105279211565997312335367209, 389098310609104285134317453130982, 404141064793986336697538568434898, 419758256872943584724920108936725, 435971554528754652409479220685359, 452803432757665670623708223877090, 470277203581922004397327682567751, 488417046842521811695079846076747, 507248042110985998459429259484795, 526796201760315464359350776696679, 547088505236731102219414154655545, 568152934575266488455567342800409, 590018511203809311687127307252334, 612715334081767115890469917261247, 636274619221167732881197198782485, 660728740639696754498715573582602, 686111272796925525945026843653041, 712457034566795468837998155742736, 739802134801300181267036250048850, 768184019542247894723453296436087, 797641520939995756479754019509642, 828214907940126384461541953702553, 859945938801188628871223490632775, 892877915508850966219245730132737, 927055740154120033417304105442008, 962525973345661150483154627293096, 999336894728725045512148125856404, 1037538565685738237862808890730425, 1077182894296256611412565818554541, 1118323702636715669545132916027707, 1161016796503239967827385826640975, 1205320037643701530177599571315808, 1251293418588246048406086764264404, 1298999140170639829538740487400392, 1348501691836033401961423652912199, 1399867934834093146873150197923358, 1453167188399924146284710058044305, 1508471319028799616465259159715202, 1565854832954428952563204364015039, 1625394971944341804108593384899633, 1687171812529944142322244059409557, 1751268368792918519654416736371481, 1817770698833899372961367582864438, 1886768015053760148203300100878234, 1958352798382407263433005670514634, 2032620916594691676354721590677202, 2109671746857927465465651449144683, 2189608302660553924852838251762659, 2272537365276698963818242826665578, 2358569619926803029838631282535603, 2447819796800050482768300054076031, 2540406817110135682763294965877868, 2636453944361870580781718687610070, 2736088941012326096252143291734183, 2839444230716598047504102236259077, 2946657066354907108220388366601875, 3057869704044588693037798323959429, 3173229583347610564085484516491496, 3292889513891581305274768632162214, 3417007868629789897776301231414204, 3545748783973654002492108548074471, 3679282367039061043003711228364746, 3817784910256470923051979955699294, 3961439113603321638004098247246517, 4110434314726248910349705434944562, 4264966727229908369928400580936415, 4425239687418784135382913976639830, 4591463909788291695396199419659989, 4763857751571746871085748754979258, 4942647486660387858058586482277468, 5128067589224615789672096393088899, 5320361027375973207226905448601785, 5519779567221121967716881853016115, 5726584087671225574778871117699620, 5941044906382699245422673566356085, 6163442117218278223548008952675872, 6394065939630785403033048480853649, 6633217080385868177750878389482874, 6881207108054337056832725384214513, 7138358840719590933829689747022153, 7405006747360972489214814378356541, 7681497363389779081310162475551246, 7968189720831077269903555004162007, 8265455793661451017717851939647249, 8573680958830373448538039644858254, 8893264473511049236308371900664008, 9224619969145349349934022253343841, 9568175962866872726169885153340668, 9924376386906241937872932270380257, 10293681136603494210215915613484634, 10676566637673888110746951314363042, 11073526433395633537949351451612262, 11485071792410992698784475782661962, 11911732337855917830066130851233136, 12354056698557913569909623211244068, 12812613183067165055549554355211655, 13287990477312184857586702030840436, 13780798366698331503158635877239241, 14291668483495569310122779379931415, 14821255080390804229992536700166623, 15370235831110075095548940456256409, 15939312659046836831153288401540075, 16529212594864575656992144181873480, 17140688664075081043668763503884223, 17774520805627901270048176171987754, 18431516822581866191402859317788452, 19112513365966110778897528730144393, 19818376952975815932646098854164161, 20550005020686940124647282995745431, 21308327016514589048969122540784750, 22094305526681404524871989401137338, 22908937444005493711605011134852941, 23753255176362012068554350142075331, 24628327897218606760247871390564045, 25535262839692571310750476560789165, 26475206635626808817172745935575769, 27449346701232603223770243364680242, 28458912670899811042911476770769362, 29505177880829466331985385121260396, 30589460904199998375606194791728055, 31713127139636355018578543328150014, 32877590454811367541872743260104021, 34084314887070750053185121712462576, 35334816403037264343886747890974909, 36630664719215869037139695448582504, 37973485185690180834507271663859568, 39364960735071379346143215258451991, 40806833898933861320754372836627194, 42300908894047573557704020156646035, 43849053780795107396222922208806798, 45453202696242405135439148775607358, 47115358164415396440600106342464290, 48837593486421139996014044943611705, 50622055213141184509832815298449672, 52470965703316978846376691335201287, 54386625769942351810118970214312419, 56371417417976449433023088603076117, 58427806676492166292582930207034784, 60558346528480145641770871790610297, 62765679941636962677315263416866967, 65052543003578261509058317565634609, 67421768165033508432838249485650218, 69876287594698774991167001146281604, 72419136649547701025556388543748776, 75053457464528641659231430618682607, 77782502665708108293755355979368648, 80609639211057112106176705256047500, 83538352363218053537202304615747412, 86572249798735521951298443669290965, 89715065858384929901338554955025930, 92970665943388465169464780516026804, 96343051062468565011442494317875950, 99836362534855170212222832838327573, 103454886854534576511574137782099536, 107203060721204948254321594835707855, 111085476243586680127410793491795002, 115106886320924980032409464256053949, 119272210208717498146554186862736552, 123586539274901749181830748822405427, 128055142952945678469746832422129805, 132683474898500226404258251709786760, 137477179356495375597157974557048204, 142442097745791153831978383528232735, 147584275468732653999636550511649992, 152909968953203567955818530877811716, 158425652935026270899848805745138385, 164138027988818401026192393066739591, 170054028315686428898550417592180317, 176180829796416184182862088855672758, 182525858319108995007762379398044310, 189096798390510297715458240605309278, 195901602040585602143604580985878803, 202948498030216869928807645752653668, 210246001372221010962969599067722723, 217802923176231667100354105539710844, 225628380828336084434602185156264468, 233731808516721039277676653361695773, 242122968114955853313371397161148310, 250811960434926897345962486418915580, 259809236861837040050948097192121926, 269125611384095660515235755624584892, 278772273031350536636061771841878760, 288760798734352584894716309126660093, 299103166620798513899243440657669005, 309811769761765432306361430365138386, 320899430383835804102291741167270714, 332379414562511369141244390606948836, 344265447413031258577372310693904940, 356571728795243064230788905923333403, 369312949549726615747474184971521822, 382504308282939245038677156219257032, 396161528719738957297089337703780851, 410300877642248784040952053675493072, 424939183434652287436586634668123706, 440093855254157357878290905246272327, 455782902849033760126157325303159554, 472024957045320020141452617164065540, 488839290924507909732321710544635129, 506245841715248706467539615730655645, 524265233422885332358173927017921473, 542918800221399180940085812938496742, 562228610633170727579381426896826704, 582217492522789706640630537099288602, 602909058932014582325822300693048242, 624327734783873115475933516644068717, 646498784484816942219632135391958157, 669448340454794166831025085316434433, 693203432616085994908676726427908663, 717792018872767389232134704492509004, 743243016613698646120382354034645472, 769586335273035724338406478004269548, 796852909983363204630159955209937546, 825074736357706043744750418606690234, 854284906437865975986347627908355088, 884517645847756708587446743752118896, 915808352191680193263388085465318163, 948193634738795513311169065274036992, 981711355436383622103386056535914325, 1016400671295906665319727920068389177, 1052302078197301319230759098366416009, 1089457456158432928933330834995946920, 1127910116118172727461582716728795931, 1167704848283145600481687965867238404, 1208887972089832321751021764202567918, 1251507387835399562119444409857877766, 1295612630032374961713738728145218349, 1341254922544084896930201046290996638, 1388487235559631071816261783667700403, 1437364344469100575319820569821185630, 1487942890701684488190067915121732038, 1540281444591424473230009819420957019, 1594440570337417079546260650947228280, 1650482893127483839419229121307918078, 1708473168496563805594994889050606272, 1768478353993406206021228845857963319, 1830567683231536691520422554267731854, 1894812742402943601839441427269836968, 1961287549335483233987652516330680078, 2030068635177637798463283949097246363, 2101235128796979208126254456169885280, 2174868843981498757901250349154628118, 2251054369535859902593086948092269569, 2329879162367621594023241241442497395, 2411433643661565956572780297996578705, 2495811298243449514450605698847573731, 2583108777237784882659836669457112848, 2673426004127653043941600050313959781, 2766866284328048404867350831166341029, 2863536418387873210079980259883471013, 2963546818939428156925897685945388905, 3067011631518095867908669507438696623, 3174048859378887035010988027128538857, 3284780492440619456568024476467619076, 3399332640492731874821156918455215595, 3517835670804101647929182601725878894, 3640424350277742141355675822017367523, 3767237992299906722038551983886018842, 3898420608436925944513437281564161652, 4034121065138057634152684668672476268, 4174493245607740948613636959348027475, 4319696217015920136172567250409032531, 4469894403220546766565362879464029717, 4625257763181986005502039823042024045, 4785961975254848523215081132568905652, 4952188627548750526943735834110761405, 5124125414555676020069861984759928296, 5301966340247983732040821562651929901, 5485911927857672435856480812332877483, 5676169436554298970211831229058197369, 5872953085245939806851784844897763573, 6076484283734806251754839748053699081, 6286991871466572354363064619443802126, 6504712364120160554011347465424442975, 6729890208292660473521668166319587030, 6962778044542238765688280506007229028, 7203636979060340456973217855763627128, 7452736864253192989096579478195666898, 7710356588521611562034872038659468759, 7976784375537377122399703414708353317, 8252318093324025380040621730416379419, 8537265573459755812630851111170386065, 8831944940730353259041724579907019613, 9136684953570521229813231822670134945, 9451825355642865603646185691866687101, 9777717238914950373929223476557807782, 10114723418606384323549039370342097664, 10463218820389800038579087736864154108, 10823590880241865964345460039858778814, 11196239957353140058362178268318731951, 11581579760518642166124264096454385326, 11980037788444504077329387800266332879, 12392055784419964238946646912482556048, 12818090205818321635455630375994494329, 13258612708905264135041510336603905106, 13714110649448254808548765762788291974, 14185087599636409957870728810066506311, 14672063881836549896394583354865103227, 15175577119727863424820069807287542451, 15696182807374915439753313061411357692, 16234454896816560691891612928671581525, 16790986404766722377001142249812284518, 17366390039041969521816735195227787446, 17961298845350400085302935427945344236, 18576366875096525956667477230988258139, 19212269874877680793157776535044954196, 19869705998368951691941377960706126272, 20549396541315791430569088640455275693, 21252086700376320466432564348738377736, 21978546356578898732141095007672189403, 22729570884184858842065226922505760350, 23505981985771367664787497270172231344, 24308628554375246053758293524784476923, 25138387563565251331624696733335320725, 25996164986337839111295056364137808674, 26882896743759796203385221501281842041, 27799549684310401497495972683152256736, 28747122594905954429630199866988235708, 29726647244620639422713699149178765619, 30739189462149798848751470814346177682, 31785850248094796845896840869556800734, 32867766923182802896142825860148157364, 33986114313570039548550614898225297635, 35142105974413356163392339699427839580, 36336995452932444172173425306314193360, 37572077592223634261113021419445699217, 38848689877126048330974739037527335601, 40168213823481956414184310344547571691, 41532076412175549432941354326231988096, 42941751569378022430117029684156061516, 44398761694471910580897622371916245995, 45904679237174074031134376128779939812, 47461128325424630828608217934798394525, 49069786445658534664093798316283488676, 50732386177127431934069885927377479511, 52450716981991958299242442408954019852, 54226627052958797415283274134996876660, 56062025220292674322501802910630709766, 57958882920091045106109121668132041269, 59919236225768626472080352952586408510, 61945187944760139051829009134118999752, 64038909782512773462843404948653108922, 66202644575904987055650034915583219532, 68438708598295362300993892585064834297, 70749493938474467184737371129065142115, 73137470955864017948244991177075771995, 75605190814381221156736542109866142310, 78155288097462033527765274339677387156, 80790483506815294407637248788909292829, 83513586647560329581903902311712411764, 86327498902483770780723208583973597896, 89235216398237059590590106131377238667, 92239833066384486641544815494831870334, 95344543802302738438574259084450116939, 98552647725026869056036452280736175978, 101867551541234468673879265468207409429, 105292773016659654787757963732499488749, 108831944558331456761669127821638944237, 112488816911137294885376290091239080031, 116267262972321668794676202155158775359, 120171281727642967509161160266156385388, 124205002313027597984005954547731737375, 128372688205680507637412439193136531032, 132678741548734758712589814946913932971, 137127707613650211795583785040889269384, 141724279404702708998259812866001047262, 146473302410040534415879111649849904369, 151379779503924494303064105040890174494, 156448876004911829543061924216071193331, 161685924894892479831800253853967833292, 167096432204039097946557369438256091274, 172686082566889802995543384260907253364, 178460744954945107334007091906515731718, 184426478591327900907463934140997510292, 190589539053227981629586113428115323373, 196956384568030538108498486452760452037, 203533682509211383421952871079582792749, 210328316098270772409994412933676065192, 217347391319172481824861790406264775068, 224598244051955669548487660116333987439, 232088447432394038179175809142323677464, 239825819444790197309851385495565770604, 247818430755213041126399579087939835860, 256074612792712632721382991422045212146, 264602966086280718909238479266309084599, 273412368865565800678519769412832231361, 282511985933599872409286932124503244772, 291911277820049741847587484088343524433, 301620010223769483525554588835598457122, 311648263753702298745061353812768078619, 322006443977460100444694302168040797274, 332705291787197763640703506661841473698, 343755894092696441639239746961065522737, 355169694851876912626749288097285505495, 366958506449279866351273535161438932175, 379134521433375650473280426275310488951, 391710324623901563363916824580975370945, 404698905600770606002688162020555458836, 418113671586452000538947265002970794232, 431968460734091066691167826837346606387, 446277555834014548688423772713516100071, 461055698451657543987842131455903141646, 476318103510350149747811617333861892518, 492080474332816173663697141109110191909, 508359018155663122693983554848775564464, 525170462131582567907224446197576324124, 542532069834433279045407473038977051342, 560461658282846633047270370011451030565, 578977615498475143403853246670658971274, 598098918615500960968735857248080375848, 617845152558532303660212263720831033435, 638236529306542437503592615952522077918, 659293907761048523370424745455839550075, 681038814237286845257551345730276955113, 703493463597717144075356334835640475584, 726680781047782507559313752260824377770, 750624424614463039204060875930866457709, 775348808328791889868382066546208409393, 800879126134151743892521199458311823896, 827241376542839082826583159473639824369, 854462388064073096933060846001018494191, 882569845427336587875503141426465852964, 911592316625668233962198564595473808651, 941559280804279819190139106744373713948, 972501157020649125571237669106232232654, 1004449333903039841064641687770944869169, 1037436200235224749507765458709920819201, 1071495176496038371841631561018607090123, 1106660747383260868863009802765851172684, 1142968495352237166143159638893865127493, 1180455135200564715946974505474091959281, 1219158549731140886845037588314426542756, 1259117826526847511355574694255650850366, 1300373295871166492469536904648131233604, 1342966569850067464072676833732319415032, 1386940582671587237306930214706894124430, 1432339632240632091248379899082611097614, 1479209423027678856383453113607484284771, 1527597110271230196535619411918797613152, 1577551345555094552118722678692831071095, 1629122323802812928405080896233059372700, 1682361831732844191885666439713321042844, 1737323297819448903117702365836079344519, 1794061843805580126375398201947639200154, 1852634337815499309899860478507267361662, 1913099449116287455841305733088417942742, 1975517704578917662675765367556644041764, 2039951546891096028927557288436529288616, 2106465394575665197878030202652145371259, 2175125703869999880639892280657434989654, 2246001032523507942326428518927297709239, 2319162105572085537803462759429625014725, 2394681883150161847602419778719559726467, 2472635630402809743358449072443186071319, 2553100989562294803702773400693689339589, 2636158054255388151037027816161873669389, 2721889446109780280629491784825760876541, 2810380393730005149431762141818549616942, 2901718814115418077642227806453268672891, 2995995396594969338861611403470025056463, 3093303689355779576538341523416349935826, 3193740188644855343048133986286705009664, 3297404430725685128482124015261788626915, 3404399086673930303539518071496429829791, 3514830060098973580266673304778996643392, 3628806587880712093900412339769336942059, 3746441344013685291423184114599846309674, 3867850546653411806696251789348725649492, 3993154068462676805601345403344093368665, 4122475550358464365212715534215704541033, 4255942518763270848709556590531206808557, 4393686506467667567059233264190721046518, 4535843177214206970598691398681393155442, 4682552454116088958508922380116464059110, 4833958652027425482926281487659998537495, 4990210613985465391664502929321231407444, 5151461851848770419720213488609692432907, 5317870691259070513788029433804837025235, 5489600421058375455741499033185830675611, 5666819447296883333857876047620789158148, 5849701451971308184172552957587846324808, 6038425556637452577526170211685244584764, 6233176491045179651330502807082187942478, 6434144766948396774449459037207062225311, 6641526857247253492405414110504646142579, 6855525380624483542973752882352905235772, 7076349291842688587959614283326036450205, 7304214077874374021969908745161495325238, 7539341960041709060651527696101277895197, 7781962102348298670972877771447721635039, 8032310826190728304516571822103978332299, 8290631831643278483009707517300449315437, 8557176425515009850550598746923105596860, 8832203756384395275761268045887911134739, 9115981056822829029420518906751002031278, 9408783893024679196645894533469693609098, 9710896422068073676869726992681349557171, 10022611657037327905415964235590286962844, 10344231740244839483869467641422351233147, 10676068224797397084451913432054621356716, 11018442364759184318198633164916612795406, 11371685414171309924821168041783574325060, 11736138935195470030731341897105630032306, 12112155115657352893032110329997086832411, 12500097096273638254129364568406589402946, 12900339307854929122821196347797972490987, 13313267818785690623766047681407204767612, 13739280693091265876089987625935823710160, 14178788359411300244946035559369069520294, 14632213991208440548035777286427451434342, 15099993898550992909236348528998831042943, 15582577931818330182691709469339276599833, 16080429897688245711161722541990847187587, 16594027987776163366091018461520561195145, 17123865220307143330671096487476035675731, 17670449895212978178213806282037242462887, 18234306063058363981123104059405301355430, 18815974008212166250641815255817815646831, 19416010746692190527511745078214920881480, 20034990539124622783171174122950587268501, 20673505419272436114177280492632996639839, 21332165738600578491452964407091846638871, 22011600727359672849983371738442115750202, 22712459072684287189096957867362594028979, 23435409514216580549216768681043186492756, 24181141457781313033736709060684924399239, 24950365607653837105078820432150561913525, 25743814617978776217655279444067399027515, 26562243763913658848429735755295006551544, 27406431633088824925252542701175780449187, 28277180837992471708487055437712717352045, 29175318749907771935533688998238154899664, 30101698255047593493719018353250087892190, 31057198533551492479846827282772286526891, 32042725862029356114154254991939546568633, 33059214440356354939298084308255484473810, 34107627243444741858284340855851896810567, 35188956898739526139519661395680836241055, 36304226590207171330300936250672373177024, 37454490989609235371507738658545825445401, 38640837215876307921509562807791125952504, 39864385823421723342917322382785035095027, 41126291820259357904788932324436437797954, 42427745716815377000543767429142076613515, 43769974606350103661980441224565064256397, 45154243277933255051577181595961302673080, 46581855362943661250302574812481036293008, 48054154516093263478312214529343471041692, 49572525632004710501334374104559020188878, 51138396098402256673541054384635418234271, 52753237087006937831814272022904434024838, 54418564883259187786203275963851474098278, 56135942256025184883033675780848826845174, 57906979868477312243893664815333877800630, 59733337731374204777631081471702309003763, 61616726700001969696468737455137310898946, 63558910016075334637815377981815199417217, 65561704895935729043665912886512289642903, 67626984166422671493841473621547747890061, 69756677949835350437494776996882059609025, 71952775399442981349947854455835475358842, 74217326487045433836701325150566999246091, 76552443844129782664764169360591425415822, 78960304658213883176078895428261326581766, 81443152626014841111157818562607933339294, 84003299965128377684316640189885118056324, 86643129485954622034977750341592268435896, 89365096725656835281826697229948006980754, 92171732145992024828625219556511601293352, 95065643396906386996372681495200070409366, 98049517647844064387444182690661989722141, 101126123988774866775964711128543473621452, 104298315903005427204355863100123357131699, 107569033813898796111168829263890269121390, 110941307707689764842787967364432959922640, 114418259834647306332944079659796014677351, 118003107490901477028952044152573917598483, 121699165883319993740699402548587906985277, 125509851079889536946534334934079414850526, 129438683048128694731495030850946679101923, 133489288784133407087171903759440897228168, 137665405534931858550862408244356577093167, 141970884116904059585528307576933690738054, 146409692333101916929278382684538772852431, 150985918492388485397522905573328951615631, 155703775033400385173016327493921142804467, 160567602256425128237568670506014500638817, 165581872166375396005001684609744850933786, 170751192430135220135330874776205357150643, 176080310451648614735683265259541625131917, 181574117568219567595606191968037458694350, 187237653371593499855336608782839599108410, 193076110157494428899202448817240492657638, 199094837507399201941346305650586135104432, 205299347006440393735491298010890871105720, 211695317101442869538561671363388208207343, 218288598103215694837832769896310130186026, 225085217337341119935617328507479613638110, 232091384447825876443532607366609664204739, 239313496858107092960202147890843709079136, 246758145394035870378822272622492886759334, 254432120073596057956765705656077274905098, 262342416068254146996486838016806825735601, 270496239840978560292288607184620181431739, 278901015466113076071437143396418763158433, 287564391136439801892208252144808498914352, 296494245862922127048053369179796424991920, 305698696372777555051762412300895307355800, 315186104211694377809824067800745695876274, 324965083056174930804295304795170843128109, 335044506242161798322194627006540097615630, 345433514516281957644296467784594488150796, 356141524016227603154218875620684608178645, 367178234486981421586174587862744138084066, 378553637739788548241914240690558759965888, 390278026360977475350350904235883849145372, 402362002677937966540986661392100920835870, 414816487989775718847618771657086786320590, 427652732070381273538574378304681258183494, 440882322951874681892466154811921800464703, 454517196996617859166024564943359945836827, 468569649266223591783489820909701213431515, 483052344196233986693359896938961741118235, 497978326585391960636465784540867721389802, 513361032908687358914858737645900418452312, 529214302963624671877291375233595346480734, 545552391859432292200311960663658841634539, 562389982359214042482435678117269316557283, 579742197585332522066279842749829922238702, 597624614098610901957524369019806359916905, 616053275362245371203982435277301047619983, 635044705601634747680848839631023982004707, 654615924071657058193414954074072630378031, 674784459743255421384045155110038952844616, 695568366421537593469936862920419503687257, 716986238307945330020214637410513534841684, 739057226019411553010514735620155800936205, 761801053077795475211959225929099083341131, 785238032883268615471514492509607846986366, 809389086185718338685779482314718194478514, 834275759068640481721561995549041125198748, 859920241460409098286203019221498426049138, 886345386188239697760169810619495821214146, 913574728590602900351246792146986020166307, 941632506704298528058841351199475312189343, 970543682042866151921114995677278647051064, 1000333960983487384823225924581400908415224, 1031029816780028119906134208995063100349128, 1062658512220375851915276276781770664218055, 1095248122946748577988257684774235713620101, 1128827561458187961756718076825868579878199, 1163426601815000877926107409911247312671830, 1199075905065480563048101312186340462889834, 1235807045415821823339310647360694770976398, 1273652537164744545758602558478951360199679, 1312645862424956590411986075938008740269139, 1352821499654221489982197712488386716918466, 1394214953019448737907795174081020025344597, 1436862782617895317814287029484889852045770, 1480802635580257032679690476964336815048937, 1526073278081137668341210705222887430467303, 1572714628283113622050872264620245251593966, 1620767790241361907998596159942712275396795, 1670275088796590998896434046441232922226854, 1721280105484807372867707872023531641028787, 1773827715493266521620553303605539321191325, 1827964125692796169875209286436391463553324, 1883736913777542205454220450627627623259317, 1941195068544074990540045428979016191639996, 2000389031342706002066542299793470385460486, 2061370738734802836764995854566155303984553, 2124193666390855237295126848177651304771906, 2188912874265036693494950830717381377028748, 2255585053083026111045491605488788770723642, 2324268572180902803925801089505241532372552, 2395023528734006463865393777009618587865097, 2467911798415762618894099450970214743830291, 2542997087527614266341531131155488309496563, 2620344986642372729167756639129596232676117, 2700023025804506238499890103635894089061265, 2782100731332124214826958614641030125525703, 2866649684266689656207103547176805808440159, 2953743580517802421127563114076865977101494, 3043458292751743520432874651720063107204341, 3135871934073855838888529023956107673712656, 3231064923556261052910373332504935862797269, 3329120053663876986526898261070055923719636, 3430122559633205372646625087287937211822652, 3534160190859908112027331948036509871665786, 3641323284352781830643904592555281862394088, 3751704840313377042758262146206083252003804, 3865400599902190780808951173413769647996364, 3982509125254091437648230938615612208665896, 4103131881807413100481036594320324769150680, 4227373323012985194323423711608184825342596, 4355340977491243188514068153816831306895351, 4487145538707498883814621981695998192364169, 4622900957237435860424466344971232268204925, 4762724535696938539859365522259172192904979, 4906737026412463548801840841684873231780860, 5055062731910321266214119225872816963618338, 5207829608305455225661590517932499593346072, 5365169371672589117533265179651465213065049, 5527217607484957221664058373483343723457242, 5694113883208245978415885137066068212123749, 5866001864139853903170598890375497722568181, 6043029432586126043327997947804537261632986, 6225348810472839597848358451250756664355121, 6413116685486911149761987232778609385930658, 6606494340850065239034236380227641058150882, 6805647788828050819868979358323999932124240, 7010747908081918653627592069900003331313885, 7221970584970881095795482028016800180820721, 7439496858919368313305215988334362724771990, 7663513071964074049835939108652486902110027, 7894211022600052038312153153213944478502286, 8131788124048283504368802122476259666266295, 8376447567070589442260008009490542419035162, 8628398487461311075206252460332652862255740, 8887856138348830806441624164049446644850259, 9155042067443756769419570588999753348369075, 9430184299374449615171525434346929913380052, 9713517523254533328367646730292257128468580, 10005283285631105617251911693555313988951766, 10305730188966550833887158622225882793870924, 10615114095811162591357578955035756794792317, 10933698338828207481051879591623783495776717, 11261753936837608871545727424765479332663030, 11599559817049104097308327355988372276048642, 11947403043660532920062240162109982732038936, 12305579053001853563436039878064111396987556, 12674391895410558576190022945518383739880457, 13054154484029380065367934740521575035737492, 13445188850722536356548468579355836503711052, 13847826409312283888776199274753856796140269, 14262408226343203250985371145381259866780148, 14689285299587470941399899516935780651704730, 15128818844510353023514200659979474735307053, 15581380588921307822374775037453775778161261, 16047353076042406735268558256873995945513104, 16527129976232279828881942708844776384464289, 17021116407610470996229825460422687493186469, 17529729265833951018746497935845078659890151, 18053397563284591024896658648428572235865795, 18592562777933648798617019961060449405909563, 19147679212156771553800491680991098027580653, 19719214361780676686556748847336177859301463, 20307649295650542327464338407254381339975427, 20913479046015228078542293790419905560761109, 21537213010035759130193615737267088448395988, 22179375362731050171081952056678531837889796, 22840505481683625455563830127361075327371679, 23521158383837114577790556963222227106000454, 24221905174726576594546126895660998853438296, 24943333510492234997442188730027525898780317, 25686048073036999702793467468390786400124671, 26450671058698216939314139092285245295973631, 27237842680814431101251934813725928051352031, 28048221686578571931124162969964326092879283, 28882485888579903642551832555531326354473378, 29741332711448297843395776670122397861883486, 30625479754025927644678434167180990258864646, 31535665367503334638305708045172921411192557, 32472649249969002223583442636051886869991257, 33437213057834087022865114174942368814910252, 34430161034606824057360675774071124844324749, 35452320657504340411776429386623070217701549, 36504543302403196013949362207515330097647793, 37587704927643928869086720565780879321511877, 38702706777219225863983333932863348093272056, 39850476103890079618538830159833487410474911, 41031966912789437618869032001059848756084848, 42248160726088413119739466638144552323713487, 43500067369316119455836884732425450126947387, 44788725779940622161938557132353149517286403, 46115204838835388698521382300086700967297095, 47480604225272965964225446909163940530854245, 48886055296105443836288374939754912569146850, 50332721989809581743968458842609321908902282, 51821801756093298129565443975439366054876444, 53354526511779563329962057216972758755120795, 54932163623703609032906044555449817428152758, 56556016919379786521948984121697568905387876, 58227427726215386308830422339091993158663088, 59947775940070288750745505735874752333374707, 61718481123983464563536630863824661110113796, 63541003637910101895183114954840145149292684, 65416845800336519376734175109252150860580603, 67347553082664049326295825379342980093338072, 69334715337277759510580422669502260806303661, 71379968060241243503324661931781060749324186, 73484993689584767139344382479620231631183677, 75651522940180830762091099949674803438719295, 77881336176228713325723232474376057863740692, 80176264822397824887364220834077902488566333, 82538192814708729095848887627141354879711412, 84969058092260527985637712495417502527185280, 87470854130943949320510443975971946835138265, 90045631520310964084053249990010937444894325, 92695499584804111262350055974260737744844448, 95422628050581942200702573081762530097483506, 98229248759211141561480162743174860460818780, 101117657429530960930753745861664678146900761, 104090215469031639746372716613046079631949469, 107149351836125512459179342432451074387037948, 110297564954727537400216830254362020974452590, 113537424682601059135272019175625182351771821, 116871574334964760305280235070093485320251361, 120302732764897999994146845039030344917099694, 123833696502124103227405361570266404624249712, 127467341951794690775316299821751262820881739, 131206627654942851319650237363078640543654792, 135054596612318891391008027499470425580432487, 139014378673369585301307698714750696823099888, 143089192992170321476772911494889854353801084, 147282350552169337941209810862656202790787526, 151597256761654393940535419677042768604712910, 156037414121904773527302487822155138327467728, 160606424970045498010525842428806297123858552, 165307994298676076201980378700802929059254471, 170145932654403084070932109870040756168710712, 175124159117464379533146881818886304115161176, 180246704364692865515871516928175716173839969, 185517713818129458146794756789700737802672595, 190941450881658341049550188940772428156908867, 196522300268102736608633731882221903643157365, 202264771419286347221163140155395229044373926, 208173502021634361753239493581781000379902438, 214253261619958533712261273633312568534432854, 220508955332143368390591600698387426550353823, 226945627667524958132062352835746248064637032, 233568466451830531002429379443766529871241848, 240382806861625383006018171677560819894185695, 247394135571294603535256144602606866240405218, 254608095015669935411733325612529295818289145, 262030487771497293652789926334662608772703764, 269667281061027961524554376702089852893750024, 277524611381106350682779059931465398510289289, 285608789261219518075063188379075841701045142, 293926304154068441300563223938797391628021832, 302483829462318433559528236497029583024925005, 311288227705286098229483859533153862573065659, 320346555829422952370468512825476501720279146, 329666070666561360868064260343000838882005942, 339254234543996793186306018801880125891768132, 349118721050591719526787469215748980389969031, 359267420963200781319340509141723359392139708, 369708448337834283241288717642941671464293868, 380450146770097643363182274556695361095570047, 391501095829568289741422903357728378777292941, 402870117672898693278270594359324766532538649, 414566283840564867726663901314692596917724884, 426598922242313840494799852942560578757434467, 438977624336501397014428660715295722645259985, 451712252508652923999834250380300716164026723, 464812947654725522641673841317054538579675578, 478290136974698833996875010300762426852994254, 492154541982275320613296817419063021480897005, 506417186736628188612904384946629177037385896, 521089406302296823756465721686332489363901014, 536182855443495667067702889308553286989842029, 551709517559272987058732033726414836044686330, 567681713866131136215790299044381782863326237, 584112112834899732091089551822696678257870194, 601013739888837904274979492259791417839597310, 618399987370131427205120722214822202847265786, 636284624782145348147246779724001081380195366, 654681809314992756214978035210013805953036282, 673606096662185762054420590231604111296001465, 693072452136345712578743276113416150752087187, 713096262092166298476936146006078235148869758, 733693345665045675620103221811925839589137272, 754879966834032170432994681991340025646287799, 776672846817962733382493486664108976957797819, 799089176813914207769909350804312788545560063, 822146631087334861139118855960812993137861856, 845863380423477656407478640401062182049753410, 870258105950017596427655710881608384191819132, 895350013341003340908903434433902590340243612, 921158847412568355077259409777167008634536574, 947704907121109296671108703260237415752302351, 975009060974929378439831181825181614138429453, 1003092762870642259012048761577536344900501189, 1031978068365937822919977630423924788381164679, 1061687651400625223260725491897381989044758504, 1092244821478190996099333866524979808922587177, 1123673541320441138175675857178371108868614648, 1155998445008135998570275650221373071413852719, 1189244856620875906567575462640079440481899776, 1223438809389853884094553311483480470730670802, 1258607065377459820245926747296470281365858120, 1294777135698098372511393066450966101993668751, 1331977301294970866081833870637554996763958665, 1370236634287969857600959477643960487220012138, 1409585019908244088581211398017660321799847492, 1450053179035411559300661824373034368888015949, 1491672691353829696660870245298238166197288200, 1534476019144774367164618227346257726463963584, 1578496531731834104647063662459881829494293743, 1623768530597292695477448002061084962635120407, 1670327275187752513696917505446102298619907925, 1718209009427743055484269864637107802492230487, 1767450988960564325635712949770501863347983237, 1818091509136133426500226272916439354488032841, 1870169933766135249256642280413869548769941928, 1923726724667324935152078810077909633202004255, 1978803472014391136559675897059347341946632697, 2035442925524365450538378425403285032080279082, 2093689026495155117192662938550026550230539608, 2153586940721383578124807244516386442633461623, 2215183092311347193890775715280006108661858745, 2278525198429536751789077317873916660427033454, 2343662304989829795921741192667051288127895168]