Rosetta Code

Jordan-Pólya numbers: Difference between revisions

Page Discussion

Jordan-Pólya numbers (view source)

Revision as of 19:11, 29 March 2024

35,349 bytes added ,  2 months ago
m
→‎{{header|EasyLang}}
(→‎{{header|Free Pascal}}: Convert using Uint64. misinterpretate 2^53 with 1E53 tse tse tse...)
 
(22 intermediate revisions by 9 users not shown)
Line 1:
{{draft task}}
 
'''Jordan-Pólya numbers''' (or '''J-P numbers''' for short) are the numbers that can be obtained by multiplying together one or more (not necessarily distinct) factorials.
Line 218:
= (4!)⁸ x (2!)¹⁶
</pre>
 
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
using System.Collections.Generic;
using System.Linq;
 
public class JordanPolyaNumbers
{
private static SortedSet<long> jordanPolyaSet = new SortedSet<long>();
private static Dictionary<long, SortedDictionary<int, int>> decompositions = new Dictionary<long, SortedDictionary<int, int>>();
 
public static void Main(string[] args)
{
CreateJordanPolya();
 
long belowHundredMillion = jordanPolyaSet.LastOrDefault(x => x < 100_000_000L);
List<long> jordanPolya = new List<long>(jordanPolyaSet);
 
Console.WriteLine("The first 50 Jordan-Polya numbers:");
for (int i = 0; i < 50; i++)
{
Console.Write($"{jordanPolya[i],5}{(i % 10 == 9 ? "\n" : "")}");
}
Console.WriteLine();
 
Console.WriteLine("The largest Jordan-Polya number less than 100 million: " + belowHundredMillion);
Console.WriteLine();
 
foreach (int i in new List<int> { 800, 1050, 1800, 2800, 3800 })
{
Console.WriteLine($"The {i}th Jordan-Polya number is: {jordanPolya[i - 1]} = {ToString(decompositions[jordanPolya[i - 1]])}");
}
}
 
private static void CreateJordanPolya()
{
jordanPolyaSet.Add(1L);
SortedSet<long> nextSet = new SortedSet<long>();
decompositions[1L] = new SortedDictionary<int, int>();
long factorial = 1;
 
for (int multiplier = 2; multiplier <= 20; multiplier++)
{
factorial *= multiplier;
foreach (long number in new SortedSet<long>(jordanPolyaSet))
{
long newNumber = number;
while (newNumber <= long.MaxValue / factorial)
{
long original = newNumber;
newNumber *= factorial;
nextSet.Add(newNumber);
 
decompositions[newNumber] = new SortedDictionary<int, int>(decompositions[original]);
if (decompositions[newNumber].ContainsKey(multiplier))
{
decompositions[newNumber][multiplier]++;
}
else
{
decompositions[newNumber][multiplier] = 1;
}
}
}
jordanPolyaSet.UnionWith(nextSet);
nextSet.Clear();
}
}
 
private static string ToString(SortedDictionary<int, int> map)
{
string result = "";
foreach (int key in map.Keys)
{
result = key + "!" + (map[key] == 1 ? "" : "^" + map[key]) + " * " + result;
}
return result.TrimEnd(' ', '*');
}
}
</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>
 
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <vector>
 
constexpr int64_t LIMIT = static_cast<uint64_t>(1) << 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>
 
=={{header|Dart}}==
{{trans|Java}}
<syntaxhighlight lang="Dart">
import "dart:collection";
import "dart:io";
 
void main() {
createJordanPolya();
 
final belowHundredMillion = jordanPolyaSet.lastWhere((element) => element <= 100000000, orElse: () => null);
List<int> jordanPolya = jordanPolyaSet.toList();
 
print("The first 50 Jordan-Polya numbers:");
for (int i = 0; i < 50; i++) {
// Right-align each number in a 5-character wide space
stdout.write(jordanPolya[i].toString().padLeft(5));
if (i % 10 == 9) {
print(""); // Newline every 10 numbers
}
}
print("");
 
print("The largest Jordan-Polya number less than 100 million: ${belowHundredMillion ?? 'Not found'}");
print("");
 
for (int i in [800, 1050, 1800, 2800, 3800]) {
var decomposition = decompositions[jordanPolya[i - 1]];
if (decomposition != null) {
print("The ${i}th Jordan-Polya number is: ${jordanPolya[i - 1]} = ${mapToString(decomposition)}");
}
}
}
 
SplayTreeSet<int> jordanPolyaSet = SplayTreeSet<int>();
Map<int, Map<int, int>> decompositions = {};
 
void createJordanPolya() {
jordanPolyaSet.add(1);
Set<int> nextSet = SplayTreeSet<int>();
decompositions[1] = {};
int factorial = 1;
 
for (int multiplier = 2; multiplier <= 20; multiplier++) {
factorial *= multiplier;
for (int number in jordanPolyaSet) {
int tempNumber = number;
while (tempNumber <= 9223372036854775807 ~/ factorial) {
int original = tempNumber;
tempNumber *= factorial;
nextSet.add(tempNumber);
var originalDecomposition = decompositions[original];
if (originalDecomposition != null) {
decompositions[tempNumber] = Map<int, int>.from(originalDecomposition)
..update(multiplier, (value) => value + 1, ifAbsent: () => 1);
}
}
}
jordanPolyaSet.addAll(nextSet);
nextSet.clear();
}
}
 
String mapToString(Map<int, int> map) {
String result = "";
map.forEach((key, value) {
result = "$key!${value == 1 ? '' : '^$value'} * $result";
});
return result.isEmpty ? result : result.substring(0, result.length - 3);
}
</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>
 
