diff options
Diffstat (limited to 'factors/table_test.go')
| -rw-r--r-- | factors/table_test.go | 404 |
1 files changed, 404 insertions, 0 deletions
diff --git a/factors/table_test.go b/factors/table_test.go new file mode 100644 index 0000000..ab06aba --- /dev/null +++ b/factors/table_test.go @@ -0,0 +1,404 @@ +package factors + +import ( + "fmt" + "maps" + "slices" + "testing" +) + +// Run a test with a table of cases +func tableTest[IN comparable, OUT any](t *testing.T, toTest func(IN) OUT, + cases map[IN]OUT, equal func(OUT, OUT) bool, name string) { + for input, expected := range cases { + t.Run(fmt.Sprintf("%v", input), func(t *testing.T) { + actual := toTest(input) + if !equal(expected, actual) { + t.Errorf("%s(%v) = %v, expect %v", name, input, actual, expected) + } + }) + } +} + +type uintPair struct{ a, b uint } + +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}}, + 9: PrimeFactorization{map[uint]uint{3: 2}}, + 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}}, + 71: PrimeFactorization{map[uint]uint{71: 1}}, + 1024: PrimeFactorization{map[uint]uint{2: 10}}, + 86400: PrimeFactorization{map[uint]uint{2: 7, 3: 3, 5: 2}}, +} + +func TestPrimeFactorize(t *testing.T) { + equal := func(a, b PrimeFactorization) bool { + return maps.Equal(a.exponents, b.exponents) + } + tableTest(t, PrimeFactorize, primeFactorCases, equal, "PrimeFactorize") +} + +var factorCases = map[uint][]uint{ + 1: []uint{1}, + 2: []uint{1, 2}, + 4: []uint{1, 2, 4}, + 6: []uint{1, 2, 3, 6}, + 9: []uint{1, 3, 9}, + 10: []uint{1, 2, 5, 10}, + 12: []uint{1, 2, 3, 4, 6, 12}, + 13: []uint{1, 13}, + 15: []uint{1, 3, 5, 15}, + 16: []uint{1, 2, 4, 8, 16}, + 18: []uint{1, 2, 3, 6, 9, 18}, + 30: []uint{1, 2, 3, 5, 6, 10, 15, 30}, + 32: []uint{1, 2, 4, 8, 16, 32}, + 33: []uint{1, 3, 11, 33}, + 60: []uint{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}, + 71: []uint{1, 71}, +} + +func TestFactors(t *testing.T) { + tableTest(t, Factors, factorCases, setEquals, "Factors") +} + +var totativeRatioCases = map[uint]float64{ + 1: 1.0, 2: 0.5, 3: 2.0 / 3.0, 4: 0.5, 6: 1.0 / 3.0, 7: 6.0 / 7.0, 8: 0.5, + 10: 0.4, 12: 1.0 / 3.0, 14: 3.0 / 7.0, 15: 8.0 / 15.0, 16: 0.5, 20: 0.4, + 24: 1.0 / 3.0, 30: 4.0 / 15.0, 60: 4.0 / 15.0, 71: 70.0 / 71.0, + 120: 4.0 / 15.0, +} + +func totativeRatio(n uint) float64 { + return float64(Totient(n)) / float64(n) +} + +func TestTotativeRatio(t *testing.T) { + tableTest(t, totativeRatio, totativeRatioCases, stdEquals, "TotativeRatio") +} + +var totientCases = map[uint]uint{ + 0: 0, 1: 1, 2: 1, 3: 2, 4: 2, 6: 2, 7: 6, 8: 4, 10: 4, 12: 4, + 14: 6, 15: 8, 16: 8, 20: 8, 24: 8, 30: 8, 60: 16, 71: 70, 120: 32, +} + +func TestTotativeCount(t *testing.T) { + tableTest(t, Totient, totientCases, stdEquals, "Totient") +} + +var totativeDigitCases = map[uint32][]uint32{ + 0: []uint32{}, + 1: []uint32{1}, + 2: []uint32{1}, + 3: []uint32{1, 2}, + 4: []uint32{1, 3}, + 6: []uint32{1, 5}, + 7: []uint32{1, 2, 3, 4, 5, 6}, + 8: []uint32{1, 3, 5, 7}, + 10: []uint32{1, 3, 7, 9}, + 12: []uint32{1, 5, 7, 11}, + 14: []uint32{1, 3, 5, 9, 11, 13}, + 15: []uint32{1, 2, 4, 7, 8, 11, 13, 14}, + 16: []uint32{1, 3, 5, 7, 9, 11, 13, 15}, + 20: []uint32{1, 3, 7, 9, 11, 13, 17, 19}, + 24: []uint32{1, 5, 7, 11, 13, 17, 19, 23}, + 30: []uint32{1, 7, 11, 13, 17, 19, 23, 29}, + 60: []uint32{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59}, + 71: []uint32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, + 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, + 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, + 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, + 61, 62, 63, 64, 65, 66, 67, 68, 69, 70}, + 120: []uint32{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, + 61, 67, 71, 73, 77, 79, 83, 89, 91, 97, 101, 103, 107, 109, 113, 119}, +} + +func TestTotativeDigits(t *testing.T) { + tableTest(t, TotativeDigits, totativeDigitCases, slices.Equal, + "TotativeDigits") +} + +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, + 71: 72.0 / 71.0, + 120: 3.0, + // number that will use bigScore + 367567200: 62496.0 / 12155.0, +} + +func TestFactorScore(t *testing.T) { + // factors.Score is accurate enough that we can test for exact floats! + tableTest(t, Score, factorScoreCases, stdEquals, "Score") +} + +var basicRankCases = map[uint]string{ + // one test per rank, plus three extra (22, 25, 44) to test that + // n%3 = 1 vs n%3 = 2 doesn't matter + 2: "D-", 3: "E-", 4: "C~", 5: "F+", 6: "B~", 7: "F-", 8: "C-", + 9: "E~", 10: "D+", 11: "F~", 12: "A-", 14: "D~", 15: "E+", 18: "B-", + 20: "C+", 22: "D-", 24: "A~", 25: "F+", 30: "B+", 44: "C~", 60: "A+", + // test that it only depends on n%60 + 62: "D-", 63: "E-", 64: "C~", 65: "F+", 66: "B~", 67: "F-", 68: "C-", + 69: "E~", 70: "D+", 71: "F~", 72: "A-", 74: "D~", 75: "E+", 78: "B-", + 80: "C+", 82: "D-", 84: "A~", 85: "F+", 90: "B+", 104: "C~", 120: "A+", + // test that it can extend to 0 and 1 as well + 0: "A+", 1: "F~", +} + +func TestBasicRank(t *testing.T) { + tableTest(t, BasicRank, basicRankCases, stdEquals, "BasicRank") +} + +var gcdCases = map[struct{ a, b uint32 }]uint32{ + {0, 0}: 0, {1, 1}: 1, + {0, 1}: 1, {1, 0}: 1, + {0, 12}: 12, {12, 0}: 12, + {1, 12}: 1, {12, 1}: 1, + {6, 10}: 2, {10, 6}: 2, + {12, 20}: 4, {20, 12}: 4, + {20, 55}: 5, {55, 20}: 5, + {60, 120}: 60, {120, 60}: 60, + {120, 180}: 60, {180, 120}: 60, +} + +// a version of gcd() for testing purposes +func gcdTest(c struct{ a, b uint32 }) uint32 { + return gcd(c.a, c.b) +} + +func TestGCD(t *testing.T) { + tableTest(t, gcdTest, gcdCases, stdEquals, "gcd") +} + +var mtcCases = map[uint32]uint64{ + 2: 0, 3: 0, 4: 2, 5: 10, 6: 8, + 7: 28, 8: 26, 9: 42, 10: 42, 11: 88, 12: 52, + 13: 130, 14: 100, 15: 116, 16: 138, 18: 146, + 20: 190, 24: 252, 28: 416, 30: 380, 32: 618, 36: 598, + 48: 1100, 60: 1496, 64: 2602, 90: 3662, 120: 6080, + 210: 18542, 360: 54362, 840: 270122, 2520: 2363528, 5040: 9409112, +} + +func TestMTC(t *testing.T) { + tableTest(t, MTC, mtcCases, stdEquals, "MTC") +} + +var sanCases = map[uint]bool{ + 1: true, 2: true, 4: true, 6: true, 12: true, 24: true, 36: true, + 48: true, 60: true, 120: true, 180: true, 240: true, 360: true, + 720: true, 840: true, 1260: true, 1680: true, 2520: true, 5040: true, + 10080: true, 15120: true, 25200: true, 27720: true, 55440: true, + 3: false, 8: false, 13: false, 18: false, 20: false, 30: false, + 31: false, 72: false, 107: false, 135: false, 144: false, 300: false, + 1728: false, 4000: false, 6912: false, 7560: false, +} + +func isSAN(n uint) bool { + return Type(n) >= Superabundant +} + +func TestSAN(t *testing.T) { + tableTest(t, isSAN, sanCases, stdEquals, "isSAN") +} + +var expOrdCases = map[uint]bool{ + 0: true, 1: true, 2: true, 4: true, 5: false, 6: true, 8: true, 12: true, + 16: true, 18: false, 20: false, 27: false, 30: true, 36: true, 44: false, + 60: true, 70: false, 90: false, 96: true, 101: false, 120: true, 144: true, + 180: true, 770: false, 900: true, 6912: true, 10010: false, +} + +func TestExponentsOrdered(t *testing.T) { + tableTest(t, exponentsOrdered, expOrdCases, stdEquals, "exponentsOrdered") +} + +var practicalCases = map[uint]bool{ + 1: true, 2: true, 4: true, 6: true, 8: true, 12: true, 16: true, + 18: true, 20: true, 24: true, 28: true, 30: true, 32: true, 36: true, + 48: true, 60: true, 120: true, 180: true, 240: true, 360: true, + 720: true, 840: true, 1260: true, 1680: true, 2520: true, 5040: true, + 10080: true, 15120: true, 25200: true, 27720: true, 55440: true, + 3: false, 10: false, 27: false, 44: false, 45: false, 68: false, + 70: false, 114: false, 121: false, 770: false, 1729: false, 10010: false, +} + +func TestPractical(t *testing.T) { + tableTest(t, practical, practicalCases, stdEquals, "practical") +} + +var typeCases = map[uint]NumberType{ + 2: ColossallyAbundant, 3: NotPractical, 4: Superabundant, + 6: ColossallyAbundant, 8: OrderedExponent, 10: NotPractical, + 12: ColossallyAbundant, 18: Practical, 20: Practical, 24: Superabundant, + 28: Practical, 30: OrderedExponent, 31: NotPractical, 34: NotPractical, + 60: ColossallyAbundant, 70: NotPractical, 90: Practical, 100: Practical, + 120: ColossallyAbundant, 144: OrderedExponent, 180: Superabundant, + 240: Superabundant, 360: ColossallyAbundant, 720: Superabundant, + 770: NotPractical, 900: OrderedExponent, 1680: Superabundant, + 1729: NotPractical, 6912: OrderedExponent, 10010: NotPractical, + 10080: Superabundant, 15120: Superabundant, 25200: Superabundant, + 27720: Superabundant, 55440: ColossallyAbundant, +} + +func TestType(t *testing.T) { + tableTest(t, Type, typeCases, stdEquals, "Type") +} + +// ====== DIGIT MAP TESTS ====== +var ( + zt = zeroType // 00 - zero + ot = oneType // 0R - one + ft = DigitType{1, Regular} // 1R - factors + rt = DigitType{2, Regular} // 2R - regulars (index 2) + wt = DigitType{0, Omega} // 0ω - omega neighbours + at = DigitType{0, Alpha} // 0α - alpha neighbours + nt = DigitType{0, Pseudoneighbour} // 0N - neighbour-like + pt = DigitType{0, Opaque} // 0P - opaque totatives +) +var digitMapCases = map[uint][]DigitType{ + 0: []DigitType{}, + 1: []DigitType{zt}, + 2: []DigitType{zt, ot}, + 3: []DigitType{zt, ot, wt}, + 4: []DigitType{zt, ot, ft, wt}, + 5: []DigitType{zt, ot, wt, at, wt}, + 6: []DigitType{zt, ot, ft, ft, rt, wt}, + 8: []DigitType{zt, ot, ft, at, ft, pt, DigitType{1, Alpha}, wt}, + 10: []DigitType{zt, ot, ft, wt, rt, ft, DigitType{1, Omega}, pt, + DigitType{3, Regular}, wt}, + 11: []DigitType{zt, ot, wt, at, at, wt, at, pt, nt, pt, wt}, + 12: []DigitType{zt, ot, ft, ft, ft, pt, ft, pt, rt, rt, + DigitType{1, Opaque}, wt}, + 16: []DigitType{zt, ot, ft, wt, ft, wt, DigitType{1, Omega}, pt, + ft, pt, DigitType{1, Omega}, pt, DigitType{1, Omega}, + pt, DigitType{1, Opaque}, wt}, + 17: []DigitType{zt, ot, wt, at, wt, pt, at, pt, wt, at, + pt, pt, nt, pt, pt, pt, wt}, + 19: []DigitType{zt, ot, wt, wt, at, at, wt, pt, nt, wt, + at, pt, nt, pt, pt, nt, pt, pt, wt}, + 22: []DigitType{zt, ot, ft, wt, rt, pt, DigitType{1, Omega}, wt, + DigitType{3, Regular}, pt, DigitType{1, Opaque}, ft, + DigitType{2, Omega}, pt, DigitType{1, Omega}, pt, + DigitType{4, Regular}, pt, DigitType{1, Opaque}, pt, + DigitType{2, Opaque}, wt}, + 24: []DigitType{zt, ot, ft, ft, ft, at, ft, pt, ft, rt, + DigitType{1, Alpha}, pt, ft, pt, DigitType{1, Opaque}, + DigitType{1, Alpha}, rt, pt, rt, pt, DigitType{1, Alpha}, + DigitType{1, Opaque}, DigitType{1, Opaque}, wt}, +} + +func TestDigitMap(t *testing.T) { + tableTest(t, DigitMap, digitMapCases, slices.Equal, "DigitMap") +} + +// ensures GetDigitType(d, r) == DigitMap(r)[d]; +// does not ensure it has the correct value (that's TestDigitMap's job) +func TestGetDigitType(t *testing.T) { + for radix := range digitMapCases { + digitMap := DigitMap(radix) + for digit := range digitMap { + actual := GetDigitType(uint(digit), radix) + if actual != digitMap[digit] { + t.Logf("GetDigitType(%d, %d) = %d", digit, radix, actual) + t.Errorf("GetDigitType(%d, %d) != DigitMap(%d)[%d]", + digit, radix, radix, digit) + } + } + } +} + +// A few test cases related to radix zero +func TestGetDigitTypeMisc(t *testing.T) { + t.Run("GetDigitType(0, 0)", func(t *testing.T) { + if GetDigitType(0, 0) != ft { + t.Errorf("GetDigitType(0, 0) = %s, expected 1R", GetDigitType(0, 0)) + } + }) + t.Run("GetDigitType(1, 0)", func(t *testing.T) { + if GetDigitType(1, 0) != ot { + t.Errorf("GetDigitType(1, 0) = %s, expected 0R", GetDigitType(1, 0)) + } + }) + t.Run("GetDigitType(2, 0)", func(t *testing.T) { + if GetDigitType(2, 0) != pt { + t.Errorf("GetDigitType(2, 0) = %s, expected 0P", GetDigitType(2, 0)) + } + }) +} + +var splitCases = map[uintPair]uintPair{ + // digit, radix, regular part, totative part + uintPair{0, 0}: uintPair{0, 1}, + uintPair{0, 1}: uintPair{1, 0}, + uintPair{0, 2}: uintPair{1, 0}, + uintPair{0, 12}: uintPair{1, 0}, + uintPair{1, 0}: uintPair{1, 1}, + uintPair{20, 0}: uintPair{1, 20}, + uintPair{360, 0}: uintPair{1, 360}, + uintPair{1, 1}: uintPair{1, 1}, + uintPair{12, 1}: uintPair{1, 12}, + uintPair{87, 1}: uintPair{1, 87}, + uintPair{120, 1}: uintPair{1, 120}, + uintPair{1, 2}: uintPair{1, 1}, + uintPair{1, 3}: uintPair{1, 1}, + uintPair{1, 7}: uintPair{1, 1}, + uintPair{1, 12}: uintPair{1, 1}, + uintPair{1, 39}: uintPair{1, 1}, + uintPair{1, 2948}: uintPair{1, 1}, + uintPair{5, 6}: uintPair{1, 5}, + uintPair{10, 6}: uintPair{2, 5}, + uintPair{12, 6}: uintPair{12, 1}, + uintPair{15, 6}: uintPair{3, 5}, + uintPair{35, 6}: uintPair{1, 35}, + uintPair{56, 6}: uintPair{8, 7}, + uintPair{5, 12}: uintPair{1, 5}, + uintPair{10, 12}: uintPair{2, 5}, + uintPair{12, 12}: uintPair{12, 1}, + uintPair{15, 12}: uintPair{3, 5}, + uintPair{35, 12}: uintPair{1, 35}, + uintPair{56, 12}: uintPair{8, 7}, + uintPair{12, 7}: uintPair{1, 12}, + uintPair{56, 7}: uintPair{7, 8}, + uintPair{70, 10}: uintPair{10, 7}, +} + +// testing version of Split +func splitTest(a uintPair) uintPair { + regular, totative := Split(a.a, a.b) + return uintPair{regular, totative} +} + +func TestSplit(t *testing.T) { + tableTest(t, splitTest, splitCases, stdEquals, "Split") +} + +// to be used as the equal paramater for tableTest +func stdEquals[T comparable](a, b T) bool { return a == b } + +func setEquals[E comparable](a, b []E) bool { + // use maps to simulate sets + // aSet[a] == true means set contains a, false means not + aSet := make(map[E]bool) + bSet := make(map[E]bool) + for _, i := range a { + aSet[i] = true + } + for _, j := range b { + bSet[j] = true + } + return maps.Equal(aSet, bSet) +} |