151227(8)

Ruby

Stern's diatomic series に現れるフィボナッチ数(1)

フィボナッチ数を取り出してみた。

def A002487(n)
  a, b = 0, 1
  ary = [a, b]
  i = 1
  while i < n
    a, b = b, b + a - 2 * (a % b)
    ary << b
    i += 1
  end
  ary[0..n]
end

# フィボナッチ数列は上とよく似ている
def fib_ary(n)
  a, b = 0, 1
  ary = [a, b]
  while b < n
    a, b = b, b + a
    ary << b
  end
  ary
end

N = 11
ary = A002487(2 ** N)
f_ary = fib_ary(ary.max)

i_ary = []
idx = 0
ary.each{|i|
  if f_ary.include?(i)
    p [idx.to_s(2), idx, i]
    i_ary << i
  end
  idx += 1
}
p i_ary

出力結果
["0", 0, 0]
["1", 1, 1]
["10", 2, 1]
["11", 3, 2]
["100", 4, 1]
["101", 5, 3]
["110", 6, 2]
["111", 7, 3]
["1000", 8, 1]
["1010", 10, 3]
["1011", 11, 5]
["1100", 12, 2]
["1101", 13, 5]
["1110", 14, 3]
["10000", 16, 1]
["10001", 17, 5]
["10100", 20, 3]
["10101", 21, 8]
["10110", 22, 5]
["11000", 24, 2]
["11010", 26, 5]
["11011", 27, 8]
["11100", 28, 3]
["11111", 31, 5]
["100000", 32, 1]
["100010", 34, 5]
["101000", 40, 3]
["101010", 42, 8]
["101011", 43, 13]
["101100", 44, 5]
["110000", 48, 2]
["110100", 52, 5]
["110101", 53, 13]
["110110", 54, 8]
["111000", 56, 3]
["111110", 62, 5]
["1000000", 64, 1]
["1000100", 68, 5]
["1000111", 71, 13]
["1001111", 79, 13]
["1010000", 80, 3]
["1010100", 84, 8]
["1010101", 85, 21]
["1010110", 86, 13]
["1011000", 88, 5]
["1100000", 96, 2]
["1101000", 104, 5]
["1101010", 106, 13]
["1101011", 107, 21]
["1101100", 108, 8]
["1110000", 112, 3]
["1110001", 113, 13]
["1111001", 121, 13]
["1111100", 124, 5]
["10000000", 128, 1]
["10000001", 129, 8]
["10000011", 131, 13]
["10001000", 136, 5]
["10001110", 142, 13]
["10011110", 158, 13]
["10100000", 160, 3]
["10101000", 168, 8]
["10101010", 170, 21]
["10101011", 171, 34]
["10101100", 172, 13]
["10110000", 176, 5]
["10111111", 191, 13]
["11000000", 192, 2]
["11000001", 193, 13]
["11010000", 208, 5]
["11010100", 212, 13]
["11010101", 213, 34]
["11010110", 214, 21]
["11011000", 216, 8]
["11100000", 224, 3]
["11100010", 226, 13]
["11110010", 242, 13]
["11111000", 248, 5]
["11111101", 253, 13]
["11111111", 255, 8]
["100000000", 256, 1]
["100000010", 258, 8]
["100000110", 262, 13]
["100001111", 271, 21]
["100010000", 272, 5]
["100011100", 284, 13]
["100011111", 287, 21]
["100100011", 291, 34]
["100111100", 316, 13]
["101000000", 320, 3]
["101010000", 336, 8]
["101010100", 340, 21]
["101010101", 341, 55]
["101010110", 342, 34]
["101011000", 344, 13]
["101100000", 352, 5]
["101110111", 375, 34]
["101111110", 382, 13]
["110000000", 384, 2]
["110000010", 386, 13]
["110001001", 393, 34]
["110100000", 416, 5]
["110101000", 424, 13]
["110101010", 426, 34]
["110101011", 427, 55]
["110101100", 428, 21]
["110110000", 432, 8]
["111000000", 448, 3]
["111000100", 452, 13]
["111011101", 477, 34]
["111100001", 481, 21]
["111100100", 484, 13]
["111110000", 496, 5]
["111110001", 497, 21]
["111111010", 506, 13]
["111111110", 510, 8]
["1000000000", 512, 1]
["1000000100", 516, 8]
["1000001100", 524, 13]
["1000011110", 542, 21]
["1000100000", 544, 5]
["1000101101", 557, 55]
["1000111000", 568, 13]
["1000111110", 574, 21]
["1001000110", 582, 34]
["1001100011", 611, 55]
["1001111000", 632, 13]
["1010000000", 640, 3]
["1010100000", 672, 8]
["1010101000", 680, 21]
["1010101010", 682, 55]
["1010101011", 683, 89]
["1010101100", 684, 34]
["1010110000", 688, 13]
["1011000000", 704, 5]
["1011010001", 721, 55]
["1011100111", 743, 55]
["1011101110", 750, 34]
["1011111100", 764, 13]
["1100000000", 768, 2]
["1100000100", 772, 13]
["1100010010", 786, 34]
["1100011001", 793, 55]
["1100101111", 815, 55]
["1101000000", 832, 5]
["1101010000", 848, 13]
["1101010100", 852, 34]
["1101010101", 853, 89]
["1101010110", 854, 55]
["1101011000", 856, 21]
["1101100000", 864, 8]
["1110000000", 896, 3]
["1110001000", 904, 13]
["1110011101", 925, 55]
["1110111010", 954, 34]
["1111000010", 962, 21]
["1111001000", 968, 13]
["1111010011", 979, 55]
["1111100000", 992, 5]
["1111100010", 994, 21]
["1111110100", 1012, 13]
["1111111100", 1020, 8]
["10000000000", 1024, 1]
["10000001000", 1032, 8]
["10000010001", 1041, 34]
["10000011000", 1048, 13]
["10000111100", 1084, 21]
["10001000000", 1088, 5]
["10001000001", 1089, 34]
["10001011010", 1114, 55]
["10001110000", 1136, 13]
["10001111001", 1145, 55]
["10001111100", 1148, 21]
["10010001100", 1164, 34]
["10010011001", 1177, 89]
["10010111011", 1211, 89]
["10011000110", 1222, 55]
["10011001001", 1225, 89]
["10011100101", 1253, 89]
["10011110000", 1264, 13]
["10011110001", 1265, 55]
["10100000000", 1280, 3]
["10100010111", 1303, 89]
["10100111001", 1337, 89]
["10101000000", 1344, 8]
["10101010000", 1360, 21]
["10101010100", 1364, 55]
["10101010101", 1365, 144]
["10101010110", 1366, 89]
["10101011000", 1368, 34]
["10101100000", 1376, 13]
["10110000000", 1408, 5]
["10110100010", 1442, 55]
["10111001110", 1486, 55]
["10111011100", 1500, 34]
["10111111000", 1528, 13]
["11000000000", 1536, 2]
["11000001000", 1544, 13]
["11000100100", 1572, 34]
["11000110010", 1586, 55]
["11001011110", 1630, 55]
["11010000000", 1664, 5]
["11010100000", 1696, 13]
["11010101000", 1704, 34]
["11010101010", 1706, 89]
["11010101011", 1707, 144]
["11010101100", 1708, 55]
["11010110000", 1712, 21]
["11011000000", 1728, 8]
["11011000111", 1735, 89]
["11011101001", 1769, 89]
["11100000000", 1792, 3]
["11100001111", 1807, 55]
["11100010000", 1808, 13]
["11100011011", 1819, 89]
["11100110111", 1847, 89]
["11100111010", 1850, 55]
["11101000101", 1861, 89]
["11101100111", 1895, 89]
["11101110100", 1908, 34]
["11110000100", 1924, 21]
["11110000111", 1927, 55]
["11110010000", 1936, 13]
["11110100110", 1958, 55]
["11110111111", 1983, 34]
["11111000000", 1984, 5]
["11111000100", 1988, 21]
["11111101000", 2024, 13]
["11111101111", 2031, 34]
["11111111000", 2040, 8]
["100000000000", 2048, 1]
[0, 1, 1, 2, 1, 3, 2, 3, 1, 3, 5, 2, 5, 3, 1, 5, 3, 8, 5, 2, 5, 8, 3, 5, 1, 5, 3, 8, 13, 5, 2, 5, 13, 8, 3, 5, 1, 5, 13, 13, 3, 8, 21, 13, 5, 2, 5, 13, 21, 8, 3, 13, 13, 5, 1, 8, 13, 5, 13, 13, 3, 8, 21, 34, 13, 5, 13, 2, 13, 5, 13, 34, 21, 8, 3, 13, 13, 5, 13, 8, 1, 8, 13, 21, 5, 13, 21, 34, 13, 3, 8, 21, 55, 34, 13, 5, 34, 13, 2, 13, 34, 5, 13, 34, 55, 21, 8, 3, 13, 34, 21, 13, 5, 21, 13, 8, 1, 8, 13, 21, 5, 55, 13, 21, 34, 55, 13, 3, 8, 21, 55, 89, 34, 13, 5, 55, 55, 34, 13, 2, 13, 34, 55, 55, 5, 13, 34, 89, 55, 21, 8, 3, 13, 55, 34, 21, 13, 55, 5, 21, 13, 8, 1, 8, 34, 13, 21, 5, 34, 55, 13, 55, 21, 34, 89, 89, 55, 89, 89, 13, 55, 3, 89, 89, 8, 21, 55, 144, 89, 34, 13, 5, 55, 55, 34, 13, 2, 13, 34, 55, 55, 5, 13, 34, 89, 144, 55, 21, 8, 89, 89, 3, 55, 13, 89, 89, 55, 89, 89, 34, 21, 55, 13, 55, 34, 5, 21, 13, 34, 8, 1]