Hamming number

Hamming numbers - Rosetta Code から
素因数分解した形が 2^i 3^j 5^k になる数をハミング数というらしい。ただし i, j, k >= 0

Haskell のコードを引用する。

Haskell

hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*) hamming
     where merge (x:xs) (y:ys)
            | x < y = x : xs `merge` (y:ys)
            | x > y = y : (x:xs) `merge` ys
            | otherwise = x : xs `merge` ys
 
main = do
    print $ take 20 hamming
    print $ hamming !! 1690
    print $ hamming !! 999999

多分 Regular number - Wikipedia のアルゴリズムをそのまま実装するとこうなる。*1

• ハミング数は 1 から始まる
• 残りの数はハミング数を 2倍、3倍、5倍したものである
• ハミング数の並びは 2倍、3倍、5倍した数をマージしたものである

今回も Groovy に直訳しようとしたが再帰できるリストが実装できなかった。
残念ながら理解が足りていないのだろう。
イメージとしては次のようになる。

      5
      4
      3
      2
      1
      -->| output
merge |<--
      2,3,5
      4,6,10
      6,9,15

今までみた無限リストと違い、ぐるぐる回っている。
output を 2倍、3倍、5倍して merge してまた output する。

take 3 [1..]                          -- ずっと続くイメージ
let xs = 1:map (+1) xs in take 3 xs   -- 回っているイメージ

直訳できなかったので『C言語による最新アルゴリズム事典』を Groovy に書き換えたものを

def hamming(N) {
  def q = []
  def j2 = j3 = j5 = 0
  def x2 = x3 = x5 = 1G
  for (i = 0; i < N; i++) {
    q[i] = [x2,x3,x5].min()
    while (x2 <= q[i]) x2 = 2 * q[j2++]
    while (x3 <= q[i]) x3 = 3 * q[j3++]
    while (x5 <= q[i]) x5 = 5 * q[j5++]
  }
  q
}
assert hamming(20) == [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]
assert hamming(1691).last() == 2125764000G
assert hamming(1000000).last() == 519312780448388736089589843750000000000000000000000000000000000000000000000000000000G

Scala のコードを引用する。

Scala

class Hamming extends Iterator[BigInt] {
  import scala.collection.mutable.Queue
  val q2 = new Queue[BigInt]
  val q3 = new Queue[BigInt]
  val q5 = new Queue[BigInt]
  def enqueue(n: BigInt) = {
    q2 enqueue n * 2
    q3 enqueue n * 3
    q5 enqueue n * 5
  }
  def next = {
    val n = q2.head min q3.head min q5.head
    if (q2.head == n) q2.dequeue
    if (q3.head == n) q3.dequeue
    if (q5.head == n) q5.dequeue
    enqueue(n)
    n
  }
  def hasNext = true
  List(q2, q3, q5) foreach (_ enqueue 1)
}

q を Queue に置き換えた感じ。

Python の実装は Cyclic Iterator と書かれていた。
詳しくないので分からないが yield があれば回るリストを実装できるのかな?

*1:意訳