diff options
| -rw-r--r-- | factors/factors_test.go | 101 | ||||
| -rw-r--r-- | factors/score.go | 28 | ||||
| -rw-r--r-- | factors/totative.go | 17 | ||||
| -rw-r--r-- | radix_info.go | 10 |
4 files changed, 129 insertions, 27 deletions
diff --git a/factors/factors_test.go b/factors/factors_test.go index a2e81cd..ceaf4d1 100644 --- a/factors/factors_test.go +++ b/factors/factors_test.go @@ -2,20 +2,21 @@ package factors import ( "fmt" + "math" "testing" ) var primeFactorCases = map[uint]PrimeFactorization{ - 0: PrimeFactorization{map[uint]uint{0: 1}}, - 1: PrimeFactorization{map[uint]uint{}}, - 2: PrimeFactorization{map[uint]uint{2: 1}}, - 3: PrimeFactorization{map[uint]uint{3: 1}}, - 4: PrimeFactorization{map[uint]uint{2: 2}}, - 6: PrimeFactorization{map[uint]uint{2: 1, 3: 1}}, - 10: PrimeFactorization{map[uint]uint{2: 1, 5: 1}}, - 12: PrimeFactorization{map[uint]uint{2: 2, 3: 1}}, - 33: PrimeFactorization{map[uint]uint{3: 1, 11: 1}}, - 60: PrimeFactorization{map[uint]uint{2: 2, 3: 1, 5: 1}}, + 0: PrimeFactorization{map[uint]uint{0: 1}}, + 1: PrimeFactorization{map[uint]uint{}}, + 2: PrimeFactorization{map[uint]uint{2: 1}}, + 3: PrimeFactorization{map[uint]uint{3: 1}}, + 4: PrimeFactorization{map[uint]uint{2: 2}}, + 6: PrimeFactorization{map[uint]uint{2: 1, 3: 1}}, + 10: PrimeFactorization{map[uint]uint{2: 1, 5: 1}}, + 12: PrimeFactorization{map[uint]uint{2: 2, 3: 1}}, + 33: PrimeFactorization{map[uint]uint{3: 1, 11: 1}}, + 60: PrimeFactorization{map[uint]uint{2: 2, 3: 1, 5: 1}}, 86400: PrimeFactorization{map[uint]uint{2: 7, 3: 3, 5: 2}}, } @@ -32,10 +33,10 @@ func TestPrimeFactorize(t *testing.T) { } var factorCases = map[uint][]uint{ - 1: []uint{1}, - 2: []uint{1, 2}, - 4: []uint{1, 2, 4}, - 6: []uint{1, 2, 3, 6}, + 1: []uint{1}, + 2: []uint{1, 2}, + 4: []uint{1, 2, 4}, + 6: []uint{1, 2, 3, 6}, 10: []uint{1, 2, 5, 10}, 12: []uint{1, 2, 3, 4, 6, 12}, 13: []uint{1, 13}, @@ -56,18 +57,52 @@ func TestFactors(t *testing.T) { } } -func setEquals(a, b []uint) bool { - // use maps to simulate sets - // aSet[a] == true means set contains a, false means not - aSet := make(map[uint]bool) - bSet := make(map[uint]bool) - for _, i := range a { - aSet[i] = true +var totativeRatioCases = map[uint]float64{ + 1: 1.0, + 2: 0.5, + 3: 2.0 / 3.0, + 4: 0.5, + 6: 1.0 / 3.0, + 8: 0.5, + 12: 1.0 / 3.0, +} + +func TestTotativeRatio(t *testing.T) { + for i, expected := range totativeRatioCases { + testname := fmt.Sprintf("%d", i) + t.Run(testname, func(t *testing.T) { + actual := TotativeRatio(i) + if !floatEquals(expected, actual, 1e-15) { + t.Errorf("TotativeRatio(%d) = %v, want %v", i, actual, expected) + } + }) } - for _, j := range b { - bSet[j] = true +} + +var factorScoreCases = map[uint]float64{ + 1: 1.0, + 2: 1.5, + 3: 4.0 / 3.0, + 4: 1.75, + 6: 2.0, + 8: 1.875, + 10: 1.8, + 12: 7.0 / 3.0, + 120: 3.0, +} + +func TestFactorScore(t *testing.T) { + for i, expected := range factorScoreCases { + testname := fmt.Sprintf("%d", i) + t.Run(testname, func(t *testing.T) { + actual := Score(i) + // factors.Score is accurate enough that we can test + // for exact float values! + if expected != actual { + t.Errorf("Score(%d) = %v, want %v", i, actual, expected) + } + }) } - return mapEquals(aSet, bSet) } func mapEquals[K comparable, V comparable](a, b map[K]V) bool { @@ -83,3 +118,21 @@ func mapEquals[K comparable, V comparable](a, b map[K]V) bool { } return true } + +func setEquals(a, b []uint) bool { + // use maps to simulate sets + // aSet[a] == true means set contains a, false means not + aSet := make(map[uint]bool) + bSet := make(map[uint]bool) + for _, i := range a { + aSet[i] = true + } + for _, j := range b { + bSet[j] = true + } + return mapEquals(aSet, bSet) +} + +func floatEquals(a, b, maxDelta float64) bool { + return math.Abs(a-b) <= maxDelta*math.Max(math.Abs(a), math.Abs(b)) +} diff --git a/factors/score.go b/factors/score.go new file mode 100644 index 0000000..707120d --- /dev/null +++ b/factors/score.go @@ -0,0 +1,28 @@ +package factors + +// Score returns a "factor score" equal to the sum of the reciprocoals +// of the number n's factors. +// Rationale: +// A number's factors are one of the most important things that determines +// how well it functions as a number base. An easy way to determine how +// good these factors are is to simply count them, but that comes with +// the problem that all factors are considered equal when they really aren't +// - divisibility by 2 (which ensures 1/2 is a terminating fraction and +// you can tell whether a number is even or odd by looking at the last digit) +// is more important than divisibility by 23. The most obvious way of +// accounting for this is by giving each factor a score and adding those +// scores to get the overall score. I chose score(f) = 1/f because it is +// the simplest function that captures the intuition that smaller factors +// are more valuable than larger ones. It also gives the score a meaning: +// a factor's score is the probability a random number is divisible by it. +func Score(n uint) float64 { + if n == 0 { + panic("Cannot get factor score of 0.") + } + + factorSum := uint(0) + for _, f := range Factors(n) { + factorSum += f + } + return float64(factorSum) / float64(n) +} diff --git a/factors/totative.go b/factors/totative.go new file mode 100644 index 0000000..558f0f0 --- /dev/null +++ b/factors/totative.go @@ -0,0 +1,17 @@ +package factors + +// TotativeRatio calculates the fraction of numbers less than n that +// are totatives of n (share no factors with n) +func TotativeRatio(n uint) float64 { + if n == 0 { + panic("0 has no totative ratio!") + } + + primeFactorization := PrimeFactorize(n) + + totativeRatio := 1.0 + for p := range primeFactorization.exponents { + totativeRatio *= float64(p - 1) / float64(p) + } + return totativeRatio +} diff --git a/radix_info.go b/radix_info.go index 770fd42..4194a2c 100644 --- a/radix_info.go +++ b/radix_info.go @@ -12,12 +12,16 @@ func main() { if len(os.Args) > 1 { if n, err := strconv.ParseUint(os.Args[1], 0, 0); err == nil { if n > 1 { - fmt.Printf("%d = %s\n", n, factors.PrimeFactorize(uint(n))) - n_factors := factors.Factors(uint(n)) + n := uint(n) + fmt.Printf("%d = %s\n", n, factors.PrimeFactorize(n)) + n_factors := factors.Factors(n) sort.Slice(n_factors, func(i, j int) bool { return n_factors[i] < n_factors[j] }) - fmt.Printf("Factors: %v\n", n_factors) + factorScore := factors.Score(n) + fmt.Printf("Factors: %v (Score: %.2f)\n", n_factors, factorScore) + fmt.Printf("Totative Ratio: %03.1f%%\n", + factors.TotativeRatio(n)*100.0) } else { fmt.Println("Argument must be an integer above 1.") } |