151227(6)

Ruby


Stern's diatomic series(3)

a(2n) = a(n), a(2n + 1) = a(n) + a(n + 1)
という性質を用いて、行列計算で求めてみた。
オンライン整数列大辞典の
A002487（http://oeis.org/A002487/list）
と比較し、答え合わせしてみる。

require 'matrix'

def f(n)
  return 0 if n == 0
  m = Matrix[[1, 0]]
  m0 = Matrix[[1, 0], [1, 1]]
  m1 = Matrix[[1, 1], [0, 1]]
  n.to_s(2).reverse[0..-2].split('').each{|i| i == '0' ? m *= m0 : m *= m1}
  (m * Vector.elements([1, 1]))[0]
end

def A002487(n)
  (0..n).map{|i| f(i)}
end
ary = A002487(91)

# OEIS A002487のデータ
ary0 =
[0,1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,3,8,5,7,
 2,7,5,8,3,7,4,5,1,6,5,9,4,11,7,10,3,11,8,13,5,12,
 7,9,2,9,7,12,5,13,8,11,3,10,7,11,4,9,5,6,1,7,6,11,
 5,14,9,13,4,15,11,18,7,17,10,13,3,14,11,19,8,21,
 13,18,5,17,12,19]
# 一致の確認
p ary == ary0

151227(5)

Ruby

Stern's diatomic series(2)

第10 ** i 項を求めてみた。

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

N = 8
ary = A002487(10 ** N)
(0..N).each{|i| p ary[10 ** i]}

出力結果
1
3
7
11
43
127
191
1249
897

151227(4)

Ruby

Stern's diatomic series(1)

a(2n) = a(n), a(2n + 1) = a(n) + a(n + 1)
という性質があるが、
a(n + 1) = a(n) + a(n - 1) - 2(a(n - 1) mod a(n))
を使って求めてみた。
オンライン整数列大辞典の
A002487（http://oeis.org/A002487/list）
と比較し、答え合わせしてみる。

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
ary = A002487(91)

# OEIS A002487のデータ
ary0 =
[0,1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,3,8,5,7,
 2,7,5,8,3,7,4,5,1,6,5,9,4,11,7,10,3,11,8,13,5,12,
 7,9,2,9,7,12,5,13,8,11,3,10,7,11,4,9,5,6,1,7,6,11,
 5,14,9,13,4,15,11,18,7,17,10,13,3,14,11,19,8,21,
 13,18,5,17,12,19]
# 一致の確認
p ary == ary0

151227(3)

Ruby

Calkin–Wilf sequence

見やすくするために、Calkin–Wilf tree における深さごとに出力してみた。

def f(n)
  1 / (2 * n.to_i - n + 1)
end

# depth = nまで出力
def calkin_wilf(n)
  p [m = 1.to_r]
  (1..n).each{|i| p (1..2 ** i).map{m = f(m)}}
end

calkin_wilf(10)

