2017年9月24日日曜日

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]

2017年9月17日日曜日

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]