Rosetta Code

Home primes: Difference between revisions

Page Discussion

Home primes (view source)

Revision as of 12:12, 8 March 2024

17,317 bytes added ,  2 months ago
added RPL
(added RPL)
 
(9 intermediate revisions by 6 users not shown)
Line 293:
19 is prime
HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413 is prime</pre>
 
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.Collectors;
import java.util.stream.Stream;
 
public final class HomePrimes {
 
public static void main(String[] aArgs) {
listPrimes(PRIME_LIMIT);
List<Integer> values = List.of( 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 65 );
for ( int value : values ) {
BigInteger number = BigInteger.valueOf(value);
List<BigInteger> previousNumbers = Stream.of( number ).collect(Collectors.toList());
boolean searching = true;
while ( searching ) {
number = concatenate(primeFactors(number));
previousNumbers.add(number);
if ( number.isProbablePrime(CERTAINTY_LEVEL) ) {
final int lastIndex = previousNumbers.size() - 1;
for ( int k = lastIndex; k >= 1; k-- ) {
System.out.print("HP" + previousNumbers.get(lastIndex - k) + "(" + k + ") = ");
}
System.out.println(previousNumbers.get(lastIndex));
searching = false;
}
}
}
}
private static List<BigInteger> primeFactors(BigInteger aNumber) {
List<BigInteger> result = new ArrayList<BigInteger>();
if ( aNumber.compareTo(BigInteger.valueOf(PRIME_LIMIT * PRIME_LIMIT)) <= 0 ) {
return smallPrimeFactors(aNumber);
}
if ( aNumber.isProbablePrime(CERTAINTY_LEVEL) ) {
result.add(aNumber);
return result;
}
BigInteger divisor = pollardRho(aNumber);
result.addAll(primeFactors(divisor));
aNumber = aNumber.divide(divisor);
result.addAll(primeFactors(aNumber));
Collections.sort(result);
return result;
}
private static List<BigInteger> smallPrimeFactors(BigInteger aNumber) {
int number = aNumber.intValueExact();
List<BigInteger> result = new ArrayList<BigInteger>();
for ( int i = 0; i < primes.size() && number > 1; i++ ) {
while ( number % primes.get(i) == 0 ) {
result.add(BigInteger.valueOf(primes.get(i)));
number /= primes.get(i);
}
}
if ( number > 1 ) {
result.add(BigInteger.valueOf(number));
}
return result;
}
 
private static BigInteger pollardRho(BigInteger aNumber) {
if ( ! aNumber.testBit(0) ) {
return BigInteger.TWO;
}
final BigInteger constant = new BigInteger(aNumber.bitLength(), RANDOM);
BigInteger x = new BigInteger(aNumber.bitLength(), RANDOM);
BigInteger y = x;
BigInteger divisor = null;
do {
x = x.multiply(x).add(constant).mod(aNumber);
y = y.multiply(y).add(constant).mod(aNumber);
y = y.multiply(y).add(constant).mod(aNumber);
divisor = x.subtract(y).gcd(aNumber);
} while ( divisor.compareTo(BigInteger.ONE) == 0 );
return divisor;
}
private static BigInteger concatenate(List<BigInteger> aList) {
String number = aList.stream().map(String::valueOf).collect(Collectors.joining());
return new BigInteger(number);
}
public static void listPrimes(int aNumber) {
BitSet sieve = new BitSet(aNumber + 1);
sieve.set(2, aNumber + 1);
for ( int i = 2; i <= Math.sqrt(aNumber); i = sieve.nextSetBit(i + 1) ) {
for ( int j = i * i; j <= aNumber; j = j + i ) {
sieve.clear(j);
}
}
primes = new ArrayList<Integer>(sieve.cardinality());
for ( int i = 2; i >= 0; i = sieve.nextSetBit(i + 1) ) {
primes.add(i);
}
}
private static List<Integer> primes;
private static final int CERTAINTY_LEVEL = 20;
private static final int PRIME_LIMIT = 10_000;
private static final ThreadLocalRandom RANDOM = ThreadLocalRandom.current();
}
</syntaxhighlight>
{{ out }}
<pre>
HP2(1) = 2
HP3(1) = 3
HP4(2) = HP22(1) = 211
HP5(1) = 5
HP6(1) = 23
HP7(1) = 7
HP8(13) = HP222(12) = HP2337(11) = HP31941(10) = HP33371313(9) = HP311123771(8) = HP7149317941(7) = HP22931219729(6)
= HP112084656339(5) = HP3347911118189(4) = HP11613496501723(3) = HP97130517917327(2) = HP531832651281459(1)
= 3331113965338635107
HP9(2) = HP33(1) = 311
HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773
HP11(1) = 11
HP12(1) = 223
HP13(1) = 13
HP14(5) = HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367
HP15(4) = HP35(3) = HP57(2) = HP319(1) = 1129
HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 31636373
HP17(1) = 17
HP18(1) = 233
HP19(1) = 19
HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8)
= HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3)
= HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413
HP65(19) = HP513(18) = HP33319(17) = HP1113233(16) = HP11101203(15) = HP332353629(14) = HP33152324247(13)
= HP3337473732109(12) = HP111801316843763(11) = HP151740406071813(10) = HP31313548335458223(9)
= HP3397179373752371411(8) = HP157116011350675311441(7) = HP331333391143947279384649(6)
= HP11232040692636417517893491(5) = HP711175663983039633268945697(4) = HP292951656531350398312122544283(3)
= HP2283450603791282934064985326977(2) = HP333297925330304453879367290955541(1) = 1381321118321175157763339900357651
</pre>
 
