61 lines
1.6 KiB
Text
61 lines
1.6 KiB
Text
with javascript_semantics
|
|
sequence is1
|
|
|
|
function comb(atom res, sequence set, integer n, at=1, sequence chosen={})
|
|
if length(chosen)=n then
|
|
sequence digits = repeat(0,10)
|
|
atom sumsq = 0
|
|
for i=1 to length(chosen) do
|
|
integer ci = chosen[i]
|
|
sumsq += ci*ci
|
|
ci += 1
|
|
digits[ci] += 1
|
|
end for
|
|
if sumsq=0 or is1[sumsq] then
|
|
atom perms = factorial(length(chosen))
|
|
for i=1 to 10 do
|
|
if digits[i] then
|
|
perms /= factorial(digits[i])
|
|
end if
|
|
end for
|
|
res += perms
|
|
end if
|
|
else
|
|
chosen = deep_copy(chosen)&0
|
|
for i=at to length(set) do
|
|
chosen[$] = set[i]
|
|
res = comb(res,set,n,i,chosen)
|
|
end for
|
|
end if
|
|
return res
|
|
end function
|
|
|
|
procedure setis1(integer n)
|
|
is1 = repeat(0,n*81)
|
|
for i=1 to length(is1) do
|
|
integer r, digit, w = i
|
|
while 1 do
|
|
r = 0
|
|
while w!=0 do
|
|
digit = mod(w,10)
|
|
r += digit*digit
|
|
w = floor(w/10)
|
|
end while
|
|
if r=89 then exit end if
|
|
if r=1 then
|
|
is1[i] = 1
|
|
exit
|
|
end if
|
|
w = r
|
|
end while
|
|
end for
|
|
end procedure
|
|
|
|
constant nums = {0,1,2,3,4,5,6,7,8,9}
|
|
atom t00 = time()
|
|
for i=1 to 16 do
|
|
atom t0 = time()
|
|
setis1(i)
|
|
printf(1,"There are %d numbers from 1 to 10^%d ending with 89 (%3.2fs)\n",{power(10,i)-comb(0,nums,i),i,time()-t0})
|
|
end for
|
|
?elapsed(time()-t00)
|