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
|
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{
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}
// A type of number (as determined by its factors)
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
)
func Type(n uint32) NumberType {
if slices.Contains(colossallyAbundantNums[:], n) {
return ColossallyAbundant
} else if isSAN(n) {
return Superabundant
} else if exponentsOrdered(n) {
return OrderedExponent
} else if practical(n) {
return Practical
} else {
return NotPractical
}
}
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 {
if n <= 2 {
return true
} else if n%4 != 0 && n%6 != 0 {
return false
}
pf := PrimeFactorize(uint(n))
maxPrime := slices.Max(pf.Primes())
lastPrime := uint(2)
for p := uint(3); p <= maxPrime; p += 2 {
if PrimeFactorize(p).Exponent(p) == 1 {
if pf.Exponent(p) > pf.Exponent(lastPrime) {
return false
} else if pf.Exponent(p) == 0 && p < maxPrime {
return false
}
lastPrime = p
}
}
return true
}
func practical(n uint32) 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
}
|