出力結果
[(1/1)]
[(1/2), (2/1)]
[(1/3), (3/2), (2/3), (3/1)]
[(1/4), (4/3), (3/5), (5/2), (2/5), (5/3), (3/4), (4/1)]
[(1/5), (5/4), (4/7), (7/3), (3/8), (8/5), (5/7), (7/2), (2/7), (7/5), (5/8), (8/3), (3/7), (7/4), (4/5), (5/1)]
[(1/6), (6/5), (5/9), (9/4), (4/11), (11/7), (7/10), (10/3), (3/11), (11/8), (8/13), (13/5), (5/12), (12/7), (7/9), (9/2), (2/9), (9/7), (7/12), (12/5), (5/13), (13/8), (8/11), (11/3), (3/10), (10/7), (7/11), (11/4), (4/9), (9/5), (5/6), (6/1)]
[(1/7), (7/6), (6/11), (11/5), (5/14), (14/9), (9/13), (13/4), (4/15), (15/11), (11/18), (18/7), (7/17), (17/10), (10/13), (13/3), (3/14), (14/11), (11/19), (19/8), (8/21), (21/13), (13/18), (18/5), (5/17), (17/12), (12/19), (19/7), (7/16), (16/9), (9/11), (11/2), (2/11), (11/9), (9/16), (16/7), (7/19), (19/12), (12/17), (17/5), (5/18), (18/13), (13/21), (21/8), (8/19), (19/11), (11/14), (14/3), (3/13), (13/10), (10/17), (17/7), (7/18), (18/11), (11/15), (15/4), (4/13), (13/9), (9/14), (14/5), (5/11), (11/6), (6/7), (7/1)]
[(1/8), (8/7), (7/13), (13/6), (6/17), (17/11), (11/16), (16/5), (5/19), (19/14), (14/23), (23/9), (9/22), (22/13), (13/17), (17/4), (4/19), (19/15), (15/26), (26/11), (11/29), (29/18), (18/25), (25/7), (7/24), (24/17), (17/27), (27/10), (10/23), (23/13), (13/16), (16/3), (3/17), (17/14), (14/25), (25/11), (11/30), (30/19), (19/27), (27/8), (8/29), (29/21), (21/34), (34/13), (13/31), (31/18), (18/23), (23/5), (5/22), (22/17), (17/29), (29/12), (12/31), (31/19), (19/26), (26/7), (7/23), (23/16), (16/25), (25/9), (9/20), (20/11), (11/13), (13/2), (2/13), (13/11), (11/20), (20/9), (9/25), (25/16), (16/23), (23/7), (7/26), (26/19), (19/31), (31/12), (12/29), (29/17), (17/22), (22/5), (5/23), (23/18), (18/31), (31/13), (13/34), (34/21), (21/29), (29/8), (8/27), (27/19), (19/30), (30/11), (11/25), (25/14), (14/17), (17/3), (3/16), (16/13), (13/23), (23/10), (10/27), (27/17), (17/24), (24/7), (7/25), (25/18), (18/29), (29/11), (11/26), (26/15), (15/19), (19/4), (4/17), (17/13), (13/22), (22/9), (9/23), (23/14), (14/19), (19/5), (5/16), (16/11), (11/17), (17/6), (6/13), (13/7), (7/8), (8/1)]
[(1/9), (9/8), (8/15), (15/7), (7/20), (20/13), (13/19), (19/6), (6/23), (23/17), (17/28), (28/11), (11/27), (27/16), (16/21), (21/5), (5/24), (24/19), (19/33), (33/14), (14/37), (37/23), (23/32), (32/9), (9/31), (31/22), (22/35), (35/13), (13/30), (30/17), (17/21), (21/4), (4/23), (23/19), (19/34), (34/15), (15/41), (41/26), (26/37), (37/11), (11/40), (40/29), (29/47), (47/18), (18/43), (43/25), (25/32), (32/7), (7/31), (31/24), (24/41), (41/17), (17/44), (44/27), (27/37), (37/10), (10/33), (33/23), (23/36), (36/13), (13/29), (29/16), (16/19), (19/3), (3/20), (20/17), (17/31), (31/14), (14/39), (39/25), (25/36), (36/11), (11/41), (41/30), (30/49), (49/19), (19/46), (46/27), (27/35), (35/8), (8/37), (37/29), (29/50), (50/21), (21/55), (55/34), (34/47), (47/13), (13/44), (44/31), (31/49), (49/18), (18/41), (41/23), (23/28), (28/5), (5/27), (27/22), (22/39), (39/17), (17/46), (46/29), (29/41), (41/12), (12/43), (43/31), (31/50), (50/19), (19/45), (45/26), (26/33), (33/7), (7/30), (30/23), (23/39), (39/16), (16/41), (41/25), (25/34), (34/9), (9/29), (29/20), (20/31), (31/11), (11/24), (24/13), (13/15), (15/2), (2/15), (15/13), (13/24), (24/11), (11/31), (31/20), (20/29), (29/9), (9/34), (34/25), (25/41), (41/16), (16/39), (39/23), (23/30), (30/7), (7/33), (33/26), (26/45), (45/19), (19/50), (50/31), (31/43), (43/12), (12/41), (41/29), (29/46), (46/17), (17/39), (39/22), (22/27), (27/5), (5/28), (28/23), (23/41), (41/18), (18/49), (49/31), (31/44), (44/13), (13/47), (47/34), (34/55), (55/21), (21/50), (50/29), (29/37), (37/8), (8/35), (35/27), (27/46), (46/19), (19/49), (49/30), (30/41), (41/11), (11/36), (36/25), (25/39), (39/14), (14/31), (31/17), (17/20), (20/3), (3/19), (19/16), (16/29), (29/13), (13/36), (36/23), (23/33), (33/10), (10/37), (37/27), (27/44), (44/17), (17/41), (41/24), (24/31), (31/7), (7/32), (32/25), (25/43), (43/18), (18/47), (47/29), (29/40), (40/11), (11/37), (37/26), (26/41), (41/15), (15/34), (34/19), (19/23), (23/4), (4/21), (21/17), (17/30), (30/13), (13/35), (35/22), (22/31), (31/9), (9/32), (32/23), (23/37), (37/14), (14/33), (33/19), (19/24), (24/5), (5/21), (21/16), (16/27), (27/11), (11/28), (28/17), (17/23), (23/6), (6/19), (19/13), (13/20), (20/7), (7/15), (15/8), (8/9), (9/1)]
[(1/10), (10/9), (9/17), (17/8), (8/23), (23/15), (15/22), (22/7), (7/27), (27/20), (20/33), (33/13), (13/32), (32/19), (19/25), (25/6), (6/29), (29/23), (23/40), (40/17), (17/45), (45/28), (28/39), (39/11), (11/38), (38/27), (27/43), (43/16), (16/37), (37/21), (21/26), (26/5), (5/29), (29/24), (24/43), (43/19), (19/52), (52/33), (33/47), (47/14), (14/51), (51/37), (37/60), (60/23), (23/55), (55/32), (32/41), (41/9), (9/40), (40/31), (31/53), (53/22), (22/57), (57/35), (35/48), (48/13), (13/43), (43/30), (30/47), (47/17), (17/38), (38/21), (21/25), (25/4), (4/27), (27/23), (23/42), (42/19), (19/53), (53/34), (34/49), (49/15), (15/56), (56/41), (41/67), (67/26), (26/63), (63/37), (37/48), (48/11), (11/51), (51/40), (40/69), (69/29), (29/76), (76/47), (47/65), (65/18), (18/61), (61/43), (43/68), (68/25), (25/57), (57/32), (32/39), (39/7), (7/38), (38/31), (31/55), (55/24), (24/65), (65/41), (41/58), (58/17), (17/61), (61/44), (44/71), (71/27), (27/64), (64/37), (37/47), (47/10), (10/43), (43/33), (33/56), (56/23), (23/59), (59/36), (36/49), (49/13), (13/42), (42/29), (29/45), (45/16), (16/35), (35/19), (19/22), (22/3), (3/23), (23/20), (20/37), (37/17), (17/48), (48/31), (31/45), (45/14), (14/53), (53/39), (39/64), (64/25), (25/61), (61/36), (36/47), (47/11), (11/52), (52/41), (41/71), (71/30), (30/79), (79/49), (49/68), (68/19), (19/65), (65/46), (46/73), (73/27), (27/62), (62/35), (35/43), (43/8), (8/45), (45/37), (37/66), (66/29), (29/79), (79/50), (50/71), (71/21), (21/76), (76/55), (55/89), (89/34), (34/81), (81/47), (47/60), (60/13), (13/57), (57/44), (44/75), (75/31), (31/80), (80/49), (49/67), (67/18), (18/59), (59/41), (41/64), (64/23), (23/51), (51/28), (28/33), (33/5), (5/32), (32/27), (27/49), (49/22), (22/61), (61/39), (39/56), (56/17), (17/63), (63/46), (46/75), (75/29), (29/70), (70/41), (41/53), (53/12), (12/55), (55/43), (43/74), (74/31), (31/81), (81/50), (50/69), (69/19), (19/64), (64/45), (45/71), (71/26), (26/59), (59/33), (33/40), (40/7), (7/37), (37/30), (30/53), (53/23), (23/62), (62/39), (39/55), (55/16), (16/57), (57/41), (41/66), (66/25), (25/59), (59/34), (34/43), (43/9), (9/38), (38/29), (29/49), (49/20), (20/51), (51/31), (31/42), (42/11), (11/35), (35/24), (24/37), (37/13), (13/28), (28/15), (15/17), (17/2), (2/17), (17/15), (15/28), (28/13), (13/37), (37/24), (24/35), (35/11), (11/42), (42/31), (31/51), (51/20), (20/49), (49/29), (29/38), (38/9), (9/43), (43/34), (34/59), (59/25), (25/66), (66/41), (41/57), (57/16), (16/55), (55/39), (39/62), (62/23), (23/53), (53/30), (30/37), (37/7), (7/40), (40/33), (33/59), (59/26), (26/71), (71/45), (45/64), (64/19), (19/69), (69/50), (50/81), (81/31), (31/74), (74/43), (43/55), (55/12), (12/53), (53/41), (41/70), (70/29), (29/75), (75/46), (46/63), (63/17), (17/56), (56/39), (39/61), (61/22), (22/49), (49/27), (27/32), (32/5), (5/33), (33/28), (28/51), (51/23), (23/64), (64/41), (41/59), (59/18), (18/67), (67/49), (49/80), (80/31), (31/75), (75/44), (44/57), (57/13), (13/60), (60/47), (47/81), (81/34), (34/89), (89/55), (55/76), (76/21), (21/71), (71/50), (50/79), (79/29), (29/66), (66/37), (37/45), (45/8), (8/43), (43/35), (35/62), (62/27), (27/73), (73/46), (46/65), (65/19), (19/68), (68/49), (49/79), (79/30), (30/71), (71/41), (41/52), (52/11), (11/47), (47/36), (36/61), (61/25), (25/64), (64/39), (39/53), (53/14), (14/45), (45/31), (31/48), (48/17), (17/37), (37/20), (20/23), (23/3), (3/22), (22/19), (19/35), (35/16), (16/45), (45/29), (29/42), (42/13), (13/49), (49/36), (36/59), (59/23), (23/56), (56/33), (33/43), (43/10), (10/47), (47/37), (37/64), (64/27), (27/71), (71/44), (44/61), (61/17), (17/58), (58/41), (41/65), (65/24), (24/55), (55/31), (31/38), (38/7), (7/39), (39/32), (32/57), (57/25), (25/68), (68/43), (43/61), (61/18), (18/65), (65/47), (47/76), (76/29), (29/69), (69/40), (40/51), (51/11), (11/48), (48/37), (37/63), (63/26), (26/67), (67/41), (41/56), (56/15), (15/49), (49/34), (34/53), (53/19), (19/42), (42/23), (23/27), (27/4), (4/25), (25/21), (21/38), (38/17), (17/47), (47/30), (30/43), (43/13), (13/48), (48/35), (35/57), (57/22), (22/53), (53/31), (31/40), (40/9), (9/41), (41/32), (32/55), (55/23), (23/60), (60/37), (37/51), (51/14), (14/47), (47/33), (33/52), (52/19), (19/43), (43/24), (24/29), (29/5), (5/26), (26/21), (21/37), (37/16), (16/43), (43/27), (27/38), (38/11), (11/39), (39/28), (28/45), (45/17), (17/40), (40/23), (23/29), (29/6), (6/25), (25/19), (19/32), (32/13), (13/33), (33/20), (20/27), (27/7), (7/22), (22/15), (15/23), (23/8), (8/17), (17/9), (9/10), (10/1)]
[(1/11), (11/10), (10/19), (19/9), (9/26), (26/17), (17/25), (25/8), (8/31), (31/23), (23/38), (38/15), (15/37), (37/22), (22/29), (29/7), (7/34), (34/27), (27/47), (47/20), (20/53), (53/33), (33/46), (46/13), (13/45), (45/32), (32/51), (51/19), (19/44), (44/25), (25/31), (31/6), (6/35), (35/29), (29/52), (52/23), (23/63), (63/40), (40/57), (57/17), (17/62), (62/45), (45/73), (73/28), (28/67), (67/39), (39/50), (50/11), (11/49), (49/38), (38/65), (65/27), (27/70), (70/43), (43/59), (59/16), (16/53), (53/37), (37/58), (58/21), (21/47), (47/26), (26/31), (31/5), (5/34), (34/29), (29/53), (53/24), (24/67), (67/43), (43/62), (62/19), (19/71), (71/52), (52/85), (85/33), (33/80), (80/47), (47/61), (61/14), (14/65), (65/51), (51/88), (88/37), (37/97), (97/60), (60/83), (83/23), (23/78), (78/55), (55/87), (87/32), (32/73), (73/41), (41/50), (50/9), (9/49), (49/40), (40/71), (71/31), (31/84), (84/53), (53/75), (75/22), (22/79), (79/57), (57/92), (92/35), (35/83), (83/48), (48/61), (61/13), (13/56), (56/43), (43/73), (73/30), (30/77), (77/47), (47/64), (64/17), (17/55), (55/38), (38/59), (59/21), (21/46), (46/25), (25/29), (29/4), (4/31), (31/27), (27/50), (50/23), (23/65), (65/42), (42/61), (61/19), (19/72), (72/53), (53/87), (87/34), (34/83), (83/49), (49/64), (64/15), (15/71), (71/56), (56/97), (97/41), (41/108), (108/67), (67/93), (93/26), (26/89), (89/63), (63/100), (100/37), (37/85), (85/48), (48/59), (59/11), (11/62), (62/51), (51/91), (91/40), (40/109), (109/69), (69/98), (98/29), (29/105), (105/76), (76/123), (123/47), (47/112), (112/65), (65/83), (83/18), (18/79), (79/61), (61/104), (104/43), (43/111), (111/68), (68/93), (93/25), (25/82), (82/57), (57/89), (89/32), (32/71), (71/39), (39/46), (46/7), (7/45), (45/38), (38/69), (69/31), (31/86), (86/55), (55/79), (79/24), (24/89), (89/65), (65/106), (106/41), (41/99), (99/58), (58/75), (75/17), (17/78), (78/61), (61/105), (105/44), (44/115), (115/71), (71/98), (98/27), (27/91), (91/64), (64/101), (101/37), (37/84), (84/47), (47/57), (57/10), (10/53), (53/43), (43/76), (76/33), (33/89), (89/56), (56/79), (79/23), (23/82), (82/59), (59/95), (95/36), (36/85), (85/49), (49/62), (62/13), (13/55), (55/42), (42/71), (71/29), (29/74), (74/45), (45/61), (61/16), (16/51), (51/35), (35/54), (54/19), (19/41), (41/22), (22/25), (25/3), (3/26), (26/23), (23/43), (43/20), (20/57), (57/37), (37/54), (54/17), (17/65), (65/48), (48/79), (79/31), (31/76), (76/45), (45/59), (59/14), (14/67), (67/53), (53/92), (92/39), (39/103), (103/64), (64/89), (89/25), (25/86), (86/61), (61/97), (97/36), (36/83), (83/47), (47/58), (58/11), (11/63), (63/52), (52/93), (93/41), (41/112), (112/71), (71/101), (101/30), (30/109), (109/79), (79/128), (128/49), (49/117), (117/68), (68/87), (87/19), (19/84), (84/65), (65/111), (111/46), (46/119), (119/73), (73/100), (100/27), (27/89), (89/62), (62/97), (97/35), (35/78), (78/43), (43/51), (51/8), (8/53), (53/45), (45/82), (82/37), (37/103), (103/66), (66/95), (95/29), (29/108), (108/79), (79/129), (129/50), (50/121), (121/71), (71/92), (92/21), (21/97), (97/76), (76/131), (131/55), (55/144), (144/89), (89/123), (123/34), (34/115), (115/81), (81/128), (128/47), (47/107), (107/60), (60/73), (73/13), (13/70), (70/57), (57/101), (101/44), (44/119), (119/75), (75/106), (106/31), (31/111), (111/80), (80/129), (129/49), (49/116), (116/67), (67/85), (85/18), (18/77), (77/59), (59/100), (100/41), (41/105), (105/64), (64/87), (87/23), (23/74), (74/51), (51/79), (79/28), (28/61), (61/33), (33/38), (38/5), (5/37), (37/32), (32/59), (59/27), (27/76), (76/49), (49/71), (71/22), (22/83), (83/61), (61/100), (100/39), (39/95), (95/56), (56/73), (73/17), (17/80), (80/63), (63/109), (109/46), (46/121), (121/75), (75/104), (104/29), (29/99), (99/70), (70/111), (111/41), (41/94), (94/53), (53/65), (65/12), (12/67), (67/55), (55/98), (98/43), (43/117), (117/74), (74/105), (105/31), (31/112), (112/81), (81/131), (131/50), (50/119), (119/69), (69/88), (88/19), (19/83), (83/64), (64/109), (109/45), (45/116), (116/71), (71/97), (97/26), (26/85), (85/59), (59/92), (92/33), (33/73), (73/40), (40/47), (47/7), (7/44), (44/37), (37/67), (67/30), (30/83), (83/53), (53/76), (76/23), (23/85), (85/62), (62/101), (101/39), (39/94), (94/55), (55/71), (71/16), (16/73), (73/57), (57/98), (98/41), (41/107), (107/66), (66/91), (91/25), (25/84), (84/59), (59/93), (93/34), (34/77), (77/43), (43/52), (52/9), (9/47), (47/38), (38/67), (67/29), (29/78), (78/49), (49/69), (69/20), (20/71), (71/51), (51/82), (82/31), (31/73), (73/42), (42/53), (53/11), (11/46), (46/35), (35/59), (59/24), (24/61), (61/37), (37/50), (50/13), (13/41), (41/28), (28/43), (43/15), (15/32), (32/17), (17/19), (19/2), (2/19), (19/17), (17/32), (32/15), (15/43), (43/28), (28/41), (41/13), (13/50), (50/37), (37/61), (61/24), (24/59), (59/35), (35/46), (46/11), (11/53), (53/42), (42/73), (73/31), (31/82), (82/51), (51/71), (71/20), (20/69), (69/49), (49/78), (78/29), (29/67), (67/38), (38/47), (47/9), (9/52), (52/43), (43/77), (77/34), (34/93), (93/59), (59/84), (84/25), (25/91), (91/66), (66/107), (107/41), (41/98), (98/57), (57/73), (73/16), (16/71), (71/55), (55/94), (94/39), (39/101), (101/62), (62/85), (85/23), (23/76), (76/53), (53/83), (83/30), (30/67), (67/37), (37/44), (44/7), (7/47), (47/40), (40/73), (73/33), (33/92), (92/59), (59/85), (85/26), (26/97), (97/71), (71/116), (116/45), (45/109), (109/64), (64/83), (83/19), (19/88), (88/69), (69/119), (119/50), (50/131), (131/81), (81/112), (112/31), (31/105), (105/74), (74/117), (117/43), (43/98), (98/55), (55/67), (67/12), (12/65), (65/53), (53/94), (94/41), (41/111), (111/70), (70/99), (99/29), (29/104), (104/75), (75/121), (121/46), (46/109), (109/63), (63/80), (80/17), (17/73), (73/56), (56/95), (95/39), (39/100), (100/61), (61/83), (83/22), (22/71), (71/49), (49/76), (76/27), (27/59), (59/32), (32/37), (37/5), (5/38), (38/33), (33/61), (61/28), (28/79), (79/51), (51/74), (74/23), (23/87), (87/64), (64/105), (105/41), (41/100), (100/59), (59/77), (77/18), (18/85), (85/67), (67/116), (116/49), (49/129), (129/80), (80/111), (111/31), (31/106), (106/75), (75/119), (119/44), (44/101), (101/57), (57/70), (70/13), (13/73), (73/60), (60/107), (107/47), (47/128), (128/81), (81/115), (115/34), (34/123), (123/89), (89/144), (144/55), (55/131), (131/76), (76/97), (97/21), (21/92), (92/71), (71/121), (121/50), (50/129), (129/79), (79/108), (108/29), (29/95), (95/66), (66/103), (103/37), (37/82), (82/45), (45/53), (53/8), (8/51), (51/43), (43/78), (78/35), (35/97), (97/62), (62/89), (89/27), (27/100), (100/73), (73/119), (119/46), (46/111), (111/65), (65/84), (84/19), (19/87), (87/68), (68/117), (117/49), (49/128), (128/79), (79/109), (109/30), (30/101), (101/71), (71/112), (112/41), (41/93), (93/52), (52/63), (63/11), (11/58), (58/47), (47/83), (83/36), (36/97), (97/61), (61/86), (86/25), (25/89), (89/64), (64/103), (103/39), (39/92), (92/53), (53/67), (67/14), (14/59), (59/45), (45/76), (76/31), (31/79), (79/48), (48/65), (65/17), (17/54), (54/37), (37/57), (57/20), (20/43), (43/23), (23/26), (26/3), (3/25), (25/22), (22/41), (41/19), (19/54), (54/35), (35/51), (51/16), (16/61), (61/45), (45/74), (74/29), (29/71), (71/42), (42/55), (55/13), (13/62), (62/49), (49/85), (85/36), (36/95), (95/59), (59/82), (82/23), (23/79), (79/56), (56/89), (89/33), (33/76), (76/43), (43/53), (53/10), (10/57), (57/47), (47/84), (84/37), (37/101), (101/64), (64/91), (91/27), (27/98), (98/71), (71/115), (115/44), (44/105), (105/61), (61/78), (78/17), (17/75), (75/58), (58/99), (99/41), (41/106), (106/65), (65/89), (89/24), (24/79), (79/55), (55/86), (86/31), (31/69), (69/38), (38/45), (45/7), (7/46), (46/39), (39/71), (71/32), (32/89), (89/57), (57/82), (82/25), (25/93), (93/68), (68/111), (111/43), (43/104), (104/61), (61/79), (79/18), (18/83), (83/65), (65/112), (112/47), (47/123), (123/76), (76/105), (105/29), (29/98), (98/69), (69/109), (109/40), (40/91), (91/51), (51/62), (62/11), (11/59), (59/48), (48/85), (85/37), (37/100), (100/63), (63/89), (89/26), (26/93), (93/67), (67/108), (108/41), (41/97), (97/56), (56/71), (71/15), (15/64), (64/49), (49/83), (83/34), (34/87), (87/53), (53/72), (72/19), (19/61), (61/42), (42/65), (65/23), (23/50), (50/27), (27/31), (31/4), (4/29), (29/25), (25/46), (46/21), (21/59), (59/38), (38/55), (55/17), (17/64), (64/47), (47/77), (77/30), (30/73), (73/43), (43/56), (56/13), (13/61), (61/48), (48/83), (83/35), (35/92), (92/57), (57/79), (79/22), (22/75), (75/53), (53/84), (84/31), (31/71), (71/40), (40/49), (49/9), (9/50), (50/41), (41/73), (73/32), (32/87), (87/55), (55/78), (78/23), (23/83), (83/60), (60/97), (97/37), (37/88), (88/51), (51/65), (65/14), (14/61), (61/47), (47/80), (80/33), (33/85), (85/52), (52/71), (71/19), (19/62), (62/43), (43/67), (67/24), (24/53), (53/29), (29/34), (34/5), (5/31), (31/26), (26/47), (47/21), (21/58), (58/37), (37/53), (53/16), (16/59), (59/43), (43/70), (70/27), (27/65), (65/38), (38/49), (49/11), (11/50), (50/39), (39/67), (67/28), (28/73), (73/45), (45/62), (62/17), (17/57), (57/40), (40/63), (63/23), (23/52), (52/29), (29/35), (35/6), (6/31), (31/25), (25/44), (44/19), (19/51), (51/32), (32/45), (45/13), (13/46), (46/33), (33/53), (53/20), (20/47), (47/27), (27/34), (34/7), (7/29), (29/22), (22/37), (37/15), (15/38), (38/23), (23/31), (31/8), (8/25), (25/17), (17/26), (26/9), (9/19), (19/10), (10/11), (11/1)]

