171231

Ruby


ラマヌジャンのタウ函数のいろいろな計算方法(2)

実はτ(1), τ(2), ... と順に求めなくても
τ(p) (pは素数) を求める方法はあります。

http://www.ipgp.fr/~rozier/math/raman.html
に載っている式をもとに実装すると次のようになります。

require 'prime'

def A259825(n)
  return -1 if n == 0
  return 0 if n % 4 == 1 || n % 4 == 2
  s = 0
  (1..Math.sqrt(n / 3).to_i).each{|a|
    (0..a).each{|b|
      c4 = n + b * b
      if c4 % (4 * a) == 0
        c = c4 / (4 * a)
        if a == c
          if a == b
            s += 4
          elsif b == 0
            s += 6
          else
            s += 12
          end
        elsif a < c
          if a == b
            s += 12
          elsif b == 0
            s += 12
          else
            s += 24
          end
        end
      end
    }
  }
  s
end

def A(n)
  m = 4 * n
  (1..(2 * Math.sqrt(n)).to_i).inject(m ** 5 * A259825(m) / 2){|s, i| s + (m - i * i) ** 5 * A259825(m - i * i)} / 12
end

# nは素数
def B(n)
  A(n) - (462 * n ** 6 + 330 * n ** 4 - 165 * n ** 3 + 55 * n ** 2 - 11 * n + 1)
end

p B(104729)

出力結果
2643202687128887204371152330

このコードは以前のコードに比べ遅いわけではないのですが、
Hurwitz class number の計算アルゴリズムがまずいので、
思ったほど高速になっておらず改善が必要です。

ちなみにPARI で書けば、τ(n) はすぐ求まります。

171224

Ruby


ラマヌジャンのタウ函数のいろいろな計算方法(1)

この記事は
インテジャーズ Advent Calendar 2017 

の12/24 分として書いております。

前回はコロちゃんぬさんの「積分を使って自然数のべき乗の和を求める私」でした。

ラマヌジャンのタウ函数τ(n) は、

q*Procuct_{n>0} (1-q^n)^24 = Sum_{n>0} τ(n)*q^n

で求められます。

基本的な性質として、

① gcd(m, n) = 1 のとき、τ(m*n) ＝ τ(m)*τ(n).
② p が素数で r > 0 のとき、τ(p^(r + 1)) = τ(p)*τ(p^r) − p^11*τ(p^(r − 1))．

があります。

