# Hamming numbers

Given a positive integer, print that many Hamming numbers, in order.

Rules:

• Input will be a positive integer $$\n \le 1,000,000 \$$
• Output should be the first $$\n\$$ terms of https://oeis.org/A051037
• Execution time must be $$\<1\$$ minute
• This is ; shortest code wins
• Which aim an answer should have? Golf? Most effective algorithm? Just searching of solution methods? Jan 28 '11 at 0:19
• Sorry for not being specific. I haven't solved this myself, so I'm not sure if the bounds I put in are reasonable. Please let me know. Jan 30 '11 at 22:54
• OEIS Aug 18 '17 at 17:24
• 1 is a Hamming number, so, printing 1,000,000 1s is conformant with your specs. It will also be in order, i.e. not an unordered sequence. :) Jan 5 '18 at 15:03
– user
May 7 '21 at 12:58

h=1:m 2h&m 3h&m 5h
m=map.(*)
c@(a:b)&o@(m:n)|a<m=a:b&o|a>m=m:c&n|0<1=a:b&n
main=print$take 1000000h  Computes the full million in 3.7s on the machine I tested on (variably more if you actually want the output stored) Ungolfed: -- print out the first million Hamming numbers main = print$ take 1000000 h

-- h is the entire Hamming sequence.
-- It starts with 1; for each number in the
-- sequence, 2n, 3n and 5n are also in.
h = 1 : (m 2 h) & (m 3 h) & (m 5 h)

-- helper: m scales a list by a constant factor
m f xs = map (f*) xs

-- helper: (&) merges two ordered sequences
a@(ha:ta) & b@(hb:tb)
|    ha < hb = ha : ta & b
|    ha > hb = hb :  a & tb
|  otherwise = ha : ta & tb


All Haskell is notoriously good at: defining a list as a lazy function of itself, in a way that actually works.

• You don't get the positive integer parameter, that add more size to your code
– Zhen
Aug 24 '11 at 8:23
• @Zhen The positive integer parameter is the second-to-last token, and its size is declared outfront in the header.
– J B
Aug 24 '11 at 8:30

Python 181 Characters

h=[]
h.append(1)
n=input()
i=j=k=0
while n:
print h[-1]
while h[i]*2<=h[-1]:
i+=1
while h[j]*3<=h[-1]:
j+=1
while h[k]*5<=h[-1]:
k+=1
h.append(min(h[i]*2,h[j]*3,h[k]*5))
n-=1

