Wasteful, equidigital and frugal numbers: Difference between revisions
Content added Content deleted
(→{{header|Ruby}}: Add Ruby) |
(Created Nim solution.) |
||
Line 204: | Line 204: | ||
First 50: {125,128,243,256,343,512,625,729,1024,1029,1215,1250,1280,1331,1369,1458,1536,1681,1701,1715,1792,1849,1875,2048,2187,2197,2209,2401,2560,2809,3125,3481,3584,3645,3721,4096,4374,4375,4489,4802,4913,5041,5103,5329,6241,6250,6561,6859,6889,7203} |
First 50: {125,128,243,256,343,512,625,729,1024,1029,1215,1250,1280,1331,1369,1458,1536,1681,1701,1715,1792,1849,1875,2048,2187,2197,2209,2401,2560,2809,3125,3481,3584,3645,3721,4096,4374,4375,4489,4802,4913,5041,5103,5329,6241,6250,6561,6859,6889,7203} |
||
Below 10^6: 3123</pre> |
Below 10^6: 3123</pre> |
||
=={{header|Nim}}== |
|||
<syntaxhighlight lang="Nim">import std/[sequtils, strformat, tables] |
|||
# Sieve to find the decomposition in prime factors. |
|||
const N = 2_700_000 |
|||
var factors: array[1..N, CountTable[int]] |
|||
factors[1].inc(1) |
|||
for n in 2..N: |
|||
if factors[n].len == 0: # "n" is prime. |
|||
var m = n # Powers of "n" |
|||
while m <= N: |
|||
for k in countup(m, N, m): |
|||
factors[k].inc(n) |
|||
m *= n |
|||
type Category {.pure.} = enum Wasteful = "wasteful" |
|||
Equidigital = "equidigital" |
|||
Frugal = "frugal" |
|||
func digitCount(n, base: Positive): int = |
|||
## Return the number of digits of the representation of "n" in given base. |
|||
var n = n.Natural |
|||
while n != 0: |
|||
inc result |
|||
n = n div base |
|||
proc d(n, base: Positive): int = |
|||
## Compute "D(n)" in given base. |
|||
for (p, e) in factors[n].pairs: |
|||
inc result, p.digitCount(base) |
|||
if e > 1: inc result, e.digitCount(base) |
|||
proc category(n, base: Positive): Category = |
|||
## Return the category of "n" in given base. |
|||
let i = n.digitCount(base) |
|||
let d = d(n, base) |
|||
result = if i < d: Wasteful elif i > d: Frugal else: Equidigital |
|||
const N1 = 50 |
|||
const N2 = 10_000 |
|||
const Limit = 1_000_000 |
|||
for base in [10, 11]: |
|||
var counts1: array[Category, int] # Total counts. |
|||
var counts2: array[Category, int] # Counts for n < Limit. |
|||
var numbers1: array[Category, array[1..N1, int]] # First N1 numbers in each category. |
|||
var numbers2: array[Category, int] # Number at position N2 in each category. |
|||
echo &"For base {base}." |
|||
echo "===========\n" |
|||
var n = 1 |
|||
while true: |
|||
if n == Limit: |
|||
counts2 = counts1 |
|||
let cat = n.category(base) |
|||
inc counts1[cat] |
|||
let c = counts1[cat] |
|||
if c <= N1: |
|||
numbers1[cat][c] = n |
|||
elif c == N2: |
|||
numbers2[cat] = n |
|||
inc n |
|||
if allIt(counts1, it >= N2) and n >= Limit: break |
|||
for cat in Category.low..Category.high: |
|||
echo &"First {N1} {cat} numbers:" |
|||
for i, n in numbers1[cat]: |
|||
stdout.write &"{n:4}" |
|||
stdout.write if i mod 10 == 0: '\n' else: ' ' |
|||
echo &"\nThe {N2}th {cat} number is {numbers2[cat]}.\n" |
|||
echo &"Among numbers less than {Limit}, there are:" |
|||
for cat in Category.low..Category.high: |
|||
echo &"- {counts2[cat]} {cat} numbers." |
|||
echo '\n' |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>For base 10. |
|||
=========== |
|||
First 50 wasteful numbers: |
|||
4 6 8 9 12 18 20 22 24 26 |
|||
28 30 33 34 36 38 39 40 42 44 |
|||
45 46 48 50 51 52 54 55 56 57 |
|||
58 60 62 63 65 66 68 69 70 72 |
|||
74 75 76 77 78 80 82 84 85 86 |
|||
The 10000th wasteful number is 14346. |
|||
First 50 equidigital numbers: |
|||
1 2 3 5 7 10 11 13 14 15 |
|||
16 17 19 21 23 25 27 29 31 32 |
|||
35 37 41 43 47 49 53 59 61 64 |
|||
67 71 73 79 81 83 89 97 101 103 |
|||
105 106 107 109 111 112 113 115 118 119 |
|||
The 10000th equidigital number is 33769. |
|||
First 50 frugal numbers: |
|||
125 128 243 256 343 512 625 729 1024 1029 |
|||
1215 1250 1280 1331 1369 1458 1536 1681 1701 1715 |
|||
1792 1849 1875 2048 2187 2197 2209 2401 2560 2809 |
|||
3125 3481 3584 3645 3721 4096 4374 4375 4489 4802 |
|||
4913 5041 5103 5329 6241 6250 6561 6859 6889 7203 |
|||
The 10000th frugal number is 1953125. |
|||
Among numbers less than 1000000, there are: |
|||
- 831231 wasteful numbers. |
|||
- 165645 equidigital numbers. |
|||
- 3123 frugal numbers. |
|||
For base 11. |
|||
=========== |
|||
First 50 wasteful numbers: |
|||
4 6 8 9 10 12 18 20 22 24 |
|||
26 28 30 33 34 36 38 39 40 42 |
|||
44 45 46 48 50 51 52 54 55 56 |
|||
57 58 60 62 63 65 66 68 69 70 |
|||
72 74 75 76 77 78 80 82 84 85 |
|||
The 10000th wasteful number is 12890. |
|||
First 50 equidigital numbers: |
|||
1 2 3 5 7 11 13 14 15 16 |
|||
17 19 21 23 25 27 29 31 32 35 |
|||
37 41 43 47 49 53 59 61 64 67 |
|||
71 73 79 81 83 89 97 101 103 107 |
|||
109 113 121 122 123 127 129 131 133 134 |
|||
The 10000th equidigital number is 33203. |
|||
First 50 frugal numbers: |
|||
125 128 243 256 343 512 625 729 1024 1331 |
|||
1369 1458 1536 1681 1701 1715 1792 1849 1875 2048 |
|||
2187 2197 2209 2401 2560 2809 3072 3125 3481 3584 |
|||
3645 3721 4096 4374 4375 4489 4802 4913 5041 5103 |
|||
5120 5329 6241 6250 6561 6859 6889 7168 7203 7921 |
|||
The 10000th frugal number is 2659171. |
|||
Among numbers less than 1000000, there are: |
|||
- 795861 wasteful numbers. |
|||
- 200710 equidigital numbers. |
|||
- 3428 frugal numbers.</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |