2015年4月29日水曜日

150429

Ruby


p(n | 和因子は相異なる)

2、3日前コードを書いてみた。
オンライン整数列大辞典の
A000009(http://oeis.org/A000009/list)
と比較し、答え合わせしてみる。

n = 55

ps = Array.new(n + 1){0}
ps[0] = 1
i = n + 1
while i > 1
  # ここまでiが最小の因子
  i -= 1
  j = [(n + i) * (n - i + 1) / 2, n - i].min
  ary = ps.clone
  (0..j).each{|k|
    ary[k + i] += ps[k]
  }
  ps = ary
end

# OEIS A000009のデータ
ary0 =
[1,1,1,2,2,3,4,5,6,8,10,12,15,18,22,27,32,38,46,
 54,64,76,89,104,122,142,165,192,222,256,296,340,
 390,448,512,585,668,760,864,982,1113,1260,1426,
 1610,1816,2048,2304,2590,2910,3264,3658,4097,4582,
 5120,5718,6378]
# 一致の確認
p ps == ary0

2015年4月25日土曜日

150425(2)

Ruby


p(n | 和因子は奇数)

オンライン整数列大辞典の
A069878(http://oeis.org/A069878/list)
に載っていなかったので、
p(100000 | 和因子は奇数)を求めてみた。

n = 10 ** 5
ary = []
1.step(n, 2){|i| ary << i}
ps = Array.new(n + 1){0}
ps[0] = 1
ary.each{|num|
  (num..n).each{|i|
    ps[i] += ps[i - num]
  }
}
p ps[n]

出力結果
42494159403332317292526619504218136903700576932083624292980870857936616016516019
12151502208964867232719338338068057175972722741603682118374467405145719404171114
14290856263711241960579022839958369762391816708218000004037412323259921968871341
72550

150425

Ruby


Taxi-cab numbers: sums of 2 cubes in more than 1 way

コードを書いてみた。
オンライン整数列大辞典の
A001235(http://oeis.org/A001235/list)
と比較し、答え合わせしてみる。

M = 704977 ** (1.0 / 3)
N = 36
h = {}
(0..M).each{|a|
  (0..a).each{|b|
    n = a ** 3 + b ** 3
    h[n] == nil ? h[n] = 1 : h[n] += 1
  }
}
ary = h.select{|k, v| v > 1}.keys[0..N - 1].sort

# OEIS A001235のデータ
ary0 =
[1729,4104,13832,20683,32832,39312,40033,46683,
 64232,65728,110656,110808,134379,149389,165464,
 171288,195841,216027,216125,262656,314496,320264,
 327763,373464,402597,439101,443889,513000,513856,
 515375,525824,558441,593047,684019,704977]
# 一致の確認
p ary == ary0

さて
   (6a^2 - 4ab + 4b^2)^3 + (3b^2 + 5ab - 5a^2)^3
= (6b^2 - 4ab + 4a^2)^3 + (3a^2 + 5ab - 5b^2)^3
という等式が成り立つので、
この形に分けられるものを出力する。
(ただし、a,bは0以上の整数に限定しておくものとする。)

M1 = 10
h = {}
(0..M1).each{|a|
  (0..a - 1).each{|b|
    u = 6 * b ** 2 - 4 * a * b + 4 * a ** 2
    if u > 0
      v = 3 * b ** 2 + 5 * a * b - 5 * a ** 2
      if v > 0
        w = 6 * a ** 2 - 4 * a * b + 4 * b ** 2
        n = w ** 3 + v ** 3
        h[n] == nil ? h[n] = 1 : h[n] += 1
      end
    end
  }
}
p h.keys.sort

出力結果
[593047, 2418271, 7620661, 16387189, 20072017, 37955008, 46343059, 79692193, 967
53187, 154769344, 186595201]

2015年4月22日水曜日

150422

Ruby


カプレカ数

コードを書いてみた。
オンライン整数列大辞典の
A099009(http://oeis.org/A099009/list)
と比較し、答え合わせしてみる。

def kaprekar_numbers(m)
  m_ary = []
  numbers = (0..9).to_a
  numbers.repeated_combination(m){|c_ary|
    # 後述のnが9の倍数ということはc_aryの和も9の倍数
    if c_ary.inject(:+) % 9 == 0
      min_ary = c_ary.clone
      min = min_ary.join.to_i
      max = min_ary.reverse.join.to_i
      n = max - min
      m_ary << n if c_ary == n.to_s.split('').map(&:to_i).sort
    end
  }
  m_ary.sort
end

N = 20
ary = [0]
m = 2
while ary.size < N
  kaprekar_numbers(m).each{|i| ary << i}
  m += 1
end
ary = ary[0..N - 1]

# OEIS A099009のデータ
ary0 =
[0,495,6174,549945,631764,63317664,97508421,
 554999445,864197532,6333176664,9753086421,
 9975084201,86431976532,555499994445,633331766664,
 975330866421,997530864201,999750842001,
 8643319766532,63333317666664]
# 一致の確認
p ary == ary0

2015年4月19日日曜日

150419

Ruby


864197532(高速化)

150418(2)分を高速化してみた。

def takahashi_number(m)
  numbers = (0..9).to_a
  numbers.repeated_combination(m){|c_ary|
    # 後述のnが9の倍数ということはc_aryの和も9の倍数
    if c_ary.inject(:+) % 9 == 0
      min_ary = c_ary.clone
      max = min_ary.reverse.join.to_i
      # 最高位を0以外にする←カプレカ数との違い
      i = 0
      while min_ary[i] == 0
        i += 1
      end
      min_ary[0], min_ary[i] = min_ary[i], min_ary[0]
      min = min_ary.join.to_i
      n = max - min
      p [m, c_ary, n] if c_ary == n.to_s.split('').map(&:to_i).sort
    end
  }
end

(2..9).each{|m| takahashi_number(m)}

出力結果
[3, [4, 5, 9], 495]
[4, [1, 4, 6, 7], 6174]
[6, [0, 2, 5, 6, 6, 8], 660852]
[6, [1, 3, 4, 6, 6, 7], 631764]
[6, [4, 4, 5, 5, 9, 9], 549945]
[8, [0, 2, 3, 5, 6, 6, 6, 8], 66308652]
[8, [1, 3, 3, 4, 6, 6, 6, 7], 63317664]
[9, [1, 2, 3, 4, 5, 6, 7, 8, 9], 864197532]
[9, [4, 4, 4, 5, 5, 5, 9, 9, 9], 554999445]

2015年4月18日土曜日

150418(2)

Ruby


864197532

各桁を並び替えてできる最大の数と
各桁を並び替えてできる最小の数(ただし、最高位は0以外にする)の差が
自身と一致するとき、高橋の数と呼ぶ。
(http://masami.d2.r-cms.jp/blog_detail/blog_id=3&id=6)
例1)
6174の場合
7641 - 1467 = 6174
となるので、高橋の数。
例2)
864197532の場合
987654321 - 123456789 = 864197532
となるので、高橋の数。

9桁までの高橋の数を出力してみる。

def takahashi_number(m)
  (10 ** (m - 1) + 8).step(9 * 10 ** (m - 1) - 1, 9){|n|
    ary = n.to_s.split('')
    min_ary = ary.sort
    max = min_ary.reverse.join.to_i
    # 最高位を0以外にする←カプレカ数との違い
    i = 0
    while min_ary[i] == '0'
      i += 1
    end
    min_ary[0], min_ary[i] = min_ary[i], min_ary[0]
    min = min_ary.join.to_i
    p [m, n] if n == max - min
  }
end

(2..9).each{|m| takahashi_number(m)}

出力結果
[3, 495]
[4, 6174]
[6, 549945]
[6, 631764]
[6, 660852]
[8, 63317664]
[8, 66308652]
[9, 554999445]
[9, 864197532]

150418

Ruby


Lucas、Perrin そして McIrvin(剰余について)

Ln mod nの個数を出力してみる。
(ただし、最初の2項は除く。)

n = 3 * 10 ** 6
ary0 = Array.new(n, 0)
a, b = 1, 2
i = 1
while i < n
  a, b = a + b, a
  i += 1
  j = a % i
  ary0[j] += 1
end
p ary0[0..500].map.with_index{|n, i| [i, n]}

出力結果
[[0, 23], [1, 216979], [2, 4117], [3, 114524], [4, 39434], [5, 2], [6, 7], [7, 6
0806], [8, 1], [9, 1], [10, 3], [11, 24795], [12, 1], [13, 2], [14, 7], [15, 4],
 [16, 1], [17, 3], [18, 42262], [19, 2], [20, 1], [21, 1], [22, 11], [23, 6], [2
4, 6], [25, 1], [26, 4], [27, 7], [28, 3], [29, 9168], [30, 3], [31, 6], [32, 1]
, [33, 0], [34, 13], [35, 4], [36, 8], [37, 1], [38, 4], [39, 2], [40, 1], [41,
7], [42, 0], [43, 5], [44, 3], [45, 4], [46, 4], [47, 32674], [48, 4], [49, 3],
[50, 11], [51, 3], [52, 0], [53, 4], [54, 8], [55, 5], [56, 1], [57, 0], [58, 3]
, [59, 12], [60, 2], [61, 8], [62, 4], [63, 8], [64, 4], [65, 5], [66, 9], [67,
4], [68, 0], [69, 3], [70, 10], [71, 4], [72, 1], [73, 10], [74, 5], [75, 3], [7
6, 14615], [77, 2], [78, 3], [79, 9], [80, 2], [81, 3], [82, 4], [83, 7], [84, 2
], [85, 2], [86, 6], [87, 4], [88, 2], [89, 6], [90, 4], [91, 9], [92, 0], [93,
4], [94, 10], [95, 19], [96, 2], [97, 1], [98, 10], [99, 3], [100, 1], [101, 1],
 [102, 7], [103, 15], [104, 1], [105, 4], [106, 10], [107, 4], [108, 21], [109,
2], [110, 1], [111, 4], [112, 0], [113, 7], [114, 4], [115, 6], [116, 2], [117,
5], [118, 4], [119, 12], [120, 9], [121, 4], [122, 8], [123, 26810], [124, 0], [
125, 2], [126, 5], [127, 66], [128, 0], [129, 4], [130, 4], [131, 6], [132, 1],
[133, 1], [134, 3], [135, 3], [136, 4], [137, 4], [138, 2], [139, 8], [140, 5],
[141, 2], [142, 6], [143, 4], [144, 5], [145, 3], [146, 12], [147, 14], [148, 0]
, [149, 4], [150, 4], [151, 3], [152, 0], [153, 4], [154, 7], [155, 5], [156, 2]
, [157, 11], [158, 5], [159, 7], [160, 1], [161, 8], [162, 5], [163, 5], [164, 1
], [165, 2], [166, 7], [167, 18], [168, 3], [169, 5], [170, 6], [171, 4], [172,
2], [173, 4], [174, 2], [175, 4], [176, 6], [177, 2], [178, 1], [179, 4], [180,
3], [181, 7], [182, 0], [183, 3], [184, 4], [185, 4], [186, 4], [187, 2], [188,
5], [189, 2], [190, 2], [191, 11], [192, 3], [193, 4], [194, 32], [195, 1], [196
, 2], [197, 5], [198, 35], [199, 6057], [200, 4], [201, 3], [202, 7], [203, 5],
[204, 4], [205, 2], [206, 6], [207, 15], [208, 1], [209, 1], [210, 3], [211, 10]
, [212, 1], [213, 1], [214, 6], [215, 10], [216, 9], [217, 3], [218, 3], [219, 0
], [220, 3], [221, 14], [222, 3], [223, 14], [224, 6], [225, 2], [226, 2], [227,
 12], [228, 5], [229, 4], [230, 1], [231, 9], [232, 3], [233, 3], [234, 5], [235
, 6], [236, 4], [237, 1], [238, 6], [239, 9], [240, 3], [241, 2], [242, 10], [24
3, 4], [244, 1], [245, 2], [246, 4], [247, 12], [248, 1], [249, 3], [250, 3], [2
51, 9], [252, 6], [253, 3], [254, 4], [255, 13], [256, 6], [257, 2], [258, 5], [
259, 5], [260, 2], [261, 4], [262, 5], [263, 4], [264, 7], [265, 9], [266, 7], [
267, 3], [268, 1], [269, 7], [270, 9], [271, 6], [272, 2], [273, 4], [274, 6], [
275, 12], [276, 2], [277, 3], [278, 2], [279, 8], [280, 2], [281, 6], [282, 2],
[283, 3], [284, 5], [285, 2], [286, 9], [287, 14], [288, 13], [289, 5], [290, 9]
, [291, 4], [292, 3], [293, 5], [294, 6], [295, 3], [296, 0], [297, 0], [298, 1]
, [299, 3], [300, 3], [301, 2], [302, 5], [303, 1], [304, 3], [305, 6], [306, 2]
, [307, 4], [308, 1], [309, 1], [310, 0], [311, 17], [312, 2], [313, 5], [314, 1
2], [315, 11], [316, 1], [317, 3], [318, 8], [319, 31], [320, 2], [321, 2], [322
, 23224], [323, 4], [324, 5], [325, 2], [326, 4], [327, 12], [328, 3], [329, 4],
 [330, 0], [331, 2], [332, 1], [333, 6], [334, 2], [335, 3], [336, 5], [337, 7],
 [338, 10], [339, 3], [340, 3], [341, 5], [342, 4], [343, 8], [344, 2], [345, 4]
, [346, 8], [347, 6], [348, 4], [349, 2], [350, 3], [351, 4], [352, 3], [353, 4]
, [354, 3], [355, 2], [356, 6], [357, 3], [358, 4], [359, 5], [360, 8], [361, 4]
, [362, 14], [363, 5], [364, 9], [365, 4], [366, 2], [367, 20], [368, 4], [369,
4], [370, 2], [371, 6], [372, 2], [373, 6], [374, 5], [375, 5], [376, 2], [377,
7], [378, 4], [379, 7], [380, 2], [381, 3], [382, 6], [383, 12], [384, 6], [385,
 1], [386, 11], [387, 3], [388, 1], [389, 5], [390, 2], [391, 1], [392, 3], [393
, 2], [394, 3], [395, 6], [396, 3], [397, 0], [398, 4], [399, 11], [400, 7], [40
1, 5], [402, 4], [403, 3], [404, 1], [405, 4], [406, 5], [407, 11], [408, 3], [4
09, 9], [410, 3], [411, 2], [412, 2], [413, 2], [414, 4], [415, 12], [416, 2], [
417, 2], [418, 4], [419, 4], [420, 3], [421, 8], [422, 1], [423, 6], [424, 3], [
425, 3], [426, 2], [427, 11], [428, 3], [429, 1], [430, 9], [431, 6], [432, 9],
[433, 2], [434, 9], [435, 3], [436, 2], [437, 6], [438, 2], [439, 15], [440, 3],
 [441, 3], [442, 4], [443, 3], [444, 3], [445, 5], [446, 2], [447, 30], [448, 4]
, [449, 2], [450, 4], [451, 6], [452, 3], [453, 2], [454, 5], [455, 8], [456, 2]
, [457, 1], [458, 9], [459, 2], [460, 0], [461, 6], [462, 0], [463, 9], [464, 10
], [465, 4], [466, 8], [467, 8], [468, 6], [469, 4], [470, 3], [471, 5], [472, 3
], [473, 11], [474, 5], [475, 3], [476, 3], [477, 1], [478, 3], [479, 4], [480,
2], [481, 3], [482, 25], [483, 8], [484, 4], [485, 1], [486, 12], [487, 11], [48
8, 1], [489, 5], [490, 3], [491, 8], [492, 1], [493, 2], [494, 3], [495, 12], [4
96, 1], [497, 4], [498, 9], [499, 8], [500, 1]]

Pn mod nの個数を出力してみる。
(ただし、最初の3項は除く。)

n = 3 * 10 ** 6
ary0 = Array.new(n, 0)
a, b, c = 2, 0, 3
i = 2
while i < n
  a, b, c = b + c, a, b
  i += 1
  j = a % i
  ary0[j] += 1
end
p ary0[0..500].map.with_index{|n, i| [i, n]}

出力結果
[[0, 216817], [1, 6], [2, 87143], [3, 19782], [4, 12], [5, 22640], [6, 5], [7, 8
998], [8, 1], [9, 3], [10, 15929], [11, 1], [12, 7158], [13, 4], [14, 3], [15, 3
], [16, 0], [17, 6482], [18, 4], [19, 3], [20, 4], [21, 11], [22, 3005], [23, 14
], [24, 5], [25, 9], [26, 8], [27, 5], [28, 3], [29, 5510], [30, 5], [31, 2], [3
2, 3], [33, 8], [34, 8], [35, 3], [36, 4], [37, 12], [38, 4], [39, 1029], [40, 7
], [41, 6], [42, 12], [43, 7], [44, 4], [45, 8], [46, 2], [47, 7], [48, 7], [49,
 4], [50, 4], [51, 4767], [52, 9], [53, 6], [54, 2], [55, 0], [56, 2], [57, 9],
[58, 6], [59, 3], [60, 2], [61, 9], [62, 6], [63, 6], [64, 4], [65, 4], [66, 6],
 [67, 16], [68, 4501], [69, 7], [70, 4], [71, 6], [72, 2], [73, 5], [74, 10], [7
5, 9], [76, 3], [77, 11], [78, 4], [79, 9], [80, 5], [81, 5], [82, 5], [83, 8],
[84, 2], [85, 10], [86, 9], [87, 0], [88, 3], [89, 3], [90, 8498], [91, 6], [92,
 3], [93, 11], [94, 3], [95, 5], [96, 1], [97, 11], [98, 3], [99, 7], [100, 5],
[101, 15], [102, 4], [103, 4], [104, 6], [105, 7], [106, 10], [107, 10], [108, 4
], [109, 7], [110, 6], [111, 2], [112, 2], [113, 10], [114, 8], [115, 9], [116,
4], [117, 4], [118, 4], [119, 1031], [120, 12], [121, 3], [122, 15], [123, 5], [
124, 8], [125, 13], [126, 2], [127, 5], [128, 3], [129, 6], [130, 6], [131, 14],
 [132, 4], [133, 14], [134, 2], [135, 8], [136, 2], [137, 3], [138, 11], [139, 5
], [140, 5], [141, 5], [142, 3], [143, 2], [144, 6], [145, 2], [146, 4], [147, 3
], [148, 3], [149, 9], [150, 8], [151, 3], [152, 1], [153, 1], [154, 13], [155,
4], [156, 5], [157, 15], [158, 1905], [159, 5], [160, 3], [161, 4], [162, 4], [1
63, 3], [164, 2], [165, 26], [166, 7], [167, 7], [168, 3], [169, 11], [170, 9],
[171, 5], [172, 3], [173, 10], [174, 11], [175, 3], [176, 3], [177, 6], [178, 5]
, [179, 5], [180, 2], [181, 13], [182, 16], [183, 12], [184, 2], [185, 5], [186,
 10], [187, 9], [188, 4], [189, 3], [190, 3], [191, 4], [192, 3], [193, 3], [194
, 6], [195, 16], [196, 5], [197, 9], [198, 0], [199, 3], [200, 4], [201, 12], [2
02, 5], [203, 4], [204, 1], [205, 7], [206, 2], [207, 7], [208, 5], [209, 1820],
 [210, 16], [211, 1], [212, 2], [213, 7], [214, 7], [215, 3], [216, 3], [217, 3]
, [218, 14], [219, 5], [220, 2], [221, 7], [222, 8], [223, 4], [224, 6], [225, 9
], [226, 0], [227, 6], [228, 3], [229, 16], [230, 7], [231, 3], [232, 4], [233,
4], [234, 6], [235, 4], [236, 4], [237, 4], [238, 2], [239, 17], [240, 2], [241,
 4], [242, 6], [243, 5], [244, 6], [245, 14], [246, 3], [247, 6], [248, 2], [249
, 4], [250, 12], [251, 3], [252, 4], [253, 9], [254, 8], [255, 8], [256, 3], [25
7, 7], [258, 5], [259, 9], [260, 4], [261, 7], [262, 3], [263, 8], [264, 5], [26
5, 9], [266, 5], [267, 5], [268, 5], [269, 7], [270, 1], [271, 7], [272, 0], [27
3, 7], [274, 4], [275, 7], [276, 4], [277, 6919], [278, 2], [279, 13], [280, 4],
 [281, 7], [282, 12], [283, 4], [284, 2], [285, 9], [286, 4], [287, 4], [288, 3]
, [289, 3], [290, 7], [291, 4], [292, 5], [293, 18], [294, 1], [295, 5], [296, 4
], [297, 2], [298, 5], [299, 4], [300, 7], [301, 5], [302, 5], [303, 2], [304, 2
], [305, 12], [306, 1], [307, 6], [308, 5], [309, 20], [310, 2], [311, 4], [312,
 7], [313, 11], [314, 10], [315, 4], [316, 7], [317, 15], [318, 7], [319, 4], [3
20, 8], [321, 2], [322, 9], [323, 2], [324, 0], [325, 9], [326, 3], [327, 7], [3
28, 3], [329, 7], [330, 9], [331, 6], [332, 3], [333, 3], [334, 9], [335, 2], [3
36, 1], [337, 7], [338, 5], [339, 2], [340, 1], [341, 7], [342, 13], [343, 2], [
344, 5], [345, 3], [346, 15], [347, 8], [348, 3], [349, 8], [350, 7], [351, 6],
[352, 4], [353, 1], [354, 8], [355, 14], [356, 7], [357, 12], [358, 3], [359, 4]
, [360, 5], [361, 2], [362, 13], [363, 9], [364, 2], [365, 6], [366, 4], [367, 8
12], [368, 1], [369, 6], [370, 9], [371, 3], [372, 4], [373, 6], [374, 8], [375,
 5], [376, 6], [377, 5], [378, 11], [379, 3], [380, 5], [381, 11], [382, 5], [38
3, 4], [384, 5], [385, 6], [386, 4], [387, 9], [388, 4], [389, 9], [390, 6], [39
1, 2], [392, 5], [393, 4], [394, 3], [395, 7], [396, 3], [397, 6], [398, 9], [39
9, 5], [400, 4], [401, 5], [402, 7], [403, 8], [404, 7], [405, 13], [406, 2], [4
07, 8], [408, 5], [409, 4], [410, 8], [411, 8], [412, 5], [413, 5], [414, 3], [4
15, 5], [416, 8], [417, 10], [418, 6], [419, 4], [420, 2], [421, 13], [422, 6],
[423, 2], [424, 2], [425, 6], [426, 6], [427, 1], [428, 4], [429, 5], [430, 9],
[431, 1], [432, 3], [433, 3], [434, 11], [435, 8], [436, 3], [437, 9], [438, 1],
 [439, 3], [440, 2], [441, 8], [442, 7], [443, 7], [444, 5], [445, 5], [446, 3],
 [447, 4], [448, 2], [449, 4], [450, 7], [451, 6], [452, 6], [453, 13], [454, 8]
, [455, 4], [456, 3], [457, 6], [458, 6], [459, 7], [460, 1], [461, 5], [462, 6]
, [463, 5], [464, 1], [465, 3], [466, 4], [467, 4], [468, 0], [469, 6], [470, 1]
, [471, 9], [472, 5], [473, 8], [474, 9], [475, 7], [476, 5], [477, 8], [478, 0]
, [479, 5], [480, 3], [481, 6], [482, 6], [483, 3], [484, 9], [485, 12], [486, 8
00], [487, 5], [488, 3], [489, 10], [490, 6], [491, 6], [492, 3], [493, 9], [494
, 10], [495, 5], [496, 2], [497, 8], [498, 8], [499, 2], [500, 6]]

Mn mod nの個数を出力してみる。
(ただし、最初の5項は除く。)

n = 3 * 10 ** 6
ary0 = Array.new(n, 0)
ary1 = Array.new(n, 0)
a, b, c, d, e = 11, -7, 3, -1, 5
i = 4
while i < n
  a, b, c, d, e = -a + b - c + e, a, b, c, d
  i += 1
  j = a % i
  ary0[j] += 1
  ary1[i - 1 - j] += 1
end
p ary0[0..1001].map.with_index{|n, i| [i, n]}
p ary1[0..1001].map.with_index{|n, i| [-(i + 1), n]}

出力結果
[[0, 11], [1, 6], [2, 15], [3, 57081], [4, 3], [5, 8], [6, 10], [7, 3], [8, 10],
 [9, 3], [10, 8], [11, 20055], [12, 6], [13, 2], [14, 10], [15, 13], [16, 3], [1
7, 6], [18, 9], [19, 4], [20, 8], [21, 0], [22, 3], [23, 7], [24, 9], [25, 7], [
26, 10], [27, 6], [28, 6], [29, 6], [30, 8], [31, 7], [32, 8], [33, 10376], [34,
 12], [35, 10], [36, 7], [37, 8], [38, 13], [39, 6], [40, 4], [41, 6], [42, 16],
 [43, 9], [44, 11], [45, 4], [46, 6], [47, 8], [48, 4], [49, 6], [50, 2], [51, 2
2], [52, 2], [53, 7], [54, 8], [55, 6], [56, 13], [57, 12], [58, 5], [59, 14], [
60, 8], [61, 5], [62, 8], [63, 11], [64, 4], [65, 17], [66, 9], [67, 5], [68, 10
], [69, 9], [70, 6], [71, 6], [72, 7], [73, 12], [74, 7], [75, 9], [76, 2], [77,
 8], [78, 16], [79, 3], [80, 3], [81, 6], [82, 7], [83, 7], [84, 6], [85, 5], [8
6, 13], [87, 11], [88, 5], [89, 5], [90, 5], [91, 5], [92, 8], [93, 8], [94, 2],
 [95, 6], [96, 16], [97, 4], [98, 4], [99, 10622], [100, 2], [101, 10], [102, 8]
, [103, 8], [104, 6], [105, 4], [106, 4], [107, 6], [108, 11], [109, 7], [110, 1
5], [111, 6], [112, 3], [113, 9], [114, 17], [115, 5], [116, 6], [117, 8], [118,
 3], [119, 7], [120, 7], [121, 4], [122, 7], [123, 6], [124, 3], [125, 5], [126,
 9], [127, 5], [128, 8], [129, 15], [130, 3], [131, 8], [132, 8], [133, 4], [134
, 8], [135, 6], [136, 6], [137, 8], [138, 7], [139, 5], [140, 6], [141, 10], [14
2, 4], [143, 8], [144, 7], [145, 3], [146, 15], [147, 4], [148, 8], [149, 6], [1
50, 13], [151, 3], [152, 6], [153, 9], [154, 10], [155, 15], [156, 4], [157, 2],
 [158, 4], [159, 9], [160, 1], [161, 9], [162, 7], [163, 8], [164, 9], [165, 4],
 [166, 6], [167, 3], [168, 13], [169, 5], [170, 7], [171, 5], [172, 6], [173, 14
], [174, 4], [175, 6], [176, 7], [177, 16], [178, 2], [179, 15], [180, 5], [181,
 2], [182, 18], [183, 8], [184, 10], [185, 7], [186, 6], [187, 7], [188, 14], [1
89, 3], [190, 7], [191, 12], [192, 7], [193, 9], [194, 13], [195, 17], [196, 3],
 [197, 6], [198, 11], [199, 0], [200, 7], [201, 3], [202, 5], [203, 10], [204, 8
], [205, 5], [206, 7], [207, 4], [208, 5], [209, 8], [210, 6], [211, 6], [212, 6
], [213, 8], [214, 6], [215, 5], [216, 2], [217, 4], [218, 16], [219, 6], [220,
2], [221, 7], [222, 10], [223, 7], [224, 6], [225, 5], [226, 5], [227, 26], [228
, 9], [229, 1], [230, 7], [231, 13], [232, 5], [233, 9], [234, 5], [235, 4], [23
6, 8], [237, 5], [238, 9], [239, 6], [240, 6], [241, 4], [242, 7], [243, 14], [2
44, 2], [245, 5], [246, 9], [247, 3], [248, 8], [249, 7], [250, 4], [251, 13], [
252, 6], [253, 3], [254, 12], [255, 5], [256, 4], [257, 9], [258, 26], [259, 3],
 [260, 10], [261, 5], [262, 3], [263, 4], [264, 4], [265, 4], [266, 7], [267, 13
], [268, 4], [269, 8], [270, 10], [271, 4], [272, 7], [273, 6], [274, 12], [275,
 9], [276, 7], [277, 6], [278, 6], [279, 4], [280, 10], [281, 12], [282, 10], [2
83, 6], [284, 7], [285, 8], [286, 3], [287, 8], [288, 5], [289, 3], [290, 14], [
291, 9], [292, 6], [293, 6], [294, 9], [295, 2], [296, 5], [297, 4], [298, 5], [
299, 10], [300, 9], [301, 4], [302, 6], [303, 6], [304, 6], [305, 5], [306, 8],
[307, 5], [308, 13], [309, 4], [310, 5], [311, 4], [312, 12], [313, 7], [314, 5]
, [315, 4], [316, 3], [317, 8], [318, 6491], [319, 4], [320, 8], [321, 6], [322,
 6], [323, 9], [324, 3], [325, 3], [326, 8], [327, 8], [328, 3], [329, 9], [330,
 9], [331, 4], [332, 9], [333, 6], [334, 8], [335, 15], [336, 6], [337, 5], [338
, 6], [339, 16], [340, 4], [341, 3], [342, 4], [343, 2], [344, 11], [345, 2], [3
46, 1], [347, 8], [348, 8], [349, 3], [350, 4], [351, 7], [352, 3], [353, 17], [
354, 7], [355, 2], [356, 5], [357, 11], [358, 4], [359, 10], [360, 7], [361, 3],
 [362, 8], [363, 4], [364, 3], [365, 5], [366, 21], [367, 3], [368, 10], [369, 4
], [370, 3], [371, 9], [372, 12], [373, 5], [374, 4], [375, 6], [376, 6], [377,
5], [378, 6], [379, 4], [380, 8], [381, 2], [382, 5], [383, 2], [384, 12], [385,
 2], [386, 8], [387, 3], [388, 3], [389, 12], [390, 4], [391, 4], [392, 7], [393
, 11], [394, 5], [395, 9], [396, 4], [397, 5], [398, 13], [399, 10], [400, 2], [
401, 8], [402, 11], [403, 5], [404, 7], [405, 4], [406, 4], [407, 9], [408, 5],
[409, 5], [410, 5], [411, 8], [412, 1], [413, 4], [414, 3], [415, 4], [416, 10],
 [417, 4], [418, 4], [419, 6], [420, 8], [421, 2], [422, 5], [423, 6], [424, 5],
 [425, 6], [426, 5], [427, 2], [428, 8], [429, 4], [430, 3], [431, 7], [432, 6],
 [433, 7], [434, 11], [435, 6], [436, 4], [437, 6], [438, 7], [439, 4], [440, 5]
, [441, 3], [442, 6], [443, 20], [444, 5], [445, 2], [446, 5], [447, 9], [448, 8
], [449, 9], [450, 13], [451, 4], [452, 5], [453, 10], [454, 6], [455, 4], [456,
 11], [457, 4], [458, 7], [459, 12], [460, 7], [461, 14], [462, 5], [463, 3], [4
64, 16], [465, 7], [466, 7], [467, 15], [468, 5], [469, 9], [470, 12], [471, 4],
 [472, 3], [473, 6], [474, 5], [475, 2], [476, 2], [477, 1], [478, 4], [479, 7],
 [480, 3], [481, 6], [482, 11], [483, 17], [484, 1], [485, 3], [486, 8], [487, 2
], [488, 10], [489, 8], [490, 5], [491, 8], [492, 5], [493, 3], [494, 18], [495,
 6], [496, 3], [497, 8], [498, 8], [499, 16], [500, 6], [501, 16], [502, 5], [50
3, 6], [504, 5], [505, 2], [506, 10], [507, 6], [508, 3], [509, 2], [510, 8], [5
11, 1], [512, 4], [513, 9], [514, 7], [515, 12], [516, 4], [517, 6], [518, 9], [
519, 7], [520, 8], [521, 5], [522, 3], [523, 7], [524, 4], [525, 1], [526, 7], [
527, 6], [528, 6], [529, 1], [530, 7], [531, 4], [532, 1], [533, 11], [534, 8],
[535, 6], [536, 10], [537, 4], [538, 9], [539, 6], [540, 8], [541, 3], [542, 9],
 [543, 3], [544, 0], [545, 14], [546, 11], [547, 2], [548, 4], [549, 5], [550, 3
], [551, 13], [552, 4], [553, 4], [554, 7], [555, 17], [556, 3], [557, 7], [558,
 4], [559, 3], [560, 7], [561, 9], [562, 4], [563, 13], [564, 9], [565, 1], [566
, 9], [567, 7], [568, 3], [569, 4], [570, 6], [571, 4], [572, 12], [573, 12], [5
74, 9], [575, 2], [576, 6], [577, 3], [578, 12], [579, 11], [580, 5], [581, 5],
[582, 16], [583, 3], [584, 7], [585, 6], [586, 3], [587, 10], [588, 9], [589, 3]
, [590, 8], [591, 11], [592, 6], [593, 5], [594, 8], [595, 5], [596, 4], [597, 5
], [598, 4], [599, 7], [600, 8], [601, 5], [602, 5], [603, 10], [604, 5], [605,
5], [606, 11], [607, 2], [608, 10], [609, 20], [610, 6], [611, 8], [612, 8], [61
3, 6], [614, 4], [615, 3], [616, 2], [617, 7], [618, 10], [619, 5], [620, 4], [6
21, 2], [622, 6], [623, 4], [624, 4], [625, 5], [626, 8], [627, 13], [628, 6], [
629, 4], [630, 7], [631, 0], [632, 11], [633, 12], [634, 5], [635, 8], [636, 14]
, [637, 2], [638, 7], [639, 2], [640, 7], [641, 12], [642, 2], [643, 11], [644,
3], [645, 7], [646, 3], [647, 4], [648, 5], [649, 4], [650, 6], [651, 2], [652,
8], [653, 8], [654, 6], [655, 1], [656, 7], [657, 8], [658, 6], [659, 10], [660,
 2], [661, 5], [662, 5], [663, 20], [664, 8], [665, 1], [666, 3], [667, 6], [668
, 7], [669, 2], [670, 3], [671, 5], [672, 6], [673, 9], [674, 7], [675, 8], [676
, 5], [677, 11], [678, 5], [679, 3], [680, 11], [681, 6], [682, 3], [683, 9], [6
84, 5], [685, 1], [686, 17], [687, 5], [688, 5], [689, 2], [690, 7], [691, 9], [
692, 8], [693, 8], [694, 5], [695, 13], [696, 8], [697, 2], [698, 13], [699, 10]
, [700, 3], [701, 5], [702, 5], [703, 3], [704, 5], [705, 7], [706, 8], [707, 13
], [708, 10], [709, 8], [710, 1], [711, 3], [712, 3], [713, 14], [714, 2], [715,
 3], [716, 5], [717, 6], [718, 6], [719, 2], [720, 9], [721, 5], [722, 9], [723,
 10], [724, 2], [725, 9], [726, 8], [727, 0], [728, 7], [729, 3], [730, 1], [731
, 15], [732, 7], [733, 5], [734, 11], [735, 10], [736, 5], [737, 3], [738, 12],
[739, 4], [740, 7], [741, 4], [742, 10], [743, 7], [744, 12], [745, 0], [746, 7]
, [747, 6], [748, 1], [749, 4], [750, 6], [751, 8], [752, 4], [753, 10], [754, 5
], [755, 9], [756, 3], [757, 3], [758, 15], [759, 7], [760, 9], [761, 9], [762,
8], [763, 3], [764, 6], [765, 2], [766, 4], [767, 10], [768, 7], [769, 2], [770,
 9], [771, 9], [772, 3], [773, 7], [774, 5], [775, 4], [776, 13], [777, 5], [778
, 6], [779, 8], [780, 4], [781, 2], [782, 5], [783, 4], [784, 1], [785, 7], [786
, 10], [787, 3], [788, 5], [789, 7], [790, 5], [791, 5], [792, 2], [793, 10], [7
94, 9], [795, 4], [796, 3], [797, 4], [798, 10], [799, 1], [800, 3], [801, 6], [
802, 2], [803, 6], [804, 4], [805, 9], [806, 4], [807, 12], [808, 4], [809, 5],
[810, 5], [811, 3], [812, 6], [813, 13], [814, 7], [815, 1], [816, 5], [817, 3],
 [818, 11], [819, 12], [820, 4], [821, 12], [822, 7], [823, 5], [824, 9], [825,
6], [826, 4], [827, 10], [828, 6], [829, 2], [830, 8], [831, 9], [832, 7], [833,
 10], [834, 12], [835, 8], [836, 5], [837, 2], [838, 6], [839, 4], [840, 3], [84
1, 3], [842, 4], [843, 9], [844, 0], [845, 4], [846, 6], [847, 1], [848, 9], [84
9, 12], [850, 6], [851, 9], [852, 9], [853, 3], [854, 5], [855, 5], [856, 8], [8
57, 7], [858, 6], [859, 5], [860, 6], [861, 8], [862, 6], [863, 8], [864, 2], [8
65, 4], [866, 6], [867, 4], [868, 1], [869, 5], [870, 10], [871, 1], [872, 9], [
873, 1], [874, 2], [875, 12], [876, 7], [877, 0], [878, 5], [879, 4], [880, 3],
[881, 6], [882, 7], [883, 5], [884, 5], [885, 6], [886, 5], [887, 3], [888, 8],
[889, 3], [890, 5], [891, 2], [892, 4], [893, 9], [894, 3], [895, 3], [896, 3],
[897, 7], [898, 4], [899, 7], [900, 1], [901, 3], [902, 15], [903, 3], [904, 6],
 [905, 4], [906, 11], [907, 6], [908, 7], [909, 4], [910, 4], [911, 6], [912, 7]
, [913, 6], [914, 9], [915, 15], [916, 3], [917, 3], [918, 10], [919, 2], [920,
9], [921, 4], [922, 4], [923, 8], [924, 7], [925, 6], [926, 8], [927, 5], [928,
5], [929, 9], [930, 5], [931, 5], [932, 6], [933, 12], [934, 8], [935, 1], [936,
 5], [937, 5], [938, 5], [939, 8], [940, 4], [941, 6], [942, 9], [943, 7], [944,
 5], [945, 3], [946, 2], [947, 7], [948, 5], [949, 3], [950, 3], [951, 10], [952
, 5], [953, 6], [954, 3], [955, 3], [956, 11], [957, 4], [958, 2], [959, 3], [96
0, 6], [961, 3], [962, 2], [963, 13], [964, 3], [965, 5], [966, 5], [967, 1], [9
68, 8], [969, 8], [970, 2], [971, 10], [972, 10], [973, 3], [974, 9], [975, 4],
[976, 2], [977, 7], [978, 9], [979, 5], [980, 1], [981, 4], [982, 4], [983, 12],
 [984, 11], [985, 2], [986, 10], [987, 16], [988, 3], [989, 12], [990, 9], [991,
 0], [992, 5], [993, 8], [994, 6], [995, 8], [996, 6], [997, 1], [998, 7], [999,
 5], [1000, 5], [1001, 1847]]
[[-1, 216814], [-2, 6], [-3, 5], [-4, 2], [-5, 4], [-6, 3], [-7, 39210], [-8, 10
], [-9, 2], [-10, 5], [-11, 4], [-12, 11], [-13, 10], [-14, 7], [-15, 5], [-16,
12237], [-17, 4], [-18, 13], [-19, 4], [-20, 1], [-21, 9], [-22, 8], [-23, 6], [
-24, 6], [-25, 7], [-26, 4], [-27, 9], [-28, 9], [-29, 5], [-30, 6], [-31, 9], [
-32, 2], [-33, 2], [-34, 7], [-35, 3], [-36, 7], [-37, 5], [-38, 6], [-39, 11],
[-40, 5], [-41, 8], [-42, 8], [-43, 14], [-44, 8], [-45, 11], [-46, 9], [-47, 12
], [-48, 5], [-49, 8], [-50, 5], [-51, 5], [-52, 9], [-53, 3], [-54, 4], [-55, 5
], [-56, 6], [-57, 4707], [-58, 6], [-59, 4], [-60, 5], [-61, 22], [-62, 7], [-6
3, 10], [-64, 3], [-65, 7], [-66, 15], [-67, 8], [-68, 3], [-69, 5], [-70, 12],
[-71, 6], [-72, 6], [-73, 3], [-74, 4], [-75, 10], [-76, 6], [-77, 4], [-78, 8],
 [-79, 12], [-80, 2], [-81, 2], [-82, 6], [-83, 2], [-84, 7], [-85, 7], [-86, 6]
, [-87, 6], [-88, 8], [-89, 7], [-90, 14], [-91, 11], [-92, 4], [-93, 18], [-94,
 9], [-95, 6], [-96, 6], [-97, 12], [-98, 5], [-99, 9], [-100, 9], [-101, 9], [-
102, 8], [-103, 8], [-104, 3], [-105, 9], [-106, 10], [-107, 3], [-108, 3], [-10
9, 9], [-110, 5], [-111, 4], [-112, 8], [-113, 6], [-114, 3], [-115, 10], [-116,
 0], [-117, 6], [-118, 3], [-119, 4], [-120, 13], [-121, 7], [-122, 4], [-123, 8
], [-124, 14], [-125, 6], [-126, 14], [-127, 6], [-128, 4], [-129, 11], [-130, 8
], [-131, 1], [-132, 3], [-133, 12], [-134, 4], [-135, 6], [-136, 10], [-137, 1]
, [-138, 10], [-139, 9], [-140, 1], [-141, 13], [-142, 8], [-143, 5], [-144, 5],
 [-145, 8], [-146, 8], [-147, 18], [-148, 7], [-149, 9], [-150, 11], [-151, 7],
[-152, 1], [-153, 5], [-154, 5], [-155, 8], [-156, 8], [-157, 15], [-158, 4], [-
159, 8], [-160, 11], [-161, 3], [-162, 5], [-163, 5], [-164, 0], [-165, 10], [-1
66, 9], [-167, 5], [-168, 8], [-169, 11], [-170, 4], [-171, 7], [-172, 7], [-173
, 10], [-174, 17], [-175, 8], [-176, 0], [-177, 7], [-178, 14320], [-179, 2], [-
180, 3], [-181, 9], [-182, 15], [-183, 2], [-184, 6], [-185, 1], [-186, 2], [-18
7, 8], [-188, 7], [-189, 12], [-190, 8], [-191, 12], [-192, 9], [-193, 7], [-194
, 3], [-195, 5], [-196, 3], [-197, 8], [-198, 4], [-199, 8], [-200, 4], [-201, 6
], [-202, 9], [-203, 3], [-204, 7], [-205, 16], [-206, 2], [-207, 2], [-208, 7],
 [-209, 4], [-210, 7], [-211, 7], [-212, 3], [-213, 5], [-214, 12], [-215, 5], [
-216, 6], [-217, 3], [-218, 2], [-219, 7], [-220, 3], [-221, 12], [-222, 7], [-2
23, 9], [-224, 5], [-225, 5], [-226, 7], [-227, 1], [-228, 20], [-229, 4], [-230
, 0], [-231, 3], [-232, 11], [-233, 4], [-234, 6], [-235, 3], [-236, 4], [-237,
18], [-238, 12], [-239, 4], [-240, 4], [-241, 12], [-242, 6], [-243, 8], [-244,
5], [-245, 5], [-246, 10], [-247, 9], [-248, 5], [-249, 10], [-250, 7], [-251, 8
], [-252, 6], [-253, 13], [-254, 8], [-255, 16], [-256, 5], [-257, 4], [-258, 5]
, [-259, 16], [-260, 3], [-261, 7], [-262, 9], [-263, 4], [-264, 14], [-265, 8],
 [-266, 4], [-267, 10], [-268, 11], [-269, 5], [-270, 7], [-271, 10], [-272, 5],
 [-273, 9], [-274, 6], [-275, 6], [-276, 4], [-277, 9], [-278, 3], [-279, 4], [-
280, 5], [-281, 1], [-282, 19], [-283, 4], [-284, 3], [-285, 8], [-286, 7], [-28
7, 8], [-288, 6], [-289, 2], [-290, 4], [-291, 2], [-292, 12], [-293, 6], [-294,
 6], [-295, 14], [-296, 4], [-297, 5], [-298, 3], [-299, 2], [-300, 6], [-301, 1
0], [-302, 6], [-303, 5], [-304, 12], [-305, 4], [-306, 7], [-307, 10], [-308, 5
], [-309, 12], [-310, 5], [-311, 6], [-312, 11], [-313, 4], [-314, 2], [-315, 6]
, [-316, 0], [-317, 3], [-318, 13], [-319, 6], [-320, 11], [-321, 4], [-322, 7],
 [-323, 4], [-324, 5], [-325, 4], [-326, 3], [-327, 7], [-328, 8], [-329, 2], [-
330, 4], [-331, 2], [-332, 3], [-333, 6], [-334, 9], [-335, 7], [-336, 5], [-337
, 9], [-338, 5], [-339, 5], [-340, 2], [-341, 2], [-342, 1], [-343, 4], [-344, 4
], [-345, 9], [-346, 7], [-347, 4], [-348, 1], [-349, 10], [-350, 10], [-351, 6]
, [-352, 3], [-353, 2], [-354, 13], [-355, 3], [-356, 2], [-357, 3], [-358, 6],
[-359, 4], [-360, 5], [-361, 5], [-362, 6], [-363, 10], [-364, 6], [-365, 6], [-
366, 11], [-367, 16], [-368, 4], [-369, 5], [-370, 14], [-371, 2], [-372, 5], [-
373, 11], [-374, 5], [-375, 6], [-376, 10], [-377, 1], [-378, 9], [-379, 4], [-3
80, 3], [-381, 7], [-382, 10], [-383, 4], [-384, 2], [-385, 6], [-386, 2], [-387
, 5], [-388, 2], [-389, 3], [-390, 8], [-391, 6], [-392, 6], [-393, 5], [-394, 5
], [-395, 2], [-396, 5], [-397, 11], [-398, 8], [-399, 5], [-400, 10], [-401, 4]
, [-402, 6], [-403, 6], [-404, 2], [-405, 6], [-406, 8], [-407, 3], [-408, 9], [
-409, 5], [-410, 2], [-411, 5], [-412, 6], [-413, 2], [-414, 5], [-415, 9], [-41
6, 7], [-417, 12], [-418, 11], [-419, 2], [-420, 3], [-421, 15], [-422, 8], [-42
3, 2], [-424, 6], [-425, 9], [-426, 5], [-427, 9], [-428, 1], [-429, 5], [-430,
10], [-431, 7], [-432, 7], [-433, 3], [-434, 3], [-435, 7], [-436, 2], [-437, 2]
, [-438, 8], [-439, 6], [-440, 1], [-441, 2], [-442, 5], [-443, 2], [-444, 6], [
-445, 9], [-446, 4], [-447, 7], [-448, 9], [-449, 5], [-450, 7], [-451, 4], [-45
2, 3], [-453, 9], [-454, 8], [-455, 3], [-456, 5], [-457, 9], [-458, 10], [-459,
 8], [-460, 4], [-461, 7], [-462, 9], [-463, 3], [-464, 3], [-465, 2], [-466, 15
], [-467, 2], [-468, 7], [-469, 1], [-470, 3], [-471, 12], [-472, 11], [-473, 2]
, [-474, 8], [-475, 13], [-476, 3], [-477, 11], [-478, 6], [-479, 4], [-480, 10]
, [-481, 7], [-482, 7], [-483, 5], [-484, 6], [-485, 2], [-486, 2], [-487, 12],
[-488, 5], [-489, 7], [-490, 7], [-491, 5], [-492, 6], [-493, 21], [-494, 2], [-
495, 6], [-496, 2], [-497, 4], [-498, 20], [-499, 7], [-500, 4], [-501, 9], [-50
2, 26], [-503, 0], [-504, 3], [-505, 6], [-506, 2], [-507, 13], [-508, 5], [-509
, 4], [-510, 4], [-511, 9], [-512, 4], [-513, 6], [-514, 8], [-515, 4], [-516, 8
], [-517, 2], [-518, 1], [-519, 5], [-520, 12], [-521, 0], [-522, 7], [-523, 4],
 [-524, 3], [-525, 21], [-526, 2], [-527, 5], [-528, 5], [-529, 8], [-530, 4], [
-531, 7], [-532, 3], [-533, 4], [-534, 5], [-535, 6], [-536, 9], [-537, 4], [-53
8, 13], [-539, 3], [-540, 5], [-541, 7], [-542, 5], [-543, 8], [-544, 9], [-545,
 1], [-546, 5], [-547, 14], [-548, 1], [-549, 7], [-550, 5], [-551, 2], [-552, 8
], [-553, 3], [-554, 5], [-555, 2], [-556, 6], [-557, 2], [-558, 5], [-559, 7],
[-560, 2], [-561, 5], [-562, 2102], [-563, 2], [-564, 6], [-565, 10], [-566, 2],
 [-567, 5], [-568, 8], [-569, 6], [-570, 6], [-571, 8], [-572, 7], [-573, 8], [-
574, 19], [-575, 2], [-576, 4], [-577, 7], [-578, 4], [-579, 9], [-580, 3], [-58
1, 4], [-582, 5], [-583, 6], [-584, 3], [-585, 6], [-586, 4], [-587, 5], [-588,
7], [-589, 19], [-590, 4], [-591, 3], [-592, 6], [-593, 4], [-594, 2], [-595, 2]
, [-596, 2], [-597, 9], [-598, 9], [-599, 0], [-600, 10], [-601, 7], [-602, 2],
[-603, 9], [-604, 7], [-605, 4], [-606, 10], [-607, 7], [-608, 3], [-609, 7], [-
610, 7], [-611, 2], [-612, 5], [-613, 8], [-614, 7], [-615, 12], [-616, 9], [-61
7, 6], [-618, 8], [-619, 10], [-620, 3], [-621, 5], [-622, 7], [-623, 2], [-624,
 4], [-625, 2], [-626, 3], [-627, 3], [-628, 6], [-629, 6], [-630, 5], [-631, 8]
, [-632, 1], [-633, 10], [-634, 9], [-635, 5], [-636, 10], [-637, 9], [-638, 2],
 [-639, 6], [-640, 7], [-641, 7], [-642, 9], [-643, 4], [-644, 4], [-645, 3], [-
646, 4], [-647, 6], [-648, 6], [-649, 6], [-650, 5], [-651, 6], [-652, 4], [-653
, 4], [-654, 7], [-655, 4], [-656, 1], [-657, 6], [-658, 7], [-659, 2], [-660, 6
], [-661, 1], [-662, 6], [-663, 7], [-664, 12], [-665, 2], [-666, 12], [-667, 6]
, [-668, 4], [-669, 9], [-670, 10], [-671, 6], [-672, 6], [-673, 4], [-674, 8],
[-675, 11], [-676, 0], [-677, 9], [-678, 5], [-679, 4], [-680, 1], [-681, 3], [-
682, 14], [-683, 2], [-684, 5], [-685, 3], [-686, 2], [-687, 8], [-688, 3], [-68
9, 6], [-690, 8], [-691, 9], [-692, 1], [-693, 3], [-694, 5], [-695, 2], [-696,
9], [-697, 12], [-698, 3], [-699, 2], [-700, 8], [-701, 14], [-702, 7], [-703, 7
], [-704, 0], [-705, 6], [-706, 7], [-707, 5], [-708, 6], [-709, 12], [-710, 2],
 [-711, 1], [-712, 6], [-713, 4], [-714, 16], [-715, 6], [-716, 0], [-717, 7], [
-718, 15], [-719, 6], [-720, 7], [-721, 6], [-722, 9], [-723, 5], [-724, 6], [-7
25, 6], [-726, 5], [-727, 10], [-728, 5], [-729, 7], [-730, 6], [-731, 5], [-732
, 6], [-733, 10], [-734, 2], [-735, 5], [-736, 11], [-737, 1], [-738, 8], [-739,
 4], [-740, 4], [-741, 13], [-742, 4], [-743, 7], [-744, 7], [-745, 9], [-746, 3
], [-747, 6], [-748, 6], [-749, 6], [-750, 6], [-751, 11], [-752, 8], [-753, 5],
 [-754, 11], [-755, 4], [-756, 3], [-757, 7], [-758, 1], [-759, 11], [-760, 7],
[-761, 5], [-762, 8], [-763, 8], [-764, 3], [-765, 6], [-766, 5], [-767, 6], [-7
68, 10], [-769, 3], [-770, 5], [-771, 6], [-772, 13], [-773, 1], [-774, 4], [-77
5, 9], [-776, 11], [-777, 7], [-778, 4], [-779, 3], [-780, 3], [-781, 12], [-782
, 7], [-783, 8], [-784, 5], [-785, 5], [-786, 14], [-787, 8], [-788, 5], [-789,
6], [-790, 4], [-791, 9], [-792, 8], [-793, 2], [-794, 3], [-795, 10], [-796, 4]
, [-797, 3], [-798, 3], [-799, 15], [-800, 1], [-801, 3], [-802, 12], [-803, 4],
 [-804, 2], [-805, 8], [-806, 4], [-807, 11], [-808, 6], [-809, 4], [-810, 4], [
-811, 5], [-812, 6], [-813, 7], [-814, 4], [-815, 10], [-816, 4], [-817, 4], [-8
18, 9], [-819, 4], [-820, 2], [-821, 5], [-822, 8], [-823, 6], [-824, 7], [-825,
 3], [-826, 15], [-827, 1], [-828, 6], [-829, 12], [-830, 4], [-831, 9], [-832,
11], [-833, 8], [-834, 3], [-835, 8], [-836, 2], [-837, 7], [-838, 3], [-839, 4]
, [-840, 7], [-841, 3], [-842, 6], [-843, 8], [-844, 7], [-845, 3], [-846, 7], [
-847, 7], [-848, 2], [-849, 10], [-850, 11], [-851, 2], [-852, 2], [-853, 10], [
-854, 3], [-855, 2], [-856, 5], [-857, 1], [-858, 2], [-859, 8], [-860, 6], [-86
1, 6], [-862, 10], [-863, 2], [-864, 7], [-865, 5], [-866, 8], [-867, 8], [-868,
 3], [-869, 2], [-870, 3], [-871, 10], [-872, 2], [-873, 5], [-874, 7], [-875, 1
], [-876, 5], [-877, 11], [-878, 3], [-879, 3], [-880, 6], [-881, 1], [-882, 10]
, [-883, 7], [-884, 2], [-885, 8], [-886, 9], [-887, 2], [-888, 2], [-889, 7], [
-890, 3], [-891, 5], [-892, 6], [-893, 7], [-894, 11], [-895, 3], [-896, 6], [-8
97, 5], [-898, 9], [-899, 2], [-900, 3], [-901, 8], [-902, 5], [-903, 11], [-904
, 11], [-905, 4], [-906, 5], [-907, 14], [-908, 2], [-909, 9], [-910, 2], [-911,
 2], [-912, 10], [-913, 4], [-914, 7], [-915, 2], [-916, 5], [-917, 3], [-918, 5
], [-919, 2], [-920, 3], [-921, 7], [-922, 9], [-923, 1], [-924, 1], [-925, 8],
[-926, 4], [-927, 6], [-928, 5], [-929, 2], [-930, 9], [-931, 5], [-932, 3], [-9
33, 7], [-934, 11], [-935, 1], [-936, 10], [-937, 7], [-938, 3], [-939, 11], [-9
40, 5], [-941, 10], [-942, 6], [-943, 14], [-944, 4], [-945, 7], [-946, 8], [-94
7, 4], [-948, 5], [-949, 12], [-950, 2], [-951, 4], [-952, 6], [-953, 3], [-954,
 4], [-955, 3], [-956, 2], [-957, 35], [-958, 4], [-959, 5], [-960, 4], [-961, 9
], [-962, 6], [-963, 5], [-964, 5], [-965, 2], [-966, 10], [-967, 13], [-968, 9]
, [-969, 4], [-970, 4], [-971, 3], [-972, 4], [-973, 5], [-974, 5], [-975, 7], [
-976, 7], [-977, 2], [-978, 5], [-979, 6], [-980, 2], [-981, 2], [-982, 8], [-98
3, 3], [-984, 6], [-985, 7], [-986, 2], [-987, 10], [-988, 7], [-989, 3], [-990,
 6], [-991, 5], [-992, 1], [-993, 4], [-994, 10], [-995, 2], [-996, 5], [-997, 9
], [-998, 2], [-999, 2], [-1000, 7], [-1001, 2], [-1002, 4]]

2015年4月14日火曜日

150414

Ruby


Lucas、Perrin そして McIrvin

L0 = 2, L1 = 1
Ln = Ln-1 + Ln-2 for n>1
と定めると、
Lp mod p = 1
が成り立つ。
n を合成数とし、
Lp mod p = 1
が成り立つとき、
n を Lucas pseudoprime とよぶ。
これらを出力してみよう。

require 'prime'

a, b = 1, 2
i = 1
while i < 10 ** 4
  a, b = a + b, a
  i += 1
  if a % i == 1
    p i if !i.prime?
  end
end

出力結果
705
2465
2737
3745
4181
5777
6721

P0 = 3, P1 = 0, P2 = 2,
Pn = Pn-2 + Pn-3 for n>2
と定めると、
Pp mod p = 0
が成り立つ。
n を合成数とし、
Pp mod p = 0
が成り立つとき、
n を Perrin pseudoprime とよぶ。
これらを出力してみよう。
(コードも出力結果も150328分と同じ。)

require 'prime'

a, b, c = 2, 0, 3
i = 2
while i < 10 ** 6
  a, b, c = b + c, a, b
  i += 1
  if a % i == 0
    p i if !i.prime?
  end
end

出力結果
271441
904631

M0 = 5, M1 = -1, M2 = 3, M3 = -7, M4 = 11
Mn = -Mn-1 + Mn-2 - Mn-3 + Mn-5 for n>4
と定めると、
Mp mod p = p - 1
が成り立つ。
n を合成数とし、
Pp mod p = p - 1
が成り立つとき、
https://mathematrec.wordpress.com/2013/05/27/my-own-monologue-about-pseudoprimes/
にしたがい、n を McIrvin pseudoprime とよぼう。
最小の McIrvin pseudoprime は4。
よって、これより大きな McIrvin pseudoprime を出力してみよう。
(以下のコードを実行することはおすすめしない。
 i < 5000000 まで計算するのに数時間かかり、
 i < 15000000 まで計算するのに一日弱かかる。)

require 'prime'

a, b, c, d, e = 11, -7, 3, -1, 5
i = 4
while i < 15000000
  a, b, c, d, e = -a + b - c + e, a, b, c, d
  i += 1
  if a % i == i - 1
    p i if !i.prime?
  end
end

出力結果
14791044

一個しか見つからなかったが、
見つけるのが難しいことはいいことかもしれない。
この後に続く McIrvin pseudoprime を知りたければ、
オンライン整数列大辞典の
A225876(http://oeis.org/A225876/list)
を見るとよいでしょう。

2015年4月13日月曜日

150413(2)

Ruby


Thue–Morse sequence

コードを書いてみた。
オンライン整数列大辞典の
A010060(http://oeis.org/A010060/list)
と比較し、答え合わせしてみる。

N = 104
ary = [0]
n = 0
while ary.size < N
  c_ary = ary.clone
  ary.each{|i| c_ary << (i + 1) % 2}
  ary = c_ary
  n += 1
end
ary = ary[0..N]

# OEIS A010060のデータ
ary0 =
[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,
 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,
 1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,
 1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,
 0,1,0,0,1,1]
# 一致の確認
p ary == ary0

150413

Ruby


Schizophrenic number(連続する個数 2.0)

150412分のコードが長ったらしかったので少し改良した。

require 'bigdecimal'
M = 700
N = 51
n = 7
a = 0
(1..N).each{|i| a = 10 * a + i
  if i % 2 == 1
    str = BigDecimal.new(a).sqrt(M * 2).to_s
    ary = str.scan(/((.)\2{#{n - 1},}|.)/).map{|v| v[0]}
    cnt = -2
    cnt0 = -2
    cnt1 = 0
    ary1 = []
    ary.each{|i|
      # 数字以外が出てきたら停止
      break if i == 'E'
      # M桁まで
      break if cnt > M - 1
      j = i.size
      cnt += j
      if j < n
        cnt0 += j
      else
        cnt1 += j
        ary1 << j
      end
    }
    p [i, cnt, cnt0, cnt1, ary1.inject(:+), ary1]
  end
}

出力結果
[1, 1, 1, 0, nil, []]
[3, 700, 700, 0, nil, []]
[5, 700, 700, 0, nil, []]
[7, 700, 700, 0, nil, []]
[9, 700, 692, 8, 8, [8]]
[11, 700, 682, 18, 18, [10, 8]]
[13, 700, 678, 22, 22, [12, 10]]
[15, 700, 666, 34, 34, [14, 12, 8]]
[17, 700, 660, 40, 40, [16, 14, 10]]
[19, 700, 646, 54, 54, [18, 16, 12, 8]]
[21, 700, 638, 62, 62, [20, 18, 14, 10]]
[23, 700, 626, 74, 74, [21, 19, 15, 12, 7]]
[25, 700, 616, 84, 84, [23, 21, 17, 14, 9]]
[27, 700, 598, 102, 102, [25, 23, 19, 16, 11, 8]]
[29, 700, 587, 113, 113, [27, 25, 21, 17, 13, 10]]
[31, 700, 570, 130, 130, [29, 27, 23, 19, 14, 11, 7]]
[33, 700, 556, 144, 144, [31, 29, 25, 21, 16, 13, 9]]
[35, 700, 536, 164, 164, [33, 31, 27, 23, 18, 15, 10, 7]]
[37, 700, 520, 180, 180, [35, 33, 29, 25, 20, 17, 12, 9]]
[39, 700, 505, 195, 195, [37, 35, 31, 27, 22, 19, 14, 10]]
[41, 700, 489, 211, 211, [39, 37, 33, 29, 24, 21, 16, 12]]
[43, 700, 465, 235, 235, [41, 39, 35, 31, 26, 23, 18, 14, 8]]
[45, 700, 448, 252, 252, [43, 41, 37, 33, 28, 24, 20, 16, 10]]
[47, 700, 424, 276, 276, [45, 43, 39, 35, 29, 26, 22, 18, 12, 7]]
[49, 700, 405, 295, 295, [47, 45, 41, 37, 31, 28, 23, 20, 14, 9]]
[51, 700, 388, 312, 312, [49, 47, 42, 39, 33, 30, 25, 21, 15, 11]]

2015年4月12日日曜日

150412

Ruby


Schizophrenic number(連続する個数 1.0)

0.
11111111111111111111111111111111111111111111111
0860
555555555555555555555555555555555555555555555
2730541
66666666666666666666666666666666666666666
0296260347
2222222222222222222222222222222222222
0426563940928819
4444444444444444444444444444444
38775551250401171874
9999999999999999999999999999
808249687711486305338541
66666666666666666666666
5987185738621440638655598958
33333333333333333333
0843460407627608206940277099609374
99999999999999
0642227587555983066639430321587456597
222222222
186349201679118083308184478360027737E25
の場合、
47, 45, 41, 37, 31, 28, 23, 20, 14, 9連続同じ数字が並んでいる。

n(>6)連続する個数を表示してみる。

require 'bigdecimal'
M = 700
N = 51
a = 0
(1..N).each{|i| a = 10 * a + i
  if i % 2 == 1
    str = BigDecimal.new(a).sqrt(M * 2).to_s
    ary1 = str.split('')
    cnt = -2
    cnt0 = -2
    cnt1 = 0
    # 変わり目の番号を収納
    ary2 = []
    # 7連続以上同じ数字ならtrue
    d = false
    b0, b1, b2, b3, b4, b5, f = -7, -6, -5, -4, -3, -2, -1
    ary1.each{|i|
      # 数字以外が出てきたら停止
      break if i == 'E'
      # M桁まで
      break if cnt > M - 1
      cnt += 1
      b0, b1, b2, b3, b4, b5, f = b1, b2, b3, b4, b5, f, i
      if [b0, b1, b2, b3, b4, b5, f].uniq.size == 1
        if !d
          cnt0 -= 6
          cnt1 += 7
          ary2 << cnt - 6
        else
          cnt1 += 1
        end
        d = true
      else
        cnt0 += 1
        ary2 << cnt if d
        d = false
      end
    }
    ary3 = []
    (0..ary2.size - 2).each{|i| ary3 << ary2[i + 1] - ary2[i] if i % 2 == 0}
    p [i, cnt, cnt0, cnt1, ary3.inject(:+), ary3]
  end
}

出力結果
[1, 1, 1, 0, nil, []]
[3, 700, 700, 0, nil, []]
[5, 700, 700, 0, nil, []]
[7, 700, 700, 0, nil, []]
[9, 700, 692, 8, 8, [8]]
[11, 700, 682, 18, 18, [10, 8]]
[13, 700, 678, 22, 22, [12, 10]]
[15, 700, 666, 34, 34, [14, 12, 8]]
[17, 700, 660, 40, 40, [16, 14, 10]]
[19, 700, 646, 54, 54, [18, 16, 12, 8]]
[21, 700, 638, 62, 62, [20, 18, 14, 10]]
[23, 700, 626, 74, 74, [21, 19, 15, 12, 7]]
[25, 700, 616, 84, 84, [23, 21, 17, 14, 9]]
[27, 700, 598, 102, 102, [25, 23, 19, 16, 11, 8]]
[29, 700, 587, 113, 113, [27, 25, 21, 17, 13, 10]]
[31, 700, 570, 130, 130, [29, 27, 23, 19, 14, 11, 7]]
[33, 700, 556, 144, 144, [31, 29, 25, 21, 16, 13, 9]]
[35, 700, 536, 164, 164, [33, 31, 27, 23, 18, 15, 10, 7]]
[37, 700, 520, 180, 180, [35, 33, 29, 25, 20, 17, 12, 9]]
[39, 700, 505, 195, 195, [37, 35, 31, 27, 22, 19, 14, 10]]
[41, 700, 489, 211, 211, [39, 37, 33, 29, 24, 21, 16, 12]]
[43, 700, 465, 235, 235, [41, 39, 35, 31, 26, 23, 18, 14, 8]]
[45, 700, 448, 252, 252, [43, 41, 37, 33, 28, 24, 20, 16, 10]]
[47, 700, 424, 276, 276, [45, 43, 39, 35, 29, 26, 22, 18, 12, 7]]
[49, 700, 405, 295, 295, [47, 45, 41, 37, 31, 28, 23, 20, 14, 9]]
[51, 700, 388, 312, 312, [49, 47, 42, 39, 33, 30, 25, 21, 15, 11]]

2015年4月10日金曜日

150410

Ruby


Schizophrenic number

require 'bigdecimal'
a = 0
(1..49).each{|i| a = 10 * a + i}
p BigDecimal.new(a).sqrt(500).to_s

出力結果
"0.11111111111111111111111111111111111111111111111086055555555555555555555555555
55555555555555555552730541666666666666666666666666666666666666666660296260347222
22222222222222222222222222222222220426563940928819444444444444444444444444444444
43877555125040117187499999999999999999999999999998082496877114863053385416666666
66666666666666665987185738621440638655598958333333333333333333330843460407627608
20694027709960937499999999999999064222758755598306663943032158745659722222222218
6349201679118083308184478360027737E25"

こんなふうに並んでいる。
0.
11111111111111111111111111111111111111111111111
0860
555555555555555555555555555555555555555555555
2730541
66666666666666666666666666666666666666666
0296260347
2222222222222222222222222222222222222
0426563940928819
4444444444444444444444444444444
38775551250401171874
9999999999999999999999999999
808249687711486305338541
66666666666666666666666
5987185738621440638655598958
33333333333333333333
0843460407627608206940277099609374
99999999999999
0642227587555983066639430321587456597
222222222
186349201679118083308184478360027737E25

2015年4月5日日曜日

150405(3)

Ruby


Generalization of the Zeckendorf representation

a.b>0とし、数列{Xn}を次の線形漸化式で定義する。
Xn+1 = a Xn + b Xn-1, X0 = 0, X1 = 1
このとき、次の定理が成り立つ。
(定理)
任意の正の整数は次のように唯一通りに表される。
N = ∑αiXi
但し、各αは整数で、0≦α1≦a-1, 0≦αi≦a (i≠1) αn≠0 
αi = aのとき、0≦αi-1≦b-1 
さらに、この表現は最小表現である。
(http://oacis.lib.kaiyodai.ac.jp/dspace/bitstream/123456789/335/1/AN00161244-51-1.pdf)

この表現を二進表記のように出力するコードを書いてみた。
言うまでもなく、150405(2)分の一般化である。

def representation(n, a, b)
  f_ary = []
  c, d = 1, a
  while c <= n
    f_ary << c
    c, d = d, b * c + a * d
  end
  s = f_ary.size
  r_ary = Array.new(s, 0)
  k = a + 1
  m = n
  i = s - 1
  while m > 0
    if m == a * f_ary[i]
      r_ary[i] = a
      m = 0
    else
      j = m / f_ary[i]
      k = (k == a)? [b - 1, j].min : [a, j].min
      r_ary[i] = k
      m -= k * f_ary[i]
      i -= 1
    end
  end
  r_ary.join.reverse.to_i
end

A0, B0 = 1, 1
ary0 = []
for n in (0..33)
  ary0 << representation(n, A0, B0)
end
p ary0

A1, B1 = 2, 1
ary1 = []
for n in (0..33)
  ary1 << representation(n, A1, B1)
end
p ary1

A2, B2 = 1, 2
ary2 = []
for n in (0..33)
  ary2 << representation(n, A2, B2)
end
p ary2

A3, B3 = 2, 2
ary3 = []
for n in (0..33)
  ary3 << representation(n, A3, B3)
end
p ary3

A4, B4 = 2, 3
ary4 = []
for n in (0..33)
  ary4 << representation(n, A4, B4)
end
p ary4

出力結果
[0, 10, 100, 1000, 1010, 10000, 10010, 10100, 100000, 100010, 100100, 101000, 10
1010, 1000000, 1000010, 1000100, 1001000, 1001010, 1010000, 1010010, 1010100, 10
000000, 10000010, 10000100, 10001000, 10001010, 10010000, 10010010, 10010100, 10
100000, 10100010, 10100100, 10101000, 10101010]
[0, 1, 10, 11, 20, 100, 101, 110, 111, 120, 200, 201, 1000, 1001, 1010, 1011, 10
20, 1100, 1101, 1110, 1111, 1120, 1200, 1201, 2000, 2001, 2010, 2011, 2020, 1000
0, 10001, 10010, 10011, 10020]
[0, 10, 11, 100, 110, 1000, 1010, 1011, 1100, 1110, 1111, 10000, 10010, 10011, 1
0100, 10110, 11000, 11010, 11011, 11100, 11110, 100000, 100010, 100011, 100100,
100110, 101000, 101010, 101011, 101100, 101110, 101111, 110000, 110010]
[0, 1, 10, 11, 20, 21, 100, 101, 110, 111, 120, 121, 200, 201, 210, 211, 1000, 1
001, 1010, 1011, 1020, 1021, 1100, 1101, 1110, 1111, 1120, 1121, 1200, 1201, 121
0, 1211, 2000, 2001]
[0, 1, 10, 11, 20, 21, 22, 100, 101, 110, 111, 120, 121, 122, 200, 201, 210, 211
, 220, 221, 1000, 1001, 1010, 1011, 1020, 1021, 1022, 1100, 1101, 1110, 1111, 11
20, 1121, 1122]

これらはそれぞれ次のことを表している。
(f_ary = [1, 1, 2, 3, 5, …]となることに注意)
 0 = 0
 1 = 1*1
 2 = 1*2
 3 = 1*3
 4 = 1*3 + 1*1
 5 = 1*5
 6 = 1*5 + 1*1
 7 = 1*5 + 1*2
 8 = 1*8
 9 = 1*8 + 1*1
10 = 1*8 + 1*2
11 = 1*8 + 1*3
12 = 1*8 + 1*3 + 1*1 
33 = 1*21 + 1*8 + 1*3 + 1*1

 0 = 0                     ← ペル数(Pell number)による表現
 1 = 1*1
 2 = 1*2
 3 = 1*2 + 1*1
 4 = 2*2
 5 = 1*5
 6 = 1*5 + 1*1
 7 = 1*5 + 1*2
 8 = 1*5 + 1*2 + 1*1
 9 = 1*5 + 2*2
10 = 2*5
11 = 2*5 + 1*1
12 = 1*12
33 = 1*29 + 2*2

 0 = 0
 1 = 1*1
 2 = 1*
 3 = 1*3
 4 = 1*3 + 1*1
 5 = 1*5
 6 = 1*5 + 1*1
 7 = 1*5 +
 8 = 1*5 + 1*3
 9 = 1*5 + 1*3 + 1*1
10 = 1*5 +
11 = 1*11
12 = 1*11 + 1*1
33 = 1*21 + 1*11 + 1*1

(f_ary = [1, 1, 3, 5, …]となることに注意)
 0 = 0
 1 = 1*1
 2 = 1*1 + 1*1
 3 = 1*3
 4 = 1*3 + 1*1
 5 = 1*5
 6 = 1*5 + 1*1
 7 = 1*5 + 1*1 + 1*1
 8 = 1*5 + 1*3
 9 = 1*5 + 1*3 + 1*1
10 = 1*5 + 1*3 + 1*1 + 1*1
11 = 1*11
12 = 1*11 + 1*1 
33 = 1*21 + 1*11 + 1*1

 0 = 0
 1 = 1*1
 2 = 1*2
 3 = 1*2 + 1*1
 4 = 2*2
 5 = 2*2 + 1*1
 6 = 2*2 + 2*1
 7 = 1*7
 8 = 1*7 + 1*1
 9 = 1*7 + 1*2
10 = 1*7 + 1*2+ 1*1
11 = 1*7 + 2*2
12 =  1*7 + 2*2 +2*1
33 = 1*20 + 1*7 + 2*2 + 2*1

150405(2)

Ruby


Zeckendorf number representation

12までの整数Nの二進表記は以下のとおりである。
0
1
10
11
100
101
110
111
1000
1001
1010
1011
1100

12までの整数Nのゼッケンドルフの表現は
 0 = 0
 1 = 1
 2 = 2
 3 = 3
 4 = 3 + 1
 5 = 5
 6 = 5 + 1
 7 = 5 + 2 
 8 = 8
 9 = 8 + 1
10 = 8 + 2
11 = 8 + 3
12 = 8 + 3 + 1
であるが、これを二進表記のように書くと以下のとおりになる。
0
1
10
100
101
1000
1001
1010
10000
10001
10010
10100
10101

このような表現を出力するコードを書いてみた。
オンライン整数列大辞典の
A014417(http://oeis.org/A014417/list)
と比較し、答え合わせしてみる。

def representation(n)
  f_ary = []
  a, b = 1, 2
  while a <= n
    f_ary << a
    a, b = b, a + b
  end
  s = f_ary.size
  r_ary = Array.new(s, 0)
  m = n
  i = s - 1
  while m > 0
    while f_ary[i] > m
      i -= 1
    end
    r_ary[i] = 1
    m -= f_ary[i]
    # 連続してはいけない
    i -= 2
  end
  r_ary.join.reverse.to_i
end

ary = []
for n in (0..33)
  ary << representation(n)
end

# OEIS A014417のデータ
ary0 =
[0,1,10,100,101,1000,1001,1010,10000,10001,10010,
 10100,10101,100000,100001,100010,100100,100101,
 101000,101001,101010,1000000,1000001,1000010,
 1000100,1000101,1001000,1001001,1001010,1010000,
 1010001,1010010,1010100,1010101]
# 一致の確認
p ary == ary0

このコードを書いた後、以下のコードをネットで見つけた。
(http://rosettacode.org/wiki/Zeckendorf_number_representation#Ruby)

def zeckendorf
  return to_enum(__method__) unless block_given?
  x = 0
  loop do
    bin = x.to_s(2)
    yield bin unless bin.include?("11")
    x += 1
  end
end

zeckendorf.take(21).each_with_index{|x,i| puts "%3d: %8s"% [i, x]}

150405

Ruby


Self-descriptive number

一昨日Self-descriptive numberを高速に求める方法を
スタック・オーバーフローで質問してみた。
(http://ja.stackoverflow.com/questions/8696/10%E6%A1%81%E3%81%BE%E3%81%A7%E3%81%AEself-descriptive-number%E3%81%AE%E6%B1%82%E3%82%81%E6%96%B9%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6)
そして、昨日h2so5さんのコードを用いて少しばかり高速化してみた。

def sdn(len, l = 0, m = 0, x = [])
  a = []
  if l == len
    if (0..len - 1).all?{|i| x.count(i) == x[i]}
      a << x.join.to_i
    end
  elsif m <= len
    s = l > 0 ? 0 : 1
    (s..len - 1).each{|n| a += sdn(len, l + 1, m + n, x + [n])}
  end
  a
end

N = 10
(1..N).each{|b|
  sdn(b).each{|n| p n}
}