Anonymous user
Humble numbers: Difference between revisions
→{{header|Lua}}
Thundergnat (talk | contribs) m (→{{header|Ring}}: Needs improvement) |
|||
Line 3,276:
1272 have 8 digits
1767 have 9 digits</pre>
=={{header|Nim}}==
A simple algorithm efficient enough to get the number of humble numbers with 18 digits in less than four seconds. To get further, we would have to use big numbers and a more efficient algorithm.
<lang Nim>import sets, strformat
proc min[T](s: HashSet[T]): T =
## Return the minimal value in a set.
if s.card == 0:
raise newException(ValueError, "set is empty.")
result = T.high
for n in s:
if n < result: result = n
iterator humbleNumbers(): Positive =
## Yield the successive humble numbers.
var s = [1].toHashSet()
while true:
let m = min(s)
yield m
s.excl(m)
for k in [2, 3, 5, 7]: s.incl(k * m)
proc showHumbleNumbers(maxCount: Positive) =
## Show the first "maxCount" humble numbers.
var currCount = 0
for n in humbleNumbers():
stdout.write n
inc currCount
if currCount == maxCount: break
stdout.write ' '
echo ""
proc showHumbleCount(ndigits: Positive) =
## Show the number of humble numbers with "n <= ndigits" digits.
echo "Digits Count"
echo "------ -----"
var currdigits = 1
var count = 0
var next = 10 # First number with "currdigits + 1" digits.
for n in humbleNumbers():
if n >= next:
# Number of digits has changed.
echo &" {currdigits:2d} {count:5d}"
inc currdigits
if currdigits > ndigits: break
next *= 10
count = 1
else:
inc count
when isMainModule:
echo "First 50 humble numbers:"
showHumbleNumbers(50)
echo ""
echo "Count of humble numbers with n digits:"
showHumbleCount(18)</lang>
{{out}}
<pre>First 50 humble numbers:
1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120
Count of humble numbers with n digits:
Digits Count
------ -----
1 9
2 36
3 95
4 197
5 356
6 579
7 882
8 1272
9 1767
10 2381
11 3113
12 3984
13 5002
14 6187
15 7545
16 9081
17 10815
18 12759</pre>
=={{header|Pascal}}==
| |||