Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
Hamming numbers are numbers which evenly divide a power of 60. Equivalently, their prime factors are all \$ \le 5 \$.
Given a positive integer, print that many Hamming numbers, in order.
Rules:
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.
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
h=[], using a minimum tab distance, and single character line breaks, and the file size ends up being 187 bytes.
\$\endgroup\$
Dec 31, 2013 at 16:50
h=[1]. Also, give a number directly in the source code, to save characters for numbers <1000000.
\$\endgroup\$
Dec 31, 2013 at 17:13
{⍺⍴{⍵[⍋⍵]}∪,⍵∘.×⍳5}⍣≡∘1
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.
1↓0 1{⍺↑{⍵[⍋⍵]}∪,⍵∘.×⍳5}⍣≡⍨1+⊢
\$\endgroup\$
{⍺⍴∧∪,⍵×⍀⍳5}`⍣≡∘1 in Extended. (Backtick needed due to bug.)
\$\endgroup\$
j, 8 bytesλdǏG7<;ȯ
λ ;ȯ # First n numbers where
dǏG # Maximum of prime factors
7< # Less than 7
My first ever Vyxal post. 29->26, adviced by @lyxal.
6ɽ{:L?<|:2*$:3*$:5*∪∪∪}s?Ẏ
# 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
?Ẏ
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
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
RḤÆfṀ€<7T
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
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.
#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>
-M, 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
Given from stdin, as a line consists of a string of decimal natural number.
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
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
$0=s is removed$ time echo 1000000 | awk -Mf Textfile/ham.awk
real 0m25.404s
user 0m24.676s
sys 0m0.716s
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]
1s is conformant with your specs. It will also be in order, i.e. not an unordered sequence. :) \$\endgroup\$