43 lines
1.2 KiB
Text
43 lines
1.2 KiB
Text
function hamming(integer N)
|
|
sequence h = repeat(1,N)
|
|
atom x2 = 2, x3 = 3, x5 = 5, hn
|
|
integer i = 1, j = 1, k = 1
|
|
for n=2 to N do
|
|
hn = min(x2,min(x3,x5))
|
|
h[n] = hn
|
|
if hn==x2 then i += 1 x2 = 2*h[i] end if
|
|
if hn==x3 then j += 1 x3 = 3*h[j] end if
|
|
if hn==x5 then k += 1 x5 = 5*h[k] end if
|
|
end for
|
|
return h[N]
|
|
end function
|
|
|
|
include builtins\mpfr.e
|
|
|
|
function mpz_hamming(integer N)
|
|
sequence h = mpz_inits(N,1)
|
|
mpz x2 = mpz_init(2),
|
|
x3 = mpz_init(3),
|
|
x5 = mpz_init(5),
|
|
hn = mpz_init()
|
|
integer i = 1, j = 1, k = 1
|
|
for n=2 to N do
|
|
mpz_set(hn,mpz_min({x2,x3,x5}))
|
|
mpz_set(h[n],hn)
|
|
if mpz_cmp(hn,x2)=0 then i += 1 mpz_mul_si(x2,h[i],2) end if
|
|
if mpz_cmp(hn,x3)=0 then j += 1 mpz_mul_si(x3,h[j],3) end if
|
|
if mpz_cmp(hn,x5)=0 then k += 1 mpz_mul_si(x5,h[k],5) end if
|
|
end for
|
|
return h[N]
|
|
end function
|
|
|
|
sequence s = {}
|
|
for i=1 to 20 do
|
|
s = append(s,hamming(i))
|
|
end for
|
|
?s
|
|
printf(1,"%d\n",hamming(1691))
|
|
printf(1,"%d (wrong!)\n",hamming(1000000)) --(the hn==x2 etc fail, so multiplies are all wrong)
|
|
|
|
mpfr_printf(1,"%Zd\n",mpz_hamming(1691))
|
|
mpfr_printf(1,"%Zd\n",mpz_hamming(1000000))
|