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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
package factors
import "slices"
// The set of all colossaly abundant numbers that are small enough
// to be stored in a uint64.
// The first 15 are also the first 15 superior highly composites.
// Number source: The Online Encyclopedia of Integer Sequences
// can be found at the URL https://oeis.org/A004490
var colossallyAbundantNums = [...]uint64{
2, 6, 12, 60, 120, 360, 2520, 5040, 55440,
720720, 1441440, 4324320, 21621600, 367567200, 6983776800,
160626866400, 321253732800, 9316358251200, 288807105787200,
2021649740510400, 6064949221531200, 224403121196654400,
9200527969062830400}
// Number source: The Online Encyclopedia of Integer Sequences
// can be found at the URL 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 classification of numbers, based on how many factors they have.
// Each type is a subset of the next (except [Practical] and [NotPractical]),
// so a number is only counted as its most exclusive type.
// The zero value of this type is invalid.
type NumberType byte
const (
// A number whose factor score is higher than any other,
// if you adjust for size by dividing by some power of the number
// (different powers yield different best numbers).
// All colossally abundant numbers are also superabundant.
ColossallyAbundant NumberType = 0xC0
// A number whose factor score is higher than any smaller number.
// All superabundant numbers have ordered exponents.
Superabundant NumberType = 0xA0
// A number whose prime factorization exponents stay the same or decrease
// as you go from smaller to larger primes.
// All of these numbers are also practical.
OrderedExponent NumberType = 0x80
// A number whose factors can sum to any smaller number without duplication.
// All practical numbers besides 1 and 2 are divisible by 4 or 6.
Practical NumberType = 0x60
// None of the above types
NotPractical NumberType = 0x40
)
// Type determines the [NumberType] of a number.
func Type(n uint) NumberType {
if slices.Contains(colossallyAbundantNums[:], uint64(n)) {
return ColossallyAbundant
} else if slices.Contains(superabundantNums[:], uint64(n)) {
return Superabundant
} else if exponentsOrdered(n) {
return OrderedExponent
} else if practical(n) {
return Practical
} else {
return NotPractical
}
}
// invariant: p must be odd and >= 3
func nextPrime(p uint) uint {
possiblePrime := p + 2
for !isPrime(possiblePrime) {
possiblePrime += 2
}
return possiblePrime
}
func exponentsOrdered(n uint) bool {
if n <= 2 {
return true
} else if n%4 != 0 && n%6 != 0 {
return false
}
pf := PrimeFactorize(n)
maxPrime := slices.Max(pf.Primes())
for prime, prevPrime := uint(3), uint(2); prime <= maxPrime; {
if pf.Exponent(prime) > pf.Exponent(prevPrime) {
return false
} else if pf.Exponent(prime) == 0 && prime < maxPrime {
return false
}
prime, prevPrime = nextPrime(prime), prime
}
return true
}
func practical(n uint) bool {
if n <= 2 {
return true
} else if n%4 != 0 && n%6 != 0 {
return false
}
pf := PrimeFactorize(uint(n))
primes := pf.Primes()
slices.Sort(primes)
// algorithm from Wikipedia
for i := 0; i < pf.Size()-1; i++ {
factorSumUptoP := uint(1)
for j := 0; j <= i; j++ {
pj := primes[j]
ej := pf.Exponent(pj)
factorSumUptoP *= (uintpow(pj, ej+1) - 1) / (pj - 1)
}
if primes[i+1] > 1+factorSumUptoP {
return false
}
}
return true
}
|
