Merge remote-tracking branch 'upstream/master'

74 files changed, 6308 insertions, 2947 deletions

diff --git a/challenge-168/duncan-c-white/perl/PrimeFactors.pm b/challenge-168/duncan-c-white/perl/PrimeFactors.pm
index 5ec2210764..95c5043d15 100644
--- a/challenge-168/duncan-c-white/perl/PrimeFactors.pm
+++ b/challenge-168/duncan-c-white/perl/PrimeFactors.pm
@@ -40,7 +40,7 @@ fun prime_factors( $n )
 {
 	die "prime_factors: n ($n) must be >1\n" if $n<=1;
 	my @result;
-	my $lim = int(sqrt($n));
+	my $lim = $n;
 	my $orign = $n;
 	foreach my $f (2..$lim)
 	{
@@ -50,8 +50,6 @@ fun prime_factors( $n )
 		{
 			say "pf($orign): n=$n, adding $f to result" if $debug;
 			push @result, $f;
-			my $other = $orign / $f;
-			push @result, $other if isprime($other) && $other != $f;
 			$n /= $f;
 			say "pf($orign): n /= $f (so n=$n now)" if $debug;
 		}
diff --git a/challenge-168/pokgopun/go/ch-1.go b/challenge-168/pokgopun/go/ch-1.go
index 39b69a4633..9e2b200626 100644
--- a/challenge-168/pokgopun/go/ch-1.go
+++ b/challenge-168/pokgopun/go/ch-1.go
@@ -1,42 +1,29 @@
+/*
+The Perrin sequence is defined to start with [3, 0, 2]; after that, term N is the sum of terms N-2 and N-3. (So it continues 3, 2, 5, 5, 7, ….)
+
+A Perrin prime is a number in the Perrin sequence which is also a prime number.
+
+Calculate the first 13 Perrin Primes.
+
+f(13) = [2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977]
+*/
 package main
 
 import (
 	"fmt"
-	"math/big"
+	"log"
 	"os"
-	"sort"
+
+	"github.com/pokgopun/go/perrinprime"
 )
 
 func main() {
-	l := 13
+	n := 13
 	if len(os.Args) > 1 {
-		fmt.Sscanf(os.Args[1], "%d", &l)
-	}
-	p := [3]uint{3, 0, 2}
-	pp := map[uint]struct{}{}
-	e := 0.25
-	i, n := 0, 1
-	for len(pp) < l && i < 1_000_000 {
-		i++
-		for float64(e) > 1/float64(p[0]) {
-			e *= 0.25
-			n++
-		}
-		//fmt.Printf("p0=%v,n=%v\n", p[0], n)
-		if big.NewInt(int64(p[0])).ProbablyPrime(n) {
-			pp[p[0]] = struct{}{}
+		_, err := fmt.Sscanf(os.Args[1], "%d", &n)
+		if err != nil {
+			log.Fatal(err)
 		}
-		p = [3]uint{p[1], p[2], p[0] + p[1]}
-	}
-	ppl := make([]uint, len(pp))
-	var j int
-	for k := range pp {
-		ppl[j] = k
-		j++
 	}
-	sort.SliceStable(ppl, func(i, j int) bool {
-		return ppl[i] < ppl[j]
-	})
-	fmt.Println(ppl)
-	//fmt.Println(len(pp))
+	fmt.Printf("f(%d) = [%v]\n", n, perrinprime.NewPerrinPrime(n))
 }
diff --git a/challenge-168/pokgopun/go/ch-2.go b/challenge-168/pokgopun/go/ch-2.go
index 59d4413c81..70b413fbcc 100644
--- a/challenge-168/pokgopun/go/ch-2.go
+++ b/challenge-168/pokgopun/go/ch-2.go
@@ -1,150 +1,37 @@
+/*
+You are given an integer greater than 1.
+
+Write a script to find the home prime of the given number.
+
+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.
+*/
 package main
 
 import (
 	"fmt"
 	"log"
-	"math"
 	"math/big"
 	"os"
-	"strconv"
+
+	"github.com/pokgopun/go/homeprime"
 )
 
 func main() {
-	var hp homePrime
-	hp.buildPrime(5_000_000, 0)
-	//fmt.Println(hp.plist, len(hp.plist))
+	var s []*big.Int
 	if len(os.Args) > 1 {
 		for _, v := range os.Args[1:] {
-			n, err := strconv.Atoi(v)
-			if err != nil {
-				log.Fatal(err)
+			n, ok := new(big.Int).SetString(v, 10)
+			if !ok {
+				log.Fatal("failed to set string for big.int")
 			}
-			fmt.Printf("HP(%d) = %d\n", n, hp.find(n))
+			s = append(s, n)
 		}
 	} else {
-		for i := 1; i <= 47; i++ {
-			fmt.Printf("HP(%d) = %d\n", i, hp.find(i))
-		}
-	}
-}
-
-func (hp homePrime) find(n int) *big.Int {
-	bi := big.NewInt(int64(n))
-	if n == 1 {
-		return bi
-	}
-	i := 1
-	e := big.NewInt(4)
-	for e.Cmp(bi) == -1 {
-		e.Mul(e, big.NewInt(4))
-		i++
-	}
-	for !bi.ProbablyPrime(i) {
-		var str string
-		f := hp.factor(bi)
-		//fmt.Println(f)
-		for _, v := range f {
-			str += strconv.Itoa(int(v))
-		}
-		//fmt.Println(str)
-		_, ok := bi.SetString(str, 0)
-		if !ok {
-			//fmt.Println("Failed on SetString for", bi)
-			return big.NewInt(-1)
+		for i := int64(2); i <= 64; i++ {
+			s = append(s, big.NewInt(i))
 		}
 	}
-	return bi
-}
-
-func (hp *homePrime) buildPrime(n int, o int) {
-	hp.pmap = make([]bool, int(n)+1)
-	//for i := 2; i <= n; i++ {
-	for i := 1; i <= n; i++ {
-		hp.pmap[i] = true
-	}
-	if o < 1 {
-		hp.pmap[1] = false
+	for _, v := range s {
+		fmt.Printf("HP(%d) = %v\n", v, homeprime.NewHomePrime(v))
 	}
-	//for i := 2; float64(i) <= math.Sqrt(float64(n)); i++ {
-	for i := 2; float64(i) <= math.Sqrt(float64(n+o)); i++ {
-		j := i * i
-		/*
-			for j <= n {
-				hp.pmap[j] = false
-				j += i
-			}
-		*/
-		for j <= n+o {
-			if j > o {
-				hp.pmap[j-o] = false
-			}
-			j += i
-		}
-	}
-	hp.plist = []int{}
-	/*
-		for i := 2; i < len(hp.pmap); i++ {
-			if hp.pmap[i] {
-				hp.plist = append(hp.plist, i)
-			}
-		}
-	*/
-	for i := 1; i < len(hp.pmap); i++ {
-		if hp.pmap[i] {
-			hp.plist = append(hp.plist, i+o)
-		}
-	}
-}
-
-func (hp *homePrime) factor(n *big.Int) (s []int) {
-	if n.Cmp(big.NewInt(1)) == 1 {
-		j := 1
-		e := big.NewInt(4)
-		for e.Cmp(n) == -1 {
-			e.Mul(e, big.NewInt(4))
-			j++
-			//fmt.Println("In factor's e calculation => e=", e)
-		}
-		if n.ProbablyPrime(j) {
-			return []int{int(n.Int64())}
-		}
-		i := 0
-		m := new(big.Int)
-		nextPrime := big.NewInt(2)
-		if hp.plist[0] != 2 {
-			hp.buildPrime(5_000_000, 0)
-		}
-		o := 0
-		for {
-			if m.Mod(n, nextPrime).Cmp(big.NewInt(0)) != 0 {
-				i++
-				if i+1 > len(hp.plist) {
-					if o < 100_000_000_000 {
-						//hp.buildPrime(l * 1_000)
-						o += 5_000_000
-						hp.buildPrime(5_000_000, o)
-						i = 0
-					} else {
-						return []int{}
-					}
-				}
-				nextPrime = big.NewInt(int64(hp.plist[i]))
-			} else {
-				s = append(s, int(nextPrime.Int64()))
-				n.Div(n, nextPrime)
-				if n.Cmp(big.NewInt(1)) == 0 {
-					break
-				} else if n.ProbablyPrime(j) {
-					s = append(s, int(n.Int64()))
-					break
-				}
-			}
-		}
-	}
-	return s
-}
-
-type homePrime struct {
-	pmap  []bool
-	plist []int
 }
diff --git a/challenge-168/pokgopun/go/homeprime/homeprime.go b/challenge-168/pokgopun/go/homeprime/homeprime.go
new file mode 100644
index 0000000000..48f56c43c6
--- /dev/null
+++ b/challenge-168/pokgopun/go/homeprime/homeprime.go
@@ -0,0 +1,97 @@
+/*
+You are given an integer greater than 1.
+
+Write a script to find the home prime of the given number.
+
+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.
+*/
+package homeprime
+
+import (
+	"log"
+	"math/big"
+
+	"github.com/jbarham/primegen"
+)
+
+type abstractPrimegen struct {
+	nextUint64 func() uint64
+	reset      func()
+}
+
+func (apg abstractPrimegen) Next() *big.Int {
+	return new(big.Int).SetUint64(apg.nextUint64())
+}
+func (apg abstractPrimegen) Reset() {
+	apg.reset()
+}
+
+type bigPrimeGenerator interface {
+	Next() *big.Int
+	Reset()
+}
+type ppFactorizer struct {
+	pg bigPrimeGenerator
+}
+
+func (ppf ppFactorizer) factor(n *big.Int) (s []*big.Int) {
+	d := new(big.Int).Set(ppf.pg.Next())
+	for {
+		if new(big.Int).Mod(n, d).Cmp(big.NewInt(0)) != 0 {
+			d.Set(ppf.pg.Next())
+		} else {
+			s = append(s, new(big.Int).Set(d))
+			n.Div(n, d)
+			if n.Cmp(big.NewInt(1)) == 0 {
+				break
+			} else if n.ProbablyPrime(0) {
+				s = append(s, n)
+				break
+			}
+		}
+	}
+	ppf.pg.Reset()
+	return s
+}
+
+type homePrime struct {
+	n, val *big.Int
+	f      interface {
+		factor(*big.Int) []*big.Int
+	}
+}
+
+func (hp homePrime) String() string {
+	return hp.val.String()
+}
+func (hp *homePrime) resolve() *homePrime {
+	if hp.n.Cmp(big.NewInt(2)) == -1 {
+		log.Fatal("input must be greater than 1")
+	} else if hp.n.Cmp(big.NewInt(49)) == 0 || hp.n.Cmp(big.NewInt(77)) == 0 {
+		hp.val = new(big.Int).SetInt64(-1)
+		return hp
+	}
+	hp.val = new(big.Int).Set(hp.n)
+	for !hp.val.ProbablyPrime(0) {
+		//hp.val.SetString(strings.ReplaceAll(hp.f.factor(hp.val), " ", ""), 10)
+		var str string
+		for _, v := range hp.f.factor(hp.val) {
+			str += v.String()
+		}
+		hp.val.SetString(str, 10)
+		//fmt.Println(hp)
+	}
+	return hp
+}
+func NewHomePrime(n *big.Int) *homePrime {
+	pg := primegen.New()
+	var apg abstractPrimegen
+	apg.nextUint64 = pg.Next
+	apg.reset = pg.Reset
+	var ppf ppFactorizer
+	ppf.pg = apg
+	var hp homePrime
+	hp.f = ppf
+	hp.n = new(big.Int).Set(n)
+	return hp.resolve()
+}
diff --git a/challenge-168/pokgopun/go/homeprime/homeprime_test.go b/challenge-168/pokgopun/go/homeprime/homeprime_test.go
new file mode 100644
index 0000000000..e0c130c962
--- /dev/null
+++ b/challenge-168/pokgopun/go/homeprime/homeprime_test.go
@@ -0,0 +1,18 @@
+package homeprime
+
+import (
+	"math/big"
+	"strings"
+	"testing"
+)
+
+const series string = "2, 3, 211, 5, 23, 7, 3331113965338635107, 311, 773, 11, 223, 13, 13367, 1129, 31636373, 17, 233, 19, 3318308475676071413, 37, 211, 23, 331319, 773, 3251, 13367, 227, 29, 547, 31, 241271, 311, 31397, 1129, 71129, 37, 373, 313, 3314192745739, 41, 379, 43, 22815088913, 3411949, 223, 47, 6161791591356884791277, -1"
+
+func TestNewHomePrime(t *testing.T) {
+	for i, ans := range strings.Split(series, ", ") {
+		res := NewHomePrime(new(big.Int).SetInt64(int64(i) + 2)).String()
+		if res != ans {
+			t.Error("incorrect result: expected " + ans + ", got " + res)
+		}
+	}
+}
diff --git a/challenge-168/pokgopun/go/perrinprime/perrinprime.go b/challenge-168/pokgopun/go/perrinprime/perrinprime.go
new file mode 100644
index 0000000000..410970b8ca
--- /dev/null
+++ b/challenge-168/pokgopun/go/perrinprime/perrinprime.go
@@ -0,0 +1,51 @@
+/*
+The Perrin sequence is defined to start with [3, 0, 2]; after that, term N is the sum of terms N-2 and N-3. (So it continues 3, 2, 5, 5, 7, ….)
+
+A Perrin prime is a number in the Perrin sequence which is also a prime number.
+
+Calculate the first 13 Perrin Primes.
+
+f(13) = [2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977]
+*/
+package perrinprime
+
+import (
+	"log"
+	"math/big"
+	"sort"
+	"strconv"
+)
+
+type perrinPrime struct {
+	big.Int
+	base [3]uint
+	vals []uint
+}
+
+func NewPerrinPrime(n int) (pp perrinPrime) {
+	if n < 1 {
+		log.Fatal("must be greater than 1")
+	}
+	pp.base = [3]uint{3, 0, 2}
+	vals := map[uint]struct{}{}
+	for i := 0; i < 1_000_000 && len(vals) < n; i++ {
+		if pp.SetInt64(int64(pp.base[0])).ProbablyPrime(0) {
+			vals[pp.base[0]] = struct{}{}
+		}
+		pp.base = [3]uint{pp.base[1], pp.base[2], pp.base[0] + pp.base[1]}
+	}
+	for k := range vals {
+		pp.vals = append(pp.vals, k)
+	}
+	sort.SliceStable(pp.vals, func(i, j int) bool {
+		return pp.vals[i] < pp.vals[j]
+	})
+	return pp
+}
+func (pp perrinPrime) String() string {
+	var str string
+	for _, v := range pp.vals {
+		str += ", " + strconv.FormatUint(uint64(v), 10)
+	}
+	return str[2:]
+}
diff --git a/challenge-168/pokgopun/go/perrinprime/perrinprime_test.go b/challenge-168/pokgopun/go/perrinprime/perrinprime_test.go
new file mode 100644
index 0000000000..917b7ba9a8
--- /dev/null
+++ b/challenge-168/pokgopun/go/perrinprime/perrinprime_test.go
@@ -0,0 +1,11 @@
+package perrinprime
+
+import "testing"
+
+func TestNewPerrinPrime(t *testing.T) {
+	res := NewPerrinPrime(13).String()
+	ans := "2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977"
+	if res != ans {
+		t.Error("incorrect result: expected " + ans + ", got " + res)
+	}
+}
diff --git a/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/.gitignore b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/.gitignore
new file mode 100644
index 0000000000..3ee7710113
--- /dev/null
+++ b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/.gitignore
@@ -0,0 +1,5 @@
+_*
+6.out
+*.6
+primes
+primespeed
diff --git a/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/LICENSE b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/LICENSE
new file mode 100644
index 0000000000..c4642a0d3e
--- /dev/null
+++ b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/LICENSE
@@ -0,0 +1,21 @@