=={{header|EasyLang}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang=easylang>
fastfunc jpnum m .
n = m
limite = 7
while 1 = 1
fac = 1
i = 1
while i < limite
i += 1
fac *= i
.
repeat
q = n div fac
if n mod fac = 0
if q = 1
return 1
.
n = q
else
fac = fac / i
i -= 1
.
until i = 1
.
limite -= 1
if limite = 0
return 0
.
n = m
.
.
numfmt 0 5
write 1
c = 1
n = 2
repeat
if jpnum n = 1
c += 1
if c <= 50
write n
if c mod 8 = 0
print ""
.
.
sn = n
.
n += 2
until n >= 1e8
.
print ""
print "The largest Jordan-Polya number before 100 million: " & sn
</syntaxhighlight>
 
=={{header|FreeBASIC}}==
{{trans|XPL0}}
Simple-minded brute force. No bonus.
<syntaxhighlight lang="vb">Dim Shared As Uinteger Factorials(1+12)
 
Function isJPNum(m As Uinteger) As Boolean
Dim As Uinteger n = m, limite = 7, i, q
Do
i = limite
Do
q = n / Factorials(i)
If n Mod Factorials(i) = 0 Then
If q = 1 Then Return True
n = q
Else
i -= 1
End If
If i = 1 Then
If limite = 1 Then Return False
limite -= 1
n = m
Exit Do
End If
Loop
Loop
End Function
 
Dim As Uinteger fact = 1, n
For n = 1 To 12
fact *= n
Factorials(n) = fact
Next
 
Print "First 50 Jordan-Polya numbers:"
Print " 1";
Dim As Uinteger c, sn
c = 1
n = 2
Do
If isJPNum(n) Then
c += 1
If c <= 50 Then
Print Using "#####"; n;
If c Mod 10 = 0 Then Print
End If
sn = n
End If
n += 2
Loop Until n >= 1e8
 
Print !"\nThe largest Jordan-Polya number before 100 million: "; sn
 
Sleep</syntaxhighlight>
{{out}}
<pre>Same as XPL0 entry.</pre>
 
=={{header|Go}}==
Line 427 ⟶ 828:
(,showjp) (<:3800){s
7213895789838336 24 24 24 24 24 24 24 24 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2</syntaxhighlight>
 
=={{header|Java}}==
<syntaxhighlight lang=java>
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
 
public final class JordanPolyaNumbers {
 
public static void main(String[] aArgs) {
createJordanPolya();
final long belowHundredMillion = jordanPolyaSet.floor(100_000_000L);
List<Long> jordanPolya = new ArrayList<Long>(jordanPolyaSet);
System.out.println("The first 50 Jordan-Polya numbers:");
for ( int i = 0; i < 50; i++ ) {
System.out.print(String.format("%5s%s", jordanPolya.get(i), ( i % 10 == 9 ? "\n" : "" )));
}
System.out.println();
System.out.println("The largest Jordan-Polya number less than 100 million: " + belowHundredMillion);
System.out.println();
for ( int i : List.of( 800, 1050, 1800, 2800, 3800 ) ) {
System.out.println("The " + i + "th Jordan-Polya number is: " + jordanPolya.get(i - 1)
+ " = " + toString(decompositions.get(jordanPolya.get(i - 1))));
}
}
private static void createJordanPolya() {
jordanPolyaSet.add(1L);
Set<Long> nextSet = new TreeSet<Long>();
decompositions.put(1L, new TreeMap<Integer, Integer>());
long factorial = 1;
for ( int multiplier = 2; multiplier <= 20; multiplier++ ) {
factorial *= multiplier;
for ( Iterator<Long> iterator = jordanPolyaSet.iterator(); iterator.hasNext(); ) {
long number = iterator.next();
while ( number <= Long.MAX_VALUE / factorial ) {
long original = number;
number *= factorial;
nextSet.add(number);
decompositions.put(number, new TreeMap<Integer, Integer>(decompositions.get(original)));
decompositions.get(number).merge(multiplier, 1, Integer::sum);
}
}
jordanPolyaSet.addAll(nextSet);
nextSet.clear();
}
}
private static String toString(Map<Integer, Integer> aMap) {
String result = "";
for ( int key : aMap.keySet() ) {
result = key + "!" + ( aMap.get(key) == 1 ? "" :"^" + aMap.get(key) ) + " * " + result;
}
return result.substring(0, result.length() - 3);
}
 
private static TreeSet<Long> jordanPolyaSet = new TreeSet<Long>();
private static Map<Long, Map<Integer, Integer>> decompositions = new HashMap<Long, Map<Integer, Integer>>();
 
}
</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>
 
=={{header|jq}}==
Line 475 ⟶ 964:
| until(.k > .mx or .t > $lim;
.t *= .k
| if .t <= $lim
then reduce JordanPolya(($lim/.t)|floor; .t)[] as $rest (.;
.v += [.t * $rest] )
| .k += 1
else .
end)
| .v
| unique
Line 508 ⟶ 997:
| .m = (.m / .factorial[$i])
| if .m == 1 then .emit = .f else . end)
| if .emit then ., break $out else . end)
| if .emit then .emit
elif .i == 2 then Decompose($n; .start-1)
Line 649 ⟶ 1,138:
The 3800th Jordan-Pólya number is: 7213895789838336
= 4!⁸ x 2!¹⁶
</pre>
 
=={{header|Kotlin}}==
{{trans|Java}}
<syntaxhighlight lang="Kotlin">
import java.util.*
 
