# 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? – Nakilon 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. – grokus Jan 30 '11 at 22:54
• OEIS – Stephen 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. :) – Will Ness Jan 5 '18 at 15:03

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. – nitro2k01 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. – nitro2k01 Dec 31 '13 at 17:13
• And oops, sorry, didn't realize the answer is super-old. – nitro2k01 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). – Peter Taylor Jan 1 '14 at 10:33

## 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


## Perl, 94 chars (but too slow)

use List::Util min;
$\=$/;$h{1}=();delete$h{$_=min keys%h},print,@h{$_*2,$_*3,$_*5}=()for 1..<>


Ungolfed:

use List::Util 'min';
my %hamming;
my $up_to = <>;$hamming{1} = (); # The value is undef, but the key exists!
for (1 .. $up_to) { my$next = min( keys %hamming );
delete $hamming{$next}; # We're done with this one
print $next, "\n"; @hamming{$next * 2, $next * 3,$next * 5 } = (); # Create keys for the multiples
} # Rinse, repeat


Takes 11 minutes to compute the first 100,000 numbers, and I don't even want to think about 1,000,000. It gets the first 10,000 done in a tidy 3 seconds; it's just something resembling O(n^2) :(

# 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.


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
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]

• The spec calls for you to print, so the code to print should be counted. This also allows a fair comparison against the other Haskell implementation. – Peter Taylor Jan 1 '14 at 10:28
• @PeterTaylor How many characters do you think I should add? – Timtech Jan 1 '14 at 14:59

## 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>


## Mathematica, 54 bytes

Sort[1##&@@@({2,3,5}^#&/@Tuples[0~Range~#,3])]~Take~#&


Inefficient but short pure function. Calculates all products of the form 2^i * 3^j * 5^k for 0 <= i, j, k <= # (# is the first argument to the function), then Sorts them and Takes only the first #.

• Somehow I don't think performing 1e18 calculations is going to happen in under a minute. – Jonathan Allan Oct 20 '18 at 17:23

# Japt, 15 bytes

@_k e§5}a°X}h1ì


Try it

ÆJ=_k d>5}f°Jª1


Try it

## 3 bytes

If Jo King's approach is considered valid.

o!²


Try it

• This doesn’t seem to come anywhere close to satisfying the requirement of executing in < 1 minute. (And Jo King's approach is not valid.) – Anders Kaseorg Feb 8 '19 at 23:58