151227(2)

Ruby

離散力学系における軌道の計算(2)

分子について、オンライン整数列大辞典の
A079271（http://oeis.org/A079271/list）
と比較し、答え合わせしてみる。

def f(lambda, x)
  lambda * x * (1 - x)
end

def A079271(n)
  x = 1 / 3.to_r
  ([x] + (1..n).map{x = f(4, x)}).map{|i| i.numerator}
end
ary = A079271(7)

# OEIS A079271のデータ
ary0 =
[1,8,32,6272,7250432,1038154236987392,
 3383826162019367796397224108032,
 674838593766753484487654913831820720085359667709963001167872]
# 一致の確認
p ary == ary0

151227

Ruby

離散力学系における軌道の計算(1)

Rationalで計算すると大変なことになった。

def f(lambda, x)
  lambda * x * (1 - x)
end

N = 12
x = 1 / 3.to_r
p [x] + (1..N).map{x = f(4, x)}

出力結果
[(1/3), (8/9), (32/81), (6272/6561), (7250432/43046721), (1038154236987392/1853020188851841), (3383826162019367796397224108032/3433683820292512484657849089281), (674838593766753484487654913831820720085359667709963001167872/11790184577738583171520872861412518665678211592275841109096961), (30004257812217921448517555209678850165868237842249191697191933280958327232676392983676899191261907114558496045481444114432/139008452377144732764939786789661303114218850808529137991604824430036072629766435941001769154109609521811665540548899435521), (13082359825356910286492360061136736044180324498109817790128474991459314029228384187522308703184360391592495083267439167657929717062912601762329623472844083023729847910612245007924921595506191938616119697389548402100243733465436848681679275425792/19323349832288915105454068722019581055401465761603328550184537628902466746415537000017939429786029354390082329294586119505153509101332940884098040478728639542560550133727399482778062322407372338121043399668242276591791504658985882995272436541441), (326587507748564819526644454569376331474154420084818092745594332137561018974006085389560132992720304408663106445778503081330740875395946979612958407581856575179900521300573125323094574403291444363685870280626797364502957292617630209535691823652432585205978126151670505839933787574882669635101678944234697049051805139530490463071202426711136068343565226938926588080054391637396003154271711916707548475413061895252789685202028958639851477169623855847348893412975686499092668317042928917676032/373391848741020043532959754184866588225409776783734007750636931722079040617265251229993688938803977220468765065431475158108727054592160858581351336982809187314191748594262580938807019951956404285571818041046681288797402925517668012340617298396574731619152386723046235125934896058590588284654793540505936202376547807442730582144527058988756251452817793413352141920744623027518729185432862375737063985485319476416926263819972887006907013899256524297198527698749274196276811060702333710356481), (61142852306159761941719350858894288745543170044146323109689703291980924851796533997103855261908015575214297660329162668746580929102334010791256690499085996667702727608110600383881916661175401025841128350218665654536958173329093283646444406916989702358602504498990873573726862396234275982132488343451071715679594802189481207543737898095804664205350986023945673496564730371922126707688091178762709213338405622273864048733071827025714877491861045148462685583532205278217127011376328565887694222960373626180059928802236919349419068041418998434116106220266700986879354395786476811458677962796732587694611828952750818857523063965617113143694838317807352194745983507768142547294302047316329224316725717274586072428240970325222521933525573197993768182995402639191191324453820256624497823309547681905713129756569529235933403577032995411915451001642656423046719386092362811348998437241697365079123990708487380245174236936757338067180490209172293310254419238315917518121075773796329193472/139421472706236791468735287967015707232606232113998186759762284283203248267399327423485002476018294548027207658124580006956269122224761375615358997681237349433785401584729106693395255281491169142017082115307947771801954704567433211464560639140944673635364155016693389201613594038984686916178623702578352190636251776039742101384851474311083735102877993131212196962695464654469816719202970619252343026646014132485548307935847260900441555694943498191955672798596377459777392636575523873495086339994375985976543710570091438233257228420529594557457359609723639787519567621434999954843382100489400924995961904023259324301047965917783124275162880514542735528152228927483841372844810255470399471841348890379437250393401562476664019972812975660227449988177768002661436897984534184331079950399306756818061310948084534985374661203278436590349231431071569402389429768922180485838968764968523571261288038064310442585283933256404572748606640151307376800250725427496845607662821346676098703361), (19144712503407417567135059100458633701667309261608387794719701072085835139938108421290218174975016215714657693126232069759616256865782480902558184057624088768345367248914677728705523334349125924209805233089412155636967764580681507466229285675684099954946152999752510440892216943190218741400027174833668946677071863297897335955473049439573127667920418447654975692709588701834242287351039317582220066092409167756751240609167198807693453352489167398606261406447370695057064406265179059513400881523612801573817543697395645633573279331847873608996935144861669021453741792200011206868696965367089813764169742463266525029607727867386150092729846004573907465251484405890652377201376321459395896086671591945559497982887561609777822082124699779405715974263703118531857016577898505897381283351314353641134506307788914991746931629670739943951673167167541172574300926553165662576893798902217928419118126936416968892344654164860264317127874477993584853836862183965649667474310078569520451512245499722386379798234696618124800502349263039691768845705811932926646241786271093837316572273943077542327574039330422577103805612624251155221033086217586676029341508566076392648196659837797500695724040328070035578093492366392131689417025783967158724647867285956529352351500875068181118448882580408080438771351439926396969467728612146280442475235449540289675384105398167854906540445142977318423987318135885441075818173283389942560829552740288844103803489518606303098944536131089369039738367199369084865077552110767959726272052448395432901848203746166527324536275834701908222021024521049717000965869513618332488406972145618119726265214858358022562966536680948229538149778771163307213368496392381156029814746882202626326165357558439353593699685923189241967919428162720017105704489398074777319153750232775130376714213645787326097409226746826821996050111345129518976879954712719532335918095906765322748778286763898574001993813959499148858315486192477572653260400061077728656392978432/19438347051575930593026637277464327123266958586038369937823081254224453278630252497889372715554605593282381159872094158595095268067402968819922058060551822238741112165184374168564842547377441712304718992557393039038068650790181662446618501807237815659967187794033032803500035732383779283962952457019941126317411288547298348393098492554260561270997109425187315296683000918052454625638849801275961486965984453943973091802013130902022480064009582344873235465674303023321390779804986857735192246409512396859725643331241004565363356447570421115052411463010710895821609990116581002342162299225771869569017520145772647959223587680923278063396420933182948493511315641718579755044437441435175740859842860053607410165012361020931202956648767463066402467873454067221827562969068586208309387212456515799198207666199100272945024205012536374239885475968620882340375145207974046250462049126376560527290449130131440049788901462599304866873205740965010110139132541314345764876189581440737408106418855697237772150397259001202610130643763522631178062380060118593870971595168515254708733434522944375449004769094553723966227387818112951763132792281368178696361699983006097111869296586184614483820710005212223076649640648680453168817055219121408137639068898013300964241873653031196757067256269494984584288619038952494840890585035037799939467208769356259970350911013289050848552248531637772378630974861351496031252497009626563341895925393417896721361397607975167965296260228765252019053692679530118811766299692563834399397255178641804981662398606198713407736666476041324967934194436339007404569332651584643092199985299610486183872564728311389752139542321950489431449936370044181920096335116574849401654651260886859807973366610174486966928282281448812271499242148110214706385942214916820701400716027195159400919830048720354640368632751312692913386133718693853550810552709435439109936878872272169754302271563047123599935593148473062504803871685643230134991892294944498425472696321)]

