From ac766f4f6ab9db683e29b093bbc48cfe3b27b2b7 Mon Sep 17 00:00:00 2001 From: Adrien Hopkins Date: Mon, 22 Sep 2025 15:56:30 -0500 Subject: Show regular complexity of prime factors This metric shows how many combinations you'll need to memorize prime powers, and how big the numbers are in complementary multiplication. The YouTube video "the best way to count" inspired me to think I need a metric to handle both size and factors, but the specific metric is entirely original (or at least independently discovered). --- factor_info.go | 31 ++++++++++++++++++++++++++++- factors/regular_complexity.go | 16 +++++++++++++++ factors/table_test.go | 45 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 91 insertions(+), 1 deletion(-) create mode 100644 factors/regular_complexity.go diff --git a/factor_info.go b/factor_info.go index 637bde2..638e333 100644 --- a/factor_info.go +++ b/factor_info.go @@ -63,6 +63,11 @@ type factorInfo struct { // reciprocoal has and what patterns are in its row of the multiplication // table. DigitMap []factors.DigitType + // The complexity of each prime factor. + // The amount of numbers to memorize for testing p^e is around RC(p)^e. + // The memorization for the product of prime powers + // is less than the memorization of worst part of the product. + PrimeRegularComplexities map[uint]float64 } const ( @@ -108,10 +113,12 @@ func getFactorInfo(a args) *factorInfo { totativeCount := factors.Totient(radix) totativeRatio := float64(totativeCount) / float64(radix) + var prcs = factors.PrimeRegularComplexities(radix) + return &factorInfo{radix, factors.PrimeFactorize(radix), r_factors, factors.Score(radix), totativeCount, totativeRatio, totativeDigits, factors.BasicRank(radix), factors.Type(radix), - mtc_ptr, math.Log2(float64(radix)), digitMap} + mtc_ptr, math.Log2(float64(radix)), digitMap, prcs} } func (fi *factorInfo) writeTo(w io.Writer) { @@ -141,6 +148,9 @@ func (fi *factorInfo) writeTo(w io.Writer) { fmt.Fprintf(w, "Base-2 Logarithm: %.3f\n", fi.Log2) fmt.Fprintf(w, "Number Length: %.4f×Decimal\n", 1/math.Log10(float64(fi.Radix))) + fmt.Fprint(w, "Prime Regular Complexities: ") + writePRCMap(w, fi.PrimeRegularComplexities) + fmt.Fprintln(w) if len(fi.DigitMap) > 0 { writeDigitMap(w, fi.DigitMap) } @@ -193,3 +203,22 @@ func typeAbbrev(t factors.CompositenessType) string { panic("Should not be possible to get here.") } } + +func writePRCMap(w io.Writer, prcs map[uint]float64) { + var first = true + var primeFactors = make([]uint, 0, len(prcs)) + for p := range prcs { + primeFactors = append(primeFactors, p) + } + sort.Slice(primeFactors, func(i, j int) bool { + return primeFactors[i] < primeFactors[j] + }) + + for _, p := range primeFactors { + if !first { + fmt.Fprintf(w, ", ") + } + first = false + fmt.Fprintf(w, "%d: %.4f", p, prcs[p]) + } +} diff --git a/factors/regular_complexity.go b/factors/regular_complexity.go new file mode 100644 index 0000000..763bcd7 --- /dev/null +++ b/factors/regular_complexity.go @@ -0,0 +1,16 @@ +package factors + +import ( + "math" +) + +func PrimeRegularComplexities(radix uint) map[uint]float64 { + var factorization = PrimeFactorize(radix) + var complexities = make(map[uint]float64, len(factorization.exponents)) + for p, e := range factorization.exponents { + var part = float64(uintpow(p, e)) + var complexity = math.Pow(float64(radix)/part, 1/float64(e)) + complexities[p] = complexity + } + return complexities +} diff --git a/factors/table_test.go b/factors/table_test.go index c7eeb24..1ff795c 100644 --- a/factors/table_test.go +++ b/factors/table_test.go @@ -18,6 +18,7 @@ package factors import ( "fmt" + "math" "testing" ) @@ -402,6 +403,30 @@ func TestSplit(t *testing.T) { tableTest(t, splitTest, splitCases, stdEquals[uintPair], "Split") } +var primeRegularComplexityCases = map[uint]map[uint]float64{ + 2: {2: 1}, + 3: {3: 1}, + 4: {2: 1}, + 6: {2: 3, 3: 2}, + 10: {2: 5, 5: 2}, + 12: {2: math.Sqrt(3), 3: 4}, + 20: {2: math.Sqrt(5), 5: 4}, + 24: {2: math.Cbrt(3), 3: 8}, + 36: {2: 3, 3: 2}, + 40: {2: math.Cbrt(5), 5: 8}, + 60: {2: math.Sqrt(15), 3: 20, 5: 12}, + 120: {2: math.Cbrt(15), 3: 40, 5: 24}, + 360: {2: math.Cbrt(45), 3: math.Sqrt(40), 5: 72}, +} + +func TestPrimeRegularComplexity(t *testing.T) { + // Use approxEquals instead of == due to differences between + // math.Sqrt/math.Cbrt and math.Pow. + // The different digits are never shown to the user, so no big deal. + tableTest(t, PrimeRegularComplexities, primeRegularComplexityCases, + mapApproxEquals[uint], "PrimeRegularComplexities") +} + // to be used as the equal paramater for tableTest func stdEquals[T comparable](a, b T) bool { return a == b } @@ -421,6 +446,26 @@ func mapEquals[K, V comparable](a, b map[K]V) bool { return true } +func approxEquals(a, b, epsilon float64) bool { + return math.Abs(a-b) <= epsilon*math.Max(math.Abs(a), math.Abs(b)) +} + +func mapApproxEquals[K comparable](a, b map[K]float64) bool { + for k, av := range a { + bv, ok := b[k] + if !ok || !approxEquals(av, bv, 1e-15) { + return false + } + } + for k, bv := range b { + av, ok := a[k] + if !ok || !approxEquals(av, bv, 1e-15) { + return false + } + } + return true +} + func setEquals[E comparable](a, b []E) bool { // use maps to simulate sets // aSet[a] == true means set contains a, false means not -- cgit v1.2.3