どう書く.orgに投稿した(#206)

2^i * 3^j * 5^k なる整数というお題。についてErlangで投稿した。解法としては単純にしらみつぶしなのだが、その探索領域の上界は簡単にわかる。しかし、うまく巡回する方法がわからなかった。うまく巡回する方法はsortする方法に直結するだろうから、よりスマートな解は結局自分の力では見つからなかったということ。
Wikipediaによれば、ハミング数という問題らしい。上界については、そのページの図を、3次元空間の第1象限を切り取る三角錐だとイメージしてもらうといいかもしれない。
例によってDijkstra氏が論文(手で↓)書いているらしい。
Hamming excercize in SASL
golfでも例題になっていたらしいが、200バイト以下ってのは、どんな感じなんだろう。
anarchy golf - Hamming Numbers
ちなみに、投稿したコードをいい加減に縮めるとこんな感じ(238バイト)

-module(len).
-export([m/1]).
p(A,B)->math:pow(A,B).
m([N|_])->K=list_to_integer(atom_to_list(N)),F=round(3*p(K,0.4)),S=lists:seq(0,F),
L = lists:sort([round(p(2, X)*p(3,Y)*p(5,Z))||X<-S,Y<-S,Z<-S]),
io:format("~p~n",[lists:sublist(L,K)]).

これでも、いちおう結果は出る。

$ erl -noshell -s len m 100 -s init stop
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,
 75,80,81,90,96,100,108,120,125,128,135,144,150,160,162,180,192,200,216,225,
 240,243,250,256,270,288,300,320,324,360,375,384,400,405,432,450,480,486,500,
 512,540,576,600,625,640,648,675,720,729,750,768,800,810,864,900,960,972,1000,
 1024,1080,1125,1152,1200,1215,1250,1280,1296,1350,1440,1458,1500,1536]