Humble numbers: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→{{header|Ring}}: Needs improvement) |
|||
Line 3,276: | Line 3,276: | ||
1272 have 8 digits |
1272 have 8 digits |
||
1767 have 9 digits</pre> |
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}}== |
=={{header|Pascal}}== |