24
\$\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\$
6
  • 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
  • 4
    \$\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
  • 1
    \$\begingroup\$ Please add the definition of a Hamming number to your question. \$\endgroup\$
    – user
    May 7 at 12:58

12 Answers 12

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\$
2
  • 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\$
4
  • \$\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
  • 2
    \$\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\$ Jan 1 '14 at 10:33
3
+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\$
2
2
+50
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Vyxal j, 10 bytes

∞'dǏG7<;?Ẏ

Try it Online!

∞          # All positive integers
 '     ;   # Filter by
  d        # Double (to handle 1, which has no prime factors)
   ǏG      # Max of prime factors
     7<    # Is less than 7
        ?Ẏ # First n
\$\endgroup\$
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\$
0
1
\$\begingroup\$

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

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.

\$\endgroup\$
0
\$\begingroup\$

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

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

\$\endgroup\$
2
  • \$\begingroup\$ Unfortunately, 8 bytes doesn't work with the time limit :( \$\endgroup\$ Oct 11 at 7:52
  • \$\begingroup\$ @cairdcoinheringaahing yeah, IO rules suck \$\endgroup\$
    – wasif
    Oct 11 at 7:53
-2
\$\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\$
2
  • \$\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\$ 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

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.