2^i * 3^j * 5^k なる整数 DouKaku?

2^i * 3^j * 5^k なる整数

2^i * 3^j * 5^k の形で表される整数を小さい方から順に 100 個列挙するプログラムを書いてください。 i, j, k は 0 以上の整数です。アルゴリズムのオーダーについても考えてみてください。

例えば最初の 10 個は次のようになります:

 1 = 2^0 * 3^0 * 5^0
 2 = 2^1 * 3^0 * 5^0
 3 = 2^0 * 3^1 * 5^0
 4 = 2^2 * 3^0 * 5^0
 5 = 2^0 * 3^0 * 5^1
 6 = 2^1 * 3^1 * 5^0
 8 = 2^3 * 3^0 * 5^0
 9 = 2^0 * 3^2 * 5^0
10 = 2^1 * 3^0 * 5^1
12 = 2^2 * 3^1 * 5^0

※解答では i, j, k の各値を示す必要はありません。

post comment

Posted feedbacks - Nested

Flatten Hidden

何も考えずに。

#include <stdio.h>

int main(){
    int m=1;
    int n=0;
    int i,j,k;
    int v;
    
    do{
        v=m;
        i=0;
        j=0;
        k=0;
        while(v%2==0)v/=2,i++;
        while(v%3==0)v/=3,j++;
        while(v%5==0)v/=5,k++;
        if(v==1){
            printf("%d = 2^%d * 3^%d * 5^%d\n",m,i,j,k);
            n++;
        }
        m++;
    }while(n<100);
    return 0;
}

よく考えたら2で割るのにループはいりませんね。
i,j,kも省いてこんな感じかな。

#include <stdio.h>

int main(){
    int m,n,v;
    
    for(n=0,m=1;n<100;m++){
        v=m/(m&-m);
        while(v%3==0)v/=3;
        while(v%5==0)v/=5;
        if(v==1){
            printf("%d\n",m);
            n++;
        }
    }
    return 0;
}

（雑談です）
この v=m/(m&-m) というのは私には逆立ちしても思いつきそうにないんですが、有名なテクニックなんですか？
いまだになぜ上手くいくのかよくわかってないけど、ビットを書き出してみると確かにそうなるぽいですが・・・教えてえらいひと

m&-mの部分は一応知られたコードのはずです。
下位ビットから見て最初に1になるビットを検出するというコードとして知ったと思います。(この数字の意味は今回はじめて気づきましたが^^;;)

-mって言うのはmと足したとき0になる数字ですので、2進表記した場合の下位ビットから見て最初に1が出て来る場所まではmと同じ、それ以上は反転となる数字です。
-m=~m+1でもありますね。
4ビットでの例：
2=0010
-2=1110

3=0011
-3=1101

ここでm&-mをとれば、下から見て一番最初の1のみが残ることがわかります。
証明：
m=1*A+2*B+4*C+8*Dとすると
~m=1*~A+2*~B+4*~C+8*~D

-m=~m+1=1*A'+2*B'+4*C'+8*D'とすると
ビット加算はsum=a^b,Carry=a&bなので
A'=~A^1 = A
B'=~B^(~A&1) = ~B^~A =B^C
C'=~C^(~B&(~A&1)) =~C^(~B&~A)=C^(B|A)
D'=~D^(~C&(~B&(~A&1))) = ~D^(~C&~B&~A)=D^(C|B|A)

m&-m=1*A''+2*B''+4*C''+8*D''

a&(a^b)=a&(a&~b|~a&b)=a&~bより

A''=A&A'=A
B''=B&B'=B&(B^A) = B&~A
C''=C&C'=C&(C^(B|A)) = C&~(B|A) = C&~B&~A
D''=D&D'=D&(D^(C|B|A))=D&~(C|B|A)=D&~C&~B&~A

下位ビットがすべて0のときのみビットがたつことがわかる。
～～証明ここまで

さて、2で割るということは2進数で考えれば、右シフトです。2で割った余りというのはm&1となるわけなので、最下位ビットが0なら2の倍数です。
ここから考えれば最下位ビットから見て0の数だけ2で割れるわけです。

つまり先ほど求めたm&-mというのは、設問で言う2^iとなっていることがわかると思います。

というのでどうでしょう？

解説ありがとうございます。何をやっているかがようやく理解できました。
（式変形はこれからじっくり解読しようと思います。。）

priority queue で。

#include <cstdio>
#include <queue>
using namespace std;

