summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--args.go13
-rw-r--r--factor_info.go26
-rw-r--r--factors/factors_test.go18
-rw-r--r--factors/mtc.go8
-rw-r--r--factors/type.go76
-rw-r--r--radix_info.go2
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 {
generated by cgit v1.2.3 (git 2.46.0) at 2025-12-09 10:52:03 +0000