Date: Fri, 3 Feb 1995 09:22:12 EST Reply-To: Kevin Brown Sender: Number Theory List From: Kevin Brown Subject: The Half-Totient Tree To: Multiple recipients of list NMBRTHRY 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 oftype 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 out- number 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.