=={{header|Julia}}==
Line 521 ⟶ 673:
HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413
HP65(19) = HP513(18) = HP33319(17) = HP1113233(16) = HP11101203(15) = HP332353629(14) = HP33152324247(13) = HP3337473732109(12) = HP111801316843763(11) = HP151740406071813(10) = HP31313548335458223(9) = HP3397179373752371411(8) = HP157116011350675311441(7) = HP331333391143947279384649(6) = HP11232040692636417517893491(5) = HP711175663983039633268945697(4) = HP292951656531350398312122544283(3) = HP2283450603791282934064985326977(2) = HP333297925330304453879367290955541(1) = 1381321118321175157763339900357651</pre>
 
=={{header|PARI/GP}}==
{{trans|Julia}}
<syntaxhighlight lang="PARI/GP">
homeprimechain(n) = {
my(chain = [], concat_result, factors, factor_str);
while (!isprime(n),
chain = concat(chain, n); /* Append n to the chain */
factors = factor(n);
/* Correctly build the concatenated string of factors */
factor_str = Str(concat(Vec(vector(#factors~, i,
concat(Vec(concat(vector(factors[i, 2], j, Str(factors[i, 1])))))))));
concat_result = factor_str;
\\print("concat_result=" concat_result);
n = eval(concat_result); /* Convert string back to number */
);
concat(chain, n); /* Append the final prime to the chain */
}
 