151226

Ruby

フィボナッチ数列、トリボナッチ数列、テトラナッチ数列、…(2)

行列計算で第10 ** i 項の下20桁を求めてみた。

require 'matrix'

def power(a, n, mod)
  return Matrix.I(a.row_size) if n == 0
  m = power(a, n >> 1, mod)
  m = (m * m).map{|i| i % mod}
  return m if n & 1 == 0
  (m * a).map{|i| i % mod}
end

def f(m, n)
  ary0 = Array.new(m, 0)
  ary0[0] = 1
  v = Vector.elements(ary0)
  ary1 = [Array.new(m, 1)]
  (0..m - 2).each{|i|
    ary2 = Array.new(m, 0)
    ary2[i] = 1
    ary1 << ary2
  }
  # 配列を引数に展開
  a = Matrix[*ary1]
  mod = 10 ** 20
  # power(a, n, mod) * vの成分はmod未満
  (power(a, n, mod) * v)[m - 1]
end

(2..9).each{|m|
  p [m, (0..10).map{|i| f(m, 10 ** i)}]
}

出力結果
[2, [1, 55, 54224848179261915075, 76137795166849228875, 66073310059947366875, 49895374653428746875, 68996526838242546875, 86998673686380546875, 6082642167760546875, 3172326981560546875, 99069175119560546875]]
[3, [0, 81, 62928098149064722658, 10783789625725711384, 84855239178776081984, 45590351831757462976, 87395036595190865536, 36466221250542429440, 95160048182486712832, 88871128684941792256, 56893269687011067904]]
[4, [0, 56, 97838180985096739296, 84465668382508012160, 72950854709025441792, 96451003184390892544, 8740034747828348928, 32803712350556868608, 84027725612141256704, 74152605583824732160, 50331276893492641792]]
[5, [0, 31, 38261258264777004033, 94147780942189200385, 22299037799913441025, 71762521041589169921, 38967967351782360833, 9226043430064117505, 68633832057834469121, 1772155374304605953, 82711718805648324353]]
[6, [0, 16, 17130007349662323904, 93240673228858160925, 88056360493937573376, 48812610302662993151, 4915217296395642996, 56390686729323541264, 27169437970338339728, 89068418041425978989, 15824280756705573376]]
[7, [0, 8, 76324494942045981696, 195920253480368658, 23778413061199575800, 44144174396274980576, 39905909105358155136, 73690200277951099392, 31576895769957220352, 80865343089788137472, 59806603832376205312]]
[8, [0, 4, 59172997404458625000, 1230887635364049824, 60556540444184606992, 10346590246637690992, 81836027114883468848, 29447872758524258224, 13483357678177838768, 93482707094876314800, 42525944029057284272]]
[9, [0, 2, 77799461090403757880, 65571732106893914592, 62937430511874341760, 54835914168209817088, 88530826807377868800, 11174062203432853504, 29289147652664426496, 7404157041260232704, 56925392030348607488]]

