Wasteful, equidigital and frugal numbers: Difference between revisions
Wasteful, equidigital and frugal numbers (view source)
Revision as of 15:19, 8 October 2023
, 7 months agoNew post.
(New post.) |
(New post.) |
||
Line 49:
* [[oeis: A046759|OEIS: A046759 - Economical numbers]]
<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#}}==
<syntaxhighlight lang="fsharp">
Line 66 ⟶ 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
</pre>
=={{header|J}}==
| |||