printHPiter(n, numperline = 4) = {
my(chain = homeprimechain(n), len = #chain, i);
for (i = 1, len,
if (i < len,
print1("HP" , chain[i] , " (" , len - i , ") = " , if(i % numperline == 0, "\n", "")),
print(chain[i], " is prime.\n\n");
);
);
}
 
{
/* Iterate over a set of numbers */
forstep(i = 2, 20, 1, print("Home Prime chain for ", i, ": "); printHPiter(i););
printHPiter(65);
}
</syntaxhighlight>
{{out}}
<pre>
Home Prime chain for 2:
2 is prime.
 
 
Home Prime chain for 3:
3 is prime.
 
 
Home Prime chain for 4:
HP4 (2) = HP22 (1) = 211 is prime.
 
 
Home Prime chain for 5:
5 is prime.
 
 
Home Prime chain for 6:
HP6 (1) = 23 is prime.
 
 
Home Prime chain for 7:
7 is prime.
 
 
Home Prime chain for 8:
HP8 (13) = HP222 (12) = HP2337 (11) = HP31941 (10) =
HP33371313 (9) = HP311123771 (8) = HP7149317941 (7) = HP22931219729 (6) =
HP112084656339 (5) = HP3347911118189 (4) = HP11613496501723 (3) = HP97130517917327 (2) =
HP531832651281459 (1) = 3331113965338635107 is prime.
 
 
Home Prime chain for 9:
HP9 (2) = HP33 (1) = 311 is prime.
 
 
Home Prime chain for 10:
HP10 (4) = HP25 (3) = HP55 (2) = HP511 (1) =
773 is prime.
 
 
Home Prime chain for 11:
11 is prime.
 
 
Home Prime chain for 12:
HP12 (1) = 223 is prime.
 
 
Home Prime chain for 13:
13 is prime.
 
 
Home Prime chain for 14:
HP14 (5) = HP27 (4) = HP333 (3) = HP3337 (2) =
HP4771 (1) = 13367 is prime.
 
 
Home Prime chain for 15:
HP15 (4) = HP35 (3) = HP57 (2) = HP319 (1) =
1129 is prime.
 
 
Home Prime chain for 16:
HP16 (4) = HP2222 (3) = HP211101 (2) = HP3116397 (1) =
31636373 is prime.
 
 
Home Prime chain for 17:
17 is prime.
 
 
Home Prime chain for 18:
HP18 (1) = 233 is prime.
 
 
Home Prime chain for 19:
19 is prime.
 
 
Home Prime chain for 20:
HP20 (15) = HP225 (14) = HP3355 (13) = HP51161 (12) =
HP114651 (11) = HP3312739 (10) = HP17194867 (9) = HP194122073 (8) =
HP709273797 (7) = HP39713717791 (6) = HP113610337981 (5) = HP733914786213 (4) =
HP3333723311815403 (3) = HP131723655857429041 (2) = HP772688237874641409 (1) = 3318308475676071413 is prime.
 
 
HP65 (19) = HP513 (18) = HP33319 (17) = HP1113233 (16) =
HP11101203 (15) = HP332353629 (14) = HP33152324247 (13) = HP3337473732109 (12) =
HP111801316843763 (11) = HP151740406071813 (10) = HP31313548335458223 (9) = HP3397179373752371411 (8) =
HP157116011350675311441 (7) = HP331333391143947279384649 (6) = HP11232040692636417517893491 (5) = HP711175663983039633268945697 (4) =
HP292951656531350398312122544283 (3) = HP2283450603791282934064985326977 (2) = HP333297925330304453879367290955541 (1) = 1381321118321175157763339900357651 is prime.
 
 
 
</pre>
 
 
=={{header|Perl}}==
Line 681 ⟶ 966:
= 1381_3211183211_75157763339900357651 [13.9s]
</pre>
=={{header|Python}}==
 
Abhorrently Slow, but it works.
<syntaxhighlight lang="python">
# home_primes.py by Xing216
def primeFactors(n: int) -> list[int]:
primeFactorsL = []
while n % 2 == 0:
primeFactorsL.append(2)
n = n // 2
for i in range(3,int(n**0.5)+1,2):
while n % i== 0:
primeFactorsL.append(i)
n = n // i
if n > 2:
primeFactorsL.append(n)
return primeFactorsL
def list_to_int(l: list[int]) -> int:
return int(''.join(str(i) for i in l))
def home_prime_chain(i:int) -> list[int]:
pf_int = i
chain = []
while True:
pf = primeFactors(pf_int)
pf_int = list_to_int(pf)
if len(pf) == 1:
return chain
else:
chain.append(pf_int)
for i in range(2,21):
chain_list = home_prime_chain(i)
chain_len = len(chain_list)
chain_idx_list = list(range(chain_len))[::-1]
j = chain_len
if chain_list != []:
print(f"HP{i}({chain_len}) =", end=" ")
for k,l in list(zip(chain_list, chain_idx_list)):
if l == 0:
print(f"{k}")
else:
print(f"HP{k}({l}) =", end=" ")
else:
print(f"HP{i}(1) = {i}")
</syntaxhighlight>
{{out}}
<pre style="height: 10em">
HP2(1) = 2
HP3(1) = 3
HP4(2) = HP22(1) = 211
HP5(1) = 5
HP6(1) = 23
HP7(1) = 7
HP8(13) = HP222(12) = HP2337(11) = HP31941(10) = HP33371313(9) = HP311123771(8) = HP7149317941(7) = HP22931219729(6) = HP112084656339(5) = HP3347911118189(4) = HP11613496501723(3) = HP97130517917327(2) = HP531832651281459(1) = 3331113965338635107
HP9(2) = HP33(1) = 311
HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773
HP11(1) = 11
HP12(1) = 223
HP13(1) = 13
HP14(5) = HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367
HP15(4) = HP35(3) = HP57(2) = HP319(1) = 1129
HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 31636373
HP17(1) = 17
HP18(1) = 233
HP19(1) = 19
HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413
</pre>
=={{header|Raku}}==
 
Line 838 ⟶ 1,187:
home prime chain for 19: 19 is prime.
home prime chain for 20: HP20(15) ─► HP225(14) ─► HP3355(13) ─► HP51161(12) ─► HP114651(11) ─► HP3312739(10) ─► HP17194867(9) ─► HP194122073(8) ─► HP709273797(7) ─► HP39713717791(6) ─► HP113610337981(5) ─► HP733914786213(4) ─► HP3333723311815403(3) ─► HP131723655857429041(2) ─► HP772688237874641409(1) ─► 3318308475676071413 is prime.
</pre>
 
=={{header|RPL}}==
{{works with|HP|49}}
« FACTORS ""
OVER SIZE 1 - 1 '''FOR''' j
"" PICK3 j DUP 1 + SUB EVAL ROT
1 ROT '''START''' OVER + '''NEXT'''
NIP +
-2 '''STEP'''
NIP STR→
» '<span style="color:blue">CONCFACT</span>' STO
« 0 → iter
« '''WHILE''' DUP ISPRIME? NOT
'''REPEAT''' DUP <span style="color:blue">CONCFACT</span> 'iter' 1 STO+ '''END'''
'''IF''' iter '''THEN'''
1 iter '''FOR''' j
"HP" ROT + "(" + j + ") = " + SWAP +
'''NEXT'''
'''ELSE''' "HP" OVER + " = " + SWAP + '''END'''
» » '<span style="color:blue">HP</span>' STO
 
« n <span style="color:blue">HP</span> » 'n' 2 20 1 SEQ
{{out}}
<pre>
1: { "HP2 = 2"
"HP3 = 3"
"HP4(2) = HP22(1) = 211"
"HP5 = 5"
"HP6(1) = 23"
"HP7 = 7"
"HP8(13) = HP222(12) = HP2337(11) = HP31941(10) = HP33371313(9) = HP311123771(8) = HP7149317941(7) = HP22931219729(6) = HP112084656339(5) = HP3347911118189(4) = HP11613496501723(3) = HP97130517917327(2) = HP531832651281459(1) = 3331113965338635107"
"HP9(2) = HP33(1) = 311"
"HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773"
"HP11 = 11"
"HP12(1) = 223"
"HP13 = 13"
"HP14(5) = HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367"
"HP15(4) = HP35(3) = HP57(2) = HP319(1) = 1129"
"HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 31636373"
"HP17 = 17"
"HP18(1) = 233"
"HP19 = 19"
"HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413" }
</pre>
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">require 'prime'
 
def concat(n)
n.prime_division.map{|pr, exp| pr.to_s * exp }.join.to_i
end
 
def hp(n)
res = [n]
res << n = concat(n) until n.prime?
res
end
 
def hp_to_s(ar)
return "HP#{ar[0]}(1) = #{ar[0]}" if ar.size == 1
ar[0..-2].map.with_index(1){|n, i| "HP#{n}(#{(ar.size-i)}) = "}.join + ar.last.to_s
end
 
(2..20).each {|n| puts hp_to_s(hp(n)) }
</syntaxhighlight>{{out}}
<pre>HP2(1) = 2
HP3(1) = 3
HP4(2) = HP22(1) = 211
HP5(1) = 5
HP6(1) = 23
HP7(1) = 7
HP8(13) = HP222(12) = HP2337(11) = HP31941(10) = HP33371313(9) = HP311123771(8) = HP7149317941(7) = HP22931219729(6) = HP112084656339(5) = HP3347911118189(4) = HP11613496501723(3) = HP97130517917327(2) = HP531832651281459(1) = 3331113965338635107
HP9(2) = HP33(1) = 311
HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773
HP11(1) = 11
HP12(1) = 223
HP13(1) = 13
HP14(5) = HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367
HP15(4) = HP35(3) = HP57(2) = HP319(1) = 1129
HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 31636373
HP17(1) = 17
HP18(1) = 233
HP19(1) = 19
HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413
</pre>
 
=={{header|Rust}}==
<syntaxhighlight lang="rust">use std::str::FromStr;
use num_bigint::BigUint;
use num_prime::nt_funcs::{is_prime, factorize};
 
fn homechains(n: &BigUint) -> Vec<BigUint> {
let mut links = vec![BigUint::from_str("0").unwrap(); 0].to_vec();
if is_prime(n, None).probably() {
links.push(n.clone());
return links;
}
let mut s = String::from_str("").unwrap();
let d = factorize(n.clone());
for (p, e) in d {
let s2 = format!("{p}");
for _ in 0..e {
s.push_str(&s2);
}
}
let k = BigUint::from_str(&s).unwrap();
links.push(k.clone());
links.append(&mut homechains(&k));
return links;
}
 
fn home_chains_print(num: u64, chains: &mut Vec<BigUint>) {
let mut clen = chains.len();
if clen == 1 {
println!("HP{num} ─► {num}");
} else {
if chains[clen - 1] == chains[clen - 2] {
chains.pop();
clen -= 1;
}
print!("HP{num}({clen}) ─► ");
for (i, k) in chains.iter().enumerate() {
if clen - i > 1 {
print!("HP{k}({}) ─► ", clen - i - 1);
if (i + 1) % 5 == 0 {
println!();
}
} else {
println!("{k}");
}
}
}
}
 
 
fn main() {
for num in 2_u64..21 {
let m = BigUint::from_str(&format!("{num}")).unwrap();
let mut chains = homechains(&m);
home_chains_print(num, &mut chains);
}
let mut chains = homechains(&BigUint::from_str("65").unwrap());
home_chains_print(65_u64, &mut chains);
}
</syntaxhighlight>{{out}}
<pre>
HP2 ─► 2
HP3 ─► 3
HP4(2) ─► HP22(1) ─► 211
HP5 ─► 5
HP6(1) ─► 23
HP7 ─► 7
HP8(13) ─► HP222(12) ─► HP2337(11) ─► HP31941(10) ─► HP33371313(9) ─► HP311123771(8) ─►
HP7149317941(7) ─► HP22931219729(6) ─► HP112084656339(5) ─► HP3347911118189(4) ─► HP11613496501723(3) ─►
HP97130517917327(2) ─► HP531832651281459(1) ─► 3331113965338635107
HP9(2) ─► HP33(1) ─► 311
HP10(4) ─► HP25(3) ─► HP55(2) ─► HP511(1) ─► 773
HP11 ─► 11
HP12(1) ─► 223
HP13 ─► 13
HP14(5) ─► HP27(4) ─► HP333(3) ─► HP3337(2) ─► HP4771(1) ─► 13367
HP15(4) ─► HP35(3) ─► HP57(2) ─► HP319(1) ─► 1129
HP16(4) ─► HP2222(3) ─► HP211101(2) ─► HP3116397(1) ─► 31636373
HP17 ─► 17
HP18(1) ─► 233
HP19 ─► 19
HP20(15) ─► HP225(14) ─► HP3355(13) ─► HP51161(12) ─► HP114651(11) ─► HP3312739(10) ─►
HP17194867(9) ─► HP194122073(8) ─► HP709273797(7) ─► HP39713717791(6) ─► HP113610337981(5) ─►
HP733914786213(4) ─► HP3333723311815403(3) ─► HP131723655857429041(2) ─► HP772688237874641409(1) ─► 3318308475676071413
HP65(19) ─► HP513(18) ─► HP33319(17) ─► HP1113233(16) ─► HP11101203(15) ─► HP332353629(14) ─►
HP33152324247(13) ─► HP3337473732109(12) ─► HP111801316843763(11) ─► HP151740406071813(10) ─► HP31313548335458223(9) ─►
HP3397179373752371411(8) ─► HP157116011350675311441(7) ─► HP331333391143947279384649(6) ─► HP11232040692636417517893491(5)
─► HP711175663983039633268945697(4) ─►
HP292951656531350398312122544283(3) ─► HP2283450603791282934064985326977(2) ─► HP333297925330304453879367290955541(1) ─► 1381321118321175157763339900357651
</pre>
 
Line 934 ⟶ 1,458:
 
Reaches HP20 in about 0.52 seconds but HP65 took just under 40 minutes!
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int
import "./big" for BigInt
var list = (2..20).toList
Line 989 ⟶ 1,513:
{{libheader|Wren-gmp}}
This reduces the overall time taken to 5.1 seconds. The factorization method used is essentially the same as the Wren-cli version so the vast improvement in performance is due solely to the use of GMP.
<syntaxhighlight lang="ecmascriptwren">/* home_primes_gmpHome_primes_2.wren */
 
import "./gmp" for Mpz
Aerobar
1,150

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/332683...361375"