diff options
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 @@ +MIT License + +Copyright (c) 2020 John Barham + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/README.md b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/README.md new file mode 100644 index 0000000000..24e32cecb9 --- /dev/null +++ b/challenge-168/pokgopun/go/vendor/github.com/jbarham/primegen/README.md @@ -0,0 +1,23 @@ +# primegen + +*primegen* is a Go package that generates prime numbers in order using the Sieve +of Atkin instead of the tradition |