150719(2)

Ruby


Aliquot sequence(2)

もう少し調べてみた。

（実行時間は30分ほどかかる。）

require 'prime'

def power(a, n)

  return 1 if n == 0

  k = power(a, n >> 1)

  k *= k

  return k if n & 1 == 0

  return k * a

end

def sigma(i)

  sum = 1

  pq = i.prime_division

  pq.each{|a, n| sum *= (power(a, n + 1) - 1) / (a - 1)}

  sum

end

def aliquot(i)

  # Lehmer Five がらみは調べない

  return '?' if [276, 306, 396, 552, 564, 660, 696, 780, 828, 888, 966, 996].include?(i)

  # iが840のときは http://www.aliquot.de/sequenzen/840.elf を見た方がいい

  return 'Hard!' if i == 840

  a_ary = []

  j = sigma(i) - i

  while !a_ary.include?(j) && !(j == 0)

    a_ary.push(j)

    j = sigma(j) - j

  end

  return a_ary.size if a_ary.include?(i) || j == 0

  return a_ary.size + 1

end

p (1..1000).map{|i| aliquot(i)}

出力結果

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

, 1, 1, 14, 1, 2, 5, 7, 2, 3, 1, 6, 2, 3, 1, 13, 1, 4, 6, 7, 1, 5, 3, 2, 3, 8, 1

, 12, 2, 4, 2, 3, 1, 10, 1, 8, 2, 3, 2, 11, 1, 4, 3, 5, 1, 8, 1, 4, 4, 4, 2, 10,

 1, 6, 4, 5, 1, 5, 2, 8, 6, 6, 1, 9, 3, 5, 3, 3, 3, 8, 1, 2, 3, 4, 1, 17, 1, 6,

7, 5, 1, 9, 1, 6, 2, 8, 1, 16, 2, 4, 3, 9, 3, 11, 7, 4, 7, 5, 2, 15, 1, 2, 2, 5,

 1, 10, 3, 6, 8, 7, 1, 177, 1, 4, 4, 5, 3, 8, 3, 5, 5, 10, 1, 176, 1, 11, 5, 7,

2, 7, 1, 6, 3, 10, 2, 3, 1, 6, 8, 9, 1, 174, 5, 8, 2, 8, 1, 15, 2, 4, 3, 6, 1, 5

1, 1, 8, 3, 5, 2, 14, 2, 11, 2, 9, 1, 12, 1, 5, 5, 3, 1, 13, 1, 3, 2, 7, 2, 9, 2

, 6, 8, 6, 2, 51, 1, 10, 5, 7, 4, 9, 3, 9, 3, 2, 2, 175, 1, 16, 7, 5, 1, 7, 1, 8

, 6, 10, 1, 174, 2, 6, 2, 6, 1, 10, 1, 2, 8, 10, 2, 14, 6, 11, 7, 10, 1, 16, 3,

6, 4, 5, 1, 13, 7, 10, 3, 7, 1, 30, 2, 8, 4, 7, 1, 12, 1, 11, 3, 5, 2, "?", 1, 6

, 2, 15, 1, 16, 1, 2, 6, 10, 4, 9, 4, 11, 2, 6, 1, 15, 3, 6, 4, 12, 2, 8, 4, 8,

8, 12, 2, "?", 1, 12, 2, 9, 1, 173, 1, 11, 3, 11, 1, 34, 2, 13, 3, 7, 2, 2, 2, 1

0, 2, 9, 3, 33, 1, 6, 3, 9, 2, 13, 1, 2, 4, 9, 2, 13, 3, 12, 7, 5, 1, 15, 1, 5,

3, 11, 1, 51, 3, 6, 4, 9, 1, 29, 7, 6, 6, 11, 2, 50, 1, 14, 4, 12, 2, 12, 1, 6,

8, 13, 2, 49, 1, 12, 2, 6, 1, 8, 2, 4, 3, 13, 1, 14, 2, 2, 9, 4, 3, "?", 1, 8, 2

, 10, 1, 14, 7, 10, 4, 12, 4, 27, 1, 6, 5, 12, 2, 13, 2, 8, 4, 9, 1, 10, 1, 8, 3

, 5, 4, 13, 4, 10, 9, 7, 1, 4, 1, 10, 7, 10, 2, 12, 1, 14, 9, 12, 1, 15, 4, 6, 6

