18
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ Which aim an answer should have? Golf? Most effective algorithm? Just searching of solution methods? \$\endgroup\$ – Nakilon Jan 28 '11 at 0:19
  • \$\begingroup\$ 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. \$\endgroup\$ – grokus Jan 30 '11 at 22:54
  • \$\begingroup\$ OEIS \$\endgroup\$ – Stephen Aug 18 '17 at 17:24
  • 3
    \$\begingroup\$ 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. :) \$\endgroup\$ – Will Ness Jan 5 '18 at 15:03
7
\$\begingroup\$

Haskell, 101 97 92+|n| characters

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.

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

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – nitro2k01 Dec 31 '13 at 16:50
  • 1
    \$\begingroup\$ Anyway... Trivial optimization: h=[1]. Also, give a number directly in the source code, to save characters for numbers <1000000. \$\endgroup\$ – nitro2k01 Dec 31 '13 at 17:13
  • \$\begingroup\$ And oops, sorry, didn't realize the answer is super-old. \$\endgroup\$ – nitro2k01 Dec 31 '13 at 17:15
  • \$\begingroup\$ @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). \$\endgroup\$ – Peter Taylor Jan 1 '14 at 10:33
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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) :(

\$\endgroup\$
1
+200
\$\begingroup\$

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.
\$\endgroup\$
0
\$\begingroup\$

Haskell, 71

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]
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Jan 1 '14 at 10:28
  • \$\begingroup\$ @PeterTaylor How many characters do you think I should add? \$\endgroup\$ – Timtech Jan 1 '14 at 14:59
0
\$\begingroup\$

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>
\$\endgroup\$
0
\$\begingroup\$

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

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

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

\$\endgroup\$
  • \$\begingroup\$ 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.) \$\endgroup\$ – Anders Kaseorg Feb 8 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.