Wasteful, equidigital and frugal numbers: Difference between revisions
Content added Content deleted
(New post.) |
(New post.) |
||
Line 49: | Line 49: | ||
* [[oeis: A046759|OEIS: A046759 - Economical numbers]] |
* [[oeis: A046759|OEIS: A046759 - Economical numbers]] |
||
<br><br> |
<br><br> |
||
=={{header|C++}}== |
|||
<syntaxhighlight lang="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; |
|||
} |
|||
} |
|||
</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 |
|||
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 |
|||
</pre> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
<syntaxhighlight lang="fsharp"> |
<syntaxhighlight lang="fsharp"> |
||
Line 66: | Line 274: | ||
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 |
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 |
||
</pre> |
</pre> |
||
=={{header|J}}== |
=={{header|J}}== |
||