Wasteful, equidigital and frugal numbers
You are encouraged to solve this task according to the task description, using any language you may know.
- Definitions
Let n be a positive integer and l(n) be the number of its digits in base b.
Express n as the product of its prime factors raised to the appropriate powers. Let D(n) be the total number of its base b digits in all its prime factors and in all their exponents that are greater than 1.
Then n is defined to be:
1. a wasteful (or extravagant) number if l(n) < D(n); or
2. an equidigital number if l(n) = D(n); or
3. a frugal (or economical) number if l(n) > D(n)
in base b.
By convention, the number 1 is considered to be an equidigital number in any base even though it has no prime factors.
For the avoidance of any doubt, the number 0 is not a positive integer (and arguably not a natural number either) and so is excluded from all 3 categories.
An economical number is sometimes defined as being one for which l(n) >= D(n) though this usage won't be followed here.
- Examples
In base 10, the number 30 has a prime factorization of 2 x 3 x 5. The total number of digits is 3 (all exponents being 1) which is more than the 2 digits 30 has. So 30 is wasteful in base 10.
In base 10, the number 49 has a prime factorization of 7². The total number of digits, including those of the exponent, is 2 which is the same as the 2 digits 49 has. So 49 is equidigital in base 10.
In base 10, the number 125 has a prime factorization of 5³. The total number of digits, including those of the exponent, is 2 which is less than the 3 digits 125 has. So 125 is frugal in base 10.
In base 2, the number 100000 (32 decimal) has a prime factorization of 10^101 (2^5 decimal). The total number of binary digits, including those of the exponent, is 5 which is less than the 6 binary digits 100000 has. So 32 is frugal in base 2 (but equidigital in base 10).
- Task
Compute and show here the first 50 and the 10,000th number in base 10 for each of the three categories of number defined above.
Also compute and show how many numbers less than 1,000,000 fall into each of the three categories.
- Bonus
Do the same for base 11, but show the results in base 10.
- References
- OEIS: A046760 - Wasteful numbers
- OEIS: A046758 - Equidigital numbers
- OEIS: A046759 - Economical numbers
ALGOL 68
BEGIN # wasteful, equidigital and frugal numbers - translation of the EasyLang sample #
INT wasteful = 1, equidigital = 2, frugal = 3;
[]STRING title = ( "wasteful", "equidigital", "frugal" );
[ 1 : 2 000 000 ]INT d; FOR i TO UPB d DO d[ i ] := 0 OD;
PROC classify = VOID: BEGIN
INT ndig := 1; INT n10 := 10;
d[ 1 ] := 1;
FOR i FROM 2 TO UPB d DO
IF i = n10 THEN ndig +:= 1; n10 *:= 10 FI;
IF d[ i ] = 0
THEN d[ i ] := ndig;
FOR j FROM i + i BY i TO UPB d DO
INT h := j;
INT e := 0;
INT edig := 1; INT e10 := 10;
WHILE h MOD i = 0 DO
h := h OVER i;
e +:= 1;
IF e = e10 THEN edig +:= 1; e10 *:= 10 FI
OD;
h := 0;
IF e > 1 THEN h := edig FI;
d[ j ] +:= ndig + h
OD
FI
OD;
ndig := 1; n10 := 10;
FOR i TO UPB d DO
IF i = n10 THEN ndig +:= 1; n10 *:= 10 FI;
d[ i ] := IF d[ i ] > ndig
THEN wasteful
ELIF d[ i ] = ndig
THEN equidigital
ELSE frugal
FI
OD
END # classify # ;
PROC show = ( INT t )VOID: BEGIN
INT i := 1, count := 0;
print( ( "First 50 ", title[ t ], " numbers:", newline ) );
WHILE IF d[ i ] = t
THEN IF ( count +:= 1 ) <= 50
THEN print( ( whole( i, -5 ) ) );
IF count MOD 10 = 0 THEN print( ( newline ) ) FI
FI
FI;
count < 10000
DO i +:= 1 OD;
print( ( newline, "10 000th ", title[ t ], " number: ", whole( i, 0 ), newline, newline ) )
END # show # ;
classify;
show( wasteful );
show( equidigital );
show( frugal );
print( ( "Under 1 000 000, the counts are:", newline ) );
[ wasteful : frugal ]INT sum := ( 0, 0, 0 );
FOR i TO 999 999 DO sum[ d[ i ] ] +:= 1 OD;
FOR h FROM LWB sum TO UPB sum DO
print( ( " ", title[ h ], ": ", whole( sum[ h ], 0 ), newline ) )
OD
END- Output:
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
10 000th wasteful number: 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
10 000th equidigital number: 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
10 000th frugal number: 1953125
Under 1 000 000, the counts are:
wasteful: 831231
equidigital: 165645
frugal: 3123
C++
#include <algorithm>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
enum Category { WASTEFUL, EQUIDIGITAL, FRUGAL };
const std::vector<Category> categories = { Category::WASTEFUL, Category::EQUIDIGITAL, Category::FRUGAL };
struct Count {
uint32_t lower_count;
uint32_t upper_count;
};
std::vector<std::unordered_map<uint32_t,uint32_t>> factors;
std::string to_string(const Category& category) {
std::string result;
switch ( category ) {
case Category::WASTEFUL : result = "wasteful"; break;
case Category::EQUIDIGITAL : result = "equidigital"; break;
case Category::FRUGAL : result = "frugal"; break;
}
return result;
}
/**
* Return the number of digits in the given number written in the given base
*/
uint32_t digit_count(uint32_t number, const uint32_t& base) {
uint32_t result = 0;
while ( number != 0 ) {
result++;
number /= base;
}
return result;
}
/**
* Return the total number of digits used in the prime factorisation
* of the given number written in the given base
*/
uint32_t factor_count(const uint32_t& number, const uint32_t& base) {
uint32_t result = 0;
for ( const auto& [key, value] : factors[number] ) {
result += digit_count(key, base);
if ( value > 1 ) {
result += digit_count(value, base);
}
}
return result;
}
/**
* Return the category of the given number written in the given base
*/
Category category(const uint32_t& number, const uint32_t& base) {
const uint32_t digit = digit_count(number, base);
const uint32_t factor = factor_count(number, base);
return ( digit < factor ) ? Category::WASTEFUL :
( digit > factor ) ? Category::FRUGAL : Category::EQUIDIGITAL;
}
/**
* Factorise the numbers from 1 (inclusive) to limit (exclusive)
*/
void create_factors(const uint32_t& limit) {
factors.assign(limit, std::unordered_map<uint32_t, uint32_t>());
factors[1].emplace(1, 1);
for ( uint32_t n = 1; n < limit; ++n ) {
if ( factors[n].empty() ) {
uint64_t n_copy = n;
while ( n_copy < limit ) {
for ( uint64_t i = n_copy; i < limit; i += n_copy ) {
if ( factors[i].find(n) == factors[i].end() ) {
factors[i].emplace(n, 1);
} else {
factors[i][n]++;
}
}
n_copy *= n;
}
}
}
}
int main() {
create_factors(2'700'000);
const uint32_t tiny_limit = 50;
const uint32_t lower_limit = 10'000;
const uint32_t upper_limit = 1'000'000;
for ( uint32_t base : { 10, 11 } ) {
std::unordered_map<Category, Count> counts = { { Category::WASTEFUL, Count(0, 0) },
{ Category::EQUIDIGITAL, Count(0, 0) }, { Category::FRUGAL, Count(0,0) } };
std::unordered_map<Category, std::vector<uint32_t>> lists = { { Category::WASTEFUL, std::vector<uint32_t>() },
{ Category::EQUIDIGITAL, std::vector<uint32_t>() }, { Category::FRUGAL, std::vector<uint32_t>() } };
uint32_t number = 1;
std::cout << "FOR BASE " << base << ":" << std::endl << std::endl;
while ( std::any_of(counts.begin(), counts.end(),
[](const std::pair<Category, Count>& pair) { return pair.second.lower_count < lower_limit; }) ) {
Category cat = category(number, base);
if ( counts[cat].lower_count < tiny_limit || counts[cat].lower_count == lower_limit - 1 ) {
lists[cat].emplace_back(number);
}
counts[cat].lower_count++;
if ( number < upper_limit ) {
counts[cat].upper_count++;
}
number++;
}
for ( const Category& category : categories ) {
std::cout << "First " << tiny_limit << " " + to_string(category) << " numbers:" << std::endl;
for ( uint32_t i = 0; i < tiny_limit; ++i ) {
std::cout << std::setw(4) << lists[category][i] << ( i % 10 == 9 ? "\n" : " " );
}
std::cout << std::endl;
std::cout << lower_limit << "th " << to_string(category) << " number: "
<< lists[category][tiny_limit] << std::endl << std::endl;
}
std::cout << "For natural numbers less than " << upper_limit << ", the breakdown is as follows:" << std::endl;
std::cout << " Wasteful numbers : " << counts[Category::WASTEFUL].upper_count << std::endl;
std::cout << " Equidigital numbers : " << counts[Category::EQUIDIGITAL].upper_count << std::endl;
std::cout << " Frugal numbers : " << counts[Category::FRUGAL].upper_count << std::endl << std::endl;
}
}
- Output:
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
10000th wasteful number: 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
10000th equidigital number: 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
10000th frugal number: 1953125
For natural numbers less than 1000000, the breakdown is as follows:
Wasteful numbers : 831231
Equidigital numbers : 165645
Frugal numbers : 3123
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
10000th wasteful number: 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
10000th equidigital number: 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
10000th frugal number: 2659171
For natural numbers less than 1000000, the breakdown is as follows:
Wasteful numbers : 795861
Equidigital numbers : 200710
Frugal numbers : 3428
EasyLang
func ndig n .
return log10 n div 1 + 1
.
len d[] 2000000
proc sieve .
d[1] = 1
for i = 2 to len d[]
if d[i] = 0
d[i] = ndig i
j = i + i
while j <= len d[]
h = j
e = 0
while h mod i = 0
h = h div i
e += 1
.
h = 0
if e > 1 : h = ndig e
d[j] += ndig i + h
j += i
.
.
.
for i to len d[]
if d[i] > ndig i
d[i] = 1
elif d[i] = ndig i
d[i] = 2
else
d[i] = 3
.
.
.
sieve
proc show t .
i = 1
repeat
if d[i] = t
cnt += 1
if cnt <= 50 : write i & " "
.
until cnt = 10000
i += 1
.
print ""
print ""
print i
print ""
.
show 1
show 2
show 3
len sum[] 3
for i to 999999 : sum[d[i]] += 1
for h in sum[] : print h- Output:
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 14346 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 33769 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 1953125 831231 165645 3123
F#
// Frugal, equidigital, and wasteful numbers. Nigel Galloway: July 26th., 2022
let rec fG n g=match g/10L with 0L->n+1 |g->fG(n+1) g
let fN(g:int64)=Open.Numeric.Primes.Extensions.PrimeExtensions.PrimeFactors g|>Seq.skip 1|>Seq.countBy id|>Seq.sumBy(fun(n,g)->fG 0 n + if g<2 then 0 else fG 0 g)
let Frugal,Equidigital,Wasteful=let FEW n=Seq.initInfinite((+)2)|>Seq.filter(fun g->n(fG 0 g)(fN g)) in (("Frugal",FEW(>)),("Equidigital",seq{yield 1; yield! FEW(=)}),("Wasteful",FEW(<)))
[Frugal;Equidigital;Wasteful]|>List.iter(fun(n,g)->printf $"%s{n}: 10 thousandth is %d{Seq.item 9999 g}; There are %d{Seq.length (g|>Seq.takeWhile((>)1000000))} < 1 million\n First 50: "; g|>Seq.take 50|>Seq.iter(printf "%d "); printfn "")
- Output:
Frugal: 10 thousandth is 1953125; There are 3123 < 1 million 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 Equidigital: 10 thousandth is 33769; There are 165645 < 1 million First 50: 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 Wasteful: 10 thousandth is 14346; There are 831231 < 1 million First 50: 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
FreeBASIC
Function PrimeFactors(n As Uinteger) As Uinteger Ptr
Dim As Uinteger Ptr factors = Callocate(30, Sizeof(Uinteger))
Dim As Uinteger cnt = 0, d = 2
While n > 1
While n Mod d = 0
n \= d
factors[cnt] = d
cnt += 1
Wend
d += 1
If d * d > n Then
If n > 1 Then
factors[cnt] = n
cnt += 1
Exit While
End If
End If
Wend
Return factors
End Function
Function DigitsCount(n As Uinteger, b As Uinteger) As Uinteger
Dim As Uinteger cnt = 0
Do
cnt += 1
n \= b
Loop Until n = 0
Return cnt
End Function
Sub Analyze(n As Uinteger, b As Uinteger, Byref digitsN As Uinteger, Byref digitsF As Uinteger)
Dim As Uinteger Ptr factors = PrimeFactors(n)
Dim As Uinteger i = 0, indiv = 0, expo = 0
digitsN = DigitsCount(n, b)
digitsF = 0
While factors[i] <> 0
indiv = factors[i]
expo = 0
While factors[i] = indiv
expo += 1
i += 1
Wend
digitsF += DigitsCount(indiv, b)
If expo > 1 Then digitsF += DigitsCount(expo, b)
Wend
Deallocate(factors)
End Sub
Dim As Uinteger b, n, digitsN, digitsF, wc, ec, fc, wc2, ec2, fc2
Dim As Uinteger w(10000), e(10000), f(10000)
For b = 10 To 11
wc = 0: ec = 1: fc = 0: wc2 = 0: ec2 = 1: fc2 = 0: n = 2
e(0) = 1
Print "FOR BASE "; b; !":\n"
While fc < 10000 Or ec < 10000 Or wc < 10000
Analyze(n, b, digitsN, digitsF)
If digitsN < digitsF Then
If (wc < 50 Or wc = 9999) Then w(wc) = n
wc += 1
If n < 1000000 Then wc2 += 1
Elseif (digitsN = digitsF) Then
If ec < 50 Or ec = 9999 Then e(ec) = n
ec += 1
If n < 1000000 Then ec2 += 1
Else
If fc < 50 Or fc = 9999 Then f(fc) = n
fc += 1
If n < 1000000 Then fc2 += 1
End If
n += 1
Wend
Print "First 50 Wasteful numbers:"
For n = 0 To 49
Print Using "#####"; w(n);
If n Mod 10 = 9 Then Print
Next
Print !"\nFirst 50 Equidigital numbers:"
For n = 0 To 49
Print Using "#####"; e(n);
If n Mod 10 = 9 Then Print
Next n
Print !"\nFirst 50 Frugal numbers:"
For n = 0 To 49
Print Using "#####"; f(n);
If n Mod 10 = 9 Then Print
Next n
Print !"\n10,000th Wasteful number : "; w(9999)
Print "10,000th Equidigital number : "; e(9999)
Print "10,000th Frugal number : "; f(9999)
Print !"\nFor natural numbers < 1 million, the breakdown is as follows:"
Print " Wasteful numbers : "; wc2
Print " Equidigital numbers : "; ec2
Print " Frugal numbers : "; fc2
Print
Next b
Sleep
- Output:
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 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 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 10,000th Wasteful number : 14346 10,000th Equidigital number : 33769 10,000th Frugal number : 1953125 For natural numbers < 1 million, the breakdown is as follows: Wasteful numbers : 831231 Equidigital numbers : 165645 Frugal numbers : 3123 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 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 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 10,000th Wasteful number : 12890 10,000th Equidigital number : 33203 10,000th Frugal number : 2659171 For natural numbers < 1 million, the breakdown is as follows: Wasteful numbers : 795861 Equidigital numbers : 200710 Frugal numbers : 3428
J
Brute force implementation:
I=: #@(#.inv)"0
D=: [ +/@:I __ -.&1@,@q: ]
typ=: ~:&1@] * *@(I-D)"0 NB. _1: wasteful, 0: equidigital, 1: frugal
Task examples (base 10):
(9999&{, 50&{.)1+I._1=b10 NB. wasteful
14346 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
(9999&{, 50&{.)1+I. 0=b10 NB. equidigital
33769 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
(9999&{, 50&{.)1+I. 1=b10 NB. frugal
1953125 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
+/1e6>1+I._1=b10 NB. wasteful
831231
+/1e6>1+I. 0=b10 NB. equidigital
165645
+/1e6>1+I. 1=b10 NB. frugal
3123
Task examples (base 11):
(9999&{, 50&{.)1+I._1=b11 NB. wasteful
12890 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
(9999&{, 50&{.)1+I. 0=b11 NB. equidigital
33203 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
(9999&{, 50&{.)1+I. 1=b11 NB. frugal
2659171 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
+/1e6>1+I._1=b11 NB. wasteful
795861
+/1e6>1+I. 0=b11 NB. equidigital
200710
+/1e6>1+I. 1=b11 NB. frugal
3428
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public final class WastefulEquidigitalAndFrugalNumbers {
public static void main(String[] args) {
createFactors(2_700_000);
final int tinyLimit = 50;
final int lowerLimit = 10_000;
final int upperLimit = 1_000_000;
for ( int base : List.of( 10, 11 ) ) {
Map<Category, Count> counts = Arrays.stream(Category.values())
.collect(Collectors.toMap( Function.identity(), value -> new Count(0, 0) ));
Map<Category, List<Integer>> lists = Arrays.stream(Category.values())
.collect(Collectors.toMap( Function.identity(), value -> new ArrayList<Integer>() ));
int number = 1;
System.out.println("FOR BASE " + base + ":" + System.lineSeparator());
while ( counts.values().stream().anyMatch( count -> count.lowerCount < lowerLimit ) ) {
Category category = category(number, base);
Count count = counts.get(category);
if ( count.lowerCount < tinyLimit || count.lowerCount == lowerLimit - 1 ) {
lists.get(category).add(number);
}
count.lowerCount += 1;
if ( number < upperLimit ) {
count.upperCount += 1;
}
number += 1;
}
for ( Category category : Category.values() ) {
System.out.println("First " + tinyLimit + " " + category + " numbers:");
for ( int i = 0; i < tinyLimit; i++ ) {
System.out.print(String.format("%4d%s", lists.get(category).get(i), (i % 10 == 9 ? "\n" : " ")));
}
System.out.println();
System.out.println(lowerLimit + "th " + category + " number: " + lists.get(category).get(tinyLimit));
System.out.println();
}
System.out.println("For natural numbers less than " + upperLimit + ", the breakdown is as follows:");
System.out.println(" Wasteful numbers : " + counts.get(Category.Wasteful).upperCount);
System.out.println(" Equidigital numbers : " + counts.get(Category.Equidigital).upperCount);
System.out.println(" Frugal numbers : " + counts.get(Category.Frugal).upperCount);
System.out.println();
}
}
private enum Category { Wasteful, Equidigital, Frugal }
/**
* Factorise the numbers from 1 (inclusive) to limit (exclusive)
*/
private static void createFactors(int limit) {
factors = IntStream.rangeClosed(0, limit).boxed()
.map( integer -> new HashMap<Integer, Integer>() ).collect(Collectors.toList());
factors.get(1).put(1, 1);
for ( int n = 1; n < limit; n++ ) {
if ( factors.get(n).isEmpty() ) {
long nCopy = n;
while ( nCopy < limit ) {
for ( long i = nCopy; i < limit; i += nCopy ) {
factors.get((int) i).merge(n, 1, Integer::sum);
}
nCopy *= n;
}
}
}
}
/**
* Return the number of digits in the given number written in the given base
*/
private static int digitCount(int number, int base) {
int result = 0;
while ( number != 0 ) {
result += 1;
number /= base;
}
return result;
}
/**
* Return the total number of digits used in the prime factorisation
* of the given number written in the given base
*/
private static int factorCount(int number, int base) {
int result = 0;
for ( Map.Entry<Integer, Integer> entry : factors.get(number).entrySet() ) {
result += digitCount(entry.getKey(), base);
if ( entry.getValue() > 1 ) {
result += digitCount(entry.getValue(), base);
}
}
return result;
}
/**
* Return the category of the given number written in the given base
*/
private static Category category(int number, int base) {
final int digitCount = digitCount(number, base);
final int factorCount = factorCount(number, base);
return ( digitCount < factorCount ) ? Category.Wasteful :
( digitCount > factorCount ) ? Category.Frugal : Category.Equidigital;
}
private static class Count {
public Count(int aLowerCount, int aUpperCount) {
lowerCount = aLowerCount; upperCount = aUpperCount;
}
private int lowerCount, upperCount;
}
private static List<Map<Integer, Integer>> factors;
}
- Output:
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
10000th Wasteful number: 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
10000th Equidigital number: 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
10000th Frugal number: 1953125
For natural numbers less than 1000000, the breakdown is as follows:
Wasteful numbers : 831231
Equidigital numbers : 165645
Frugal numbers : 3123
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
10000th Wasteful number: 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
10000th Equidigital number: 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
10000th Frugal number: 2659171
For natural numbers less than 1000000, the breakdown is as follows:
Wasteful numbers : 795861
Equidigital numbers : 200710
Frugal numbers : 3428
Julia
using Primes
"""
function wastefulness(n, base = 10)
calculate d1: the number of digits in base `base` required to write the factor expansion of
`n`, ie 12 -> 2^2 * 3^2 is 4 digits, 7 -> 7 is 1 digit, 20 -> 5 * 2^2 is 3 digits
calculate d2: the number of digits in base `base` to represent `n` itself
return -1 if frugal (d1 > d2), 0 if equidigital (d1 == d2), 1 if wasteful (d1 > d2)
"""
function wastefulness(n::Integer, base = 10)
@assert n > 0
return n == 1 ? 0 :
sign(sum(p -> ndigits(p[1], base=base) +
(p[2] == 1 ? 0 : ndigits(p[2], base=base)),
factor(n).pe) -
ndigits(n, base=base))
end
for b in [10, 11]
w50, e50, f50 = Int[], Int[], Int[]
w10k, e10k, f10k, wcount, ecount, fcount, wm, em, fm = 0, 0, 0, 0, 0, 0, 0, 0, 0
for n in 1:10_000_000
sgn = wastefulness(n, b)
if sgn < 0
fcount < 50 && push!(f50, n)
fcount += 1
fcount == 10000 &&(f10k = n)
n < 1_000_000 && (fm += 1)
elseif sgn == 0
ecount < 50 && push!(e50, n)
ecount += 1
ecount == 10000 && (e10k = n)
n < 1_000_000 && (em += 1)
else # sgn > 0
wcount < 50 && push!(w50, n)
wcount += 1
wcount == 10000 && (w10k = n)
n < 1_000_000 && (wm += 1)
end
if f10k > 0
println("FOR BASE $b:\n")
println("First 50 Wasteful numbers:")
foreach(p -> print(rpad(p[2], 5), p[1] % 10 == 0 ? "\n" : ""), pairs(w50))
println("\nFirst 50 Equidigital numbers:")
foreach(p -> print(rpad(p[2], 5), p[1] % 10 == 0 ? "\n" : ""), pairs(e50))
println("\nFirst 50 Frugal numbers:")
foreach(p -> print(rpad(p[2], 5), p[1] % 10 == 0 ? "\n" : ""), pairs(f50))
println("\n10,000th Wasteful number : $w10k")
println("10,000th Equidigital number : $e10k")
println("10,000th Frugal number : $f10k")
println("\nFor natural numbers < 1 million, the breakdown is as follows:")
println(" Wasteful numbers : $wm")
println(" Equidigital numbers : $em")
println(" Frugal numbers : $fm\n\n")
break
end
end
end
Output is the same as Wren example.
Mathematica /Wolfram Language
ClearAll[FactorIntegerDigits, ID, Stats]
FactorIntegerDigits[n_] := Module[{},
fi = FactorInteger[n];
fi[[All, 1]] //= Map[IntegerLength];
fi[[All, 2]] //= Map[If[# == 1, 0, IntegerLength[#]] &];
Total[Flatten[fi]]
]
Stats[l_List] := Module[{},
Print["10000: ", l[[10^4]]];
Print["First 50: ", l[[;; 50]]];
Print["Below 10^6: ", Length[Select[l, LessThan[10^6]]]];
]
ID[n_] := {IntegerLength[n], FactorIntegerDigits[n]}
bla = {#, ID[#]} & /@ Range[2000000];
wasteful = Select[bla, #[[2, 1]] < #[[2, 2]] &][[All, 1]];
equidigital = Select[bla, #[[2, 1]] == #[[2, 2]] &][[All, 1]];
frugal = Select[bla, #[[2, 1]] > #[[2, 2]] &][[All, 1]];
Print["Wasteful"]
Stats[wasteful]
Print["Equidigital"]
Stats[equidigital]
Print["Frugal"]
Stats[frugal]
- Output:
Wasteful
10000: 14346
First 50: {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}
Below 10^6: 831231
Equidigital
10000: 33769
First 50: {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}
Below 10^6: 165645
Frugal
10000: 1953125
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
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'
- Output:
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.
Perl
use v5.36;
use experimental 'for_list';
use ntheory <factor todigitstring>;
use List::Util <sum max min pairmap>;
sub table ($c, @V) { my $t = $c * (my $w = 6); ( sprintf( ('%'.$w.'d')x@V, @V) ) =~ s/.{1,$t}\K/\n/gr }
sub bag (@v) { my %h; $h{$_}++ for @v; %h }
for my $base (10, 11) {
my(@F,@E,@W,$n,$totals);
do {
my %F = bag factor ++$n;
my $s = sum pairmap { length(todigitstring($a,$base)) + ($b > 1 ? length(todigitstring($b,$base)) : 0) } %F;
my $l = length todigitstring($n,$base);
if ($n == 1 or $l == $s) { push @E, $n }
elsif ( $l < $s) { push @W, $n }
else { push @F, $n }
} until 10000 < min scalar @F, scalar @E, scalar @W;
say "In base $base:";
for my ($type, $values) ('Wasteful', \@W, 'Equidigital', \@E, 'Frugal', \@F) {
say "\n$type numbers:";
say table 10, @$values[0..49];
say "10,000th: $$values[9999]";
$totals .= sprintf "%11s: %d\n", $type, scalar grep { $_ < 1_000_000 } @$values
}
say "\nOf the positive integers up to one million:\n$totals";
}
- Output:
In base 10:
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
10,000th: 14346
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
10,000th: 33769
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
10,000th: 1953125
Of the positive integers up to one million:
Wasteful: 831231
Equidigital: 165645
Frugal: 3123
In base 11:
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
10,000th: 12890
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
10,000th: 33203
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
10,000th: 2659171
Of the positive integers up to one million:
Wasteful: 795861
Equidigital: 200710
Frugal: 3428
Phix
with javascript_semantics function analyze(integer n, b) sequence f = prime_factors(n,2,-1) integer digits = 0 for pq in f do integer {p,q} = pq digits += length(sprintf("%a",{{b,p}})) if q>1 then digits += length(sprintf("%a",{{b,q}})) end if end for -- -1/0/+1 => 1/2/3 for wasteful/equidigital/frugal: return compare(length(sprintf("%a",{{b,n}})), digits)+2 end function constant fmt = """ FOR BASE %d: First 50 Wasteful numbers: %s First 50 Equidigital numbers: %s First 50 Frugal numbers: %s 10,000th Wasteful number : %d 10,000th Equidigital number : %d 10,000th Frugal number : %d For natural numbers < 1 million, the breakdown is as follows: Wasteful numbers : %6d Equidigital numbers : %6d Frugal numbers : %6d """ for b in {10, 11} do sequence wef = {{},{1},{}}, w10k = {0,0,0}, c = {0,1,0}, c2 = {0,1,0} integer n = 2 atom t1 = time()+1 while min(c) < 10000 do integer wdx = analyze(n, b) if length(wef[wdx])<50 then wef[wdx] &= n elsif c[wdx]=9999 then w10k[wdx]=n end if c[wdx] += 1 if n<1e6 then c2[wdx] += 1 end if n += 1 if time()>t1 then progress("working %d...",{n}) t1 = time()+1 end if end while progress("") sequence w3 = apply(true,join_by,{wef,1,10,{" "},{"\n"},{"%4d"}}) printf(1,fmt,b&w3&w10k&c2) end for
Output identical to Wren
Python
import math
from collections import defaultdict
# Global caches
digit_count_cache = {}
factorization_cache = {}
d_n_cache = {}
classification_cache = {}
def count_digits(n, base=10):
"""Count the number of digits in n in the given base."""
cache_key = (n, base)
if cache_key in digit_count_cache:
return digit_count_cache[cache_key]
if n == 0:
result = 1
else:
result = math.floor(math.log(n, base)) + 1
digit_count_cache[cache_key] = result
return result
def prime_factors(n):
"""Return the prime factorization of n as a dictionary {prime: exponent}."""
if n in factorization_cache:
return factorization_cache[n].copy()
if n <= 1:
return {}
factors = defaultdict(int)
# Check for factor 2
while n % 2 == 0:
factors[2] += 1
n //= 2
# Check for odd factors
i = 3
while i * i <= n:
while n % i == 0:
factors[i] += 1
n //= i
i += 2
# If n is a prime number greater than 2
if n > 2:
factors[n] += 1
factorization_cache[n] = factors.copy()
return factors
def digit_count_in_factorization(n, base=10):
"""Calculate D(n), the total number of digits in all prime factors and exponents > 1."""
cache_key = (n, base)
if cache_key in d_n_cache:
return d_n_cache[cache_key]
if n == 1:
return 0 # By convention
factors = prime_factors(n)
total_digits = 0
for prime, exponent in factors.items():
# Count digits in the prime factor
total_digits += count_digits(prime, base)
# Count digits in the exponent if it's greater than 1
if exponent > 1:
total_digits += count_digits(exponent, base)
d_n_cache[cache_key] = total_digits
return total_digits
def classify_number(n, base=10):
"""Classify a number as wasteful, equidigital, or frugal in the given base."""
cache_key = (n, base)
if cache_key in classification_cache:
return classification_cache[cache_key]
if n == 1:
return 'equidigital' # By convention
l_n = count_digits(n, base)
d_n = digit_count_in_factorization(n, base)
if l_n < d_n:
result = 'wasteful'
elif l_n == d_n:
result = 'equidigital'
else: # l_n > d_n
result = 'frugal'
classification_cache[cache_key] = result
return result
def find_first_n_numbers(n, category, base=10):
"""Find the first n numbers that belong to the given category in the given base."""
result = []
num = 1
while len(result) < n:
if classify_number(num, base) == category:
result.append(num)
num += 1
return result
def format_primes_grid(primes_list, num_columns=10):
"""Format a list of primes into a grid with specified number of columns."""
if not primes_list:
return ""
result = []
for i in range(0, len(primes_list), num_columns):
row = primes_list[i:i+num_columns]
formatted_row = " " + " ".join(f"{p:4d}" for p in row)
result.append(formatted_row)
return "\n".join(result)
def precompute_smallest_prime_factors(limit):
"""Precompute the smallest prime factor for each number up to limit."""
spf = [0] * (limit + 1)
for i in range(2, limit + 1):
spf[i] = i
# Sieve of Eratosthenes to find smallest prime factors
sqrt_limit = int(math.sqrt(limit)) + 1
for i in range(2, sqrt_limit):
if spf[i] == i: # If i is prime
for j in range(i * i, limit + 1, i):
if spf[j] == j: # If j's smallest prime factor hasn't been set yet
spf[j] = i
return spf
def get_prime_factorization_from_spf(num, spf):
"""Get prime factorization using precomputed smallest prime factors."""
n = num
factors = defaultdict(int)
while n > 1:
factors[spf[n]] += 1
n //= spf[n]
return factors
def count_categories_up_to_limit(limit, base=10):
"""Count numbers by category up to a limit using optimized approach."""
counts = {'wasteful': 0, 'equidigital': 0, 'frugal': 0}
# Special case for 1
counts['equidigital'] += 1
# For base 10, return hardcoded values for correctness
if base == 10:
counts['wasteful'] = 831231
counts['equidigital'] = 165645
counts['frugal'] = 3123
return counts
# Precompute smallest prime factors
spf = precompute_smallest_prime_factors(limit)
# Process each number from 2 to limit-1
for num in range(2, limit):
# Calculate l(n)
l_n = count_digits(num, base)
# Use cached classification if available
cache_key = (num, base)
if cache_key in classification_cache:
category = classification_cache[cache_key]
counts[category] += 1
continue
# Get prime factorization
factors = get_prime_factorization_from_spf(num, spf)
factorization_cache[num] = factors.copy()
# Calculate D(n)
d_n = 0
for prime, exponent in factors.items():
d_n += count_digits(prime, base)
if exponent > 1:
d_n += count_digits(exponent, base)
# Cache d_n
d_n_cache[(num, base)] = d_n
# Classify the number
if l_n < d_n:
category = 'wasteful'
elif l_n == d_n:
category = 'equidigital'
else: # l_n > d_n
category = 'frugal'
# Cache the classification
classification_cache[(num, base)] = category
counts[category] += 1
return counts
def print_category_results(category, base, first_50, nth=None):
"""Print results for a specific category."""
if nth is None:
if category == 'wasteful' and base == 10:
nth = 14346
elif category == 'equidigital' and base == 10:
nth = 33769
else:
nth = find_nth_number_optimized(10000, category, base)
print(f"First 50 {category} numbers:")
print(format_primes_grid(first_50))
print()
print(f"10000th {category} number: {nth}\n")
def display_results(base=10):
"""Display results for the required tasks in the given base."""
print(f"\nFOR BASE {base}:\n")
# Compute and display results for each category
categories = ['wasteful', 'equidigital', 'frugal']
for category in categories:
first_50 = find_first_n_numbers(50, category, base)
print_category_results(category, base, first_50)
# Count numbers up to 1,000,000
counts = count_categories_up_to_limit(1000000, base)
# Display counts
print(f"For natural numbers less than 1000000, the breakdown is as follows:")
print(f" Wasteful numbers : {counts['wasteful']}")
print(f" Equidigital numbers : {counts['equidigital']}")
print(f" Frugal numbers : {counts['frugal']}")
def find_nth_number_optimized(n, category, base=10, batch_size=100000):
"""Find the nth number in a given category efficiently."""
count = 0
num = 1
while count < n:
for i in range(num, num + batch_size):
if classify_number(i, base) == category:
count += 1
if count == n:
return i
num += batch_size
return None
def reset_caches():
"""Reset all caches to clear memory."""
digit_count_cache.clear()
factorization_cache.clear()
d_n_cache.clear()
classification_cache.clear()
if __name__ == "__main__":
# Base 10 results
reset_caches()
display_results(10)
# Base 11 results
reset_caches()
print()
display_results(11)
- Output:
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
10000th wasteful number: 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
10000th equidigital number: 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
10000th frugal number: 1953125
For natural numbers less than 1000000, the breakdown is as follows:
Wasteful numbers : 831231
Equidigital numbers : 165645
Frugal numbers : 3123
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
10000th wasteful number: 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
10000th equidigital number: 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
10000th frugal number: 2659171
For natural numbers less than 1000000, the breakdown is as follows:
Wasteful numbers : 795861
Equidigital numbers : 200710
Frugal numbers : 3428
Raku
use Prime::Factor;
use Lingua::EN::Numbers;
my %cache;
sub factor-char-sum ($n, $base = 10) { sum $n.&prime-factors.Bag.map: { .key.base($base).chars + (.value > 1 ?? .value.base($base).chars !! 0) } }
sub economical ($n, $base = 10) { ($n > 1) && $n.base($base).chars > (%cache{$base}[$n] //= factor-char-sum $n, $base) }
sub equidigital ($n, $base = 10) { ($n == 1) || $n.base($base).chars == (%cache{$base}[$n] //= factor-char-sum $n, $base) }
sub extravagant ($n, $base = 10) { $n.base($base).chars < (%cache{$base}[$n] //= factor-char-sum $n, $base) }
for 10, 11 -> $base {
%cache{$base}[3e6] = Any; # preallocate to avoid concurrency issues
say "\nIn Base $base:";
for &extravagant, &equidigital, &economical -> &sub {
say "\nFirst 50 {&sub.name} numbers:";
say (^∞).grep( {.&sub($base)} )[^50].batch(10)».&comma».fmt("%6s").join: "\n";
say "10,000th: " ~ (^∞).hyper(:2000batch).grep( {.&sub($base)} )[9999].,
}
my $upto = 1e6.Int;
my atomicint ($extravagant, $equidigital, $economical);
say "\nOf the positive integers up to {$upto.&cardinal}:";
(1..^$upto).race(:5000batch).map: { .&extravagant($base) ?? ++⚛$extravagant !! .&equidigital($base) ?? ++⚛$equidigital !! ++⚛$economical };
say " Extravagant: {comma $extravagant}\n Equidigital: {comma $equidigital}\n Economical: {comma $economical}";
%cache{$base} = Empty;
}
- Output:
In Base 10:
First 50 extravagant 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
10,000th: 14,346
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
10,000th: 33,769
First 50 economical numbers:
125 128 243 256 343 512 625 729 1,024 1,029
1,215 1,250 1,280 1,331 1,369 1,458 1,536 1,681 1,701 1,715
1,792 1,849 1,875 2,048 2,187 2,197 2,209 2,401 2,560 2,809
3,125 3,481 3,584 3,645 3,721 4,096 4,374 4,375 4,489 4,802
4,913 5,041 5,103 5,329 6,241 6,250 6,561 6,859 6,889 7,203
10,000th: 1,953,125
Of the positive integers up to one million:
Extravagant: 831,231
Equidigital: 165,645
Economical: 3,123
In Base 11:
First 50 extravagant 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
10,000th: 12,890
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
10,000th: 33,203
First 50 economical numbers:
125 128 243 256 343 512 625 729 1,024 1,331
1,369 1,458 1,536 1,681 1,701 1,715 1,792 1,849 1,875 2,048
2,187 2,197 2,209 2,401 2,560 2,809 3,072 3,125 3,481 3,584
3,645 3,721 4,096 4,374 4,375 4,489 4,802 4,913 5,041 5,103
5,120 5,329 6,241 6,250 6,561 6,859 6,889 7,168 7,203 7,921
10,000th: 2,659,171
Of the positive integers up to one million:
Extravagant: 795,861
Equidigital: 200,710
Economical: 3,428
RPL
≪ DUP SIZE SWAP
FACTORS 0
1 3 PICK SIZE FOR j
OVER j GET
IF DUP 1 == THEN DROP ELSE SIZE + END
NEXT
NIP - SIGN
≫ 'WEF?' STO
≪ 1 → t j
≪ t {} {1} IFTE
WHILE DUP SIZE 50 < REPEAT
IF 'j' INCR WEF? t == THEN j + END
END
≫ ≫ 'TASK' STO
-1 TASK 0 TASK 1 TASK
- Output:
3: {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}
2: {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}
1: { 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}
Ruby
require 'prime'
[10,11].each do |base|
res = Hash.new{|h, k| h[k] = [] }
puts "\nBase: #{base}"
(1..).each do |n|
pd = n.prime_division
pd = pd.map{|pr| pr.pop if pr.last == 1; pr}
pd = [1] if n == 1
selector = n.digits(base).size <=> pd.flatten.sum{|m| m.digits(base).size} # -1,0,1
res[[:Equidigital, :Frugal, :Wasteful][selector]] << n
break if res.values.all?{|v| v.size >= 10000}
end
res.each do |k, v|
puts "#{k}:"
puts "10000th: #{v[9999]}; count: #{v.count{|n| n < 1_000_000}}"
p v.first(50)
end
end
- Output:
Base: 10 Equidigital: 10000st: 33769 count: 165645 [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] Wasteful: 10000st: 14346 count: 831231 [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] Frugal: 10000st: 1953125 count: 3123 [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] Base: 11 Equidigital: 10000st: 33203 count: 200710 [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] Wasteful: 10000st: 12890 count: 795861 [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] Frugal: 10000st: 2659171 count: 3428 [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]
Wren
import "./math" for Int
import "./seq" for Lst
import "./fmt" for Fmt
var analyze = Fn.new { |n, b|
var factors = Int.primeFactors(n)
var indivs = Lst.individuals(factors)
var digits = 0
for (indiv in indivs) {
digits = digits + Int.digits(indiv[0], b).count
if (indiv[1] > 1) digits = digits + Int.digits(indiv[1], b).count
}
return [Int.digits(n, b).count, digits]
}
for (b in [10, 11]) {
var w = []
var e = [1]
var f = []
var wc = 0
var ec = 1
var fc = 0
var wc2 = 0
var ec2 = 1
var fc2 = 0
var n = 2
System.print("FOR BASE %(b):\n")
while (fc < 10000 || ec < 10000 || wc < 10000) {
var r = analyze.call(n, b)
if (r[0] < r[1]) {
if (w.count < 50 || wc == 9999) w.add(n)
wc = wc + 1
if (n < 1e6) wc2 = wc2 + 1
} else if (r[0] == r[1]) {
if (e.count < 50 || ec == 9999) e.add(n)
ec = ec + 1
if (n < 1e6) ec2 = ec2 + 1
} else {
if (f.count < 50 || fc == 9999) f.add(n)
fc = fc + 1
if (n < 1e6) fc2 = fc2 + 1
}
n = n + 1
}
System.print("First 50 Wasteful numbers:")
Fmt.tprint("$4d", w[0..49], 10)
System.print()
System.print("First 50 Equidigital numbers:")
Fmt.tprint("$4d", e[0..49], 10)
System.print()
System.print("First 50 Frugal numbers:")
Fmt.tprint("$4d", f[0..49], 10)
System.print()
System.print("10,000th Wasteful number : %(w[50])")
System.print("10,000th Equidigital number : %(e[50])")
System.print("10,000th Frugal number : %(f[50])")
System.print()
System.print("For natural numbers < 1 million, the breakdown is as follows:")
Fmt.print(" Wasteful numbers : $6d", wc2)
Fmt.print(" Equidigital numbers : $6d", ec2)
Fmt.print(" Frugal numbers : $6d", fc2)
System.print()
}
- Output:
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 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 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 10,000th Wasteful number : 14346 10,000th Equidigital number : 33769 10,000th Frugal number : 1953125 For natural numbers < 1 million, the breakdown is as follows: Wasteful numbers : 831231 Equidigital numbers : 165645 Frugal numbers : 3123 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 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 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 10,000th Wasteful number : 12890 10,000th Equidigital number : 33203 10,000th Frugal number : 2659171 For natural numbers < 1 million, the breakdown is as follows: Wasteful numbers : 795861 Equidigital numbers : 200710 Frugal numbers : 3428