• How is this 181 chars? I've saved this to a file, removing the whitespace after h=[], using a minimum tab distance, and single character line breaks, and the file size ends up being 187 bytes. Dec 31 '13 at 16:50
• Anyway... Trivial optimization: h=[1]. Also, give a number directly in the source code, to save characters for numbers <1000000. Dec 31 '13 at 17:13
• And oops, sorry, didn't realize the answer is super-old. Dec 31 '13 at 17:15
• @nitro2k01, I make it 183 chars. (There's some trailing whitespace at the end of the first line, and the indentation should be a space for one level and a tab for two levels). Jan 1 '14 at 10:33

# APL (Dyalog Classic), 34 23 bytes

{⍺⍴{⍵[⍋⍵]}∪,⍵∘.×⍳5}⍣≡∘1


Try it online!

TIO throws a WS FULL error for $$\n = 1000000\$$, but Dyalog on my laptop runs in about 45 seconds, not counting the scrolling to display numbers.

{⍺⍴{⍵[⍋⍵]}∪,⍵∘.×⍳5}⍣≡∘1     Monadic function:
{⍺⍴{⍵[⍋⍵]}∪,⍵∘.×⍳5}         Define the following helper function g(⍺,⍵):
⍵∘.×⍳5             Make a multiplication table between ⍵ and (1 2 3 4 5).
(Including 4 is unnecessary but saves bytes.)
,                   Flatten the table into an array.
∪                    Keep unique elements.
{⍵[⍋⍵]}                     Grade up the array and access it at those indices.
(This is the APL idiom to sort an array.)
⍺⍴                             Keep the first ⍺ elements; pad by repeating the array.
{⍺⍴{⍵[⍋⍵]}∪,⍵∘.×⍳5}⍣≡       Repeatedly apply g with some fixed left argument
until a fixed point is reached.
At this point we have a dyadic function that takes
n on the left and the starting value on the right,
and returns multiples of the n Hamming numbers.
∘1     Fix 1 as the right argument.


# Vyxalj, 8 bytes

λdǏG7<;ȯ


Try it Online!

λ     ;ȯ # First n numbers where
dǏG     # Maximum of prime factors
7<   # Less than 7


# Vyxal, 29 26 bytes, times out when n>=200,000 on online interpreter.

My first ever Vyxal post. 29->26, adviced by @lyxal.

6ɽ{:L?<|:2*$:3*$:5*∪∪∪}s?Ẏ


## How it works

# let first hamming numbers are 1 to 6
6ɽ
# while items of they are less than n; do
{:L?<|
# for each item, multiply with those numbers
# and then unify them; done
:2*$:3*$:5*∪∪∪}
# sort
s
# take first n items
?Ẏ


Try it Online!

## Ruby - 154 231 characters

def k i,n;(l=Math).log(i,2)*l.log(i,3)*l.log(i,5)/6>n end
def l i,n;k(i,n)?[i]:[i]+l(5*i,n)end
def j i,n;k(i,n)?[i]:[i]+j(3*i,n)+l(5*i,n)end
def h i,n;k(i,n)?[i]:[i]+h(2*i,n)+j(3*i,n)+l(5*i,n)end
puts h(1,n=gets.to_i).sort.first n


And now it's fast enough, there is definitely a lot of golfing that can still happen though.

→ time echo 1000000 | ruby golf-hamming.rb | wc
1000000 1000000 64103205
echo 1000000  0.00s user 0.00s system 0% cpu 0.003 total
ruby golf-hamming.rb  40.39s user 0.81s system 99% cpu 41.229 total
wc  1.58s user 0.05s system 3% cpu 41.228 total


# MMIX, 92 bytes (23 instrs)

I'm cheating a bit; instead of printing (which would take a lot of work, this being machine language), I instead pass the numbers to a function passed in!

00000000: fe020004 34000100 e3030000 c1040300  “£¡¥4¡¢¡ẉ¤¡¡Ḋ¥¤¡
00000010: e7030001 da040403 3c040304 1d050403  ḃ¤¡¢ḷ¥¥¤<¥¤¥ø¦¥¤
00000020: feff0006 6204ff05 43fffffd 1d050405  “”¡©b¥”¦C””’ø¦¥¦
00000030: feff0006 6204ff05 43fffffd 31ff0401  “”¡©b¥”¦C””’1”¥¢
00000040: 5bfffff3 e7000001 c1050300 bf040100  [””ṙḃ¡¡¢Ḋ¦¤¡Ḃ¥¢¡
00000050: 5b00ffef f6040002 f8000000           [¡”ṁẇ¥¡£ẏ¡¡¡

smooth5 GET    $2,rJ NEG$0,1,$0 // n = 1 - n SETL$3,0         // i = 0
0H      SET    $4,$3
INCL   $3,1 // loop: j = i++ SADD$4,$4,$3     // j = popcnt(j & ~i)
SR     $4,$3,$4 // j = i >> j (cheap way of getting out factors of 2) 1H DIV$5,$4,3 // lp3: k = j / 3 GET$255,rR      // tmp = j % 3
CSZ    $4,$255,$5 // if(!tmp) j = k BZ$255,1B      // if(!tmp) goto lp3
1H      DIV    $5,$4,5      // lp5: k = j / 5
GET    $255,rR // tmp = j % 5 CSZ$4,$255,$5   // if(!tmp) j = k
BZ     $255,1B // if(!tmp) goto lp3 CMP$255,$4,1 // tmp = j <=> 1 PBNZ$255,0B      // iflikely(tmp) goto loop
INCL   $0,1 // n++ SET$5,$3 PUSHGO$4,$1,0 // f(i) PBNZ$0,0B        // iflikely(n) goto loop
PUT    rJ,$2 POP 0,0 // return  # Jelly, 9 bytes RḤÆfṀ€<7T  Try it online! Returns all hamming numbers under n. How? RḤÆfṀ€<7T Main Link. Takes n on the left T Filter by R Inclusive range Ḥ Double each Æf Prime factors € For each Ṁ Maximum <7 Less than 7  My first serious jelly answer • Unfortunately, 8 bytes doesn't work with the time limit :( Oct 11 '21 at 7:52 • @cairdcoinheringaahing yeah, IO rules suck Oct 11 '21 at 7:53 ## Ursala, 103 #import std #import nat smooth"p" "n" = ~&z take/"n" nleq-< (rep(length "n") ^Ts/~& product*K0/"p") <1>  Output for main = smooth<2,3,5>* nrange(1,20) <1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36>  # JavaScript (ES6), 110 bytes f=h=>eval("g=n=>n-1n?n%2n?n%3n?n%5n?0:g(n/5n):g(n/3n):g(n/2n):1;r=[i=1n];while(!r[h-1])if(g(++i))r.push(i);r")  Theoretically works for arbitrarily large inputs, but prohibitively slow. # GAWK-M, 138 120 bytes. It was originally a post on rosetta code. Without -M it overflows when huge value is input. {a=2 b=3 c=5 for(s=h[0]=1;--$0;c-z||c=5*h[++k]){z=a<b?a:b
s=s" "(z=h[++n]=z<c?z:c)
a-z||a=2*h[++i]
b-z||b=3*h[++j]}}$0=s  Try it online! ## Usage Given from stdin, as a line consists of a string of decimal natural number. ## Execution time Tested in my Termux. CPU is: Architecture: aarch64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 8 On-line CPU(s) list: 0-7 Thread(s) per core: 1 Core(s) per socket: 4 Socket(s): 2 Vendor ID: ARM Model: 4 Model name: Cortex-A53 Stepping: r0p4 CPU max MHz: 1768.0000 CPU min MHz: 449.0000 BogoMIPS: 52.00 Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32  ### With original code 10^6th Hamming number is 519312780448388736089589843750000000000000000000000000000000000000000000000000000000. $ time echo 1000000 | awk -Mf Textfile/ham.awk
# lots of output
real    2m36.842s
user    0m25.224s
sys     0m5.356s


### If $0=s is removed $ time echo 1000000 | awk -Mf Textfile/ham.awk
real    0m25.404s
user    0m24.676s
sys     0m0.716s


## Note

• Original 138 bytes of post outputs incorrectly: it outputs n+1 numbers, not n.
• OBTW replacing variables a,b,c,i,j,k with arrays resulted in 132 bytes. Try it online!
– user100411
May 25 '21 at 10:09
• @tailsparkrabbitear In the case 130 bytes: Try it online!
– user100411
May 26 '21 at 9:03

h n = drop n $iterate (\(_,(a:t))-> (a,union t [2*a,3*a,5*a])) (0,[1])  Output *Main> map fst$ take 20 \$ h 1