Add tests for properties of many outputs

- Test that every number returned by factors.Factors is actually a
  factor of its argument.
- Test that every number returned by factors.TotativeDigits is actually
  a totative of its argument, and that len(factors.TotativeDigits(r)) ==
  factors.Totient(r).
- Test the properties of factors.Split (regular * totative == digit,
  totative is a totative of radix).

Some of these tests don't test every number in the range, instead
picking randomly, which is done in order to avoid tests taking too long
to execute.  Some testing is better than no testing!

2 files changed, 105 insertions, 0 deletions

diff --git a/factors/property_test.go b/factors/property_test.go
new file mode 100644
index 0000000..7072050
--- /dev/null
+++ b/factors/property_test.go
@@ -0,0 +1,105 @@
+package factors
+
+import (
+	"fmt"
+	"math/rand"
+	"testing"
+)
+
+// TestFactorsDivisible ensures that every number returned by
+// Factors is actually a factor of the argument.
+func TestFactorsDivisible(t *testing.T) {
+	for r := uint(1); r < (1 << 16); r++ {
+		t.Run(fmt.Sprintf("%d", r), func(t *testing.T) {
+			testFactorsDivisibleOnce(t, r)
+		})
+	}
+}
+
+// One execution of TestFactorsDivisible
+func testFactorsDivisibleOnce(t *testing.T, r uint) {
+	t.Parallel()
+	factors := Factors(r)
+	for _, factor := range factors {
+		if r%factor != 0 {
+			t.Errorf("%d reported as factor of %d, but not divisible", factor, r)
+		}
+	}
+}
+
+// TestTotatives ensures that every number returned by
+// TotativeDigits is actually a totative of the argument.
+// It also tests that len(TotativeDigits(r)) = Totient(r).
+func TestTotatives(t *testing.T) {
+	for r := uint32(0); r < (1 << 12); r++ {
+		t.Run(fmt.Sprintf("%d", r), func(t *testing.T) {
+			testTotativesOnce(t, r)
+		})
+	}
+}
+
+// TestTotativesRandom is like TestTotatives,
+// except it randomly chooses radices.
+func TestTotativesRandom(t *testing.T) {
+	for testRun := 0; testRun < 144; testRun++ {
+		r := uint32(rand.Int31n(1 << 16))
+		t.Run(fmt.Sprintf("%d", r), func(t *testing.T) {
+			testTotativesOnce(t, r)
+		})
+	}
+}
+
+// One execution of TestTotatives
+func testTotativesOnce(t *testing.T, r uint32) {
+	t.Parallel()
+	totatives := TotativeDigits(r)
+	for _, totative := range totatives {
+		if gcd(totative, r) != 1 {
+			t.Errorf("%d reported as totative of %d, but gcd(%d, %d) = %d",
+				totative, r, totative, r, gcd(totative, r))
+		}
+	}
+
+	totient := Totient(uint(r))
+	if uint(len(totatives)) != totient {
+		t.Errorf(
+			"len(TotativeDigits(%d)) = %d, Totient(%d) = %d, should be equal",
+			r, len(totatives), r, totient)
+	}
+}
+
+// TestSplitProperties tests Split(digit, radix) to ensure
+// totative is a totative and regular * totative = digit.
+func TestSplitProperties(t *testing.T) {
+	for radix := uint(1); radix < 1<<7; radix++ {
+		for digit := uint(1); digit < 1<<8; digit++ {
+			t.Run(fmt.Sprintf("radix=%d,digit=%d", radix, digit),
+				func(t *testing.T) { testSplitOnce(t, digit, radix) })
+		}
+	}
+}
+
+// TestSplitRandom is like TestSplitProperties,
+// but with randomly chosen values.
+func TestSplitRandom(t *testing.T) {
+	for i := 0; i < 1728; i++ {
+		radix := uint(rand.Int31n((1<<15)-1)) + 1
+		digit := uint(rand.Int31n((1<<16)-1)) + 1
+		t.Run(fmt.Sprintf("radix=%d,digit=%d", radix, digit),
+			func(t *testing.T) { testSplitOnce(t, digit, radix) })
+	}
+}
+
+// One execution of TestSplitProperties
+func testSplitOnce(t *testing.T, digit, radix uint) {
+	t.Parallel()
+	regular, totative := Split(digit, radix)
+	if gcd(uint32(totative), uint32(radix)) != 1 {
+		t.Errorf("Split(%d, %d) = %d, %d; %d not coprime to %d.",
+			digit, radix, regular, totative, totative, radix)
+	}
+	if regular*totative != digit {
+		t.Errorf("Split(%d, %d) = %d, %d; %d * %d ≠ %d.",
+			digit, radix, regular, totative, regular, totative, digit)
+	}
+}
diff --git a/factors/factors_test.go b/factors/table_test.go
index ab06aba..ab06aba 100644
--- a/factors/factors_test.go
+++ b/factors/table_test.go