const int DNUM = 100;

int main(void)
{
    int pre = 0, i = 0;
    priority_queue<int, vector<int>, greater<int> > pq;
    pq.push(1);
    
    while(i < DNUM)
    {
        int a = pq.top();
        pq.pop();
        if(a == pre) continue;
        
        printf("%d\n", a);
        pq.push(a * 2);
        pq.push(a * 3);
        pq.push(a * 5);
        
        pre = a;
        i++;
    }
    
    return 0;
}

25までのものが出てくるようにDNUMを指定したときに16が出てくるのでしょうか？

(注：2 ^ 4 = 16, 5 ^ 2 = 25)

25までの数を表示するようにDNUMを指定すると、heapに入っている数はi + j + k <= 3を満たすものしかない気がします。しかし、16も指定の数です。

DNUM=16 としてみました。25 まで正しく列挙されているように思いますが…… http://codepad.org/QQfKglM7

勘違いです。失礼しました。 8が先にqueueから抜かれますね。orz

8を取り出したときに, 16, 24, 40が入れられるので, 25の前に16出ますよ.

あとこのアルゴリズムの正当性も証明できます. n (> 1) 回目が終わったとき出てなかったものの最小値をAとします. このAがn回目に出た数より小さいと仮定します. A = 2^i 3^j 5^kで, queのことを考えると, A/2またはA/3またはA/5のどれかも出ていません. なので最小性に反します. よって矛盾.

おなじアルゴリズムになってしまいました。
100個目は1536。

public class Int235 {
    public static void main(String[] a) {
        int limit = 100;
        for (int n = 0, i = 1; n < limit; i++) {
            int tmp = i;
            while (tmp % 2 == 0) tmp /= 2;
            while (tmp % 3 == 0) tmp /= 3;
            while (tmp % 5 == 0) tmp /= 5;
            if (tmp == 1) {
                System.out.println(i);
                n++;
            }
        }
    }
}

軽く候補の絞込み(2と3と5の倍数しか回答は無いので)を入れてみました。

list max b n
    | (b^n) > max   =   []
    | otherwise = n : list max b (n+1)

scan n = [(n,i,j,k)|i<-list n 2 0,j<-list n 3 0,k<-list n 5 0,n == (2^i*3^j*5^k)]

result = take 100 $ concatMap (scan) $ filter (check) [1..]

check n
    | n == 1            =   True
    | (n `mod` 2) == 0  =   True
    | (n `mod` 3) == 0  =   True
    | (n `mod` 5) == 0  =   True
    | otherwise         =   False

main=do
    mapM (\x-> putStrLn $ format x) result
    where
        format (n,i,j,k) = concat [show n," = ",fmt 2 i," * ",fmt 3 j," * ",fmt 5 k]
        fmt b n = show b ++ "^" ++ show n

しまった、これでは12の次が15(3*5)じゃなくて14(2*7)になってしまう。
反省して--self。
そして、まともに動くものを。

#include <iostream>
#include <map>

std::map<int,int> factor(int n)
{
  std::map<int, int> r;
  r[2] = r[3] = r[5] = 0;
  while ( n%2==0 ) { n/=2; ++r[2]; }
  while ( n%3==0 ) { n/=3; ++r[3]; }
  while ( n%5==0 ) { n/=5; ++r[5]; }

  if ( n != 1 ) r.clear();
  return r;
}

int main()
{
  for ( int i = 1, n = 0; n < 100; ++i ) {
    std::map<int,int> f = factor(i);

    if ( !f.empty() ) {
      std::cout << i << " = 2^" << f[2] <<
                        " * 3^" << f[3] <<
                        " * 5^" << f[5] << "\n";
      ++n;
    }
  }
  return 0;
}

#7638 さんのアルゴリズムを借用。
priority queueの代わりに、標準ライブラリのヒープキューを使います。

#!/usr/bin/python

from heapq import heappush, heappop

def doukaku206(num_answers):
    answers = []
    heap = [1]
    prev_answer = 0
    while len(answers) < num_answers:
        a = heappop(heap)
        if a == prev_answer:
            continue
        answers.append(a)
        heappush(heap, a * 2)
        heappush(heap, a * 3)
        heappush(heap, a * 5)
        prev_answer = a
    return answers

print doukaku206(100)

# eof

元になったコードへのコメントを確認してください。

確認しました。問題ないということでよろしいですね。

#7642 にマイナス評価が付いてるけど、ジェネレイタにしなかった罰だと思うことにしますw