object JordanPolyaNumbers {
private val jordanPolyaSet = TreeSet<Long>()
private val decompositions = HashMap<Long, TreeMap<Int, Int>>()
 
@JvmStatic
fun main(aArgs: Array<String>) {
createJordanPolya()
 
val belowHundredMillion = jordanPolyaSet.floor(100_000_000L)
val jordanPolya = ArrayList(jordanPolyaSet)
 
println("The first 50 Jordan-Polya numbers:")
for (i in 0 until 50) {
print(String.format("%5s%s", jordanPolya[i], if (i % 10 == 9) "\n" else ""))
}
println()
 
println("The largest Jordan-Polya number less than 100 million: $belowHundredMillion")
println()
 
for (i in listOf(800, 1050, 1800, 2800, 3800)) {
println("The $i th Jordan-Polya number is: ${jordanPolya[i - 1]} = ${toString(decompositions[jordanPolya[i - 1]]!!)}")
}
}
 
private fun createJordanPolya() {
jordanPolyaSet.add(1L)
val nextSet = TreeSet<Long>()
decompositions[1L] = TreeMap()
var factorial = 1L
 
for (multiplier in 2..20) {
factorial *= multiplier
val iterator = jordanPolyaSet.iterator()
while (iterator.hasNext()) {
var number = iterator.next()
while (number <= Long.MAX_VALUE / factorial) {
val original = number
number *= factorial
nextSet.add(number)
decompositions[number] = TreeMap(decompositions[original]!!)
decompositions[number]?.merge(multiplier, 1) { a, b -> a + b }
}
}
jordanPolyaSet.addAll(nextSet)
nextSet.clear()
}
}
 
private fun toString(aMap: Map<Int, Int>): String {
return aMap.entries.joinToString(separator = " * ") { (key, value) ->
"$key!${if (value == 1) "" else "^$value"}"
}
}
}
 
fun main(args: Array<String>) {
JordanPolyaNumbers.main(arrayOf<String>())
}
 
</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 800 th Jordan-Polya number is: 18345885696 = 2!^2 * 4!^7
The 1050 th Jordan-Polya number is: 139345920000 = 2! * 5!^3 * 8!
The 1800 th Jordan-Polya number is: 9784472371200 = 2!^15 * 4!^2 * 6!^2
The 2800 th Jordan-Polya number is: 439378587648000 = 7! * 14!
The 3800 th Jordan-Polya number is: 7213895789838336 = 2!^16 * 4!^8
 
</pre>
 
Line 743 ⟶ 1,317:
const
MaxIdx = 3800;//7279 < 2^62
maxFac = 2125;//21!> 2^63
type
tnum = Uint64;
Line 749 ⟶ 1,323:
tFac_mul = packed record
fm_num : tnum;
fm_pow : tpow; //which Factorials where used for fm_num
fm_high_idx : word;//memorize highest Factorial Index
fm_high_pow : word;// and it's power
end;
tpFac_mul = ^tFac_mul;
tFacMulPow = array of tFac_mul;
tFactorial = array[0..maxFac-2] of tnum;
 
var
Factorial: array[0..maxFac-2] of tnum;
FacMulPowGes : tFacMulPow;
Factorial: tFactorial;
LastSearchFor :tFac_mul;
dblLimit : tnum;
 
function CommatizeUint64(num:Uint64):AnsiString;
procedure QuickSort(var AI: tFacMulPow; ALo, AHi: Int32);
var
fromIdx,toIdx :Int32;
Tmp :tFac_mul;
Begin
Pivot : tnum;
str(num,result);
Lo, Hi : Int32;
fromIdx := length(result);
begin
LotoIdx := ALofromIdx-1;
Hiif :=toIdx AHi;< 3 then
exit;
Pivot := AI[(Lo + Hi) div 2].fm_num;
 
toIdx := 4*(toIdx DIV 3)+toIdx MOD 3 +1 ;
setlength(result,toIdx);
repeat
result[toIdx] := result[FromIdx];
while AI[Lo].fm_num < Pivot do
result[toIdx-1] := result[FromIdx-1];
Inc(Lo);
result[toIdx-2] := result[FromIdx-2];
while AI[Hi].fm_num > Pivot do
result[toIdx-3] := Dec(Hi)',';
dec(toIdx,4);
if Lo <= Hi then
begindec(FromIdx,3);
until FromIdx<=3;
Tmp := AI[Lo];
AI[Lo] := AI[Hi];
AI[Hi] := Tmp;
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if Hi > ALo then
QuickSort(AI, ALo, Hi) ;
if Lo < AHi then
QuickSort(AI, Lo, AHi) ;
end;
 
Line 795 ⟶ 1,363:
fac,
num : tNum;
i,jFacIdx,pow : integer;
begin
num := fm.fm_num;
FacIdx := fm.fm_high_idx;
write(num:20);
write(CommatizeUint64(num):25,' = ');
i := fm.fm_high_idx;
 
repeat
jpow := 0;
fac := Factorial[iFacIdx];
while (num>=fac) AND (num mod Fac = 0) do
Begin
num := num DIV Fac;
inc(jpow);
end;
if jpow = 0 then
write(' 1')
else
if jpow = 1 then
write(' ',iFacIdx+2,'!')
else
write(' (',iFacIdx+2,'!)^',jpow);
if num = 1 then
BREAK;
dec(i); repeat
dec(FacIdx);
while (i>=0 ) AND Not(i in fm.fm_pow) do
until(FacIdx<0) OR (FacIdx in fm.fm_pow);
dec(i);
until iFacIdx < 0;
writeln;
 
end;
 
