150225

Ruby


Square-free integer

m未満のsquare-freeな整数の個数を出力するコードを書いてみた。

オンライン整数列大辞典の
A005117（http://oeis.org/A005117/list）

と比較し、答え合わせしてみる。

require 'prime'

N0 = 113

N  = 101

# m未満のsquare-freeな整数の個数

def number_of_squarefree_numbers(m , n = m)

  s = 0

  Prime.each{|x|

    break if x * x >= m || x >= n

    s += number_of_squarefree_numbers((m - 1) / (x * x) + 1, x)

  }

  return m - 1 - s

end

for i in (1..N)

  p [i, number_of_squarefree_numbers(i + 1, )]

end

# OEIS A005117との比較用

ary = []

fn = 0

for i in (1..N0)

  bn = number_of_squarefree_numbers(i + 1, )

  ary << i if fn != bn

  fn = bn

end

# OEIS A005117のデータ

ary0 =

[1,2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,

 30,31,33,34,35,37,38,39,41,42,43,46,47,51,53,55,

 57,58,59,61,62,65,66,67,69,70,71,73,74,77,78,79,

 82,83,85,86,87,89,91,93,94,95,97,101,102,103,105,

 106,107,109,110,111,113]

# 一致の確認

p ary == ary0