Home primes: Difference between revisions

Line 116:

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

HP65 = HP513(1) = HP33319(2) = HP1113233(3) = HP11101203(4) = HP332353629(5) = HP33152324247(6) = HP3337473732109(7) = HP111801316843763(8) = HP151740406071813(9) = HP31313548335458223(10) = HP3397179373752371411(11) = HP157116011350675311441(12) = HP331333391143947279384649(13) = HP11232040692636417517893491(14) = HP711175663983039633268945697(15) = HP292951656531350398312122544283(16) = HP2283450603791282934064985326977(17) = HP333297925330304453879367290955541(18) = HP1381321118321175157763339900357651(19) = 1381321118321175157763339900357651</pre>

=={{header|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>

<pre>

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

</pre>