Jordan-Pólya numbers: Difference between revisions
Content added Content deleted
m (Minor improvements to code.) |
(New post.) |
||
Line 217: | Line 217: | ||
The 3,800th Jordan-Pólya number is : 7,213,895,789,838,336 |
The 3,800th Jordan-Pólya number is : 7,213,895,789,838,336 |
||
= (4!)⁸ x (2!)¹⁶ |
= (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> |
</pre> |
||