From 7fa8cf9666cd3427dd078bb4a5fdb9fa30c94b09 Mon Sep 17 00:00:00 2001 From: Adrien Hopkins Date: Thu, 7 Sep 2023 11:38:32 -0500 Subject: Calculate type of all radices without -l MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit factors.Type now supports all numbers; I have used lookup arrays instead of determining whether a number is SAN or not. There are only 117 elements to store, and this makes the algorithm Θ(1), so it's an improvement. Also, I have changed the size of some integer values to correspond to this change - they now indicate the size of numbers they can accept. The only outputs that are hidden for large radices are: - The digit map, which goes up to 36 because I don't have any more digits beyond that point - The multiplication table complexity, which is estimated above 2^16 (for performance), and can optionally be extended to 2^32 (above this, the output could overflow a uint64). --- args.go | 13 +++++---- factor_info.go | 26 ++++++----------- factors/factors_test.go | 18 +++++++----- factors/mtc.go | 8 +++--- factors/type.go | 76 +++++++++++++++++++++++++------------------------ radix_info.go | 2 +- 6 files changed, 70 insertions(+), 73 deletions(-) diff --git a/args.go b/args.go index 99f4874..a211435 100644 --- a/args.go +++ b/args.go @@ -11,10 +11,10 @@ const ProgramVersion = "1.0.0-alpha+dev" // The arguments to this program type args struct { - Radix uint - Compact bool - FullMap bool - LargeCalc bool + Radix uint + Compact bool + FullMap bool + ExactMTCLarge bool // If true, exit the program immediately after parsing args. Exit bool } @@ -25,8 +25,9 @@ func parseArgs() (args, error) { flag.BoolVar(&a.FullMap, "f", false, fmt.Sprintf("Show full digit map (up to %d) for every radix", maxSmallRadix)) - flag.BoolVar(&a.LargeCalc, "l", false, - "Calculate exact MTC and radix class for very large radices, which may take a while.") + flag.BoolVar(&a.ExactMTCLarge, "m", false, + fmt.Sprintf("Calculate exact MTC for very large radices (up to %d instead of %d), which may take a while.", + maxExtended, maxNormal)) help := flag.Bool("?", false, "Get information about program usage then exit") version := flag.Bool("V", false, diff --git a/factor_info.go b/factor_info.go index 522112a..03c81f3 100644 --- a/factor_info.go +++ b/factor_info.go @@ -32,7 +32,7 @@ type factorInfo struct { // Whether or not this radix is part of any special factor-related classes. // This is not calculated if the radix is too large - in this case // this field will be nil. - Type *factors.NumberType + Type factors.NumberType // An estimate of the complexity of the radix's multiplication table. // This is not calculated if the radix is too large - in this case // this field will be nil. @@ -58,20 +58,14 @@ const ( maxExtended = 1 << 32 ) -func getFactorInfo(radix uint, fullMap bool, largeCalc bool) *factorInfo { +func getFactorInfo(radix uint, fullMap bool, exactMTCLarge bool) *factorInfo { r_factors := factors.Factors(radix) slices.Sort(r_factors) - var r_type_ptr *factors.NumberType - var mtc_ptr *uint64 - if radix < maxNormal || (largeCalc && radix < maxExtended) { - r_type := factors.Type(uint32(radix)) - r_type_ptr = &r_type - mtc := factors.MTC(uint64(radix)) + var mtc_ptr *uint64 = nil + if radix < maxNormal || (exactMTCLarge && radix < maxExtended) { + mtc := factors.MTC(uint32(radix)) mtc_ptr = &mtc - } else { - r_type_ptr = nil - mtc_ptr = nil } var digitMap []factors.DigitType @@ -91,7 +85,7 @@ func getFactorInfo(radix uint, fullMap bool, largeCalc bool) *factorInfo { return &factorInfo{radix, factors.PrimeFactorize(radix), r_factors, factors.Score(radix), totativeCount, totativeRatio, - factors.BasicRank(radix), r_type_ptr, mtc_ptr, + factors.BasicRank(radix), factors.Type(radix), mtc_ptr, math.Log(float64(radix)), digitMap} } @@ -101,9 +95,7 @@ func (fi *factorInfo) writeTo(w io.Writer) { fmt.Fprintln(w, "2345 Rank:", fi.BasicRank) fmt.Fprintf(w, "Totative Digit Count: %d (%.3f%%)\n", fi.Totient, fi.TotativeRatio*100.0) - if fi.Type != nil { - writeTypeMessage(w, *fi.Type) - } + writeTypeMessage(w, fi.Type) if fi.MTC != nil { fmt.Fprintln(w, "Multiplication Table Complexity:", *fi.MTC) } else { @@ -122,9 +114,7 @@ func (fi *factorInfo) writeTo(w io.Writer) { func (fi *factorInfo) writeToCompact(w io.Writer) { fmt.Fprintf(w, "%d = %s | σ(r)/r: %.2f | φ(r)/r: %.3f\n", fi.Radix, fi.PrimeFactorization, fi.Score, fi.TotativeRatio) - if fi.Type != nil { - fmt.Fprintf(w, "%s | ", typeAbbrev(*fi.Type)) - } + fmt.Fprintf(w, "%s | ", typeAbbrev(fi.Type)) if fi.MTC != nil { fmt.Fprintf(w, "MTC: %d | ", *fi.MTC) } else { diff --git a/factors/factors_test.go b/factors/factors_test.go index 745fd2c..dec651c 100644 --- a/factors/factors_test.go +++ b/factors/factors_test.go @@ -115,7 +115,7 @@ func TestBasicRank(t *testing.T) { tableTest(t, BasicRank, basicRankCases, stdEquals, "BasicRank") } -var gcdCases = map[struct{ a, b uint64 }]uint64{ +var gcdCases = map[struct{ a, b uint32 }]uint32{ {0, 0}: 0, {1, 1}: 1, {6, 10}: 2, {10, 6}: 2, {12, 20}: 4, {20, 12}: 4, @@ -124,7 +124,7 @@ var gcdCases = map[struct{ a, b uint64 }]uint64{ } // a version of gcd() for testing purposes -func gcdTest(c struct{ a, b uint64 }) uint64 { +func gcdTest(c struct{ a, b uint32 }) uint32 { return gcd(c.a, c.b) } @@ -132,7 +132,7 @@ func TestGCD(t *testing.T) { tableTest(t, gcdTest, gcdCases, stdEquals, "gcd") } -var mtcCases = map[uint64]uint64{ +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, @@ -145,7 +145,7 @@ func TestMTC(t *testing.T) { tableTest(t, MTC, mtcCases, stdEquals, "MTC") } -var sanCases = map[uint32]bool{ +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, @@ -155,11 +155,15 @@ var sanCases = map[uint32]bool{ 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[uint32]bool{ +var expOrdCases = map[uint]bool{ 1: true, 2: true, 4: true, 5: false, 6: true, 12: true, 18: false, 20: false, 30: true, 44: false, 60: true, 70: false, 96: true, 101: false, 120: true, 144: true, 770: false, 6912: true, 10010: false, @@ -169,7 +173,7 @@ func TestExponentsOrdered(t *testing.T) { tableTest(t, exponentsOrdered, expOrdCases, stdEquals, "exponentsOrdered") } -var practicalCases = map[uint32]bool{ +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, @@ -183,7 +187,7 @@ func TestPractical(t *testing.T) { tableTest(t, practical, practicalCases, stdEquals, "practical") } -var typeCases = map[uint32]NumberType{ +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, diff --git a/factors/mtc.go b/factors/mtc.go index 655124c..024391e 100644 --- a/factors/mtc.go +++ b/factors/mtc.go @@ -3,15 +3,15 @@ package factors // MTC returns the multiplication table complexity of a radix n. // This is an estimate of how difficult it is to learn a radix's // multiplication table. -func MTC(n uint64) uint64 { +func MTC(n uint32) uint64 { mtc := uint64(0) - for i := uint64(2); i <= n-2; i++ { - mtc += n / gcd(i, n) + for i := uint32(2); i <= n-2; i++ { + mtc += uint64(n / gcd(i, n)) } return mtc } -func gcd(a, b uint64) uint64 { +func gcd(a, b uint32) uint32 { for b > 0 { a, b = b, a%b } diff --git a/factors/type.go b/factors/type.go index 4b58a1d..7a0f877 100644 --- a/factors/type.go +++ b/factors/type.go @@ -3,14 +3,41 @@ package factors import "slices" // The set of all colossaly abundant numbers that are small enough -// to be stored in a uint32. -// These numbers are also the first 14 superior highly composites. -var colossallyAbundantNums = [...]uint32{ +// to be stored in a uint64. +// The first 15 are also the first 15 superior highly composites. +// source: https://oeis.org/A004490 +var colossallyAbundantNums = [...]uint64{ 2, 6, 12, 60, 120, 360, 2520, 5040, 55440, - 720720, 1441440, 4324320, 21621600, 367567200} - -// A cache containing all superabundant numbers up to a certain value -var sanCache = []uint32{1} + 720720, 1441440, 4324320, 21621600, 367567200, 6983776800, + 160626866400, 321253732800, 9316358251200, 288807105787200, + 2021649740510400, 6064949221531200, 224403121196654400, + 9200527969062830400} + +// source: https://oeis.org/A004394 +var superabundantNums = [...]uint64{ + 1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, + 2520, 5040, 10080, 15120, 25200, 27720, 55440, 110880, 166320, 277200, + 332640, 554400, 665280, 720720, 1441440, 2162160, 3603600, 4324320, + 7207200, 8648640, 10810800, 21621600, 36756720, 61261200, 73513440, + 122522400, 147026880, 183783600, 367567200, 698377680, 735134400, + 1102701600, 1163962800, 1396755360, 2327925600, 2793510720, 3491888400, + 6983776800, 13967553600, 20951330400, 27935107200, 41902660800, + 48886437600, 80313433200, 160626866400, 321253732800, 481880599200, + 642507465600, 963761198400, 1124388064800, 1927522396800, 2248776129600, + 3373164194400, 4497552259200, 4658179125600, 6746328388800, 9316358251200, + 13974537376800, 18632716502400, 27949074753600, 32607253879200, + 55898149507200, 65214507758400, 97821761637600, 130429015516800, + 144403552893600, 195643523275200, 288807105787200, 433210658680800, + 577614211574400, 866421317361600, 1010824870255200, 1732842634723200, + 2021649740510400, 3032474610765600, 4043299481020800, 6064949221531200, + 10685862914126400, 12129898443062400, 21371725828252800, 24259796886124800, + 30324746107656000, 32057588742379200, 37400520199442400, 64115177484758400, + 74801040398884800, 112201560598327200, 149602080797769600, + 224403121196654400, 448806242393308800, 897612484786617600, + 1122015605983272000, 1346418727179926400, 1533421328177138400, + 2244031211966544000, 3066842656354276800, 4600263984531415200, + 6133685312708553600, 9200527969062830400, 18401055938125660800, +} // A type of number (as determined by its factors) type NumberType byte @@ -35,10 +62,10 @@ const ( NotPractical NumberType = 0x40 ) -func Type(n uint32) NumberType { - if slices.Contains(colossallyAbundantNums[:], n) { +func Type(n uint) NumberType { + if slices.Contains(colossallyAbundantNums[:], uint64(n)) { return ColossallyAbundant - } else if isSAN(n) { + } else if slices.Contains(superabundantNums[:], uint64(n)) { return Superabundant } else if exponentsOrdered(n) { return OrderedExponent @@ -49,32 +76,7 @@ func Type(n uint32) NumberType { } } -func isSAN(n uint32) bool { - if n <= 2 { - return true - } else if n%4 != 0 && n%6 != 0 { - return false - } - - cachedMax := sanCache[len(sanCache)-1] - maxScore := Score(uint(cachedMax)) - nScore := Score(uint(n)) - for i := cachedMax + 1; i <= n; i++ { - iScore := Score(uint(i)) - if iScore > maxScore { - sanCache = append(sanCache, i) - maxScore = iScore - if maxScore > nScore { - return false - } - } - } - - _, found := slices.BinarySearch(sanCache, n) - return found -} - -func exponentsOrdered(n uint32) bool { +func exponentsOrdered(n uint) bool { if n <= 2 { return true } else if n%4 != 0 && n%6 != 0 { @@ -99,7 +101,7 @@ func exponentsOrdered(n uint32) bool { return true } -func practical(n uint32) bool { +func practical(n uint) bool { if n <= 2 { return true } else if n%4 != 0 && n%6 != 0 { diff --git a/radix_info.go b/radix_info.go index afcc5b2..9845572 100644 --- a/radix_info.go +++ b/radix_info.go @@ -12,7 +12,7 @@ func main() { } if err == nil { - factorInfo := getFactorInfo(args.Radix, args.FullMap, args.LargeCalc) + factorInfo := getFactorInfo(args.Radix, args.FullMap, args.ExactMTCLarge) if args.Compact { factorInfo.writeToCompact(os.Stdout) } else { -- cgit v1.2.3