また、インテジャーズ にはτ(n)(http://integers.hatenablog.com/archive/category/%CF%84%28n%29)

に関するいろいろな事柄が載っています。

しかし、実際τ(n) をどのように求めればよいでしょうか？

性質①②を使えるときはいいのですが、τ(p)  (pは素数) を求めるには、

どうすればいいでしょうか？

方法1

定義に従う。

(Product_{n>0} (1-q^n))^24 のp - 1 次以下の項を計算する。

# m次以下を取り出す
def mul(f_ary, b_ary, m)
  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[0..m]
end

# m次以下を取り出す
def power(ary, n, m)
  return [1] if n == 0
  k = power(ary, n >> 1, m)
  k = mul(k, k, m)
  return k if n & 1 == 0
  return mul(k, ary, m)
end

def A(n)
  ary = [1]
  (1..n).each{|i|
    b_ary = Array.new(i + 1, 0)
    b_ary[0], b_ary[-1] = 1, -1
    ary = mul(ary, b_ary, n)
  }
  power(ary, 24, n)
end

n = 19
p A(n - 1)

出力結果
[1, -24, 252, -1472, 4830, -6048, -16744, 84480, -113643, -115920, 534612, -370944, -577738, 401856, 1217160, 987136, -6905934, 2727432, 10661420]

方法2
ヤコビの公式を用いる。（「数学の微笑み」山下純一著 p.289 ）

(Product_{n>0} (1-q^n))^3 の8乗のp - 1 次以下の項を計算する。

# m次以下を取り出す
def mul(f_ary, b_ary, m)
  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[0..m]
end

# m次以下を取り出す
def power(ary, n, m)
  return [1] if n == 0
  k = power(ary, n >> 1, m)
  k = mul(k, k, m)
  return k if n & 1 == 0
  return mul(k, ary, m)
end

def A(n)
  ary = Array.new(n + 1, 0)
  # ヤコビの公式の必要なところだけ取り出す
  i = 0
  j, k = 2 * i + 1, i * (i + 1) / 2
  while k <= n
    i & 1 == 1? ary[k] = -j : ary[k] = j
    i += 1
    j, k = 2 * i + 1, i * (i + 1) / 2
  end
  power(ary, 8, n)
end

n = 19
p A(n - 1)

出力結果
[1, -24, 252, -1472, 4830, -6048, -16744, 84480, -113643, -115920, 534612, -370944, -577738, 401856, 1217160, 987136, -6905934, 2727432, 10661420]

方法3
{-24, -24, -24, ... } のEuler transform を利用する。

171119 分において、
f(n) = -m, g(n) = 1
とすると、次のようになる。

Product_{n>0} (1-q^n)^m = a(0) + a(1)*q + a(2)*q^2 + ... .
このとき、
a(n) = -(m/n) * Sum_{k=1..n} b(k)*a(n-k).
(ただし、b(n) = Sum_{d|n} d)

この方法はm乗しているのに、計算量が少なくてすむので、良い方法と言えます。

以下は、b(n) について公式を使わず単純に約数を足していったコードです。

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

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

n = 19
p A(24, n - 1)

出力結果
[1, -24, 252, -1472, 4830, -6048, -16744, 84480, -113643, -115920, 534612, -370944, -577738, 401856, 1217160, 987136, -6905934, 2727432, 10661420]

この方法が速いとしばらく思っていたのですが、
今年（2017）9月に「ラマヌジャン《ゼータ関数論文集》」p.112
に次の方法が載っていて見つけて、衝撃を受けました。
(もちろん方法3 も載っていました。さすがですね、Ramanujan は！)

方法4
次の等式を利用する。

1*(n - 1)*τ(n - 0) - 3*(n - 10)*τ(n - 1) + 5(n - 28)*τ(n - 3) - 7*(n-55)*τ(n - 6) + ... = 0
ここで、
数列0, 1, 3, 6, ... の第r項はr*(r - 1)/2 であり、
数列1, 10, 28, 55, ... の第r項は1+9*r*(r - 1)/2.

def A(n)
  ary = [0, 1]
  (2..n).each{|i|
    s, t, u = 0, 1, 0
    (1..n).each{|j|
      t += 9 * j
      u += j
      break if i <= u
      s += (-1) ** (j % 2 + 1) * (2 * j + 1) * (i - t) * ary[-u]
    }
    ary << s / (i - 1)
  }
  ary[1..-1]
end

n = 458329
p A(n)[-1]

出力結果
-11695495424911987900947041440697

方法5
方法4 に対し、性質①②を使う。

require 'prime'

def A(n)
  ary = [0, 1]
  (2..n).each{|i|
    a = i.prime_division
    # i = p^q
    if a.size == 1
      s, t, u = 0, 1, 0
      (1..n).each{|j|
        t += 9 * j
        u += j
        break if i <= u
        s += (-1) ** (j % 2 + 1) * (2 * j + 1) * (i - t) * ary[-u]
      }
      ary << s / (i - 1)
    else
      s = 1
      a.each{|j|
        k, l = j[0], j[1]
        if l == 1
          s *= ary[k]
        else
          s *= ary[k ** (l - 1)] * ary[k] - k ** 11 * ary[k ** (l - 2)]
        end
      }
      ary << s
    end
  }
  ary[1..-1]
end

n = 458329
p A(n)[-1]

出力結果
-11695495424911987900947041440697

171209(2)

Ruby


Number of Gaussian primes a+b*i such that a^2 + b^2 <= 10^n

A091098 のデータを用いて計算してみた。

require 'prime'

def A(n)
  ary = []
  cnt = 0
  (0..n).each{|i|
    cnt += 1 if i % 4 == 3 && i.prime?
    ary << cnt
  }
  ary
end

ary1 = [0] +
[1,11,80,609,4783,39175,332180,2880504,25423491,
 227523275,2059020280,18803924340,173032709183,
 1602470783672,14922284735484,139619168787795,
 1311778575685086,12369977142579584,
 117028833597800689,1110409801150582707]
ary2 =
[1,3,10,31,100,316,1000,3162,10000,31622,100000,
 316227,1000000,3162277,10000000,31622776,
 100000000,316227766,1000000000,3162277660,
 10000000000,31622776601,100000000000]

n = 8
ary = A(10 ** n)
p (1..2 * n).map{|i| 8 * ary1[i] + 4 * ary[ary2[i]] + 4}

出力結果
[16, 100, 668, 4928, 38404, 313752, 2658344, 23046512, 203394764, 1820205436, 16472216912, 150431552012, 1384262129028, 12819767598972, 119378281788240, 1116953361826164]

171209

Ruby


Number of Gaussian primes a+b*i such that sqrt(a^2 + b^2) <= 10^n

A091098 とA091099 のデータを用いて計算してみた。

ary1 = [0] +
[1,11,80,609,4783,39175,332180,2880504,25423491,
 227523275,2059020280,18803924340,173032709183,
 1602470783672,14922284735484,139619168787795,
 1311778575685086,12369977142579584,
 117028833597800689,1110409801150582707]
ary3 = [0] +
[2,13,87,619,4808,39322,332398,2880950,25424042,
 227529235,2059034532,18803987677,173032827655,
 1602470967129,14922285687184,139619172246129,
 1311778581969146,12369977145161275,
 117028833678543917,1110409801410336132]
p (1..10).map{|i| 8 * ary1[2 * i] + 4 * ary3[i] + 4}

出力結果
[100, 4928, 313752, 23046512, 1820205436, 150431552012, 12819767598972, 1116953361826164, 98959817242332844, 8883278410114778600]

171119

A generalized Euler transform

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

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

このとき、

 a(n) = (1/n) * Sum_{k=1..n} b(k)*a(n-k). 

(ただし、b(n) = Sum_{d|n} d*f(d)*g(d)^(n/d))

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

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

171118

Ruby


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

それぞれ計算してみた。

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

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

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

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

171109

Ruby


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

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

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

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

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

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

171106

Ruby


8765432 * 8 = 70123456

数遊びをしてみる。

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

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

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

171009

Ruby


PD(n), PD_t(n), PDO(n) and PDO_t(n)

つい最近の論文だが、
Bernard L. S. Lin, The number of tagged parts over the partitions with designated summands, Journal of Number Theory.
においてPD_t(n) と PDO_t(n) が考え出されたので、数えてみた。
n の分割を一つずつcheck しているので、かなり遅いコードです。

# 和因子はmin以上max以下
def partition(n, min, max)
  return [[]] if n == 0
  [max, n].min.downto(min).flat_map{|i| partition(n - i, min, i).map{|rest| [i, *rest]}}
end

def PD(n)
  partition(n, 1, n).map{|i| i.each_with_object(Hash.new(0)){|v, o| o[v] += 1}.values.inject(:*)}.inject(:+)
end

def PD_t(n)
  partition(n, 1, n).map{|i| i.each_with_object(Hash.new(0)){|v, o| o[v] += 1}.values}.map{|i| i.size * i.inject(:*)}.inject(:+)
end

def PDO(n)
  partition(n, 1, n).select{|i| i.all?{|j| j.odd?}}.map{|a| a.each_with_object(Hash.new(0)){|v, o| o[v] += 1}.values.inject(:*)}.inject(:+)
end

def PDO_t(n)
  partition(n, 1, n).select{|i| i.all?{|j| j.odd?}}.map{|a| a.each_with_object(Hash.new(0)){|v, o| o[v] += 1}.values}.map{|i| i.size * i.inject(:*)}.inject(:+)
end

n = 40
p (1..n).map{|i| PD(i)}
p (1..n).map{|i| PD_t(i)}
p (1..n).map{|i| PDO(i)}
p (1..n).map{|i| PDO_t(i)}

出力結果
[1, 3, 5, 10, 15, 28, 41, 69, 102, 160, 231, 352, 498, 732, 1027, 1470, 2031, 2856, 3896, 5382, 7272, 9896, 13233, 17800, 23579, 31362, 41219, 54288, 70791, 92456, 119698, 155097, 199512, 256664, 328134, 419436, 533162, 677412, 856573, 1082284]
[1, 3, 6, 13, 24, 45, 77, 132, 213, 346, 537, 834, 1257, 1893, 2778, 4077, 5865, 8421, 11903, 16785, 23364, 32444, 44562, 61041, 82859, 112164, 150639, 201768, 268413, 356100, 469636, 617724, 808236, 1054802, 1370127, 1775286, 2290610, 2948427, 3780717, 4836814]
[1, 2, 4, 5, 8, 12, 16, 22, 32, 42, 56, 76, 98, 128, 168, 213, 272, 348, 436, 548, 688, 852, 1056, 1308, 1603, 1964, 2404, 2920, 3544, 4296, 5176, 6230, 7488, 8958, 10704, 12772, 15182, 18024, 21368, 25254]
[1, 2, 4, 6, 10, 16, 24, 36, 52, 74, 104, 144, 196, 264, 352, 468, 614, 800, 1036, 1332, 1704, 2168, 2744, 3456, 4331, 5408, 6724, 8328, 10278, 12640, 15496, 18936, 23072, 28030, 33960, 41040, 49470, 59488, 71368, 85428]

170924

Ruby


途中で自身と交差しないgolygon の数

自身と交差しないように伸ばしていき、始点と終点が一致したらカウントする。
以下において、線対称のものや点対称なものは同一なものとみなすために、[[0, 0], [1, 0], [1, 1], [1, 2]] から出発している。

def A(n)
  b_ary = [[[0, 0], [1, 0], [1, 1], [1, 2]]]
  s = 4
  (3..n).each{|i|
    s += i
    t = 0
    f_ary, b_ary = b_ary, []
    if i % 2 == 1
      f_ary.each{|a|
        b = a.clone
        x, y = *b[-1]
        b += (1..i).map{|j| [x + j, y]}
        b_ary << b if b.uniq.size == s
        t += 1 if b[-1] == [0, 0] && b.uniq.size == s - 1
        c = a.clone
        x, y = *c[-1]
        c += (1..i).map{|j| [x - j, y]}
        b_ary << c if c.uniq.size == s
        t += 1 if c[-1] == [0, 0] && c.uniq.size == s - 1
      }
    else
      f_ary.each{|a|
        b = a.clone
        x, y = *b[-1]
        b += (1..i).map{|j| [x, y + j]}
        b_ary << b if b.uniq.size == s
        t += 1 if b[-1] == [0, 0] && b.uniq.size == s - 1
        c = a.clone
        x, y = *c[-1]
        c += (1..i).map{|j| [x, y - j]}
        b_ary << c if c.uniq.size == s
        t += 1 if c[-1] == [0, 0] && c.uniq.size == s - 1
      }
    end
    p [i, b_ary.size, t]
  }
end

A(24)

出力結果
[3, 2, 0]
[4, 4, 0]
[5, 8, 0]
[6, 16, 0]
[7, 29, 1]
[8, 54, 1]
[9, 98, 0]
[10, 176, 0]
[11, 318, 0]
[12, 572, 0]
[13, 1026, 0]
[14, 1826, 0]
[15, 3255, 1]
[16, 5794, 3]
[17, 10233, 0]
[18, 18172, 0]
[19, 32012, 0]
[20, 56488, 0]
[21, 99469, 0]
[22, 175034, 0]
[23, 307479, 25]
[24, 540068, 67]

170917

Ruby


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

いろいろ計算してみた。

# m次以下を取り出す
def mul(f_ary, b_ary, m)
  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[0..m]
end

def q(n)
  ary = [1]
  (1..n).each{|i|
    b_ary = Array.new(i + 1, 0)
    b_ary[0], b_ary[-1] = 1, -1 * i ** i
    ary = mul(ary, b_ary, n)
  }
  ary
end

def r(n)
  ary = [1]
  (1..n).each{|i|
    b_ary = Array.new(i + 1, 0)
    b_ary[0], b_ary[-1] = 1, i ** i
    ary = mul(ary, b_ary, n)
  }
  ary
end

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

n = 30
p ary0 = q(n)
p ary1 = r(n)
p ary2 = I(ary0, n)
p ary3 = I(ary1, n)
p mul(ary2, ary1, n)
p mul(ary3, ary0, n)

出力結果
[1, -1, -4, -23, -229, -2761, -42615, -758499, -15702086, -365588036, -9516954786, -273061566624, -8575969258607, -292418459301779, -10762887030763337, -425243370397722674, -17953905924215881215, -806666656048846472309, -38431184040433830671913, -1935181289882115032490348, -102696392415846742681733803, -5728632608276744273452117182, -335107577316074301942345694886, -20512630873623057901876906465743, -1311322803795912839879249103895553, -87390960343889620272724433296491880, -6061384949468492645254259961399089464, -436878303197147196764997753948315233462, -32675044025947179003139330924063144267098, -2532599985989370726380519904538079256177793, -203178927579931810874025726965036433479741952]
[1, 1, 4, 31, 283, 3489, 50913, 890635, 17891170, 409850236, 10494427982, 297780829216, 9261266862273, 313453533534739, 11464487066049791, 450644378868285130, 18942868694407904729, 847930346323808122469, 40266107916200371331007, 2021842180288047801103956, 107026915281000730387703597, 5956920792270319632604392638, 347766996555495797707882798050, 21249290771649866280391823962687, 1356203113541047768153856405218415, 90247872040648581142764137451127200, 6251045242578198262043978824453943552, 449986789520111038545971104837143420374, 33616803977128282789561343587331315553990, 2602827576431911410805372650653659864258097, 208607296163683382331588381297500504996596528]
[1, 1, 5, 32, 304, 3537, 52010, 895397, 18016416, 410889848, 10523505770, 298220329546, 9274349837081, 313761671751672, 11474635626789410, 450964042480390679, 18954785687060988578, 848386888530723146912, 40285405287225043910550, 2022698192735125064374800, 107067613600574960842869576, 5958957516540411012538481312, 347874804978251035491293556717, 21255282815702806741512542156320, 1356552811381527011063310886545470, 90269224251818008284503526617607078, 6252407532636283837248750189467023717, 450077403312833906134664153832793562364, 33623078468794716158752737057969922475976, 2603279113832594183853952144206489719837940, 208641020463859049059313644666998258355430174]
[1, -1, -3, -24, -216, -2801, -42166, -762397, -15685040, -366477168, -9523974486, -273453483050, -8583651341879, -292700900034984, -10770969729108326, -425541512224476567, -17964544188354355022, -807097409926675847400, -38449179088918106730042, -1935995586006883907808752, -102735038083633766766200104, -5730581947986227695150297888, -335210860205816356266926854547, -20518393122544722624597111147808, -1311659607987077558310145244098602, -87411571945797047722216818621423270, -6062701957007870019784615581091956971, -436966047377686875806620404700796453836, -32681127837457227556660506055780683473056, -2533038365769715605507253992215447626184148, -203211706477802433958484054091329820521418882]
[1, 2, 10, 72, 670, 7896, 113572, 1939028, 38463550, 869985586, 22098989952, 622728621984, 19271496576612, 649553583740576, 23680212403186584, 928276782505698920, 38931911577966732814, 1739307919812511213916, 82457732209611432170734, 4134332214683068511774360, 218571693750448020952237320, 12151433216474061126692855544, 708681796526773664772725730484, 43262208674596350481233572256220, 2758850451023924655314677909544156, 183447630069846653980774132586045578, 12697779769212378577890958151960322616, 913481287056820111505540890891259894512, 68202897342458921851677850241305214595856, 5277856400612667842830537137988358006717320, 422789855843929721189297554892073186276560960]
[1, -2, -6, -40, -386, -4952, -77116, -1406164, -29389570, -692122610, -18136684128, -523599632000, -16516245738140, -565284631133600, -20867650682241704, -826570263691236456, -34971594470460748146, -1574134630989710480092, -75112891524338162634738, -3787501458905707932689624, -201240964401742491982486232, -11237894858423246782723969912, -658024667786251446968867597516, -40314567351662431043301810882140, -2579273656774611774378855454069348, -172016784947022142035636886184836810, -11938944232415141586380847510506717576, -861035041333795546595133505653207412816, -64435043361878584792236753365477810430576, -4996889981730534854860472118983399729109384, -401072365202100827015447833505813210666185920]

170827

Ruby


j がn 以下のとき、Sum_{i=1..j} s_i | Product_{i=1..j} s_i を満たす1～n の順列

小学生のときから何度か考えた問題だったのですが、
昨日まで自明な[1] 以外に答えがあるかわかりませんでした。

実はこれ以外にも条件を満たすものがあります。

例えば、[10, 15, 5, 6, 4, 8, 2, 14, 11, 13, 3, 7, 1, 9, 12] が条件を満たします。

Excel で簡単に確認できます。

10		10		10		1
15		25		150		6
5		30		750		25
6		36		4,500		125
4		40		18,000		450
8		48		144,000		3,000
2		50		288,000		5,760
14		64		4,032,000		63,000
11		75		44,352,000		591,360
13		88		576,576,000		6,552,000
3		91		1,729,728,000		19,008,000
7		98		12,108,096,000		123,552,000
1		99		12,108,096,000		122,304,000
9		108		108,972,864,000		1,009,008,000
12		120		1,307,674,368,000		10,897,286,400

n が17以下のとき、条件を満たすものを探してみた。

def search(a, prod, sum, size, num)
  if num == size + 1
    @ary << a.clone
  else
    (1..size).each{|i|
      p, s = prod * i, sum + i
      if a[i - 1] == 0 && p % s == 0
        a[i - 1] = num
        search(a, p, s, size, num + 1)
        a[i - 1] = 0
      end
    }
  end
end

def A(n)
  a = [0] * n
  @ary = []
  search(a, 1, 0, n, 1)
  @ary.map{|i| (1..n).map{|j| i.index(j) + 1}}
end

n = 17
(1..n).each{|i| p [i, A(i)]}

出力結果
[1, [[1]]]
[2, []]
[3, []]
[4, []]
[5, []]
[6, []]
[7, []]
[8, []]
[9, []]
[10, []]
[11, []]
[12, []]
[13, []]
[14, []]
[15, [[10, 15, 5, 6, 4, 8, 2, 14, 11, 13, 3, 7, 1, 9, 12], [10, 15, 5, 6, 12, 2, 14, 11, 13, 3, 7, 1, 9, 4, 8], [10, 15, 5, 6, 12, 2, 14, 11, 13, 3, 9, 4, 1, 7, 8], [10, 15, 5, 6, 14, 13, 2, 7, 8, 11, 9, 4, 1, 3, 12], [10, 15, 5, 6, 14, 13, 2, 7, 8, 11, 9, 4, 1, 12, 3], [10, 15, 5, 6, 14, 13, 7, 2, 8, 11, 9, 4, 1, 3, 12], [10, 15, 5, 6, 14, 13, 7, 2, 8, 11, 9, 4, 1, 12, 3], [10, 15, 5, 6, 14, 13, 7, 8, 2, 11, 9, 4, 1, 3, 12], [10, 15, 5, 6, 14, 13, 7, 8, 2, 11, 9, 4, 1, 12, 3], [10, 15, 5, 6, 14, 13, 9, 8, 11, 7, 2, 4, 1, 3, 12], [10, 15, 5, 6, 14, 13, 9, 8, 11, 7, 2, 4, 1, 12, 3], [10, 15, 5, 6, 14, 13, 12, 3, 2, 11, 7, 1, 9, 4, 8], [10, 15, 5, 6, 14, 13, 12, 3, 2, 11, 9, 4, 1, 7, 8], [15, 10, 5, 6, 4, 8, 2, 14, 11, 13, 3, 7, 1, 9, 12], [15, 10, 5, 6, 12, 2, 14, 11, 13, 3, 7, 1, 9, 4, 8], [15, 10, 5, 6, 12, 2, 14, 11, 13, 3, 9, 4, 1, 7, 8], [15, 10, 5, 6, 14, 13, 2, 7, 8, 11, 9, 4, 1, 3, 12], [15, 10, 5, 6, 14, 13, 2, 7, 8, 11, 9, 4, 1, 12, 3], [15, 10, 5, 6, 14, 13, 7, 2, 8, 11, 9, 4, 1, 3, 12], [15, 10, 5, 6, 14, 13, 7, 2, 8, 11, 9, 4, 1, 12, 3], [15, 10, 5, 6, 14, 13, 7, 8, 2, 11, 9, 4, 1, 3, 12], [15, 10, 5, 6, 14, 13, 7, 8, 2, 11, 9, 4, 1, 12, 3], [15, 10, 5, 6, 14, 13, 9, 8, 11, 7, 2, 4, 1, 3, 12], [15, 10, 5, 6, 14, 13, 9, 8, 11, 7, 2, 4, 1, 12, 3], [15, 10, 5, 6, 14, 13, 12, 3, 2, 11, 7, 1, 9, 4, 8], [15, 10, 5, 6, 14, 13, 12, 3, 2, 11, 9, 4, 1, 7, 8]]]
[16, []]
[17, [[10, 15, 5, 6, 4, 8, 2, 14, 11, 9, 12, 16, 13, 1, 17, 7, 3], [10, 15, 5, 6, 4, 8, 2, 14, 11, 9, 16, 12, 13, 1, 17, 7, 3], [10, 15, 5, 6, 4, 8, 2, 14, 11, 13, 3, 7, 12, 16, 17, 1, 9], [10, 15, 5, 6, 4, 8, 2, 14, 11, 13, 3, 17, 12, 16, 7, 1, 9], [10, 15, 5, 6, 4, 8, 2, 14, 11, 13, 12, 17, 3, 16, 7, 1, 9], [10, 15, 5, 6, 4, 8, 2, 14, 11, 13, 16, 1, 3, 17, 7, 12, 9], [10, 15, 5, 6, 4, 8, 2, 14, 11, 13, 16, 1, 12, 9, 17, 7, 3], [10, 15, 5, 6, 4, 8, 2, 14, 11, 13, 17, 3, 12, 16, 7, 1, 9], [10, 15, 5, 6, 4, 8, 2, 14, 11, 13, 17, 7, 16, 12, 3, 1, 9], [10, 15, 5, 6, 4, 8, 2, 14, 11, 13, 17, 12, 3, 16, 7, 1, 9], [10, 15, 5, 6, 4, 8, 16, 11, 13, 2, 14, 1, 3, 17, 7, 12, 9], [10, 15, 5, 6, 4, 8, 16, 11, 13, 2, 14, 1, 12, 9, 17, 7, 3], [10, 15, 5, 6, 12, 2, 14, 11, 9, 4, 8, 16, 13, 1, 17, 7, 3], [10, 15, 5, 6, 12, 2, 14, 11, 9, 16, 8, 4, 13, 1, 17, 7, 3], [10, 15, 5, 6, 12, 2, 14, 11, 9, 16, 8, 17, 3, 7, 1, 4, 13], [10, 15, 5, 6, 12, 2, 14, 11, 9, 16, 8, 17, 7, 3, 1, 4, 13], [10, 15, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 7, 1, 8, 16, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 7, 1, 16, 8, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 7, 16, 1, 8, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 7, 16, 8, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 8, 16, 7, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 16, 7, 1, 8, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 16, 7, 8, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 16, 8, 7, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 8, 4, 17, 3, 16, 7, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 16, 1, 3, 17, 7, 4, 8, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 16, 1, 3, 17, 7, 8, 4, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 16, 4, 9, 8, 1, 17, 7, 3], [10, 15, 5, 6, 12, 2, 14, 11, 13, 16, 4, 17, 1, 9, 8, 7, 3], [10, 15, 5, 6, 12, 2, 14, 11, 13, 16, 4, 17, 3, 7, 1, 8, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 16, 4, 17, 3, 7, 8, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 16, 4, 17, 3, 8, 7, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 16, 4, 17, 7, 3, 1, 8, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 16, 4, 17, 7, 3, 8, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 16, 4, 17, 7, 8, 3, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 7, 1, 8, 16, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 7, 1, 16, 8, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 7, 16, 1, 8, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 7, 16, 8, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 8, 16, 7, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 16, 7, 1, 8, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 16, 7, 8, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 16, 8, 7, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 17, 7, 8, 16, 4, 3, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 17, 7, 16, 4, 3, 1, 8, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 17, 7, 16, 4, 3, 8, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 17, 7, 16, 4, 8, 3, 1, 9], [10, 15, 5, 6, 12, 2, 14, 11, 13, 17, 7, 16, 8, 4, 3, 1, 9], [10, 15, 5, 6, 12, 16, 11, 13, 2, 9, 1, 8, 17, 7, 4, 14, 3], [10, 15, 5, 6, 12, 16, 11, 13, 2, 9, 1, 17, 8, 7, 4, 14, 3], [10, 15, 5, 6, 12, 16, 11, 13, 2, 14, 1, 3, 17, 7, 4, 8, 9], [10, 15, 5, 6, 12, 16, 11, 13, 2, 14, 1, 3, 17, 7, 8, 4, 9], [10, 15, 5, 6, 12, 16, 11, 13, 2, 14, 4, 9, 8, 1, 17, 7, 3], [10, 15, 5, 6, 12, 16, 11, 13, 2, 14, 4, 17, 1, 9, 8, 7, 3], [10, 15, 5, 6, 12, 16, 11, 13, 2, 14, 4, 17, 3, 7, 1, 8, 9], [10, 15, 5, 6, 12, 16, 11, 13, 2, 14, 4, 17, 3, 7, 8, 1, 9], [10, 15, 5, 6, 12, 16, 11, 13, 2, 14, 4, 17, 3, 8, 7, 1, 9], [10, 15, 5, 6, 12, 16, 11, 13, 2, 14, 4, 17, 7, 3, 1, 8, 9], [10, 15, 5, 6, 12, 16, 11, 13, 2, 14, 4, 17, 7, 3, 8, 1, 9], [10, 15, 5, 6, 12, 16, 11, 13, 2, 14, 4, 17, 7, 8, 3, 1, 9], [10, 15, 5, 6, 14, 13, 2, 7, 3, 16, 17, 11, 1, 8, 4, 12, 9], [10, 15, 5, 6, 14, 13, 2, 7, 3, 16, 17, 11, 1, 8, 12, 4, 9], [10, 15, 5, 6, 14, 13, 2, 7, 3, 16, 17, 11, 1, 12, 4, 8, 9], [10, 15, 5, 6, 14, 13, 2, 7, 3, 16, 17, 11, 1, 12, 8, 4, 9], [10, 15, 5, 6, 14, 13, 2, 7, 8, 4, 16, 17, 11, 12, 3, 1, 9], [10, 15, 5, 6, 14, 13, 2, 7, 8, 16, 4, 17, 11, 12, 3, 1, 9], [10, 15, 5, 6, 14, 13, 2, 7, 8, 16, 12, 17, 11, 4, 3, 1, 9], [10, 15, 5, 6, 14, 13, 2, 7, 12, 16, 4, 1, 3, 17, 11, 8, 9], [10, 15, 5, 6, 14, 13, 2, 7, 12, 16, 8, 17, 11, 4, 3, 1, 9], [10, 15, 5, 6, 14, 13, 2, 7, 12, 16, 17, 8, 11, 4, 3, 1, 9], [10, 15, 5, 6, 14, 13, 2, 7, 12, 16, 17, 11, 4, 3, 1, 8, 9], [10, 15, 5, 6, 14, 13, 2, 7, 12, 16, 17, 11, 4, 3, 8, 1, 9], [10, 15, 5, 6, 14, 13, 2, 7, 12, 16, 17, 11, 4, 8, 3, 1, 9], [10, 15, 5, 6, 14, 13, 2, 7, 12, 16, 17, 11, 8, 4, 3, 1, 9], [10, 15, 5, 6, 14, 13, 7, 2, 3, 16, 17, 11, 1, 8, 4, 12, 9], [10, 15, 5, 6, 14, 13, 7, 2, 3, 16, 17, 11, 1, 8, 12, 4, 9], [10, 15, 5, 6, 14, 13, 7, 2, 3, 16, 17, 11, 1, 12, 4, 8, 9], [10, 15, 5, 6, 14, 13, 7, 2, 3, 16, 17, 11, 1, 12, 8, 4, 9], [10, 15, 5, 6, 14, 13, 7, 2, 8, 4, 16, 17, 11, 12, 3, 1, 9], [10, 15, 5, 6, 14, 13, 7, 2, 8, 16, 4, 17, 11, 12, 3, 1, 9], [10, 15, 5, 6, 14, 13, 7, 2, 8, 16, 12, 17, 11, 4, 3, 1, 9], [10, 15, 5, 6, 14, 13, 7, 2, 12, 16, 4, 1, 3, 17, 11, 8, 9], [10, 15, 5, 6, 14, 13, 7, 2, 12, 16, 8, 17, 11, 4, 3, 1, 9], [10, 15, 5, 6, 14, 13, 7, 2, 12, 16, 17, 8, 11, 4, 3, 1, 9], [10, 15, 5, 6, 14, 13, 7, 2, 12, 16, 17, 11, 4, 3, 1, 8, 9], [10, 15, 5, 6, 14, 13, 7, 2, 12, 16, 17, 11, 4, 3, 8, 1, 9], [10, 15, 5, 6, 14, 13, 7, 2, 12, 16, 17, 11, 4, 8, 3, 1, 9], [10, 15, 5, 6, 14, 13, 7, 2, 12, 16, 17, 11, 8, 4, 3, 1, 9], [10, 15, 5, 6, 14, 13, 7, 8, 2, 4, 16, 17, 11, 12, 3, 1, 9], [10, 15, 5, 6, 14, 13, 7, 8, 2, 16, 4, 17, 11, 12, 3, 1, 9], [10, 15, 5, 6, 14, 13, 7, 8, 2, 16, 12, 17, 11, 4, 3, 1, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 4, 7, 17, 11, 1, 8, 16, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 4, 7, 17, 11, 1, 16, 8, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 4, 7, 17, 11, 16, 1, 8, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 4, 7, 17, 11, 16, 8, 1, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 4, 16, 8, 17, 11, 7, 1, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 4, 16, 17, 8, 11, 7, 1, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 4, 16, 17, 11, 7, 1, 8, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 4, 16, 17, 11, 7, 8, 1, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 4, 16, 17, 11, 8, 7, 1, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 7, 1, 8, 16, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 7, 1, 16, 8, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 7, 16, 1, 8, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 7, 16, 8, 1, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 8, 16, 7, 1, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 16, 7, 1, 8, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 16, 7, 8, 1, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 16, 8, 7, 1, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 16, 4, 8, 17, 11, 7, 1, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 16, 4, 17, 8, 11, 7, 1, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 16, 4, 17, 11, 7, 1, 8, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 16, 4, 17, 11, 7, 8, 1, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 16, 4, 17, 11, 8, 7, 1, 9], [10, 15, 5, 6, 14, 13, 12, 3, 2, 16, 8, 4, 17, 11, 7, 1, 9], [10, 15, 5, 6, 14, 13, 12, 16, 7, 2, 4, 1, 3, 17, 11, 8, 9], [10, 15, 5, 6, 14, 13, 12, 16, 7, 2, 8, 17, 11, 4, 3, 1, 9], [10, 15, 5, 6, 14, 13, 12, 16, 7, 2, 17, 8, 11, 4, 3, 1, 9], [10, 15, 5, 6, 14, 13, 12, 16, 7, 2, 17, 11, 4, 3, 1, 8, 9], [10, 15, 5, 6, 14, 13, 12, 16, 7, 2, 17, 11, 4, 3, 8, 1, 9], [10, 15, 5, 6, 14, 13, 12, 16, 7, 2, 17, 11, 4, 8, 3, 1, 9], [10, 15, 5, 6, 14, 13, 12, 16, 7, 2, 17, 11, 8, 4, 3, 1, 9], [10, 15, 5, 6, 14, 13, 12, 16, 17, 4, 7, 11, 2, 3, 1, 8, 9], [10, 15, 5, 6, 14, 13, 12, 16, 17, 4, 7, 11, 2, 3, 8, 1, 9], [10, 15, 5, 6, 14, 13, 12, 16, 17, 4, 7, 11, 2, 8, 3, 1, 9], [10, 15, 5, 6, 14, 13, 12, 16, 17, 11, 7, 2, 4, 3, 1, 8, 9], [10, 15, 5, 6, 14, 13, 12, 16, 17, 11, 7, 2, 4, 3, 8, 1, 9], [10, 15, 5, 6, 14, 13, 12, 16, 17, 11, 7, 2, 4, 8, 3, 1, 9], [10, 15, 5, 6, 14, 13, 12, 16, 17, 11, 7, 2, 8, 4, 3, 1, 9], [10, 15, 5, 6, 14, 13, 12, 16, 17, 11, 7, 4, 2, 3, 1, 8, 9], [10, 15, 5, 6, 14, 13, 12, 16, 17, 11, 7, 4, 2, 3, 8, 1, 9], [10, 15, 5, 6, 14, 13, 12, 16, 17, 11, 7, 4, 2, 8, 3, 1, 9], [15, 10, 5, 6, 4, 8, 2, 14, 11, 9, 12, 16, 13, 1, 17, 7, 3], [15, 10, 5, 6, 4, 8, 2, 14, 11, 9, 16, 12, 13, 1, 17, 7, 3], [15, 10, 5, 6, 4, 8, 2, 14, 11, 13, 3, 7, 12, 16, 17, 1, 9], [15, 10, 5, 6, 4, 8, 2, 14, 11, 13, 3, 17, 12, 16, 7, 1, 9], [15, 10, 5, 6, 4, 8, 2, 14, 11, 13, 12, 17, 3, 16, 7, 1, 9], [15, 10, 5, 6, 4, 8, 2, 14, 11, 13, 16, 1, 3, 17, 7, 12, 9], [15, 10, 5, 6, 4, 8, 2, 14, 11, 13, 16, 1, 12, 9, 17, 7, 3], [15, 10, 5, 6, 4, 8, 2, 14, 11, 13, 17, 3, 12, 16, 7, 1, 9], [15, 10, 5, 6, 4, 8, 2, 14, 11, 13, 17, 7, 16, 12, 3, 1, 9], [15, 10, 5, 6, 4, 8, 2, 14, 11, 13, 17, 12, 3, 16, 7, 1, 9], [15, 10, 5, 6, 4, 8, 16, 11, 13, 2, 14, 1, 3, 17, 7, 12, 9], [15, 10, 5, 6, 4, 8, 16, 11, 13, 2, 14, 1, 12, 9, 17, 7, 3], [15, 10, 5, 6, 12, 2, 14, 11, 9, 4, 8, 16, 13, 1, 17, 7, 3], [15, 10, 5, 6, 12, 2, 14, 11, 9, 16, 8, 4, 13, 1, 17, 7, 3], [15, 10, 5, 6, 12, 2, 14, 11, 9, 16, 8, 17, 3, 7, 1, 4, 13], [15, 10, 5, 6, 12, 2, 14, 11, 9, 16, 8, 17, 7, 3, 1, 4, 13], [15, 10, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 7, 1, 8, 16, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 7, 1, 16, 8, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 7, 16, 1, 8, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 7, 16, 8, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 8, 16, 7, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 16, 7, 1, 8, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 16, 7, 8, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 3, 17, 4, 16, 8, 7, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 8, 4, 17, 3, 16, 7, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 16, 1, 3, 17, 7, 4, 8, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 16, 1, 3, 17, 7, 8, 4, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 16, 4, 9, 8, 1, 17, 7, 3], [15, 10, 5, 6, 12, 2, 14, 11, 13, 16, 4, 17, 1, 9, 8, 7, 3], [15, 10, 5, 6, 12, 2, 14, 11, 13, 16, 4, 17, 3, 7, 1, 8, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 16, 4, 17, 3, 7, 8, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 16, 4, 17, 3, 8, 7, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 16, 4, 17, 7, 3, 1, 8, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 16, 4, 17, 7, 3, 8, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 16, 4, 17, 7, 8, 3, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 7, 1, 8, 16, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 7, 1, 16, 8, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 7, 16, 1, 8, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 7, 16, 8, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 8, 16, 7, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 16, 7, 1, 8, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 16, 7, 8, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 17, 3, 4, 16, 8, 7, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 17, 7, 8, 16, 4, 3, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 17, 7, 16, 4, 3, 1, 8, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 17, 7, 16, 4, 3, 8, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 17, 7, 16, 4, 8, 3, 1, 9], [15, 10, 5, 6, 12, 2, 14, 11, 13, 17, 7, 16, 8, 4, 3, 1, 9], [15, 10, 5, 6, 12, 16, 11, 13, 2, 9, 1, 8, 17, 7, 4, 14, 3], [15, 10, 5, 6, 12, 16, 11, 13, 2, 9, 1, 17, 8, 7, 4, 14, 3], [15, 10, 5, 6, 12, 16, 11, 13, 2, 14, 1, 3, 17, 7, 4, 8, 9], [15, 10, 5, 6, 12, 16, 11, 13, 2, 14, 1, 3, 17, 7, 8, 4, 9], [15, 10, 5, 6, 12, 16, 11, 13, 2, 14, 4, 9, 8, 1, 17, 7, 3], [15, 10, 5, 6, 12, 16, 11, 13, 2, 14, 4, 17, 1, 9, 8, 7, 3], [15, 10, 5, 6, 12, 16, 11, 13, 2, 14, 4, 17, 3, 7, 1, 8, 9], [15, 10, 5, 6, 12, 16, 11, 13, 2, 14, 4, 17, 3, 7, 8, 1, 9], [15, 10, 5, 6, 12, 16, 11, 13, 2, 14, 4, 17, 3, 8, 7, 1, 9], [15, 10, 5, 6, 12, 16, 11, 13, 2, 14, 4, 17, 7, 3, 1, 8, 9], [15, 10, 5, 6, 12, 16, 11, 13, 2, 14, 4, 17, 7, 3, 8, 1, 9], [15, 10, 5, 6, 12, 16, 11, 13, 2, 14, 4, 17, 7, 8, 3, 1, 9], [15, 10, 5, 6, 14, 13, 2, 7, 3, 16, 17, 11, 1, 8, 4, 12, 9], [15, 10, 5, 6, 14, 13, 2, 7, 3, 16, 17, 11, 1, 8, 12, 4, 9], [15, 10, 5, 6, 14, 13, 2, 7, 3, 16, 17, 11, 1, 12, 4, 8, 9], [15, 10, 5, 6, 14, 13, 2, 7, 3, 16, 17, 11, 1, 12, 8, 4, 9], [15, 10, 5, 6, 14, 13, 2, 7, 8, 4, 16, 17, 11, 12, 3, 1, 9], [15, 10, 5, 6, 14, 13, 2, 7, 8, 16, 4, 17, 11, 12, 3, 1, 9], [15, 10, 5, 6, 14, 13, 2, 7, 8, 16, 12, 17, 11, 4, 3, 1, 9], [15, 10, 5, 6, 14, 13, 2, 7, 12, 16, 4, 1, 3, 17, 11, 8, 9], [15, 10, 5, 6, 14, 13, 2, 7, 12, 16, 8, 17, 11, 4, 3, 1, 9], [15, 10, 5, 6, 14, 13, 2, 7, 12, 16, 17, 8, 11, 4, 3, 1, 9], [15, 10, 5, 6, 14, 13, 2, 7, 12, 16, 17, 11, 4, 3, 1, 8, 9], [15, 10, 5, 6, 14, 13, 2, 7, 12, 16, 17, 11, 4, 3, 8, 1, 9], [15, 10, 5, 6, 14, 13, 2, 7, 12, 16, 17, 11, 4, 8, 3, 1, 9], [15, 10, 5, 6, 14, 13, 2, 7, 12, 16, 17, 11, 8, 4, 3, 1, 9], [15, 10, 5, 6, 14, 13, 7, 2, 3, 16, 17, 11, 1, 8, 4, 12, 9], [15, 10, 5, 6, 14, 13, 7, 2, 3, 16, 17, 11, 1, 8, 12, 4, 9], [15, 10, 5, 6, 14, 13, 7, 2, 3, 16, 17, 11, 1, 12, 4, 8, 9], [15, 10, 5, 6, 14, 13, 7, 2, 3, 16, 17, 11, 1, 12, 8, 4, 9], [15, 10, 5, 6, 14, 13, 7, 2, 8, 4, 16, 17, 11, 12, 3, 1, 9], [15, 10, 5, 6, 14, 13, 7, 2, 8, 16, 4, 17, 11, 12, 3, 1, 9], [15, 10, 5, 6, 14, 13, 7, 2, 8, 16, 12, 17, 11, 4, 3, 1, 9], [15, 10, 5, 6, 14, 13, 7, 2, 12, 16, 4, 1, 3, 17, 11, 8, 9], [15, 10, 5, 6, 14, 13, 7, 2, 12, 16, 8, 17, 11, 4, 3, 1, 9], [15, 10, 5, 6, 14, 13, 7, 2, 12, 16, 17, 8, 11, 4, 3, 1, 9], [15, 10, 5, 6, 14, 13, 7, 2, 12, 16, 17, 11, 4, 3, 1, 8, 9], [15, 10, 5, 6, 14, 13, 7, 2, 12, 16, 17, 11, 4, 3, 8, 1, 9], [15, 10, 5, 6, 14, 13, 7, 2, 12, 16, 17, 11, 4, 8, 3, 1, 9], [15, 10, 5, 6, 14, 13, 7, 2, 12, 16, 17, 11, 8, 4, 3, 1, 9], [15, 10, 5, 6, 14, 13, 7, 8, 2, 4, 16, 17, 11, 12, 3, 1, 9], [15, 10, 5, 6, 14, 13, 7, 8, 2, 16, 4, 17, 11, 12, 3, 1, 9], [15, 10, 5, 6, 14, 13, 7, 8, 2, 16, 12, 17, 11, 4, 3, 1, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 4, 7, 17, 11, 1, 8, 16, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 4, 7, 17, 11, 1, 16, 8, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 4, 7, 17, 11, 16, 1, 8, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 4, 7, 17, 11, 16, 8, 1, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 4, 16, 8, 17, 11, 7, 1, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 4, 16, 17, 8, 11, 7, 1, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 4, 16, 17, 11, 7, 1, 8, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 4, 16, 17, 11, 7, 8, 1, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 4, 16, 17, 11, 8, 7, 1, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 7, 1, 8, 16, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 7, 1, 16, 8, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 7, 16, 1, 8, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 7, 16, 8, 1, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 8, 16, 7, 1, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 16, 7, 1, 8, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 16, 7, 8, 1, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 11, 17, 4, 16, 8, 7, 1, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 16, 4, 8, 17, 11, 7, 1, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 16, 4, 17, 8, 11, 7, 1, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 16, 4, 17, 11, 7, 1, 8, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 16, 4, 17, 11, 7, 8, 1, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 16, 4, 17, 11, 8, 7, 1, 9], [15, 10, 5, 6, 14, 13, 12, 3, 2, 16, 8, 4, 17, 11, 7, 1, 9], [15, 10, 5, 6, 14, 13, 12, 16, 7, 2, 4, 1, 3, 17, 11, 8, 9], [15, 10, 5, 6, 14, 13, 12, 16, 7, 2, 8, 17, 11, 4, 3, 1, 9], [15, 10, 5, 6, 14, 13, 12, 16, 7, 2, 17, 8, 11, 4, 3, 1, 9], [15, 10, 5, 6, 14, 13, 12, 16, 7, 2, 17, 11, 4, 3, 1, 8, 9], [15, 10, 5, 6, 14, 13, 12, 16, 7, 2, 17, 11, 4, 3, 8, 1, 9], [15, 10, 5, 6, 14, 13, 12, 16, 7, 2, 17, 11, 4, 8, 3, 1, 9], [15, 10, 5, 6, 14, 13, 12, 16, 7, 2, 17, 11, 8, 4, 3, 1, 9], [15, 10, 5, 6, 14, 13, 12, 16, 17, 4, 7, 11, 2, 3, 1, 8, 9], [15, 10, 5, 6, 14, 13, 12, 16, 17, 4, 7, 11, 2, 3, 8, 1, 9], [15, 10, 5, 6, 14, 13, 12, 16, 17, 4, 7, 11, 2, 8, 3, 1, 9], [15, 10, 5, 6, 14, 13, 12, 16, 17, 11, 7, 2, 4, 3, 1, 8, 9], [15, 10, 5, 6, 14, 13, 12, 16, 17, 11, 7, 2, 4, 3, 8, 1, 9], [15, 10, 5, 6, 14, 13, 12, 16, 17, 11, 7, 2, 4, 8, 3, 1, 9], [15, 10, 5, 6, 14, 13, 12, 16, 17, 11, 7, 2, 8, 4, 3, 1, 9], [15, 10, 5, 6, 14, 13, 12, 16, 17, 11, 7, 4, 2, 3, 1, 8, 9], [15, 10, 5, 6, 14, 13, 12, 16, 17, 11, 7, 4, 2, 3, 8, 1, 9], [15, 10, 5, 6, 14, 13, 12, 16, 17, 11, 7, 4, 2, 8, 3, 1, 9]]]

170826

New game(Cubes)(2)

1～n のカードを使った場合を考える。

最初の人が1 とn 以外を引き、n 番目の人が1 とn 以外で終わる

場合があるか考えてみた。

今のところ以下の場合が見つかった。

n = 6

[[2, 1, 6, 5, 4, 3], [2, 6, 1, 5, 4, 3]]

n = 7

[[2, 1, 6, 5, 7, 3, 4], [2, 6, 1, 5, 7, 3, 4], [3, 1, 5, 7, 2, 6, 4], [3, 5, 1, 7, 2, 6, 4], [3, 5, 7, 1, 2, 6, 4], [3, 7, 5, 1, 2, 6, 4], [5, 1, 3, 7, 2, 6, 4], [5, 3, 1, 7, 2, 6, 4], [5, 3, 7, 1, 2, 6, 4], [5, 7, 3, 1, 2, 6, 4], [6, 1, 2, 5, 7, 3, 4], [6, 2, 1, 5, 7, 3, 4]]

例えば、

2 | 2^3 (2 | 8),

2 + 1 | 2^3 + 1^3 (3 | 9),

2 + 1 + 6 | 2^3 + 1^3 + 6^3 (9 | 225),

2 + 1 + 6 + 5 | 2^3 + 1^3 + 6^3 + 5^3 (14 | 350),

2 + 1 + 6 + 5 + 4 | 2^3 + 1^3 + 6^3 + 5^3 + 4^3 (18 | 414),

2 + 1 + 6 + 5 + 4 + 3 | 2^3 + 1^3 + 6^3 + 5^3 + 4^3 + 3^3 (21 | 441)

なので、[2, 1, 6, 5, 4, 3] は条件を満たす。

170824

New game(Cubes)(1)

2～4人用のゲームを考えてみました。

①最初の人が1～13 のカードから一枚引きます。
sum1 は引いたカードから始めます。
sum3 は引いたカードの３乗から始めます。
例えば、引いたカードが5 とします。
sum1 は5、sum3 は125からとなります。

②次の人は以下の条件を満たす数字を言わないと負けです。
ア）1～13 でまだ使われていない数字 (x とする) である。
sum1 += x, sum3 += x^3 とし、
イ）sum3 がsum1 で割り切れる。

③まだ使われていない数字が一つになっても勝負が決まらなかったら、
負けていない人全員が勝ちです。

170813

PARI


A159463

3848000000 までは条件を満たすものがないことを確認のうえで、2*10^10 までの範囲で探してみた。

for (i=3848000000, 2*10^10, if (sumdigits(i^3)==216, print1(i, ", ")))

出力結果
3848163483, 4462569999, 4479677412, 4586158119, 4594661259, 4594665192, 4594700889, 4625720379, 4641588459, 5644008999, 5828410842, 5833034823, 5838252576, 5848025709, 6453471192, 6617331999, 6619097067, 6686657169, 7107126942, 7230291999, 7277907183, 7298954529, 7361104599, 7655249499, 7696321113, 7752292599, 7763935413, 7807648032, 7849790355, 7861079679, 7870842513, 7882662024, 7899769239, 7928513619, 7936309899, 8040925644, 8087527866, 8168254083, 8188243593, 8217313053, 8242024149, 8280652632, 8290998999, 8324036319, 8329419948, 8329894083, 8371920453, 8385953229, 8386243995, 8386623423, 8427714576, 8429586192, 8434259829, 8508456957, 8608298259, 8702125599, 8749417494, 8750034276, 8767580826, 8813357679, 8814253116, 8827927632, 8831296395, 8831814675, 8861606859, 8870574612, 8878954773, 8887441362, 8950297629, 8999835345, 9061217229, 9099512259, 9105748326, 9111328683, 9164461683, 9200791413, 9200826942, 9201177342, 9203865459, 9205040826, 9232148829, 9236117229, 9236435532, 9236514492, 9239456457, 9243860229, 9259475979, 9265691559, 9271519599, 9271524144, 9274580826, 9275392599, 9278832576, 9279153159, 9282750192, 9282751383, 9282766863, 9283020159, 9316934409, 9320930229, 9386451357, 9457795719, 9464078862, 9491142213, 9497838099, 9537601263, 9545158146, 9545221113, 9545999622, 9563558259, 9574843299, 9575174463, 9578073729, 9582330753, 9596601429, 9607458999, 9610159842, 9613846716, 9614711529, 9618097326, 9618778272, 9618968892, 9631726989, 9636575532, 9642246894, 9643724112, 9650346753, 9650922513, 9652586844, 9654353742, 9654406353, 9718439997, 9776365719, 9791995299, 9823536192, 9826299999, 9847688529, 9854520498, 9857965089, 9857992413, 9862414998, 9887976423, 9895235574, 9895341129, 9895486122, 9898595148, 9898982259, 9912163032, 9918939999, 9919211679, 9924690132, 9926069772, 9928621557, 9929468529, 9932542299, 9952642494, 9953055627, 9955426599, 9956248755, 9959838219, 9960709155, 9961179132, 9961850913, 9962116599, 9962791716, 9962818149, 9963523692, 9964500795, 9965882259, 9966167163, 9966507279, 9966509223, 9966539799, 9972758859, 9976527882, 9983271999, 9986144136, 9989218299, 9989955213, 9991252299, 9993261123, 9993291123, 9993528429, 9996275175, 9996293619, 9999285879, 9999322254, 9999622299, 9999884994, 10256240559, 10321795953, 10620675192, 10828176813, 10857602286, 10880214366, 10897084083, 10910782389, 11186324622, 11186886192, 11266225857, 11286808683, 11315902632, 11370297999, 11417020842, 11423631999, 11446868529, 11588777229, 11616830229, 11617298529, 11634560229, 11637268389, 11642213649, 11643937533, 11647125372, 11647130139, 11664062862, 11665725999, 11691171129, 11695093323, 11756672592, 11807411529, 11811377229, 11811758529, 11826153186, 11840423865, 11877919353, 11880333729, 11899222857, 11906656866, 11924760159, 11927673195, 11930343132, 11934524994, 12050665413, 12092110596, 12093909459, 12096216942, 12096420816, 12116617536, 12118932999, 12135047592, 12136133616, 12137074998, 12141696999, 12141817155, 12153012849, 12154928829, 12156965616, 12161694954, 12162601362, 12163498326, 12163694355, 12163800192, 12163950216, 12168826599, 12200108142, 12215592999, 12229380942, 12270919353, 12275892966, 12293590839, 12298067397, 12310594782, 12311001435, 12317862159, 12317862429, 12319645383, 12330836523, 12336976389, 12337172799, 12339601116, 12340675899, 12357812076, 12359468529, 12363309999, 12363853557, 12376026519, 12376424739, 12383229366, 12383430192, 12383443866, 12383662689, 12385098882, 12385353327, 12385401435, 12400520031, 12492838116, 12493322682, 12503951559, 12507937353, 12511815999, 12518904513, 12529101195, 12531377157, 12533690229, 12533768316, 12545179413, 12547763706, 12550680426, 12552833442, 12556368759, 12557048889, 12561210129, 12566893413, 12567405213, 12569572581, 12570578595, 12571176813, 12571753299, 12573497349, 12573535539, 12573725376, 12575803692, 12576022635, 12576046053, 12576657459, 12577544616, 12577744782, 12577852866, 12577957554, 12582127995, 12591835413, 12592266582, 12592876188, 12594343854, 12595805667, 12596593413, 12596866599, 12596895132, 12597947679, 12598345293, 12598555299, 12598759599, 12598919442, 12599183199, 12599199513, 12599206299, 12944118675, 12980221383, 12997431423, 13180703316, 13199314683, 13199955999, 13332161559, 13351296966, 13360520529, 13368260229, 13384936749, 13517391942, 13535392599, 13535773413, 13548322389, 13568440716, 13678009899, 13693242576, 13715265999, 13731044169, 13747156299, 13750448382, 13750688529, 13783206099, 13838219124, 13839978936, 13852012632, 13852880649, 13853848383, 13853919312, 13864160349, 13864329999, 13898065716, 13903732413, 13905828999, 13907328999, 13914442122, 13922177037, 13922665383, 13922695329, 13923047142, 14022070593, 14027154423, 14057062476, 14058882759, 14060891169, 14070898329, 14073877809, 14074362627, 14074377759, 14075769423, 14084497149, 14087191389, 14092747926, 14092831683, 14094160731, 14094161169, 14094592926, 14094597123, 14158022394, 14192741775, 14194555869, 14202678675, 14205943422, 14208080742, 14208775899, 14209424559, 14210752599, 14224059915, 14227519683, 14240648382, 14240711652, 14242331853, 14243503593, 14243939148, 14244016299, 14249931999, 14250415383, 14254689498, 14256592413, 14256970359, 14257151829, 14258455869, 14259442122, 14259560532, 14260278675, 14260424403, 14260429155, 14289786813, 14293132389, 14325697155, 14341738089, 14356329366, 14357777229, 14358059823, 14361113382, 14372239431, 14373904413, 14374081866, 14379051942, 14387294229, 14387778123, 14388602829, 14388657954, 14389857483, 14389868529, 14389889379, 14390196288, 14390335413, 14393092413, 14398225089, 14398401942, 14403188382, 14403191595, 14403994998, 14404505499, 14404830423, 14406224802, 14406256299, 14406356229, 14406419442, 14406452382, 14412071442, 14412537123, 14412793557, 14414316216, 14420331999, 14420394036, 14421662355, 14422162353, 14422296189, 14422446009, 14422451826, 14528722599, 14672900835, 14678947449, 14810637282, 14839517229, 14881886592, 14883090813, 14886355689, 14989592469, 15022189359, 15036768612, 15077509899, 15110122692, 15120128529, 15152484627, 15165847692, 15174972213, 15176084559, 15178041129, 15179757216, 15180399327, 15180771129, 15182189823, 15182791116, 15295599999, 15300556599, 15307675389, 15307715076, 15310234194, 15311842299, 15323293149, 15326187027, 15363856599, 15380320026, 15410549442, 15424285413, 15424453557, 15437220882, 15448528089, 15450049026, 15452856813, 15462130089, 15464795019, 15465393435, 15466106499, 15466648998, 15507051942, 15520665999, 15521744832, 15534760692, 15544347498, 15545791176, 15558047619, 15561913683, 15577153692, 15577344798, 15589268862, 15589695282, 15589827342, 15589834215, 15590932566, 15591163995, 15591165414, 15600647559, 15602025528, 15602139195, 15603494148, 15603521913, 15604685592, 15604756872, 15604885602, 15617173299, 15642893676, 15644093529, 15651035463, 15657819999, 15671422299, 15671528676, 15672746595, 15680860092, 15682406199, 15683893431, 15686176413, 15686594442, 15696086763, 15698195526, 15699710379, 15700137459, 15709115829, 15710807019, 15712697019, 15713516829, 15713637075, 15713642394, 15718992795, 15721009899, 15721613835, 15722545383, 15722800749, 15724043229, 15725255826, 15727627632, 15732371037, 15733309899, 15733607367, 15733833483, 15736566288, 15737173692, 15737509923, 15737581113, 15737759733, 15737769423, 15737819475, 15739410192, 15740338719, 15740581935, 15740582259, 15766794279, 15780153783, 15791539293, 15794025132, 15801959778, 15805851555, 15807430755, 15818742099, 15820477866, 15831965259, 15833546319, 15833906499, 15833940921, 15841878696, 15842060592, 15843258186, 15844681632, 15845782383, 15845909442, 15846045882, 15846074532, 15846802116, 15846892389, 15847081989, 15847229148, 15847412592, 15854923326, 15854937435, 15856357515, 15856659999, 15857456379, 15858105816, 15858914124, 15859180092, 15859324719, 15859327995, 15860342979, 15860463576, 15860664999, 15861648213, 15868411392, 15869359353, 15869876499, 15869961192, 15869974116, 15870039366, 15870158616, 15871337229, 15871344096, 15871363992, 15872263149, 15872515413, 15872681853, 15873843813, 15873970827, 15873983442, 15873990675, 15873994602, 15973888242, 15977153199, 15995701683, 15999844893, 16004807019, 16005176709, 16074264144, 16093070715, 16095631299, 16119620229, 16132954593, 16134270966, 16154237529, 16185344244, 16195212729, 16247429829, 16248528192, 16253131683, 16259932689, 16311278529, 16318850997, 16370270076, 16372509216, 16372704942, 16386162192, 16470039036, 16482319413, 16484920413, 16490020632, 16495548159, 16498376292, 16505694759, 16507172883, 16509122592, 16509632436, 16569306033, 16577834619, 16581050859, 16581802032, 16594541436, 16605791019, 16612549155, 16616053563, 16617388029, 16618697139, 16626751983, 16629697155, 16677662592, 16690558431, 16702860816, 16712553423, 16713609435, 16713763353, 16714945899, 16725223299, 16733906499, 16736180499, 16737226635, 16737365376, 16737475089, 16738504383, 16738546116, 16746880833, 16747062675, 16747107219, 16749127632, 16749261123, 16749493413, 16749961869, 16750306299, 16750418286, 16750550913, 16784711619, 16794479229, 16803740532, 16804986813, 16807940772, 16828488429, 16830698853, 16832001522, 16832530149, 16833292926, 16840830966, 16849766199, 16850828676, 16851988059, 16852069293, 16853387403, 16854337248, 16854349413, 16854547719, 16854571053, 16855634244, 16855634442, 16855757319, 16856366199, 16856790036, 16856811159, 16856905875, 16860049383, 16867011729, 16867351389, 16868289879, 16868290089, 16868523129, 16868606199, 16868627382, 16879174422, 16880119299, 16889230149, 16891920966, 16897547559, 16901365326, 16901387442, 16903718553, 16911897123, 16914195966, 16924066176, 16925716248, 16926427029, 16934232498, 16934906529, 16935034635, 16941865995, 16944326253, 16948975899, 16949002413, 16949428692, 16950046842, 16950136083, 16953377259, 16954545816, 16954896576, 16958209899, 16958212221, 16958352492, 16959533259, 16960669326, 16960913313, 16966253676, 16968416559, 16968785859, 16969989729, 16971114366, 16971648213, 16971925749, 16972134159, 16972259829, 16973404782, 16973408229, 16973427795, 16973429829, 16976848299, 16978044309, 16978055616, 16980123927, 16980227295, 16980597123, 16981513692, 16984494096, 16984529859, 16984632999, 16984645743, 16984737153, 17030739882, 17036551113, 17037746229, 17042318898, 17042556513, 17048303211, 17050140192, 17051514783, 17052519999, 17052661383, 17052772089, 17053795893, 17054005413, 17058309561, 17059559829, 17061698733, 17062821429, 17063197872, 17063692899, 17064266076, 17064873195, 17064918429, 17065261692, 17065374429, 17065464192, 17070396426, 17071898259, 17072674899, 17074630113, 17075378082, 17075649012, 17076563061, 17076659442, 17076694842, 17077911129, 17080117767, 17082443616, 17082523782, 17083761627, 17083965999, 17084698395, 17084755299, 17085931278, 17086981983, 17087141775, 17087195229, 17087654529, 17087665923, 17087846313, 17088339576, 17088349449, 17088350859, 17092888275, 17092898259, 17095069155, 17096985423, 17097353622, 17098048428, 17098241865, 17098831116, 17099210997, 17099280636, 17099403783, 17099519826, 17099553753, 17099596191, 17177595999, 17189205075, 17193356229, 17200618893, 17201577282, 17209042926, 17211371829, 17268711192, 17312000826, 17313429132, 17322438342, 17411853342, 17430360159, 17432763729, 17434899159, 17506336413, 17510465457, 17521975092, 17532174387, 17536478466, 17544081942, 17606909832, 17626885092, 17647342899, 17650642899, 17651023692, 17651623629, 17651738466, 17692193136, 17703996246, 17714409195, 17715675942, 17718883449, 17724879942, 17734434216, 17735637075, 17735830149, 17742068529, 17744918616, 17745163053, 17746410129, 17747362398, 17747502075, 17751365259, 17753417229, 17755952592, 17756641299, 17756906652, 17756978529, 17757653898, 17757952116, 17758016559, 17785276593, 17807198829, 17808451176, 17809481829, 17810669652, 17828388576, 17828501859, 17844305199, 17845156353, 17846282259, 17847253749, 17847850149, 17849003229, 17850504609, 17851525557, 17851637289, 17852456229, 17856764442, 17858979009, 17859677229, 17860013379, 17861059689, 17862925644, 17867952999, 17871293709, 17871407559, 17892975942, 17894234229, 17894234589, 17901726783, 17910044889, 17911904619, 17913837129, 17914705413, 17923108113, 17923440132, 17933909898, 17934617607, 17934918159, 17941026942, 17942708442, 17944953195, 17945596866, 17945895942, 17946216927, 17946235092, 17946331893, 17951204259, 17952518895, 17952544635, 17955403899, 17955495579, 17955629394, 17956271112, 17956272426, 17956339431, 17956361259, 17956623921, 17959451727, 17959537389, 17959557999, 17961728148, 17961736548, 17962161966, 17962499994, 17963402799, 17963785092, 17963813997, 17964611529, 17965756866, 17965762632, 17966994999, 17966996499, 17967017595, 17987623797, 17993514123, 18000925692, 18007972389, 18011183994, 18012011529, 18016712523, 18017141076, 18018270426, 18018344442, 18025615782, 18028555383, 18031616919, 18033866283, 18033876099, 18034440132, 18034898529, 18035525259, 18036858072, 18036899592, 18037665747, 18037850379, 18046380366, 18047812116, 18047815155, 18048016692, 18048612999, 18048736113, 18053226189, 18054113382, 18054228999, 18057010599, 18057416235, 18057419376, 18057826242, 18058421148, 18058430244, 18058624893, 18059130519, 18059462595, 18063356775, 18064847157, 18066194529, 18066502788, 18067412829, 18067431129, 18067431942, 18067442259, 18068014272, 18068033457, 18068647329, 18068666523, 18069336366, 18069340899, 18069423033, 18069423144, 18069635367, 18069646713, 18069688692, 18079684782, 18097199469, 18099041463, 18099242949, 18106233813, 18109090383, 18110103813, 18110432199, 18118223529, 18118451823, 18119133483, 18119533359, 18119559942, 18120351942, 18120565413, 18128685627, 18128694882, 18129649926, 18130329774, 18130471635, 18130530192, 18130735083, 18133776753, 18135688059, 18136106859, 18138839763, 18139237029, 18139441548, 18139843842, 18140218599, 18140757435, 18143591559, 18145901604, 18147034635, 18147538389, 18147648423, 18148463259, 18148553415, 18148932999, 18148945035, 18149249748, 18149848239, 18149935842, 18149960157, 18149971116, 18150386136, 18150653529, 18150790122, 18150889875, 18150905199, 18150968739, 18155665719, 18158038992, 18158071716, 18159818457, 18159856353, 18160658442, 18160781559, 18160842219, 18160982496, 18163819329, 18164075475, 18164943783, 18165862689, 18165952092, 18167162862, 18168126033, 18168640344, 18168772275, 18169671129, 18169770966, 18169829859, 18169990092, 18170074053, 18170181195, 18170195229, 18170580795, 18170900826, 18170973132, 18170992413, 18170993892, 18171003216, 18171054366, 18171090393, 18171103755, 18171153429, 18171185631, 18249498942, 18251597622, 18269479299, 18321179442, 18348120636, 18360723144, 18369907566, 18408163299, 18409222692, 18409244832, 18437811129, 18439363083, 18439479459, 18449354409, 18449581719, 18458176539, 18464356299, 18468057819, 18504259842, 18505913859, 18508134216, 18536289129, 18546752457, 18546995199, 18552601113, 18562185642, 18562476813, 18564169464, 18564798144, 18566036121, 18585500223, 18613094355, 18621291759, 18630657999, 18630897195, 18633506499, 18639527349, 18641274366, 18642425382, 18643174026, 18643190076, 18646252299, 18648168774, 18649135692, 18650067327, 18651821919, 18651997692, 18652624389, 18652855689, 18656120859, 18658619259, 18659480826, 18660622299, 18662239899, 18689122989, 18689248092, 18698737632, 18700740498, 18710019699, 18718832667, 18719773692, 18724231866, 18724384089, 18726173229, 18727777413, 18741256842, 18747300132, 18748000257, 18748197894, 18749092599, 18752321529, 18753668733, 18755308899, 18755575248, 18756274635, 18756637353, 18757281435, 18757421142, 18766106499, 18784260999, 18785461683, 18785773113, 18789834342, 18804824616, 18810473997, 18812457498, 18813503199, 18818209842, 18827498529, 18830138676, 18833144619, 18835035192, 18836679459, 18837561429, 18837671529, 18838789299, 18841610124, 18841618599, 18842078676, 18842537667, 18847926399, 18847981842, 18848077386, 18848264163, 18848282259, 18850065342, 18850159155, 18850929036, 18851848113, 18851899992, 18851937519, 18852034326, 18867029937, 18867833913, 18869744898, 18870661683, 18880036932, 18891990942, 18897852513, 18898498326, 18903374442, 18905234442, 18905271795, 18905335221, 18906277029, 18907574169, 18907756599, 18915972219, 18922862313, 18925645632, 18925648389, 18925734099, 18926306859, 18926316279, 18926772093, 18931989999, 18932928999, 18933260229, 18933278436, 18933451113, 18934112499, 18934770942, 18935664189, 18935866395, 18935874453, 18935877075, 18936068259, 18937885383, 18940459689, 18940605195, 18941368275, 18941369466, 18941454123, 18941536449, 18942472242, 18942511362, 18942856932, 18943321113, 18943390782, 18944240928, 18944341239, 18944379459, 18945054366, 18945158457, 18945225159, 18945251433, 18945363627, 18951733353, 18962991999, 18980339589, 18987618429, 18989550579, 18989826498, 18990667059, 18990728529, 18991405899, 18995622999, 18996293709, 18996824676, 18998586192, 18999069195, 19000621383, 19000883595, 19000919151, 19005259842, 19008260229, 19009093299, 19009123299, 19009869882, 19010029413, 19011901749, 19015365195, 19015456467, 19016299899, 19017154383, 19018226826, 19018417413, 19018898076, 19019170749, 19021745076, 19023974259, 19024777452, 19025631129, 19025818047, 19026463272, 19026550692, 19027179999, 19027516914, 19028005413, 19028010372, 19028249748, 19028291076, 19028459319, 19028552526, 19030318989, 19030788213, 19031331498, 19032207195, 19032225999, 19034071644, 19035003783, 19035664275, 19035795816, 19035823299, 19035896826, 19036399104, 19036573869, 19036586889, 19036675899, 19037111214, 19037302521, 19037396061, 19037468616, 19037488302, 19037578113, 19037770635, 19041416382, 19041828429, 19044217413, 19046853423, 19054312644, 19055037783, 19055101164, 19055148144, 19061295459, 19062334413, 19064232999, 19065140862, 19068723423, 19073482293, 19073582457, 19074111192, 19074407559, 19080818529, 19082466288, 19082701176, 19082740353, 19083655599, 19085475192, 19086260229, 19088047191, 19090572144, 19091650449, 19091779113, 19091788239, 19091881263, 19092713886, 19092781998, 19092786033, 19096891383, 19096986813, 19097193195, 19097281299, 19097375403, 19098619152, 19100379366, 19101030213, 19101186753, 19101570366, 19102848162, 19106834619, 19106849499, 19107313299, 19107420159, 19107963342, 19108114932, 19109759529, 19110052782, 19110085299, 19110144996, 19110148473, 19110161529, 19110163242, 19110984699, 19111027383, 19111038342, 19111075692, 19113412176, 19113810798, 19114452288, 19114629216, 19115719995, 19115991648, 19116183753, 19116534012, 19117176144, 19117461522, 19117913523, 19118074299, 19118206599, 19118374344, 19119102246, 19119286413, 19119724053, 19119896283, 19120052298, 19120097829, 19120142394, 19120157049, 19120181322, 19121082684, 19123643217, 19124471595, 19124481435, 19124573772, 19124715942, 19124738799, 19125478635, 19125655599, 19125666498, 19126358979, 19126393593, 19126464366, 19127179035, 19127279874, 19127364342, 19127371371, 19127398692, 19127471019, 19127488839, 19127762226, 19128199521, 19128380229, 19128382635, 19128819729, 19129014216, 19129020192, 19129099353, 19129118892, 19129122327, 19129199538, 19129272984, 19129275099, 19129298979, 19190995089, 19218050859, 19264058319, 19289111919, 19299929199, 19300588719, 19305933813, 19307976129, 19308617229, 19309294899, 19309393353, 19309490682, 19309607697, 19317819276, 19334763783, 19354382259, 19369321155, 19385005413, 19388048382, 19388403186, 19388998029, 19389015492, 19389555729, 19395140826, 19398773229, 19406600466, 19439117394, 19447888299, 19448067555, 19451221398, 19456179399, 19463574153, 19464981195, 19466563695, 19467614559, 19468139499, 19468841529, 19475532213, 19478080362, 19478155683, 19484303643, 19485722082, 19485862899, 19510534731, 19536595749, 19544617359, 19547312499, 19554307518, 19555071627, 19555597629, 19556272083, 19556831529, 19561876599, 19563849249, 19564327692, 19564484829, 19564500942, 19565109531, 19567282599, 19569106413, 19569794772, 19571596353, 19573980282, 19606290999, 19614273813, 19615031589, 19617254259, 19617541206, 19617581319, 19623970827, 19624656582, 19625443995, 19641944559, 19643081823, 19643429829, 19643482242, 19643591259, 19648784883, 19649372199, 19649645076, 19652056776, 19652236302, 19652322999, 19656499899, 19656587112, 19657068213, 19657317813, 19658233539, 19659881163, 19659979995, 19659985599, 19659991893, 19660666353, 19660675413, 19660692402, 19669475259, 19677898692, 19680590019, 19681965999, 19685919213, 19692461844, 19694495259, 19701379299, 19708941366, 19711345632, 19714253466, 19718358675, 19718462919, 19718537496, 19719980826, 19720240389, 19720267389, 19720758435, 19725978576, 19726264683, 19726938657, 19727598375, 19727865459, 19727886588, 19728577299, 19728744183, 19729095426, 19729430229, 19729431129, 19729438692, 19732255623, 19733821299, 19733951559, 19734638733, 19734823749, 19735648389, 19735757076, 19736155089, 19736434326, 19737138627, 19737226599, 19737348213, 19737394149, 19737823995, 19738066176, 19738135899, 19738219839, 19740810549, 19742190783, 19743644793, 19743968616, 19744037115, 19744138089, 19744173159, 19745072733, 19745743716, 19745867742, 19745953173, 19746280686, 19746466176, 19746507279, 19746542235, 19746543099, 19746694254, 19746718719, 19746779148, 19762941498, 19763017155, 19769843859, 19771472709, 19772155686, 19772254782, 19779471129, 19787396997, 19787669832, 19788919995, 19795383159, 19796264124, 19796847498, 19797523692, 19797565413, 19797718293, 19797965961, 19801159413, 19802887716, 19803224457, 19804324149, 19804594383, 19805089299, 19805190192, 19805616498, 19806462282, 19809693192, 19811392431, 19811546355, 19811982999, 19813150635, 19813878936, 19814085357, 19814441526, 19814699229, 19814777229, 19817497149, 19818268683, 19820290053, 19821493155, 19821729876, 19822542513, 19822596807, 19822672083, 19823273529, 19823323515, 19823428866, 19823437494, 19823444052, 19824208299, 19825981842, 19827430182, 19827599829, 19827686319, 19828269195, 19828446753, 19828490826, 19828661259, 19829278437, 19829957403, 19830009216, 19830174882, 19830211842, 19830227526, 19830803199, 19830885459, 19830892494, 19830975213, 19830989859, 19831068627, 19831406199, 19831711155, 19831729293, 19831830882, 19831838028, 19831906089, 19831915503, 19831923936, 19839508899, 19844537163, 19844705595, 19847422293, 19848412032, 19854659529, 19856466435, 19857213696, 19857312492, 19857316914, 19863934683, 19864660053, 19865556513, 19865683173, 19871305293, 19872517359, 19876572009, 19879169442, 19880089998, 19880107719, 19881295089, 19881616989, 19882616469, 19882639326, 19885932576, 19885988529, 19887661593, 19888462032, 19889190192, 19889277993, 19889377566, 19889641923, 19891552755, 19894855683, 19895243595, 19895936613, 19896117075, 19897720755, 19898624442, 19898653053, 19899311853, 19899384423, 19899473862, 19899487326, 19904545113, 19905072459, 19905318132, 19905344019, 19907067672, 19907556648, 19907573103, 19907718189, 19907773692, 19907909787, 19908405882, 19909414395, 19911844392, 19912029459, 19912921389, 19913693862, 19913777061, 19913792259, 19914182259, 19914534216, 19914599763, 19915289829, 19915299999, 19915366353, 19915453767, 19915642566, 19916114442, 19916137176, 19916199195, 19916213229, 19916221113, 19916232099, 19916290866, 19916305032, 19921156239, 19922927403, 19932513342, 19932940557, 19939810626, 19941319515, 19941328029, 19941434157, 19941485622, 19944744129, 19946590395, 19947285093, 19948180662, 19949026503, 19957405113, 19957408755, 19957793289, 19957822413, 19958223594, 19959055299, 19959668529, 19959910344, 19962118719, 19963089414, 19964937129, 19965188559, 19966023729, 19966108239, 19966332429, 19966534683, 19966599192, 19971556632, 19972452891, 19972461129, 19973295942, 19973714532, 19974037116, 19974040389, 19974207576, 19974352866, 19974382857, 19974686229, 19974751305, 19974767262, 19974793152, 19974931842, 19974946116, 19974950613, 19974967749, 19975299423, 19977224061, 19978894392, 19979383719, 19979560692, 19979870355, 19980562689, 19980787716, 19980812229, 19981313019, 19981439442, 19981479513, 19981481667, 19982058909, 19982142393, 19982199996, 19982309355, 19982405775, 19982477559, 19982484072, 19982785089, 19983143286, 19983235599, 19983292293, 19983316419, 19983319155, 19984137129, 19986394635, 19987231842, 19987315239, 19987380366, 19987405362, 19987407423, 19987821744, 19988089299, 19988309835, 19988322999, 19989073731, 19989160749, 19989710532, 19989944259, 19989952866, 19990160157, 19990236813, 19990491288, 19991162592, 19991396199, 19991412513, 19991542257, 19991561994, 19991569749, 19991577018, 19991595366, 19991636235, 19991637075, 19991646426, 19991651076, 19993135719, 19993236879, 19993976826, 19994993745, 19996080882, 19996515192, 19996665192, 19997226282, 19997306949, 19997324532, 19997906355, 19998227076, 19998232257, 19998322242, 19998498999, 19998647229, 19998649875, 19998765507, 19998788259, 19998974589, 19999066536, 19999106499, 19999124595, 19999133229, 19999299048, 19999324893, 19999599999, 19999604823, 19999723326, 19999732413, 19999749075, 19999831746, 19999832331, 19999891449, 19999964889

170807

Ruby


Matiyasevich's Identity

ベルヌーイ数に関する恒等式を確認してみた。

三つ目が1997年にMatiyasevich が見つけた恒等式です。

def bernoulli(n)
  ary = []
  a = []
  (0..n).each{|i|
    a << 1r / (i + 1)
    i.downto(1){|j| a[j - 1] = j * (a[j - 1] - a[j])}
    ary << a[0] # Bn = a[0]
  }
  ary
end

def ncr(n, r)
  return 1 if r == 0
  (n - r + 1..n).inject(:*) / (1..r).inject(:*)
end

n = 20
p b_ary = bernoulli(2 * n)
p ''
(2..n).each{|i|
  x = i + 1
  p [i, x == (0..i).inject(0){|s, j| s + ncr(i + 1, j) * b_ary[j]}, x]
}
p ''
(2..n).each{|i|
  x = -(i + 1) * b_ary[i]
  p [i, x == (2..i - 2).inject(0){|s, j| s + ncr(i, j) * b_ary[j] * b_ary[i - j]}, x]
}
p ''
(2..n).each{|i|
  x = i * (i + 1) * b_ary[i]
  p [i, x == (i + 2) * (2..i - 2).inject(0){|s, j| s + b_ary[j] * b_ary[i - j]} - 2 * (2..i - 2).inject(0){|s, j| s += ncr(i + 2, j) * b_ary[j] * b_ary[i - j]}, x]
}

出力結果
[(1/1), (1/2), (1/6), (0/1), (-1/30), (0/1), (1/42), (0/1), (-1/30), (0/1), (5/66), (0/1), (-691/2730), (0/1), (7/6), (0/1), (-3617/510), (0/1), (43867/798), (0/1), (-174611/330), (0/1), (854513/138), (0/1), (-236364091/2730), (0/1), (8553103/6), (0/1), (-23749461029/870), (0/1), (8615841276005/14322), (0/1), (-7709321041217/510), (0/1), (2577687858367/6), (0/1), (-26315271553053477373/1919190), (0/1), (2929993913841559/6), (0/1), (-261082718496449122051/13530)]
""
[2, true, 3]
[3, true, 4]
[4, true, 5]
[5, true, 6]
[6, true, 7]
[7, true, 8]
[8, true, 9]
[9, true, 10]
[10, true, 11]
[11, true, 12]
[12, true, 13]
[13, true, 14]
[14, true, 15]
[15, true, 16]
[16, true, 17]
[17, true, 18]
[18, true, 19]
[19, true, 20]
[20, true, 21]
""
[2, false, (-1/2)]
[3, true, (0/1)]
[4, true, (1/6)]
[5, true, (0/1)]
[6, true, (-1/6)]
[7, true, (0/1)]
[8, true, (3/10)]
[9, true, (0/1)]
[10, true, (-5/6)]
[11, true, (0/1)]
[12, true, (691/210)]
[13, true, (0/1)]
[14, true, (-35/2)]
[15, true, (0/1)]
[16, true, (3617/30)]
[17, true, (0/1)]
[18, true, (-43867/42)]
[19, true, (0/1)]
[20, true, (1222277/110)]
""
[2, false, (1/1)]
[3, true, (0/1)]
[4, true, (-2/3)]
[5, true, (0/1)]
[6, true, (1/1)]
[7, true, (0/1)]
[8, true, (-12/5)]
[9, true, (0/1)]
[10, true, (25/3)]
[11, true, (0/1)]
[12, true, (-1382/35)]
[13, true, (0/1)]
[14, true, (245/1)]
[15, true, (0/1)]
[16, true, (-28936/15)]
[17, true, (0/1)]
[18, true, (131601/7)]
[19, true, (0/1)]
[20, true, (-2444554/11)]

170730

Ruby


5乗したとき、下桁の数が自分自身と同じになる数

「平方したとき、下桁の数が自分自身と同じになる数」をAutomorphic number と言いますが、

「5乗したとき、下桁の数が自分自身と同じになる数」を探してみた。

ちなみに、Automorphic number は「5乗したとき、下桁の数が自分自身と同じになる数」になる。

def A(n)
  (n..n * 10 - 1).select{|i| (i ** 5 - i) % (n * 10) == 0}
end

(0..7).each{|i| p [i, A(10 ** i)]}

出力結果
[0, [1, 2, 3, 4, 5, 6, 7, 8, 9]]
[1, [24, 25, 32, 43, 49, 51, 57, 68, 75, 76, 93, 99]]
[2, [125, 193, 249, 251, 307, 375, 376, 432, 443, 499, 501, 557, 568, 624, 625, 693, 749, 751, 807, 875, 943, 999]]
[3, [1249, 1251, 1693, 1875, 2057, 2499, 2501, 2943, 3125, 3307, 3568, 3749, 3751, 4193, 4375, 4557, 4999, 5001, 5443, 5625, 5807, 6249, 6251, 6432, 6693, 6875, 7057, 7499, 7501, 7943, 8125, 8307, 8749, 8751, 9193, 9375, 9376, 9557, 9999]]
[4, [13568, 15625, 18751, 20807, 22943, 24999, 25001, 27057, 29193, 31249, 34375, 40625, 43751, 45807, 47943, 49999, 50001, 52057, 54193, 56249, 59375, 65625, 68751, 70807, 72943, 74999, 75001, 77057, 79193, 81249, 84375, 86432, 90624, 90625, 93751, 95807, 97943, 99999]]
[5, [109375, 109376, 140625, 172943, 186432, 204193, 218751, 249999, 250001, 281249, 295807, 327057, 359375, 390625, 422943, 454193, 468751, 499999, 500001, 531249, 545807, 577057, 609375, 640625, 672943, 704193, 718751, 749999, 750001, 781249, 795807, 813568, 827057, 859375, 890624, 890625, 922943, 954193, 968751, 999999]]
[6, [1204193, 1295807, 1718751, 2077057, 2109375, 2499999, 2500001, 2890624, 2890625, 2922943, 3281249, 3704193, 3795807, 4218751, 4577057, 4609375, 4999999, 5000001, 5390625, 5422943, 5781249, 6204193, 6295807, 6718751, 7077057, 7109375, 7109376, 7499999, 7500001, 7890625, 7922943, 8281249, 8704193, 8795807, 9186432, 9218751, 9577057, 9609375, 9999999]]
[7, [12109375, 12890624, 12890625, 16295807, 17077057, 20813568, 24218751, 24999999, 25000001, 25781249, 32922943, 33704193, 37109375, 37890625, 41295807, 42077057, 49218751, 49999999, 50000001, 50781249, 57922943, 58704193, 62109375, 62890625, 66295807, 67077057, 74218751, 74999999, 75000001, 75781249, 79186432, 82922943, 83704193, 87109375, 87109376, 87890625, 91295807, 92077057, 99218751, 99999999]]

170728

Ruby


nil.to_i

http://easyramble.com/ruby-nil-to-i.html
上記の記事では、nil.to_i がfalse ではなく、0 に変換されtrue になることが使いにくいと書いてあるが、
たまたまnil.to_i が0 になることも上手く利用できる場合があったので記しておきます。

三百二十一を通常とは逆に"123"と書くことにします。
では、例えば万の位は？と聞かれると、
万の位はないからないと答える場合や
"12300"だから0と答える場合もあると思うのですが、
このことはRuby では以下のようになります。

irb(main):001:0> nil.to_i
=> 0
irb(main):002:0> str = "123"
=> "123"
irb(main):003:0> str[4]
=> nil
irb(main):004:0> str[4].to_i
=> 0

170725

Number of knight's tours on a m×n chessboard(5)

3 X k(https://oeis.org/A118067) の計算を日曜日に行い、月曜日の朝承認されました。

1861番目まで求めています。

170717

Ruby


q * Delta' / Delta

E_2 = q * Delta' / Delta が成り立つことを確認しておく。

# m次以下を取り出す
def mul(f_ary, b_ary, m)
  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[0..m]
end

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

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

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

def E_2(n)
  a0 = A([[1, 24]], n)
  a = [0] + a0
  puts "Delta'"
  p b = (1..n + 1).map{|i| i * a[i]}
  puts "q / Delta"
  p I(a0, n)
  puts "E_2"
  mul(I(a0, n), b, n)
end

n = 10
p ary = E_2(n)

出力結果
Delta'
[1, -48, 756, -5888, 24150, -36288, -117208, 675840, -1022787, -1159200, 5880732]
q / Delta
[1, 24, 324, 3200, 25650, 176256, 1073720, 5930496, 30178575, 143184000, 639249300]
E_2
[1, -24, -72, -96, -168, -144, -288, -192, -360, -312, -432]

170715(2)

Ruby


Values of Zagier's function J_1(2)

以下、コードです。

# m次以下を取り出す
def mul(f_ary, b_ary, m)
  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[0..m]
end

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

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

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

def A027652(n)
  a = [-1] + Array.new(n, 0)
  (1..n / 4).each{|i| a[i * 4] -= 240 * A001158(i)}
  mul(A([[1, 2], [2, -1], [4, -6]], n), a, n)
end

n = 10000
ary = A027652(n + 1)
-1.upto(n){|i|
  j = ary[i + 1]
  break if j.to_s.size > 1000
  print i
  print ' '
  puts j
}

170715

Values of Zagier's function J_1(1)

170713 のコメントにおいて

「A027652 での出力プログラム（-1から10000までの数表提示）を教えてください。」

とあったので、

Values of Zagier's function J_1(1)　計算式

Values of Zagier's function J_1(2)　コード

を書くことにします。

計算式

こちらの論文(https://projecteuclid.org/download/pdf_1/euclid.em/1064858788) の
6. A FORMULA OF KANEKO AND ZAGIER をご覧ください。

そこには、以下の定義式が書かれています。

Zagier defined the sequence of numbers t(n) using certain singular values of j(z). We call the numbers t(n) Zagier coefficients. Zagier gave an equivalent definition of the t(n) by means of the Fourier expansion of a meromorphic modular form of weight 3/2, namely,

g(z) = - E_4(4*z)*theta_1(z)/eta(4*z)^6 = Sum t(d)*q^d,
（以下省略）

170713

Ruby


j-invariant

次の求め方は多項式同士のかけ算をするより速いと思う。

require 'prime'

def power0(a, n)
  return 1 if n == 0
  k = power0(a, n >> 1)
  k *= k
  return k if n & 1 == 0
  return k * a
end

# x > 0
def sigma(x, i)
  sum = 1
  pq = i.prime_division
  pq.each{|a, n| sum *= (power0(a, (n + 1) * x) - 1) / (power0(a, x) - 1)}
  sum
end

def A000521(n)
  s3 = [0] + (1..n + 1).map{|i| sigma(3, i)}
  s5 = [0] + (1..n + 1).map{|i| sigma(5, i)}
  ary = [1]
  (0..n).each{|i| ary << (1..i + 1).inject(0){|s, j| s + (504 * s5[j] - 240 * (i - j) * s3[j]) * ary[-j]} / (i + 1)}
  ary
end

n = 50
p A000521(n)

出力結果
[1, 744, 196884, 21493760, 864299970, 20245856256, 333202640600, 4252023300096, 44656994071935, 401490886656000, 3176440229784420, 22567393309593600, 146211911499519294, 874313719685775360, 4872010111798142520, 25497827389410525184, 126142916465781843075, 593121772421445058560, 2662842413150775245160, 11459912788444786513920, 47438786801234168813250, 189449976248893390028800, 731811377318137519245696, 2740630712513624654929920, 9971041659937182693533820, 35307453186561427099877376, 121883284330422510433351500, 410789960190307909157638144, 1353563541518646878675077500, 4365689224858876634610401280, 13798375834642999925542288376, 42780782244213262567058227200, 130233693825770295128044873221, 389608006170995911894300098560, 1146329398900810637779611090240, 3319627709139267167263679606784, 9468166135702260431646263438600, 26614365825753796268872151875584, 73773169969725069760801792854360, 201768789947228738648580043776000, 544763881751616630123165410477688, 1452689254439362169794355429376000, 3827767751739363485065598331130120, 9970416600217443268739409968824320, 25683334706395406994774011866319670, 65452367731499268312170283695144960, 165078821568186174782496283155142200, 412189630805216773489544457234333696, 1019253515891576791938652011091437835, 2496774105950716692603315123199672320, 6060574415413720999542378222812650932, 14581598453215019997540391326153984000]