Home primes: Difference between revisions
Thundergnat (talk | contribs) (Changed iteration count from count-up to count-down to better match wikipedia. Update for modified reqs.) |
Thundergnat (talk | contribs) m (→{{header|Raku}}: remove unnecessary intermediate variables) |
||
Line 93: | Line 93: | ||
for flat 2..20, 65 -> $m { |
for flat 2..20, 65 -> $m { |
||
my ( |
my (@steps, @factors) = $m; |
||
@steps.push: |
@steps.push: @factors.join.Int while (@factors = prime-factors @steps[*-1]) > 1; |
||
my $step = +@steps; |
my $step = +@steps; |
||
say (@steps[0..*-2].map( { "HP$_\({--$step})" } ).join: ' = '), |
say (@steps[0..*-2].map( { "HP$_\({--$step})" } ).join: ' = '), |
Revision as of 23:59, 24 May 2021
This page uses content from Wikipedia. The original article was at Home prime. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
In number theory, the home prime HP(n) of an integer n greater than 1 is the prime number obtained by repeatedly factoring the increasing concatenation of prime factors including repetitions.
The traditional notation has the prefix "HP" and a postfix count of the number of iterations until the Home prime is found (if the count is greater than 0).
Prime numbers are their own Home prime;
So:
HP2 = 2 HP7 = 7
If the integer obtained by concatenating increasing prime factors is not prime, iterate until you reach a prime number; the Home prime.
HP4(2) = HP22(1) = 211 HP4(2) = 2 × 2 => 22; HP22(1) = 2 × 11 => 211; 211 is prime HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773 HP10(4) = 2 × 5 => 25; HP25(3) = 5 × 5 => 55; HP55(2) = 5 × 11 => 511; HP511(1) = 7 × 73 => 773; 773 is prime
- Task
Find and show here, on this page, the Home prime iteration chains for the integers 2 through 20 inclusive.
- Stretch goal
Find and show the iteration chain for 65.
- Impossible goal
Show the the Home prime for HP49.
- See also
Factor
<lang factor>USING: formatting kernel make math math.parser math.primes math.primes.factors math.ranges present prettyprint sequences sequences.extras ;
- squish ( seq -- n ) [ present ] map-concat dec> ;
- next ( m -- n ) factors squish ; inline
- (chain) ( n -- ) [ dup prime? ] [ dup , next ] until , ;
- chain ( n -- seq ) [ (chain) ] { } make ;
- chain. ( n -- )
chain [ last ] [ ] bi unclip "HP%d = " printf [ 1 + "HP%d(%d) = " printf ] each-index . ;
2 20 [a,b] [ chain. ] each</lang>
- Output:
HP2 = 2 HP3 = 3 HP4 = HP22(1) = HP211(2) = 211 HP5 = 5 HP6 = HP23(1) = 23 HP7 = 7 HP8 = HP222(1) = HP2337(2) = HP31941(3) = HP33371313(4) = HP311123771(5) = HP7149317941(6) = HP22931219729(7) = HP112084656339(8) = HP3347911118189(9) = HP11613496501723(10) = HP97130517917327(11) = HP531832651281459(12) = HP3331113965338635107(13) = 3331113965338635107 HP9 = HP33(1) = HP311(2) = 311 HP10 = HP25(1) = HP55(2) = HP511(3) = HP773(4) = 773 HP11 = 11 HP12 = HP223(1) = 223 HP13 = 13 HP14 = HP27(1) = HP333(2) = HP3337(3) = HP4771(4) = HP13367(5) = 13367 HP15 = HP35(1) = HP57(2) = HP319(3) = HP1129(4) = 1129 HP16 = HP2222(1) = HP211101(2) = HP3116397(3) = HP31636373(4) = 31636373 HP17 = 17 HP18 = HP233(1) = 233 HP19 = 19 HP20 = HP225(1) = HP3355(2) = HP51161(3) = HP114651(4) = HP3312739(5) = HP17194867(6) = HP194122073(7) = HP709273797(8) = HP39713717791(9) = HP113610337981(10) = HP733914786213(11) = HP3333723311815403(12) = HP131723655857429041(13) = HP772688237874641409(14) = HP3318308475676071413(15) = 3318308475676071413
Raku
Using Prime::Factor from the Raku ecosystem.
<lang perl6>use Prime::Factor;
for flat 2..20, 65 -> $m {
my (@steps, @factors) = $m; @steps.push: @factors.join.Int while (@factors = prime-factors @steps[*-1]) > 1; my $step = +@steps; say (@steps[0..*-2].map( { "HP$_\({--$step})" } ).join: ' = '), (+@steps > 1 ?? !! "HP$m"), " = ", @steps.tail;
}</lang>
- Output:
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
Wren
Not an easy task for Wren which lacks a fast factorization routine for 'big' integers - for now I've just modified the one I use for 'small' integers.
Manages to reach HP20 in about 78 seconds but HP65 is out of reasonable reach using the present approach. <lang ecmascript>import "/math" for Int import "/big" for BigInt import "/fmt" for Fmt import "/ioutil" for Output
// simple wheel based prime factors routine for BigInt var primeFactors = Fn.new { |n|
var inc = [4, 2, 4, 2, 4, 6, 2, 6] var factors = [] while (n%2 == 0) { factors.add(2) n = n / 2 } while (n%3 == 0) { factors.add(3) n = n / 3 } while (n%5 == 0) { factors.add(5) n = n / 5 } var k = BigInt.new(7) var i = 0 while (k * k <= n) { if (n%k == 0) { factors.add(k) n = n / k } else { k = k + inc[i] i = (i + 1) % 8 } } if (n > 1) factors.add(n) return factors
}
for (i in 2..20) {
Fmt.write("HP$-2d = ", i) if (Int.isPrime(i)) { System.print(i) continue } var n = 1 var j = BigInt.new(i) while (true) { var k = primeFactors.call(j).reduce("") { |acc, f| acc + f.toString } j = BigInt.new(k) Output.fwrite("HP%(k)(%(n)) = ") if (j.isProbablePrime(1)) { System.print(k) break } else { n = n + 1 } }
}</lang>
- Output:
HP2 = 2 HP3 = 3 HP4 = HP22(1) = HP211(2) = 211 HP5 = 5 HP6 = HP23(1) = 23 HP7 = 7 HP8 = HP222(1) = HP2337(2) = HP31941(3) = HP33371313(4) = HP311123771(5) = HP7149317941(6) = HP22931219729(7) = HP112084656339(8) = HP3347911118189(9) = HP11613496501723(10) = HP97130517917327(11) = HP531832651281459(12) = HP3331113965338635107(13) = 3331113965338635107 HP9 = HP33(1) = HP311(2) = 311 HP10 = HP25(1) = HP55(2) = HP511(3) = HP773(4) = 773 HP11 = 11 HP12 = HP223(1) = 223 HP13 = 13 HP14 = HP27(1) = HP333(2) = HP3337(3) = HP4771(4) = HP13367(5) = 13367 HP15 = HP35(1) = HP57(2) = HP319(3) = HP1129(4) = 1129 HP16 = HP2222(1) = HP211101(2) = HP3116397(3) = HP31636373(4) = 31636373 HP17 = 17 HP18 = HP233(1) = 233 HP19 = 19 HP20 = HP225(1) = HP3355(2) = HP51161(3) = HP114651(4) = HP3312739(5) = HP17194867(6) = HP194122073(7) = HP709273797(8) = HP39713717791(9) = HP113610337981(10) = HP733914786213(11) = HP3333723311815403(12) = HP131723655857429041(13) = HP772688237874641409(14) = HP3318308475676071413(15) = 3318308475676071413