Squeak Smalltalk で。

| count n |
count := 0.
n := 0.
World findATranscript: nil.
[n := n + 1. count < 100] whileTrue: [
    (#(2 3 5) inject: n into: [:quo :each |
            [quo isDivisibleBy: each] whileTrue: [quo := quo / each]. quo]) = 1
         ifTrue: [
            count := count + 1.
            Transcript cr; show: n]]

適当に生成しながら小さい順に並べてます。動けばいい的な作りですが。考え方は 84q さんのと同じでしょうか。

計算量は時間 O(N^2) 空間 O(N) かと思いましたが、実際に試してみた感じだともっと小さいかもしれません。また balanced tree をつかうなど真面目に効率化をやればもっと速くなると思います。

(defun add (n list)
  (if (find n list) list (merge 'list list (list n) #'<)))

(defun h (n)
  (let ((a (list 1)) (c 0))
    (loop (let ((m (pop a)))
            (print m)
            (setf a (add (* m 2) (add (* m 3) (add (* m 5) a))))
            (if (= (incf c) n) (return))))))

別のアルゴリズムで解いてみました。

数が大きくなれば有利かな？

public class Sample206 {
    public static void main(String[] args) {
        OUTER: for (int i = 1, n = 0; n < 100; i++) {
            for (int p = 7; p <= i; p += 2) {
                if (p % 3 == 0) continue;
                if (p % 5 == 0) continue;
                if (i % p == 0) {
                    continue OUTER;
                }
            }
            System.out.println(i);
            n++;
        }
    }
}

Javascript@Firebug。 n2,n3,n5の最大値は試行錯誤で決めてます

var o={};
for(var n2=0; n2<=11; n2++)
  for(var n3=0; n3<=8; n3++)
    for(var n5=0; n5<=7; n5++)
      o[Math.pow(2,n2)*Math.pow(3,n3)*Math.pow(5,n5)] = [n2,n3,n5];
for(var i=0,c=0;c<100;i++)
  if(o[i]!=null)
    console.debug(++c, ". ", i, "= 2^", o[i][0], " + 3^", o[i][1], " + 5^", o[i][2]);

one-linerというかgolfというか...
アルゴリズムは他の皆さんと同じです。

1
2
3

1==shift@z&&++$n&&printf"%d = 2^%d * 3^%d *%s 5^%d\n",@z
while$n<100&&(@z=(++$i,$i,0,0,'',0))&&
map{$z[0]/=$_,++$z[$_]until$z[0]%$_}2,3,5

ちゃんと計算してないけど、時間計算量はO(n logn)、空間計算量はO(1)ぐらい？再帰してるから空間計算量はO(logn)なのかな。

class P
{
  static void Main(string[] args)
  {
    for (int i = 1, c = 0; c < 100; i++)
    {
      int[] f = F(i);
      if (f != null)
      {
        ++c;
        System.Console.WriteLine
          ("{0} = 2^{1} * 3^{2} * 5^{3}", i, f[2], f[3], f[5]);
      }
    }
  }

  static int[] F(int n)
  {
    if (n == 1) return new int[6];
    int[] a = { 2, 3, 5 };
    foreach (int d in a)
      if (n % d == 0)
      {
        int[] r = F(n / d);
        if (r == null) return null;
        ++r[d];
        return r;
      }
    return null;
  }
}

アプローチとしては#7638と同じでしょうか。配列。

n=1
for ((i = 0; i < 100; i++));do
    echo $n
    ary[$((n*2))]=1
    ary[$((n*3))]=1
    ary[$((n*5))]=1
    while [ "${ary[$((++n))]}" != 1 ];do :;done
done

配列の添字が冗長だったので微修正します。

n=1
for ((i = 0; i < 100; i++));do
    echo $n
    ary[n*2]=1
    ary[n*3]=1
    ary[n*5]=1
    while [ "${ary[++n]}" != 1 ];do :;done
done

ハミング数ですね。
anarchy golf の Hamming Numbers問題
http://golf.shinh.org/p.rb?Hamming+Numbers
のときに投稿した golf用の富豪コードです。

30のx乗 ≡ 0 (mod x) となる x がハミング数に
なることを使っています。（30 は 2,3,5 の最小公倍数）

富豪だから、け、計算量なんて気にしてないんだからね！

main = do
  n <- readLn
  mapM_ print $ take n [x| x <- [1..], mod (30^x) x == 0]