151224(2)

Ruby


Topswops(3)

1が一番上にくるまでの回数が最も多い並べ方を調べてみた。

def conway2(n)
  ary = []
  max = 0
  (1..n).to_a.permutation{|c|
    a = c.clone
    i = 0
    while (c0 = c[0]) > 1
      c[0..c0 - 1] = c[0..c0 - 1].reverse
      i += 1
    end
    if i > max
      ary = [a]
      max = i
    elsif i == max
      ary << a
    else
    end
  }
  [max, ary]
end

(1..11).each{|i| p conway2(i)}

出力結果
[0, [[1]]]
[1, [[2, 1]]]
[2, [[2, 3, 1], [3, 1, 2]]]
[4, [[2, 4, 1, 3], [3, 1, 4, 2]]]
[7, [[3, 1, 4, 5, 2]]]
[10, [[3, 6, 5, 1, 4, 2], [4, 1, 5, 2, 6, 3], [4, 1, 6, 5, 2, 3], [4, 5, 6, 2, 1, 3], [5, 6, 4, 1, 3, 2]]]
[16, [[3, 1, 4, 6, 7, 5, 2], [4, 7, 6, 2, 1, 5, 3]]]
[22, [[6, 1, 5, 7, 8, 3, 2, 4]]]
[30, [[6, 1, 5, 9, 7, 2, 8, 3, 4]]]
[38, [[5, 9, 1, 8, 6, 2, 10, 4, 7, 3]]]
[51, [[4, 9, 11, 6, 10, 7, 8, 2, 1, 3, 5]]]

