Add totative ratio and factor score to program

3 files changed, 122 insertions, 24 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
+}