Jordan-Pólya numbers: Difference between revisions
m
→{{header|EasyLang}}
(Add Rust implementation) |
|||
| (5 intermediate revisions by one other user not shown) | |||
Line 217:
The 3,800th Jordan-Pólya number is : 7,213,895,789,838,336
= (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>
Line 318 ⟶ 418:
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>
Line 362 ⟶ 551:
if c <= 50
write n
if c mod
print ""
.
Line 949 ⟶ 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 1,623 ⟶ 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}}==
Line 1,851 ⟶ 2,204:
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}}==
| |||