From e50fb2eb3ea3d7040c73daf7cbc7797f45efd893 Mon Sep 17 00:00:00 2001 From: Michael Manring Date: Thu, 16 Jun 2022 15:45:28 +0700 Subject: refactored and add test --- challenge-169/pokgopun/go/achilles/achilles.go | 137 +++++++++++++++++++++ .../pokgopun/go/achilles/achilles_test.go | 11 ++ challenge-169/pokgopun/go/brilliant/brilliant.go | 98 +++++++++++++++ .../pokgopun/go/brilliant/brilliant_test.go | 11 ++ challenge-169/pokgopun/go/ch-1.go | 84 +------------ challenge-169/pokgopun/go/ch-2.go | 124 +------------------ 6 files changed, 263 insertions(+), 202 deletions(-) create mode 100644 challenge-169/pokgopun/go/achilles/achilles.go create mode 100644 challenge-169/pokgopun/go/achilles/achilles_test.go create mode 100644 challenge-169/pokgopun/go/brilliant/brilliant.go create mode 100644 challenge-169/pokgopun/go/brilliant/brilliant_test.go diff --git a/challenge-169/pokgopun/go/achilles/achilles.go b/challenge-169/pokgopun/go/achilles/achilles.go new file mode 100644 index 0000000000..ceefeb2381 --- /dev/null +++ b/challenge-169/pokgopun/go/achilles/achilles.go @@ -0,0 +1,137 @@ +/* +Write a script to generate first 20 Achilles Numbers. Please checkout wikipedia for more information. + +An Achilles number is a number that is powerful but imperfect (not a perfect power). Named after Achilles, a hero of the Trojan war, who was also powerful but imperfect. + +A positive integer n is a powerful number if, for every prime factor p of n, p^2 is also a divisor. + +A number is a perfect power if it has any integer roots (square root, cube root, etc.). +*/ +package achilles + +import ( + "log" + "math" + "math/big" + "strconv" + "strings" +) + +func NewAchlls(n uint) (an achlls) { + if n < 1 { + log.Fatal("number must be greater than 0") + } + // build enough prime numbers to check n numbers of achilles + an.n = int(n) + k := 2 * an.n + if k < 3 { + k = 3 + } + an.buildPrime(k) + // First archilles is 1st prime power of three multiplied by square of 2nd prime => 72 + i := an.plist[0] * an.plist[0] * an.plist[0] * an.plist[1] * an.plist[1] + an.vals = append(an.vals, i) + i++ + for len(an.vals) < an.n { + // pontential achilles would never be prime, fast-forward to the one that is not + for big.NewInt(int64(i)).ProbablyPrime(0) { + i++ + } + // check if it is achilles and store or try next if it is not + if an.isAchlls(i) { + an.vals = append(an.vals, i) + } + i++ + } + //fmt.Println(an.plist) + return an +} + +type achlls struct { + n int + pmap []bool + plist []int + vals []int +} + +func (an achlls) isAchlls(n int) bool { + // achilles is powerful but with imperfect power + m := make(map[int]int) + var d int + max := n + for _, d = range an.plist { + if d*d >= max { + break + } + for n%d == 0 { + m[d]++ + n /= d + } + // a prime factor happens less than twice is not powerful + if m[d] != 0 && m[d] < 2 { + return false + } + } + // a remainder is a prime factor happens once, thus is not powerful + if n > 1 { + return false + } + // having less than two prime factors is not powerful + l := len(m) + if l < 2 { + return false + } + // check for imperfect power + // prime factor powers having a gcd other than 1 indicate a perfect power + var min int + // find the minimum of prime factor powers + for _, v := range m { + if min == 0 { + min = v + } else if min > v { + min = v + } + } + // check if there a valid gcd other than 1 up to min, if so, it idicates a perfect power thus not achilles + for gcd := 2; gcd <= min; gcd++ { + var sum int + for _, v := range m { + sum += v % gcd + } + if sum == 0 { + return false + } + } + // without any further objections, it is achilles + return true +} + +func (an achlls) String() string { + var b strings.Builder + for i := 0; i < an.n; i++ { + b.WriteString(", " + strconv.Itoa(an.vals[i])) + } + return b.String()[2:] +} +func (an *achlls) buildPrime(n int) { + an.pmap = make([]bool, int(n)+1) + for i := 2; i <= n; i++ { + an.pmap[i] = true + } + for i := 2; float64(i) <= math.Sqrt(float64(n)); i++ { + if !an.pmap[i] { + continue + } + j := i * i + for j <= n { + an.pmap[j] = false + j += i + } + } + an.plist = []int{} + for i := 2; i < len(an.pmap); i++ { + if an.pmap[i] { + an.plist = append(an.plist, i) + } + } +} diff --git a/challenge-169/pokgopun/go/achilles/achilles_test.go b/challenge-169/pokgopun/go/achilles/achilles_test.go new file mode 100644 index 0000000000..abf890921a --- /dev/null +++ b/challenge-169/pokgopun/go/achilles/achilles_test.go @@ -0,0 +1,11 @@ +package achilles + +import "testing" + +func TestNewAchlls(t *testing.T) { + res := NewAchlls(20).String() + ans := "72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, 1125, 1152, 1323, 1352, 1372, 1568, 1800" + if res != ans { + t.Error("incorrect result: expected " + ans + ", got " + res) + } +} diff --git a/challenge-169/pokgopun/go/brilliant/brilliant.go b/challenge-169/pokgopun/go/brilliant/brilliant.go new file mode 100644 index 0000000000..2914036105 --- /dev/null +++ b/challenge-169/pokgopun/go/brilliant/brilliant.go @@ -0,0 +1,98 @@ +/* +Write a script to generate first 20 Brilliant Numbers. + +Brilliant numbers are numbers with two prime factors of the same length. + +The number should have exactly two prime factors, i.e. it’s the product of two primes of the same length. +*/ +package brilliant + +import ( + "log" + "math" + "sort" + "strconv" + "strings" +) + +func NewBrllnt(n uint) (bn brllnt) { + if n < 1 { + log.Fatal("number must be greater than 0") + } + bn.n = int(n) + k := 99 + for { + bn.buildPrime(k) + bn.pgroup = [][]int{[]int{}} + bn.vals = []int{} + var i, j int + j++ + for { + if len(strconv.Itoa(bn.plist[i])) == j { + bn.pgroup[j-1] = append(bn.pgroup[j-1], bn.plist[i]) + i++ + if i >= len(bn.plist) { + break + } + } else { + j++ + bn.pgroup = append(bn.pgroup, []int{}) + } + } + for l := 0; l < j; l++ { + for p := 0; p < len(bn.pgroup[l]); p++ { + for q := p; q < len(bn.pgroup[l]); q++ { + bn.vals = append(bn.vals, bn.pgroup[l][p]*bn.pgroup[l][q]) + } + } + } + if len(bn.vals) >= bn.n { + break + } + k = 10*k + 9 + } + sort.SliceStable(bn.vals, func(i, j int) bool { + return bn.vals[i] < bn.vals[j] + }) + //fmt.Println(bn.pgroup) + return bn +} + +type brllnt struct { + n int + pmap []bool + plist []int + pgroup [][]int + vals []int +} + +func (bn brllnt) String() string { + var b strings.Builder + for i := 0; i < bn.n; i++ { + b.WriteString(", " + strconv.Itoa(bn.vals[i])) + } + return b.String()[2:] +} + +func (bn *brllnt) buildPrime(n int) { + bn.pmap = make([]bool, int(n)+1) + for i := 2; i <= n; i++ { + bn.pmap[i] = true + } + for i := 2; float64(i) <= math.Sqrt(float64(n)); i++ { + if !bn.pmap[i] { + continue + } + j := i * i + for j <= n { + bn.pmap[j] = false + j += i + } + } + bn.plist = []int{} + for i := 2; i < len(bn.pmap); i++ { + if bn.pmap[i] { + bn.plist = append(bn.plist, i) + } + } +} diff --git a/challenge-169/pokgopun/go/brilliant/brilliant_test.go b/challenge-169/pokgopun/go/brilliant/brilliant_test.go new file mode 100644 index 0000000000..135dea2176 --- /dev/null +++ b/challenge-169/pokgopun/go/brilliant/brilliant_test.go @@ -0,0 +1,11 @@ +package brilliant + +import "testing" + +func TestNewBrllnt(t *testing.T) { + res := NewBrllnt(20).String() + ans := "4, 6, 9, 10, 14, 15, 21, 25, 35, 49, 121, 143, 169, 187, 209, 221, 247, 253, 289, 299" + if res != ans { + t.Error("incorrect result: expected " + ans + ", got " + res) + } +} diff --git a/challenge-169/pokgopun/go/ch-1.go b/challenge-169/pokgopun/go/ch-1.go index fa6ae0e57c..4a4c03dafa 100644 --- a/challenge-169/pokgopun/go/ch-1.go +++ b/challenge-169/pokgopun/go/ch-1.go @@ -10,11 +10,9 @@ package main import ( "fmt" "log" - "math" "os" - "sort" - "strconv" - "strings" + + "github.com/pokgopun/go/brilliant" ) func main() { @@ -25,81 +23,5 @@ func main() { log.Fatal(err) } } - fmt.Println(newBrlntNum(n)) -} - -func newBrlntNum(n uint) (bn brlntNum) { - if n < 1 { - log.Fatal("number must be greater than 0") - } - bn.n = int(n) - k := 99 - for len(bn.vals) < bn.n { - bn.buildPrime(k) - bn.pgroup = [][]int{[]int{}} - bn.vals = []int{} - var i, j int - j++ - for { - if len(strconv.Itoa(bn.plist[i])) == j { - bn.pgroup[j-1] = append(bn.pgroup[j-1], bn.plist[i]) - i++ - if i >= len(bn.plist) { - break - } - } else { - j++ - bn.pgroup = append(bn.pgroup, []int{}) - } - } - for l := 0; l < j; l++ { - for p := 0; p < len(bn.pgroup[l]); p++ { - for q := p; q < len(bn.pgroup[l]); q++ { - bn.vals = append(bn.vals, bn.pgroup[l][p]*bn.pgroup[l][q]) - } - } - } - k = 10*k + 9 - } - sort.SliceStable(bn.vals, func(i, j int) bool { - return bn.vals[i] < bn.vals[j] - }) - //fmt.Println(bn.pgroup) - return bn -} - -type brlntNum struct { - n int - pmap []bool - plist []int - pgroup [][]int - vals []int -} - -func (bn brlntNum) String() string { - var b strings.Builder - for i := 0; i < bn.n; i++ { - b.WriteString(", " + strconv.Itoa(bn.vals[i])) - } - return b.String()[2:] -} - -func (bn *brlntNum) buildPrime(n int) { - bn.pmap = make([]bool, int(n)+1) - for i := 2; i <= n; i++ { - bn.pmap[i] = true - } - for i := 2; float64(i) <= math.Sqrt(float64(n)); i++ { - j := i * i - for j <= n { - bn.pmap[j] = false - j += i - } - } - bn.plist = []int{} - for i := 2; i < len(bn.pmap); i++ { - if bn.pmap[i] { - bn.plist = append(bn.plist, i) - } - } + fmt.Println(brilliant.NewBrllnt(n)) } diff --git a/challenge-169/pokgopun/go/ch-2.go b/challenge-169/pokgopun/go/ch-2.go index 19c93edbe4..ccd59169ee 100644 --- a/challenge-169/pokgopun/go/ch-2.go +++ b/challenge-169/pokgopun/go/ch-2.go @@ -12,11 +12,9 @@ package main import ( "fmt" "log" - "math" - "math/big" "os" - "strconv" - "strings" + + "github.com/pokgopun/go/achilles" ) func main() { @@ -27,121 +25,5 @@ func main() { log.Fatal(err) } } - fmt.Println(newAchlsNum(n)) -} - -func newAchlsNum(n uint) (an achlsNum) { - if n < 1 { - log.Fatal("number must be greater than 0") - } - // build enough prime numbers to check n numbers of achilles - an.n = int(n) - k := 2 * an.n - if k < 3 { - k = 3 - } - an.buildPrime(k) - // First archilles is 1st prime power of three multiplied by square of 2nd prime => 72 - i := an.plist[0] * an.plist[0] * an.plist[0] * an.plist[1] * an.plist[1] - an.vals = append(an.vals, i) - i++ - for len(an.vals) < an.n { - // pontential achilles would never be prime, fast-forward to the one that is not - for big.NewInt(int64(i)).ProbablyPrime(0) { - i++ - } - // check if it is achilles and store or try next if it is not - if an.isAchls(i) { - an.vals = append(an.vals, i) - } - i++ - } - //fmt.Println(an.plist) - return an -} - -type achlsNum struct { - n int - pmap []bool - plist []int - vals []int -} - -func (an achlsNum) isAchls(n int) bool { - // achilles is powerful but with imperfect power - m := make(map[int]int) - var d int - max := n - for _, d = range an.plist { - if d*d >= max { - break - } - for n%d == 0 { - m[d]++ - n /= d - } - // a prime factor happens less than twice is not powerful - if m[d] != 0 && m[d] < 2 { - return false - } - } - // a remainder is a prime factor happens once, thus is not powerful - if n > 1 { - return false - } - // having less than two prime factors is not powerful - l := len(m) - if l < 2 { - return false - } - // check for imperfect power - // prime factor powers having a gcd other than 1 indicate a perfect power - var min int - // find the minimum of prime factor powers - for _, v := range m { - if min == 0 { - min = v - } else if min > v { - min = v - } - } - // check if there a valid gcd other than 1 up to min, if so, it idicates a perfect power thus not achilles - for gcd := 2; gcd <= min; gcd++ { - var sum int - for _, v := range m { - sum += v % gcd - } - if sum == 0 { - return false - } - } - // without any further objections, it is achilles - return true -} - -func (an achlsNum) String() string { - var b strings.Builder - for i := 0; i < an.n; i++ { - b.WriteString(", " + strconv.Itoa(an.vals[i])) - } - return b.String()[2:] -} -func (an *achlsNum) buildPrime(n int) { - an.pmap = make([]bool, int(n)+1) - for i := 2; i <= n; i++ { - an.pmap[i] = true - } - for i := 2; float64(i) <= math.Sqrt(float64(n)); i++ { - j := i * i - for j <= n { - an.pmap[j] = false - j += i - } - } - an.plist = []int{} - for i := 2; i < len(an.pmap); i++ { - if an.pmap[i] { - an.plist = append(an.plist, i) - } - } + fmt.Println(achilles.NewAchlls(n)) } -- cgit