## 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.
```