Part 4: HigherOrder Solutions 

Solution Triples: A set of three distinct integers {M,N,T} such that Mx(M) = Nx(N) = Tx(T) will be called a solution triple. We can partition three such integers into seven coprime factors a,b,..,g as illustrated in Figure 1a. 



Clearly, each of the pairs {M,N}, {M,T}, and {N,T} is a solution pair. Considering the pair {M,N} we note that gcd(M,N) = eg, so the solution kernel of this pair is ad,bf. By Proposition 2 we have 



Expanding the left side by the additive property gives 



Similarly the solution pair {N,T} leads to the condition 

_{} 

The difference between these last two equations gives a necessary and sufficient condition for {M,N,T} to be a solution triple: 

_{} 

One way of searching for such triples is to generate a list of solution (pair) kernels and then examine these pairs two at a time to determine if they satisfy (4). However, each set of solution pairs actually corresponds to two possible solution triples. Consider the three pairs {M,N}, {M,T}, and {N,T} illustrated in Figure 1a. The kernels corresponding to these pairs are {ad,bf}, {ae,cf},{be,cd}. Now consider the three pairs {M',N'}, {M',T'}, and {N',T'} illustrated in Figure 1b. The kernels of these pairs are {bf,ad}, {cf,ae}, and {cd,be}, which are identical to the pairwise kernels for {M,N,T}, in spite of the fact that {M,N,T} and {M',N',T'} are distinct. This occurs because there is a permutation of the components a,b,..,f that leaves the pairwise kernels unchanged (except that the components are transposed). Specifically, the permutation consisting of the three transpositions 

_{} 

produces a new triple with the same pairwise kernels. We refer to these two triples as duals of each other. 

Given two solution kernels {u,v} and {r,s}, we could make the assignments 

_{} 

and then compute the individual components as follows 

_{} 

If these components satisfy (4) then we call the integers a,b,..,f a triple kernel. We can then use (3) to compute x(g). For any g having this value of x(g) the integers M = adeg, N = bfeg, T = cdfg constitute a solution triple. 

On the other hand, given the same solution pairs {u,v} and {r,s}, we could equally well make the assignments 

_{} 

in which case the individual components are given by 

_{} 

If these components satisfy (4) then the integers M',N',T' as defined in Figure 1b are a solution triple. As an example, consider the two solution pairs {12,11} and {22,19}. If we make the assignments 

_{} 

then we have the components 

_{} 

which gives the three integers (according to Figure 1a) 

_{} 

These numbers do not constitute a solution triple, since the components fail to satisfy equation (4). However, the "dual" of this triple gives the components 

_{} 

yielding the three integers 

_{} 

which do satisfy the requirements of a solution triple with g defined such that x(g) = 18. 

Evidently any number of triple kernels can be found in this way. Table 4 contains those that can be produced from the double kernels of Table 1, but evaluating only one of the two possible permutations in each case, so the list is incomplete. The smallest solution triple is 

_{} 

which is based on the kernel 

_{} 

taking g = 21. 

We observe that most of the kernels listed in Table 4 have at most only one of a,b,c > 1. Also, it appears that the six integers 

_{} 

constitute a triple kernel if and only if u,v and u,w (allowing transpositions) are double kernels with q(u,v) = q(u,w). 

Higher Order Solution Sets: Similarly we can determine sets of 4 integers A,B,C,D such that 

Ax(A) = Bx(B) = Cx(C) = Dx(D) 

and Table 4 provides several examples. One such 4solution consists of the integers 

_{} 

which satisfy the equality 

_{} 

Table 4 also gives examples of 5solutions. If we define 

_{} 

then the integers 

_{} 

for any k such that x(k) = 52 constitute a 5solution. This is equivalent to the statement that the set of primes 

S = {2,2,3,5,11,17,19,29,59,71,89} 

contains 5 distinct subsets s_{1}, s_{2}, ..., s_{5} such that 



where 

_{} 

If we add the prime 47 and another 5 to S, then the 52 in the above equation vanishes. However, the primes 5 and 47 are, in a sense, inert elements of the set. (We consider later whether there are such sets with no inert elements.) 

We might remove the restriction that the elements of S be primes, and instead search for sets of general integers such that 



A further generalization is to allow the constant to be negative. The subsets s_{i} may or may not be disjoint and covering (as they are in the preceding example). 

Finding Solution Sets of Order k: Proposition 4 stated that {m,n} constitutes a solution kernel if and only if the quantity 



is a positive integer. This can be rewritten in the form 



which is true if and only if 



(because we can expand the x functions and subtract x(q) from both sides). It follows that for any two integers M and N such that M + x(M) = N + x(N) and gcd(M,N) = q, where q is any positive integer, the integers M/q and N/q constitute a solution kernel. 

This can be immediately generalized to solution sets of k elements. For any positive integer c let c(c) denote the number of integers n such that n + x(n) = c. (This is called the valence of the function G.) Also, let t(c) denote c minus the sum of the values x(n) over this set of n values. Then, given this set of k integers n_{1}, n_{2}, ..., n_{k} such that 

_{} 

we can construct a set of integers N_{1}, N_{2}, ..,N_{k} such that 

_{} 

by taking 


where the quantities u_{j} and s are defined by 



and x^{}^{1} signifies the inverse x function. Thus, the righthand factor in the expression for N_{j} is an integer b such x(b) = t(c) + x(s). (In general the function x^{}^{1} is multivalued.) This requires that t(c) + x(s) be positive. 

Thus, every integer c with c(c) = k and t(c) + x(s) > 0 corresponds to a solution set of k elements. It is conjectured that the converse is also true, i.e., that every solution set of k elements is associated with an integer c for which c(c) is equal to (or greater than) k. The values of x(c) and t(c) and the n_{i} for each integer c from 1 to 500 are listed in Table 5. 

It's useful to consider an example. The first "triple" in Table 4 is defined by the values 

_{} 

This gives the family of solution triples 

_{} 

where g = x^{}^{1}(165). This same triple is represented in Table 5 where, for c = 216, we find 

_{} 

which gives 

_{} 

and 
s = gcd(38000, 39000, 37050) = 50 

Noting that x(s) = 12, we see that this gives the same family of solution triples as found in the earlier table. 

Discussion: We could simply have factored s out of the three integers (n_{1}n_{2}), (n_{1}n_{3}), (n_{2}n_{3}) and asserted the solution triples {760q, 780q, 741q} where now q = 50 x^{}^{1}(153). These values of q are a subset of the values of g = x^{}^{1}(165). However, they do not constitute the complete set, because there are integers g for which x(g) = 165 but which are not divisible by 50. For example, g = (163)(2). This arises because of the nonuniqueness of the inverse x function. 

Very High Order Solution Sets: Table 7 gives the first few values of c for which c(c) equals 1, 2, ..., 24. Presumably, for any given positive integer k there are infinitely many c such that c(c) = k. The smallest integer c such that c(c) = 12 is 14399. This leads to the 12kernal with the values of n_{i} shown below: 



In this case c = 14399, the sum of the x(n_{i}) is 13400, and the n_{i} have no common factor, so b is any integer such that x(b) = 999. 

The next smallest integer c for which c(c) = 12 is 15119. The corresponding values of n_{i} are as follows 



In this case the sum of the x(n_{i}) is greater than c, and the n_{i} have no common factor, so we have x(b) = 2759, which is not satisfied for any integer b. 

To give another example of a very high order solution set, we note that c(720719) = 24, which implies the existence of the 24kernel presented in the following table. 



This table shows that t(720729) = 219745 and there are no common factors in the n_{i}. Therefore, we can construct a family of 24solutions using the formulas given above. The number of solutions in this family is equal to the number of prime partitions of 219745. 

Each value of n_{i} in this 24solution is of the form p_{i}q_{i} where p_{i} and q_{i} are primes such that 



An efficient way of searching for such solutions is to observe that we can add 1 to both sides and factor the resulting equation as follows: 



Therefore, we need only determine the twopart multiplicative partitions ab = c + 1 such that a1 and b1 are primes. In the present case we have c = 720719, so we need to examine the factors of 

c + 1 = 720720 = (2)^{4}(3)^{2}(5)(7)(11)(13) 

Cunningham Chains: The is an obvious tendancy for the n_{i} factors to be primes of the form p = 2q+1 where q is also a prime. Sequences of primes with this property are called Cunningham chains. The first two Cunningham chains of unusual length are 

_{} 

If N = rs for primes r and s then N + x(N) = rs + r + s. Now, if M = pq where p = 2r + 1 and q = (s1)/2 (both primes), then we have 

_{} 

Thus, by forming a sequence of integers given by multiplying the elements of a Cunningham chain in increasing order times the elements of a chain in decreasing order gives integers with the same value of N + x(N). For example, the smallest set of 11 integers with equal G functions is 



In this case c = 4319 so x(b) = 159, which means that this set cannot be used to construct an 11kernel. However, this clearly illustrates how Cunningham chains can be used to produce solution sets. We can also explain several of the 3kernels by considering the convoluted chains 

_{} 

It is conjectured, but not proven, that there exist Cunningham chains of any finite length, which would imply the existence of solution sets of arbitrary size. 