, 8, 1, 11, 2, 6, 3, 9, 4, 29, 1, 11, 4, 11, 1, 13, 1, 8, 9, 7, 1, 14, 5, 5, 3,

11, 3, 16, 4, 15, 8, 3, 1, 65, 4, 11, 7, 7, 2, 15, 1, 13, 2, 9, 1, 14, 2, 6, 10,

 1, 2, 33, 1, 9, 3, 7, 1, 9, 2, 10, 8, 14, 1, 32, 5, 6, 5, 11, 2, 13, 2, 5, 4, 2

5, 1, 12, 1, 11, 2, 9, 4, 172, 5, 13, 8, 14, 3, 32, 2, 8, 4, 12, 4, 22, 1, 6, 3,

 11, 3, 31, 1, 10, 2, 12, 4, "?", 7, 16, 5, 6, 1, 13, 3, 17, 9, 3, 1, "?", 4, 11

, 2, 7, 1, 172, 1, 13, 6, 11, 6, 6, 1, 4, 2, 21, 4, 48, 3, 10, 9, 7, 1, 13, 4, 1

0, 3, 8, 1, 47, 2, 10, 3, 7, 1, 69, 1, 10, 2, 12, 2, 14, 1, 3, 4, 11, 2, 46, 1,

10, 10, 10, 1, 13, 1, 14, 5, 12, 2, 18, 8, 12, 4, 4, 3, 12, 1, 8, 5, 14, 4, 7, 3

, 13, 5, 13, 1, 30, 1, 16, 6, 11, 1, 11, 2, 3, 2, 2, 1, 29, 2, 12, 3, 7, 1, "?",

 1, 10, 8, 11, 4, 28, 2, 15, 2, 17, 2, 26, 1, 10, 5, 3, 1, 13, 8, 20, 7, 6, 1, 1

3, 4, 12, 2, 4, 2, 12, 1, 10, 6, 6, 4, "?", 2, 12, 3, 15, 1, 300, 3, 10, 7, 7, 2

, 16, 1, 8, 4, 14, 3, 10, 2, 12, 9, 7, 1, 194, 3, 2, 3, 13, 3, 172, 1, 18, 12, 1

1, 2, 21, 1, 13, 6, 8, 2, 4, 1, 24, 2, 17, 1, 28, 3, 14, 8, 23, 3, 30, 1, 9, 5,

11, 2, 20, 1, 7, 10, 19, 1, 8, 4, 22, 6, 5, 2, 22, 1, 13, 4, 8, 1, 7, 4, 7, 2, 3

, 2, "?", 2, 12, 5, 2, 2, 31, 1, 8, 5, 4, 8, 17, 5, 11, 4, 13, 1, 30, 3, 2, 5, 1

1, 3, 25, 2, 13, 4, 3, 1, 28, 1, 11, 3, 17, 6, 27, 3, 13, 4, 9, 1, 48, 1, 9, 9,

11, 1, "?", 1, 7, 2, 15, 2, 47, 2, 15, 2, 9, 1, "Hard!", 15, 6, 7, 14, 4, 46, 4,

 12, 5, 10, 2, 20, 1, 15, 8, 23, 1, 167, 1, 17, 8, 11, 1, 59, 2, 11, 8, 10, 4, 1

71, 5, 4, 2, 12, 2, 6, 1, 13, 5, 11, 1, 6, 1, 12, 6, 7, 1, "?", 9, 12, 10, 4, 2,

 14, 3, 15, 7, 7, 2, 3, 2, 12, 3, 14, 3, 13, 1, 5, 5, 19, 1, 4, 4, 12, 7, 7, 2,

12, 1, 21, 2, 9, 3, 9, 4, 8, 5, 16, 1, 45, 3, 8, 4, 6, 8, 184, 1, 7, 2, 19, 1, 6

, 3, 8, 3, 14, 1, 19, 7, 20, 4, 17, 1, 5, 2, 14, 8, 12, 4, 171, 3, 15, 10, 12, 2

, "?", 1, 5, 4, 12, 1, 15, 6, 10, 2, 15, 1, 299, 2, 9, 2, 7, 1, 17, 3, 15, 3, 16

, 2, 298, 1, 8, 3, 14, 3, "?", 1, 8, 2, 17]