151224

Ruby


Topswops(2)

1が一番上にくるまでの回数の分布を調べてみた。

def conway1(n)
  ary = []
  (1..n).to_a.permutation{|c|
    i = 0
    while (c0 = c[0]) > 1
      c[0..c0 - 1] = c[0..c0 - 1].reverse
      i += 1
    end
    ary[i] == nil ? ary[i] = 1 : ary[i] += 1
  }
  ary
end

(1..11).each{|i| p conway1(i)}

出力結果
[1]
[1, 1]
[2, 2, 2]
[6, 6, 6, 4, 2]
[24, 24, 24, 20, 14, 8, 5, 1]
[120, 120, 120, 104, 82, 60, 43, 34, 19, 13, 5]
[720, 720, 720, 648, 548, 440, 338, 268, 218, 160, 104, 65, 44, 26, 14, 5, 2]
[5040, 5040, 5040, 4608, 4020, 3360, 2750, 2324, 1943, 1607, 1274, 958, 726, 551, 409, 277, 182, 122, 61, 21, 4, 2, 1]
[40320, 40320, 40320, 37440, 33504, 28692, 24432, 21212, 18227, 15567, 13197, 10966, 9011, 7363, 5870, 4575, 3479, 2697, 2047, 1413, 948, 593, 333, 157, 87, 47, 31, 23, 6, 2, 1]
[362880, 362880, 362880, 339840, 308640, 271104, 236844, 208332, 182840, 160043, 139694, 120793, 104010, 89139, 75614, 63268, 52466, 43133, 35365, 28277, 21961, 17020, 12791, 9127, 6353, 4473, 3153, 2172, 1425, 900, 582, 369, 230, 117, 51, 22, 8, 3, 1]
[3628800, 3628800, 3628800, 3427200, 3153600, 2811600, 2500368, 2232276, 1988976, 1771746, 1575696, 1393265, 1226695, 1076080, 940355, 818482, 707501, 607993, 520100, 441353, 370227, 307401, 253430, 206784, 165950, 130999, 102035, 78913, 60141, 45064, 33614, 24828, 17835, 12622, 8961, 6203, 4214, 2819, 1871, 1231, 792, 503, 295, 168, 83, 50, 32, 25, 14, 5, 4, 1]

151223(4)

Ruby


Topswops(1)

すぐに求まる部分だけ求めてみた。

なお、オンライン整数列大辞典の
A000375（http://oeis.org/A000375/list）
にこの続きが載っている。

def conway(n)
  max = 0
  (1..n).to_a.permutation{|c|
    if c[0] > 1
      i = 0
      while (c0 = c[0]) > 1
        c[0..c0 - 1] = c[0..c0 - 1].reverse
        i += 1
      end
      max = i if i > max
    end
  }
  max
end

(1..11).each{|i| p conway(i)}

出力結果
0
1
2
4
7
10
16
22
30
38
51