{- anarchy golf に投稿したコードはこちら

main=readLn>>=mapM print.(`take`[x|x<-[1..],mod(30^x)x<1])

-}

素因数分解していくバージョンで

:new
:let s:n=1
:let s:m=0
:while s:m < 100
: if s:n != 1 && s:n % 2 != 0 && s:n % 3 != 0 && s:n % 5 != 0
:   let s:n = s:n + 1
:   continue
: endif
: let s:_ = s:n
: let s:i = 0
: let s:j = 0
: let s:k = 0
: while s:_ % 2 == 0
:   let s:_ = s:_ / 2
:   let s:i = s:i + 1
: endwhile
: while s:_ % 3 == 0
:   let s:_ = s:_ / 3
:   let s:j = s:j + 1
: endwhile
: while s:_ % 5 == 0
:   let s:_ = s:_ / 5
:   let s:k = s:k + 1
: endwhile
: if s:_ == 1
:   call append(s:m, printf("%d = 2^%d * 3^%d * 5^%d", s:n, s:i, s:j, s:k))
:   let s:m = s:m + 1
: endif
: let s:n = s:n + 1
:endwhile
:unlet! s:n
:unlet! s:m
:unlet! s:i
:unlet! s:j
:unlet! s:k
:unlet! s:_

　#7652を参考に書いてみました。

class HummingNumbers
    def self.get(c)
        (30**c % c == 0) ? c : get(c+1)
    end
    def self.take(n,c=1)
        (n==0) ? [] : ((c = get(c)) && take(n-1,c+1).unshift(c))
    end
end

puts HummingNumbers.take(ARGV.length == 1 ? ARGV[0].to_i : 100).join("\n")

　[1..100]>>=penさんの投稿を参考に書いてみました。

class CHummingNumbers {
    def next(c:Int):Int = (BigInt(30).pow(c) % c).intValue match {
            case 0 => c
            case _ => next(c+1)
        }
    def take(n:Int,c:Int):List[Int] = n match {
            case 0 => List()
            case _ => next(c) match { case v => v::take(n-1,v+1) }
        }
    def take(n:Int):List[Int] = take(n,1)
}
object HummingNumbers {
    def main(args:Array[String]):Unit = {
        try {
            val    n:Int = args.length match {
                case 1 => args(0).toInt
                case _ => 100
            }
            println((new CHummingNumbers).take(n).mkString("\n"))
        } catch {
            case e => e.printStackTrace
        }
    }
}

Haskellらしく素直に無限リストで :)

main :: IO ()
main = print $ take 100 hamming

hamming :: [Integer]
hamming = 1 : foldr1 (#) (zipWith map (map (*) [2,3,5]) (repeat hamming))

(#) :: Ord a => [a] -> [a] -> [a]
xxs@(x:xs) # yys@(y:ys) | x < y     = x : xs  # yys
                        | y < x     = y : xxs # ys
                        | otherwise = x : xs  # ys

dictでmemo化

本来は配列でmemo化したほうがよいのだが、pythonでListのreserveを適切に行う方法がわからない。index errorをexceptするのもだるいし・・・。

appendするならdictを使うほうがマシでしょう。

class IsN235WithMemo(object):
  def __init__(self):
    self.memo = dict()
  def __call__(self, n):
    r = self.memo.get(n, None)
    if r is not None:
      return r
    if n == 1:
      return True
    d, m = divmod(n, 2)
    if d and m == 0:
      return is_n235(d)
    d, m = divmod(n, 3)
    if d and m == 0:
      return is_n235(d)
    d, m = divmod(n, 5)
    if d and m == 0:
      return is_n235(d)
    return False

is_n235 = IsN235WithMemo()

for i in range(10):
  print i, is_n235(i)

出題時に考えていた答。平衡木を使うので、求める数の個数を n としたとき、時間計算量は O(log n)、空間計算量は O(n) のはず。

see: Gauche ユーザリファレンス: 6.14 ツリーマップ

(define (main args)
  (let ((tm (alist->tree-map '((1 . #t)) = <)))
    (let loop ((n (string->number (cadr args)))
               (rs '()))
      (cond
       ((zero? n)
        (print (reverse rs))
        0)
       (else
        (let ((m (car (tree-map-pop-min! tm))))
          (for-each (cut tree-map-put! tm <> #t)
                    (map (cute * m <>) '(2 3 5)))
          (loop (- n 1) (cons m rs))))))))