Observations regarding the prime factorization of a number and that number's usefulness as a base. Just amateur ones (studied architecture in college).
Every integer draws its "identity" from its prime factorization, a little like chemical compounds do from their atomic composition. A prime integer r offers at least 2 divisors, and r-1 totatives (integers smaller than r which are relatively prime to r). This means that every integer smaller than r is indivisible by r or any of its factors. (I like to think of totatives as spots that the primes which compose r "miss".) An integer composed of two primes will have 3 or 4 divisors, and a reduced set of totatives. The primes, if different, will interact and wipe out more totatives. It's interesting to observe how the diversity of primes in a base's composition "buy" a lower totient function value.
The totient functions (total number of totatives divided by the base) of the following primes are:
| CODE |
2 1/2 {1}
3 2/3 {1,2}
5 4/5 {1,2,3,4}
7 6/7 {1,2,3,4,5,6}
11 10/11 {1,2,3,4,5,6,7,8,9,10} |
Here are some observations regarding totatives, numbers "missed" by the interaction of the primes in the base's prime composition.:
1. Integers which contain a diverse set of primes in their factorization feature reduced totatives.
| CODE |
6 2*3 (1/2)*(2/3) 1/3 {1,5}
8 2^3 (1/2) 1/2 {1,3,5,7}
9 3^2 (2/3) 2/3 {1,2,4,5,7,8}
10 2*5 (1/2)*(4/5) 2/5 {1,3,7,9}
12 2^2*3 (1/2)*(2/3) 1/3 {1,5,7,11}
14 2*7 (1/2)*(6/7) 3/7 {1,3,5,9,11,13}
16 2^4 (1/2) 1/2 {1,3,5,7,9,11,13,15} |
2. "Compact" compositions featuring the simplest primes are most efficient:
| CODE |
2 (1/2) 1/2
2*3 (1/2)*(2/3) 1/3
2*5 (1/2)*(4/5) 2/5
2*7 (1/2)*(6/7) 3/7
2*11 (1/2)*(10/11) 5/11
2*3*5 (1/2)*(2/3)*(4/5) 4/15
2*3*7 (1/2)*(2/3)*(6/7) 2/7
2*5*7 (1/2)*(4/5)*(6/7) 12/35 |
3. Additional powers of the same prime do not reduce the totient function.
4. "Efficiency regimes" are set up, governed by the simplest instance prime content. These simplest manifestations of a prime content "template" establish low totient function values which may be met but apparently never bested. The addition of each successive prime to the formula yields "diminishing returns", as the totient function value is diminished in successively smaller steps.
| CODE |
2 2 (1/2)
6 2*3 (1/3)
30 2*3*5 (4/15)
210 2*3*5*7 (8/35)
2310 2*3*5*7*11 (16/77) |
5. Twelve lies in the regime governed by 6 (2*3), so its totatives will be a multiple of 6's totative set. This totient function value isn't improved upon until we reach 30 (2*3*5). So 6, 12, 18, and 24 share a relatively low "gap in coverage" thanks to their compact, simple prime factorization. The binary bases, powers of 2, will always feature a "gap in coverage" that encompasses every odd digit, half of their total digits.
This is part of a validation for dozenal, though in this instance base 6 proves better.
| QUOTE (icarus @ Jan 16 2008, 03:47 PM) |
| A prime integer r offers at least 2 divisors, and r-1 totatives (integers smaller than r which are relatively prime to r). |
" ... at least two divisors ..."
No prime can have more than two divisors.
"A prime has two divisors, one of which is not the number 1."
That definition, which I heard many years ago, is better than the usual quoted "A prime can only be divided by itself" which seems to allow 1 to be a prime; (to remove which error you have to invoke the prime factorisation theorem which says that the factorisation of any number into its prime factors can be done in inly one way: e.g. 6 = 2 x 3).
Where did the word "totative" come from? sounds awful!