procedure Out_I_th(i: integer);
begin
if i < 0 then
write(i:8,': ');
write(i:8,' too small');
if i <= High(FacMulPowGes) then
begin
write(i:6,'-th : ');
Out_MulFac(i,FacMulPowGes[i-1])
end
else
writeln('Too big');
end;
 
procedure Out_First_N(n: integer);
var
s,fmt : AnsiString;
i,tmp : integer;
Begin
if n<1 then
EXIT;
writeln('The first ',n,' Jordan-Polia numbers');
s := '';
If n > Length(FacMulPowGes) then
n := Length(FacMulPowGes);
dec(n);
tmp := length(CommatizeUint64(FacMulPowGes[n].fm_num))+1;
fmt := '%'+IntToStr(tmp)+'s';
tmp := 72 DIV tmp;
For i := 0 to n do
Begin
s += Format(fmt,[CommatizeUint64(FacMulPowGes[i].fm_num)]);
if (i+1) mod tmp = 0 then
Begin
writeln(s);
s := '';
end;
end;
if s <>'' then
writeln(s);
writeln;
end;
 
Line 850 ⟶ 1,453:
inc(idx);
end;
Fillchar(LastSearchFor,SizeOf(LastSearchFor),#0);
LastSearchFor.FM_NUM := 0;
// dblLimit := 1 shl 53;// 1 shl 6;
dblLimit := 1 shl 5;
end;
end;
 
procedure ResetSearch;
Begin
setlength(FacMulPowGes,0);
end;
 
Line 863 ⟶ 1,467:
//generating the first entry with (2!)^n
var
res_p : tpFac_mul;
Fac_mul :tFac_mul;
facPow,Fac : tnum;
i,MaxIdxMaxPowOfFac : integer;
begin
fac := Factorial[idx];
MaxIDxMaxPowOfFac := trunc(ln(dblLimit)/ln(Fac))+1;
setlength(res,MaxIdxMaxPowOfFac);
 
fillchar(Fac_Mul,SizeOf(Fac_Mul),#0);
with Fac_Mul do
begin
Line 878 ⟶ 1,481:
fm_high_idx := 0;
end;
 
res_p := @res[0];
res_p^res[0] := Fac_Mul;
facPow := 1;
For i := 1 to MaxIdx-1 do;
beginrepeat
facPow *= Fac;
if facPow >dblLimit then
BREAK;
with Fac_Mul do
begin
Line 889 ⟶ 1,494:
fm_high_pow := i;
end;
inc(res_p)res[i] := Fac_Mul;
res_p^ := Fac_Mulinc(i);
until i = MaxPowOfFac;
end;
setlength(res,i);
end;
 
procedure DelDoublettes(var FMP:tFacMulPow);
//throw out doublettes,
//the one with highest power in the highest n! survives
var
pIpNext,pJpCurrent : tpFac_mul;
i, jlen,idx : integer;
begin
jlen := 0;
pJpCurrent := @FMP[0];
pIpNext := pJpCurrent;
For i := 0 to High(FMP)-1 do
begin
inc(pIpNext);
// don't increment pCurrent if equal
if pJ^.fm_num = pI^.fm_num then
// pCurrent gets or stays the highest Value in n!^high_pow
if pCurrent^.fm_num = pNext^.fm_num then
Begin
idx := pJpCurrent^.fm_high_idx;
if idx < pIpNext^.fm_high_idx then
pJpCurrent^ := pIpNext^
else
if idx = pIpNext^.fm_high_idx then
if pJpCurrent^.fm_high_pow < pIpNext^.fm_high_pow then
pJpCurrent^ := pIpNext^;
end
else
begin
inc(jlen);
inc(pJpCurrent);
pJpCurrent^ := pIpNext^;
end;
end;
setlength(FMP,jlen);
end;
 
procedure InsertFacMulPowQuickSort(var resAI: tFacMulPow;Facidx ALo, AHi:integer Int32);
var
Tmp :tFac_mul;
Pivot : tnum;
Lo, Hi : Int32;
begin
Lo := ALo;
Hi := AHi;
Pivot := AI[(Lo + Hi) div 2].fm_num;
repeat
while AI[Lo].fm_num < Pivot do
Inc(Lo);
while AI[Hi].fm_num > Pivot do
Dec(Hi);
if Lo <= Hi then
begin
Tmp := AI[Lo];
AI[Lo] := AI[Hi];
AI[Hi] := Tmp;
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if Hi > ALo then
QuickSort(AI, ALo, Hi) ;
if Lo < AHi then
QuickSort(AI, Lo, AHi) ;
end;
 
function InsertFacMulPow(var res:tFacMulPow;Facidx:integer):boolean;
var
Fac,newFacFacPow,NewNum,limit : tnum;
l_res,l_NewMaxPow,idx,i,j : Integer;
begin
fac := Factorial[Facidx];
 
if length(res)= 0 then
Begin
GenerateFirst(Facidx,res);
EXIT;
end;
 
if fac>dblLimit then
EXIT(false);
l_NewMaxPow := trunc(ln(dblLimit)/ln(Fac))+1;
l_res := length(res);
 
//calc new length, reduces allocation of big memory chunks
j := 0;
idx := High(res);
For i := 1 to l_NewMaxPow do
Begin
limit := dblLimit DIV fac;
if limit < 1 then
BREAK;
repeat
dec(idx);
until res[idx].fm_num<=limit;
inc(j,idx);
fac *=Factorial[Facidx];
end;
j += l_res+l_NewMaxPow+2;
setlength(res,j);
 
if length(res)> 0 then
fac := Factorial[Facidx];
idx := l_res;
For j := 0 to l_NewMaxPow-1 do
begin
l_NewMaxPow := trunc(ln(dblLimit)/ln(Fac))+1;
For i := 0 to l_res-1 do
l_res := length(res);
//calc new length, reduces allocation of big memory chunks
//first original length + length of the new to insert
j := l_res+l_NewMaxPow;
//find the maximal needed elements which stay below dbllimit
// for every Fac^i
idx := High(res);
FacPow := Fac;
For i := 1 to l_NewMaxPow do
Begin
limit := dblLimit DIV FacPow;
if limit < 1 then
BREAK;
//search for the right position
repeat
dec(idx);
until res[idx].fm_num<=limit;
inc(j,idx);
FacPow *= fac;
end;
j += 2;
setlength(res,j);
 
idx := l_res;
FacPow := fac;
For j := 1 to l_NewMaxPow do
begin
NewFacFor i := res[i].fm_num*Fac;0 to l_res do
if NewFac>dblLimit thenbegin
BreakNewNum := res[i].fm_num*FacPow;
if NewNum>dblLimit then
res[idx]:= res[i];
with res[idx] do Break;
Begin res[idx]:= res[i];
fm_numwith :=res[idx] NewFac;do
include(fm_pow,Facidx);Begin
fm_high_idx fm_num := FacidxNewNum;
fm_high_pow := jinclude(fm_pow,Facidx);
end; fm_high_idx := Facidx;
inc(idx) fm_high_pow := j;
end;
inc(idx);
end;
FacPow *= fac;
end;
setlength(res,idx);
fac *= Factorial[Facidx];
QuickSort(res,Low(res),High(res));
end;
setlength DelDoublettes(res,idx);
end
QuickSort(res,Low(res),High(res));
else
DelDoublettes(res);
GenerateFirst(Facidx,res);
Exit(true);
end;
 
Line 993 ⟶ 1,632:
BEGIn
InitFirst;
 
repeat
ResetSearch;
i := 0;
repeat
if Factorial[Not(InsertFacMulPow(FacMulPowGes,i] < dblLimit)) then
InsertFacMulPow(FacMulPowGes,i)BREAK;
else
break;
inc(i);
until i > High(Factorial);
//check if MaxIdx is found
if (Length(FacMulPowGes) > MaxIdx) then
begin
Line 1,008 ⟶ 1,647:
Begin
LastSearchFor := FacMulPowGes[MaxIdx-1];
//the next factorial is to big, so search is done
if LastSearchFor.fm_num < Factorial[i] then
break;
end
else
Break;
end;
if dblLimit> HIGH(tNUm) DIV 256 then
BREAK;
dblLimit *= 256;
until false;
 
write('Found ',length(FacMulPowGes),' Jordan-Polia numbers ');
writeln('up to ',CommatizeUint64(dblLimit));
writeln;
 
Out_First_N(50);
writeln('The first 50 Jordan-Polia numbers');
For i := 1 to 50 do
Begin
write(FacMulPowGes[i-1].fm_num:5);
if i mod 10 = 0 then
writeln;
end;
writeln;
 
write('The last < 1E8 ');
Line 1,040 ⟶ 1,674:
writeln;
 
Out_I_th(01);
Out_I_th(100);
Out_I_th(800);
Line 1,050 ⟶ 1,684:
{{out|@home}}
<pre>
Found 3876 Jordan-Polia numbers up to 90071992547409929,007,199,254,740,992
 
The first 50 Jordan-Polia 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 1,024 1,152 1,296 1,440 1,536
1,728 1,920 2,048 2,304 2,592 2,880 3,072 3,456 3,840 4,096 4,320 4,608
5,040 5,184
 
The last < 1E8 99,532,800 = (6!)^2 4! (2!)^3
 
1-th : 1 = 1
100-th : 92,160 = 6! (2!)^7
800-th : 18,345,885,696 = (4!)^7 (2!)^2
1050-th : 139,345,920,000 = 8! (5!)^3 2!
1800-th : 9,784,472,371,200 = (6!)^2 (4!)^2 (2!)^15
2800-th : 439,378,587,648,000 = 14! 7!
3800-th : 7,213,895,789,838,336 = (4!)^8 (2!)^16
real 0m0,004s user 0m0,004s sys 0m0,000s</pre>
 
=={{header|Perl}}==
{{trans|Raku}}
{{libheader|ntheory}}
<syntaxhighlight lang="perl" line>
use strict;
use warnings;
use feature 'say';
 
use ntheory 'factorial';
use List::AllUtils <max firstidx>;
 
sub table { my $t = 10 * (my $c = 1 + length max @_); ( sprintf( ('%'.$c.'d')x@_, @_) ) =~ s/.{1,$t}\K/\n/gr }
 
sub Jordan_Polya {
my $limit = shift;
my($k,@JP) = (2);
push @JP, factorial $_ for 0..18;
 
while ($k < @JP) {
my $rk = $JP[$k];
for my $l (2 .. @JP) {
my $kl = $JP[$l] * $rk;
last if $kl > $limit;
LOOP: {
my $p = firstidx { $_ >= $kl } @JP;
if ($p < $#JP and $JP[$p] != $kl) { splice @JP, $p, 0, $kl }
elsif ($p == $#JP ) { push @JP, $kl }
$kl > $limit/$rk ? last LOOP : ($kl *= $rk)
}
}
$k++
}
shift @JP; return @JP
}
 
my @JP = Jordan_Polya 2**27;
say "First 50 Jordan-Pólya numbers:\n" . table @JP[0..49];
say 'The largest Jordan-Pólya number before 100 million: ' . $JP[-1 + firstidx { $_ > 1e8 } @JP];
</syntaxhighlight>
{{out}}
<pre>
First 50 Jordan-Pólya numbers:
1 2 4 6 8 12 16 24 32 36
48 64 72 96 120 128 144 192 216 240
Line 1,059 ⟶ 1,752:
2592 2880 3072 3456 3840 4096 4320 4608 5040 5184
 
The last < 1E8 largest Jordan-Pólya number before 100 million: 99532800 (6!)^2 4! (2!)^3
</pre>
 
0: 1 1
100: 92160 6! (2!)^7
800: 18345885696 (4!)^7 (2!)^2
1050: 139345920000 8! (5!)^3 2!
1800: 9784472371200 (6!)^2 (4!)^2 (2!)^15
2800: 439378587648000 14! 7!
3800: 7213895789838336 (4!)^8 (2!)^16
 
real 0m0,002s user 0m0,002s sys 0m0,000s</pre>
 
=={{header|Phix}}==
Line 1,213 ⟶ 1,897:
</pre>
Some 80%-90% of the time is now spent in the decomposing phase.
 
=={{header|Python}}==
{{trans|Java}}
<syntaxhighlight lang="Python">
from collections import defaultdict
from itertools import product
 
class JordanPolyaNumbers:
def __init__(self):
self.jordan_polya_set = set()
self.decompositions = defaultdict(dict)
 
def create_jordan_polya(self):
self.jordan_polya_set.add(1)
next_set = set()
self.decompositions[1] = {}
factorial = 1
 
for multiplier in range(2, 21):
factorial *= multiplier
for number in list(self.jordan_polya_set):
while number <= 2**63 - 1 // factorial:
original = number
number *= factorial
next_set.add(number)
self.decompositions[number] = self.decompositions[original].copy()
self.decompositions[number][multiplier] = self.decompositions[number].get(multiplier, 0) + 1
 
self.jordan_polya_set.update(next_set)
next_set.clear()
 
def to_string(self, a_map):
result = ""
for key in sorted(a_map.keys(), reverse=True):
exponent = a_map[key]
result += f"{key}!" + ("" if exponent == 1 else f"^{exponent}") + " * "
return result[:-3]
 
def display_results(self):
below_hundred_million = max(n for n in self.jordan_polya_set if n < 100_000_000)
jordan_polya = sorted(list(self.jordan_polya_set))
 
print("The first 50 Jordan-Polya numbers:")
for i in range(50):
end = "\n" if (i % 10 == 9) else ""
print(f"{jordan_polya[i]:5}", end=end)
print()
 
print(f"The largest Jordan-Polya number less than 100 million: {below_hundred_million}")
print()
 
for i in [800, 1050, 1800, 2800, 3800]:
print(f"The {i}th Jordan-Polya number is: {jordan_polya[i-1]}"
f" = {self.to_string(self.decompositions[jordan_polya[i-1]])}")
 
 
if __name__ == "__main__":
jpn = JordanPolyaNumbers()
jpn.create_jordan_polya()
jpn.display_results()
</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>
 
=={{header|Raku}}==
'''Partial translation of [[#Go|Go]]'''
<syntaxhighlight lang="raku" line># 20230719 Raku programming solution
 
my \factorials = 1, | [\*] 1..18; # with 0!
 
sub JordanPolya (\limit) {
my \ix = (factorials.keys.first: factorials[*] >= limit) // factorials.end;
my ($k, @res) = 2, |factorials[0..ix];
 
while $k < @res.elems {
my \rk = @res[$k];
for 2 .. @res.elems -> \l {
my \kl = $ = @res[l] * rk;
last if kl > limit;
loop {
my \p = @res.keys.first: { @res[$_] >= kl } # performance
if p < @res.elems and @res[p] != kl {
@res.splice: p, 0, kl
} elsif p == @res.elems {
@res.append: kl
}
kl > limit/rk ?? ( last ) !! kl *= rk
}
}
$k++
}
return @res[1..*]
}
 
my @result = JordanPolya 2**30 ;
say "First 50 Jordan-Pólya numbers:";
say [~] $_>>.fmt('%5s') for @result[^50].rotor(10);
print "\nThe largest Jordan-Pólya number before 100 million: ";
say @result.first: * < 100_000_000, :end; </syntaxhighlight>
You may [https://ato.pxeger.com/run?1=bZNNbptAFMcX3XGKv12qYGKPwZWlyNROV110lUV3NrFwPNQjhg8NoMRKnIt0k0V7gh6h6iV6mj5gqEHNSAjNvP_7vY958-27CqLy5eVHWYSTqz9vfsdHbMLgrkiVCGSOJdwxnrDe2D5cxtwrD29xL4oDnIFh5OUOn1O1D5KbVB4DWBspYlGM8GgAqFDigRDWGcgifsxZKFReLHA-XhN-tYT2nk47JsaTvQfNs8xojI-K5yPCziizDsJhTDz4nlFJ7w9CcpgRPtRqxiWP8yYrnZiKiFDZ1mZETo0hTBVmYKzrNFlhI_-5au9IkrfZEqQPGyryzhoZ5AVECNKtmqq6xjTNukDNzDSu16JHneO27g_hTtT_jCvKNA6SO96jUMCsX3GQ7BtA5mNQ-_fj0qrMFPmplt1m_phUY73NGKOL0avneAKXeR1vuey1GK_xWZBldI2LKoE-prc7d2tK13N9Datp5AiDQWW0l9Rl4z_n9m9Gl5dGu1e8KFXSFO9WZRgnw6A2VwelLKji7uDObPu9AxqzPDhi-KnqPeaOlkxufv2sREkZ77jKF0Ovlq2ffZjb1YqFcWFdvJvnF6N6gHSE9e3c8ZlKaTwt1xl5RqZEUmC4Sb4cONWlvnIK8loE7DhxOFzHQSykFGmygA6q4e142HTdJNs6zTfGon4tzWvWj7p93H8B Attempt This Online!]
 
=={{header|Rust}}==
{{trans|C++}}
<syntaxhighlight lang="Rust">
use std::collections::{HashMap, HashSet};
 
const LIMIT: u64 = 1 << 53;
 
fn to_string(map: &HashMap<u64, u64>) -> String {
let mut result = String::new();
for (&key, &value) in map {
// println!("key={} value={}", key, value);
let part = if value == 1 {
format!("{}!", key)
} else {
format!("{}!^{}", key, value)
};
result = part + " * " + &result;
}
result.trim_end_matches(" * ").to_string()
}
 
fn insert_or_update(map: &mut HashMap<u64, u64>, entry: u64) {
let count = map.entry(entry).or_insert(0);
*count += 1;
}
 
fn create_jordan_polya() -> (HashSet<u64>, HashMap<u64, HashMap<u64, u64>>) {
let mut jordan_polya_set = HashSet::new();
let mut decompositions = HashMap::new();
 
jordan_polya_set.insert(1);
decompositions.insert(1, HashMap::new());
let mut factorial = 1u64;
 
for multiplier in 2..=20 {
factorial *= multiplier; // Using u64 for multiplier
let mut to_update = Vec::new();
 
for &number in &jordan_polya_set {
let mut current = number;
while current <= LIMIT / factorial {
to_update.push((current, current * factorial)); // Store original and new number
current *= factorial;
}
}
 
for (original, new_number) in to_update {
jordan_polya_set.insert(new_number);
let mut new_decomposition = decompositions[&original].clone();
insert_or_update(&mut new_decomposition, multiplier);
decompositions.insert(new_number, new_decomposition);
}
}
 
(jordan_polya_set, decompositions)
}
 
 
fn main() {
let (jordan_polya_set, decompositions) = create_jordan_polya();
let mut jordan_polya: Vec<_> = jordan_polya_set.into_iter().collect();
jordan_polya.sort();
 
println!("The first 50 Jordan-Polya numbers:");
for i in 0..50 {
print!("{:5}", jordan_polya[i]);
if i % 10 == 9 {
println!();
}
}
 
let hundred_million = jordan_polya.iter().position(|&x| x >= 100_000_000).unwrap();
println!(
"\nThe largest Jordan-Polya number less than 100 million: {}\n",
jordan_polya[hundred_million - 1]
);
 
for &i in &[800, 1050, 1800, 2800, 3800] {
println!(
"The {}th Jordan-Polya number is: {} = {}",
i,
jordan_polya[i - 1],
to_string(&decompositions[&jordan_polya[i - 1]])
);
}
}
</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 = 2!^2 * 4!^7
The 1050th Jordan-Polya number is: 139345920000 = 2! * 5!^3 * 8!
The 1800th Jordan-Polya number is: 9784472371200 = 2!^15 * 6!^2 * 4!^2
The 2800th Jordan-Polya number is: 439378587648000 = 14! * 7!
The 3800th Jordan-Polya number is: 7213895789838336 = 2!^16 * 4!^8
 
</pre>
 
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
import java.util.{ArrayList, HashMap, TreeMap, TreeSet}
import scala.jdk.CollectionConverters._
 
object JordanPolyaNumbers {
private val jordanPolyaSet = new TreeSet[Long]()
private val decompositions = new HashMap[Long, TreeMap[Integer, Integer]]()
 
def main(args: Array[String]): Unit = {
createJordanPolya()
 
val belowHundredMillion = jordanPolyaSet.floor(100_000_000L)
val jordanPolya = new ArrayList[Long](jordanPolyaSet)
 
println("The first 50 Jordan-Polya numbers:")
jordanPolya.asScala.take(50).zipWithIndex.foreach { case (number, index) =>
print(f"$number%5s${if(index % 10 == 9) "\n" else ""}")
}
println()
 
println(s"The largest Jordan-Polya number less than 100 million: $belowHundredMillion")
println()
 
List(800, 1050, 1800, 2800, 3800).foreach { i =>
println(s"The ${i}th Jordan-Polya number is: ${jordanPolya.get(i - 1)} = ${toString(decompositions.get(jordanPolya.get(i - 1)))}")
}
}
 
private def createJordanPolya(): Unit = {
jordanPolyaSet.add(1L)
val nextSet = new TreeSet[Long]()
decompositions.put(1L, new TreeMap[Integer, Integer]())
var factorial = 1L
 
for (multiplier <- 2 to 20) {
factorial *= multiplier
val it = jordanPolyaSet.iterator()
while (it.hasNext) {
var number = it.next()
while (number <= Long.MaxValue / factorial) {
val original = number
number *= factorial
nextSet.add(number)
decompositions.put(number, new TreeMap[Integer, Integer](decompositions.get(original)))
val currentMap = decompositions.get(number)
currentMap.merge(multiplier, 1, (a: Integer, b: Integer) => Integer.sum(a, b))
}
}
jordanPolyaSet.addAll(nextSet)
nextSet.clear()
}
}
 
private def toString(aMap: TreeMap[Integer, Integer]): String = {
aMap.descendingMap().asScala.map { case (key, value) =>
s"$key!${if (value == 1) "" else "^" + value}"
}.mkString(" * ")
}
}
</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>
 
You may [https://ato.pxeger.com/run?1=fVXbbtQwEH1E2q8YokWyYWuyrSqVFYuEeAHUVkjl8lAuchPvrlvHWdlOL6zyJbzwAv8EX8MkdrLZEJDa1I1nzpw5c8m3nzbhih98__6jcIu9o9_3fslsnRsHl_yas8JJxTbPjeF3x9K6CbzkdnXC1xN4a4RoD2fClaPgV-Oxy_SKvciVEomTuX6R62thnDCWfRmN8otLfA2vc5Ny_SZXd_y0yC7wEjYjAPxZG3nNnYBrruBya4VRYA5a3DQxz49zvfxEaM8lFUmOXKysQtvgEojXLi3781faiaUwEwiHTxUawqViARmXmnCztDOoBTg_c0ZiPDqDd1pWVCq6AIkRGLmTjYeAmsuFUPnNy0KnRqQnUilkhI67SbGFynNDpnH8Jfa_x7QF6JiGTNpqhPR3wUJs1EM7pUn0diVgIY11cBgHyfc8mvaizyIfrAPDuD2rq-j4lSCHMWVf5fqDdKtXOhW3bJFjxskKNpBwK4B4oAnI6pbC_FmNFziQRTT2Bg8O7XgjF6Q2gwcwjWE-hycUoo86AqEQKorKwKbcyaKXlK2zUlgbYd1QUqCEteBWXGOUGDIv_AzGA-UIAXuhKn3JURxPEOCwetbn_fp5gE_aUUH2Um4ZYrqlWw0SlNhV401X86VwRMIeTGmJhR5vXO77jey2c2037EdpV71y1BmLqp8H-rTXyb225GlKpp1W1OLW_W8GoTd5bF04BJi05oMTR2gTwcCCJy43EmPNYXrsK4E6A8kK5eRaSVTu6R7sg8thP6aBNnT8Hs5haxtuK-51lr38JC4kjn6BPMDNSirsZ-nYittTzHYbwfMLxZsjHKvUaD1b32DxdA6VLuyE377nqhDweMuxC-rJ4eul1HXW3r9zHwAxrxage-tLUpfKW9LO7UA5mln9f0kGWq7hSCntsU8KY4R2iIT8Bzz_5rX1YJnAIe6UFydtAoTPoCV10Z6r1dKcmS0ywvG2Q6cc7f79u52fK0WCZI1bo2CiBG86YXB82nnkyHv2b_FwqLxhO1aVA0uFTYRO8T3-R2i7YjOUrVmkV-JuUklaiM4WtdEY39-vVieQ-rJam1Ncm83S_BzBI-9WRp4_y64C2QgeQr0UylHpv_DhQ9988P8A Attempt This Online!]
 
=={{header|Swift}}==
{{trans|Java}}
<syntaxhighlight lang="Swift">
import Foundation
 
class JordanPolyaNumbers {
 
static var jordanPolyaSet = Set<Int64>()
static var decompositions = [Int64: [Int: Int]]()
 
static func main() {
createJordanPolya()
 
let belowHundredMillion = jordanPolyaSet.filter { $0 <= 100_000_000 }.max() ?? 0
let jordanPolya = Array(jordanPolyaSet).sorted()
 
print("The first 50 Jordan-Polya numbers:")
for i in 0..<50 {
if i % 10 == 9 {
print("\(jordanPolya[i])\n", terminator: "")
} else {
print(String(format: "%5d ", jordanPolya[i]), terminator: "")
}
}
print("\nThe largest Jordan-Polya number less than 100 million: \(belowHundredMillion)\n")
 
for i in [800, 1050, 1800, 2800, 3800] {
print("The \(i)th Jordan-Polya number is: \(jordanPolya[i - 1]) = \(toString(decompositions[jordanPolya[i - 1]] ?? [:]))")
}
}
 
static func createJordanPolya() {
jordanPolyaSet.insert(1)
var nextSet = Set<Int64>()
decompositions[1] = [:]
var factorial: Int64 = 1
 
for multiplier in 2...20 {
factorial *= Int64(multiplier)
for number in jordanPolyaSet {
var current = number
while current <= Int64.max / factorial {
let original = current
current *= factorial
nextSet.insert(current)
decompositions[current] = decompositions[original]?.merging([multiplier: 1], uniquingKeysWith: +) ?? [:]
}
}
jordanPolyaSet.formUnion(nextSet)
nextSet.removeAll()
}
}
 
static func toString(_ aMap: [Int: Int]) -> String {
var result = ""
for key in aMap.keys.sorted().reversed() {
let value = aMap[key] ?? 0
result += "\(key)!" + (value == 1 ? "" : "^\(value)") + " * "
}
return String(result.dropLast(3))
}
}
 
JordanPolyaNumbers.main()
</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>
 
=={{header|Wren}}==
Line 1,220 ⟶ 2,294:
{{libheader|Wren-fmt}}
This uses the recursive PARI/Python algorithm in the OEIS entry.
<syntaxhighlight lang="ecmascriptwren">import "./set" for Set
import "./seq" for Lst
import "./fmt" for Fmt
Line 1,324 ⟶ 2,398:
{{libheader|Wren-sort}}
This uses the same non-recursive algorithm as the Phix entry to generate the J-P numbers which, at 1.1 seconds on my machine, is about 40 times quicker than the OEIS algorithm.
<syntaxhighlight lang="ecmascriptwren">import "./sort" for Find
import "./seq" for Lst
import "./fmt" for Fmt
Chkas
2,063

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/345185...363028"