The Half-Totient Tree
The number of ways in which an integer n>2 can be partitioned into
two co-prime parts is
phi(n)
H(n) = ---------
2
where phi(n) is Euler's "totient" function, i.e., the number of
integers less than and co-prime to n. The half-totient function is
intimately involved in many interesting areas of mathematics. For
example, H(n) gives the number of distinct linear fractional
transformations of order n.
The half-totient function can be used to construct a tree containing
all the integers. On the zeroth rank we have just the integers 1
and 2. The immediate "ancestors" of 1 and 2 are
1: 3 4 6
2: 5 8 10 12
so these numbers constitute the first rank. The ancestors of these
numbers constitute the second rank
3: 7 9 14 18
4: 15 16 20 24 30
6: 13 21 26 28 36 42
5: 11 22
8: 17 32 34 40 48 60
10: 25 33 44 50 66
12: 35 39 45 52 56 70 72 78 84 90
and so on. Each positive integer is in either the "1 family" or the
"2 family", i.e., it ultimately descends to either 1 or 2. Let T(n)
denote the "type" of the integer n, where T(n)=1 or 2 depending on
whether 1 or 2 is a descendant of n.
The values of T(p^k) for the first few primes are tabulated below:
k
p 1 2 3 4 5 6 7 8 9 ...
2 2 1 2 1 2 1 2 1 2... 41 1 2 1 2 1 2 1 2 1....
3 1 1 1 1 1 1 1 1 1... 43 1 1 1 1 1 1 1 1 1....
5 2 2 2 2 2 2 2 2 2... 47 2 1 2 1 2 1 2 1 2...
7 1 1 1 1 1 1 1 1 1... 53 1 2 1 2 1 2 1 2 1...
11 2 1 2 1 2 1 2 1 2... 59 1 1 2 1 2 1 2 1 2...
13 1 2 1 2 1 2 1 2 1... 61 1 2 1 2 1 2 1 2 1...
17 2 2 2 2 2 2 2 2 2... 67 2 1 2 1 2 1 2 1 2...
19 1 1 1 1 1 1 1 1 1... 71 2 1 2 1 2 1 2 1 2...
23 2 1 1 1 1 1 1 1 1... 73 1 2 1 2 1 2 1 2 1...
29 1 2 2 2 2 2 2 2 2... 79 2 1 2 1 2 1 2 1 2...
31 1 1 1 1 1 1 1 1 1... 83 1 1 1 1 1 1 1 1 1...
37 1 1 1 1 1 1 1 1 1... 89 2 2 2 2 2 2 2 2 2...
97 2 2 2 2 2 2 2 2 2...
This clearly suggests that the powers of any given prime are either
all type 1, all type 2, or alternating between 1 and 2. For the primes
less than 100, only the first powers of 23, 29, and 59 violate their
respective patterns.
I'm interested in whether, for any given integer N, the type of N can
be expressed simply in terms of the types of the prime factors of N.
In other words, I'm trying to find "equivalence classes" relative to
"type" under multiplication. The best classification I've been able
to find is summarized below:
U_p < 0 U_p = 0 U_p > 0
--------------------- ----------- ----------------------
U_p odd U_p even U_p even U_p odd U_p even
-------- ---------- ---------- ---------- ----------
-1 +1 -1 +1 -1 +1 -1 +1 -1 +1
3 109 379 1949 7 37 11 13 23 5
19 653 487 2053 43 229 47 41 31 17
127 757 1999 2269 223 1297 59 53 83 29
163 3889 2287 2917 271 1549 67 61 103 89
811 4549 2647 11689 1307 1597 71 73 107 97
883 4789 3079 12637 1423 1621 79 137 131 101
1459 4861 11827 13693 1483 7793 167 193 139 113
3919 5869 12043 13933 1567 7993 179 233 151 149
3943 23473 12779 15877 1627 8209 227 241 191 157
etc.
where
U_n = s2(n) - 2 s3(n)
and sx(n) is the sum of the highest exponents k_j of x dividing phi(n_j)
for the sequence of n values given by n_0 = n
n_(j+1) = phi(n_j)/(x^(k_j))
The values of "-1" and "+1" in the table headers signify the residue
class of p (mod 4).
Notice that all the primes in a given column exhibit the same pattern
of types for consecutive powers. For example, the primes 11, 47, 59,
67, 71, 79, etc all exhibit the pattern "212121..." for the types of
their consecutive powers.
The rough "equivalence" of primes in each of the ten columns extends
to the types of products of different primes as well. For example,
the product of any two primes from the column 5,17,29,89... is usually
of type 2. The only exception to this for primes less than 1000 is the
product of 13 and 509, which is type 1. (The prime 509 happens to be
the smallest prime whose "power pattern" is exceptional in the SECOND
power, viz, we expect "12121212..." but it is actually "1112121212...".)
The product of any two DISTINCT primes from the column 23,31,83... is
of type 2, without exception for primes less than 1000, although the
square of any prime in this column is type 1.
As can be seen in the above table, the great majority of primes have
U_p > 0, so they fall in one of the four right-most columns. If we
label these four columns as A, B, C, and D, then we can express a
rough generalization for the products of any of these primes as
follows:
If, for a given integer N, the symbols a,b,c,d denote
the sums of the prime exponents of primes of type A, B,
C, and D respectively, then N is type 2 iff a+b is even,
unless (b=c=d=0 and a is even) or (a=b=c=0), in which
case N is type 1.
Caution: There are exceptions to this rule, such as the first or second
powers of certain primes noted earlier, as well as some composite
exceptions.
It's also interesting to consider the possible ranges of integers of a
certain rank. It's not too hard to show that the largest integer of
rank r must be at least 12(7^(r-1)). Obviously the smallest member of
rank r can be no smaller than about 2^r. The smallest integer of rank r
is often related to Cunningham chains, which give the slowest rate of
"descent" under the half-totient function, i.e., decreasing by a factor
of 2 on each step.
Another interesting aspect is to consider the ratio of the number of
type 1 integers to number of type 2 integers less than x as x -> inf.
Here is a brief table showing the number of types 1 and 2 on each rank:
Rank # of type 1 # of type 2 total
------ ------------ ----------- --------
0 1 1 2
1 3 4 7
2 15 23 38
3 84 142 226
4 439 860 1299
5 2371 4850 7221
6 12779 26614 39393
7 68638 145947 214585
8 366344 791667 1158011
9 1954833 4275444 6230277
This shows that on any given rank the number of type 2 integers
exceeds the number of type 1 integers. However, the type 1 integers
always outnumber the type 2 integers less than any fixed N. This
is because the type 1 integers are more prevalent in the lower
members of each rank, and before any rank is completely filled the
next rank has started to appear. Since each rank has about 5 times
as many members as the previous rank, the ratio of types up to
any fixed N is always dominated by the low members of the nascent
rank. If we let Type1(x) and Type2(x) denote, respectively, the
numbers of type 1 and 2 integers less than x, we can plot the
proportion of the two types as shown in the figure below.
The logarithmic periodicity of this proportion is shown even more
clearly in the following plot as a function of the log of x
Does this ratio converge on 0? If not, what is the asymptotic
value?
For another example of this kind of "logarithmic wave" propogating
through the natural numbers, see Meandering Convergence.
Return to MathPages Main Menu