Jordan-Pólya numbers: Difference between revisions
New post.
m (Minor improvements to code.) |
(New post.) |
||
Line 217:
The 3,800th Jordan-Pólya number is : 7,213,895,789,838,336
= (4!)⁸ x (2!)¹⁶
</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <vector>
const int64_t LIMIT = pow(2, 53);
std::set<int64_t> jordan_polya_set;
std::unordered_map<int64_t, std::map<int32_t, int32_t>> decompositions;
std::string toString(const std::map<int32_t, int32_t>& a_map) {
std::string result;
for ( const auto& [key, value] : a_map ) {
result = std::to_string(key) + "!" + ( value == 1 ? "" : "^" + std::to_string(value) ) + " * " + result;
}
return result.substr(0, result.length() - 3);
}
std::vector<int64_t> set_to_vector(const std::set<int64_t>& a_set) {
std::vector<int64_t> result;
result.reserve(a_set.size());
for ( const int64_t& element : a_set ) {
result.emplace_back(element);
}
return result;
}
void insert_or_update(std::map<int32_t, int32_t>& map, const int32_t& entry) {
if ( map.find(entry) == map.end() ) {
map.emplace(entry, 1);
} else {
map[entry]++;
}
}
void create_jordan_polya() {
jordan_polya_set.emplace(1);
decompositions[1] = std::map<int32_t, int32_t>();
int64_t factorial = 1;
for ( int32_t multiplier = 2; multiplier <= 20; ++multiplier ) {
factorial *= multiplier;
for ( int64_t number : jordan_polya_set ) {
while ( number <= LIMIT / factorial ) {
int64_t original = number;
number *= factorial;
jordan_polya_set.emplace(number);
decompositions[number] = decompositions[original];
insert_or_update(decompositions[number], multiplier);
}
}
}
}
int main() {
create_jordan_polya();
std::vector<int64_t> jordan_polya = set_to_vector(jordan_polya_set);
std::cout << "The first 50 Jordan-Polya numbers:" << std::endl;
for ( int64_t i = 0; i < 50; ++i ) {
std::cout << std::setw(5) << jordan_polya[i] << ( i % 10 == 9 ? "\n" : "" );
}
const std::vector<int64_t>::iterator hundred_million =
std::lower_bound(jordan_polya.begin(), jordan_polya.end(), 100'000'000);
std::cout << "\n" << "The largest Jordan-Polya number less than 100 million: "
<< jordan_polya[(hundred_million - jordan_polya.begin() - 1)] << std::endl << std::endl;
for ( int32_t i : { 800, 1050, 1800, 2800, 3800 } ) {
std::cout << "The " << i << "th Jordan-Polya number is: " << jordan_polya[i - 1]
<< " = " << toString(decompositions[jordan_polya[i - 1]]) << std::endl;
}
}
</syntaxhighlight>
{{ out }}
<pre>
The first 50 Jordan-Polya numbers:
1 2 4 6 8 12 16 24 32 36
48 64 72 96 120 128 144 192 216 240
256 288 384 432 480 512 576 720 768 864
960 1024 1152 1296 1440 1536 1728 1920 2048 2304
2592 2880 3072 3456 3840 4096 4320 4608 5040 5184
The largest Jordan-Polya number less than 100 million: 99532800
The 800th Jordan-Polya number is: 18345885696 = 4!^7 * 2!^2
The 1050th Jordan-Polya number is: 139345920000 = 8! * 5!^3 * 2!
The 1800th Jordan-Polya number is: 9784472371200 = 6!^2 * 4!^2 * 2!^15
The 2800th Jordan-Polya number is: 439378587648000 = 14! * 7!
The 3800th Jordan-Polya number is: 7213895789838336 = 4!^8 * 2!^16
</pre>
| |||