Part 1:  Definitions and Basic Propositions

 

Among real-valued functions f the logarithms f(x) = logb(x) for any positive real base b uniquely possess the Additive Property

 

 

for any positive real numbers x and y.  If we restrict our attention to the positive integers then clearly the analagous functions must satisfy f(1) = 0 and

 

 

We're free to define the values of  f  for prime arguments arbitrarily.  If  we set f(pi) = pi  for each prime pi then f(N) is the sum of the prime factors of N.  Hereafter we will denote this function by x(N). As an example, x(12) = 2 + 2 + 3 = 7.  The first several values of this function are shown in the table below.

 

 

This note focuses primarily on pairs of distinct integers M,N such that Mx(M) = Nx(N).  We will often make use of the obvious fact that x(N) £ N, which is a consequence of the stronger inequality given by the following lemma.

 

Lemma 1:  If the positive integer N is the product of k primes (not necessarily distinct) then

 

 

Also, we have the equality x(N) = N  if and only if N equals 4 or a prime.  (The left hand relation in the above expression is also an equality for N = 1.)

 

Proof:  The right-hand relation can be re-written as

 

 

Since 2k £ N, this relation follows from

 

 

which simpifies to k £ 2k-1, which is true for all integers k (with equality for k = 1 or 2).  To prove the left-hand relation of the Lemma, note that, by definition, x(1) = 0 and x(N) = N if N is a prime, and both of these cases satisfy the Lemma by inspection, so this covers the cases k = 0 and k = 1.  If N is composite (i.e., if k > 1) then there are positive integers a,b such that ab = N and x(N) = x(a) + x(b) and 1 < a,b < N.  Let the positive integers k, ka, kb denote the numbers of prime factors of N, a, b respectively, so we have k = ka + kb.  If we suppose N is the smallest integer for which the lemma does not hold, then the lemma does hold for the smaller integers a,b, so we have

 

 

Therefore,

 

Re-arranging terms, this gives

 

 

Since and , it follows that the product of  and  is a positive number less than N, so the relation is preserved if we omit this product from the above expression, which leads to the relation that was to be proven. à

 

Proposition 1:  If  Mx(M) = Nx(N), then gcd(M,N) > 1.

 

Proof:  Suppose gcd(M,N) = 1.  Then N divides x(M) and M divides x(N).  Using Lemma 1 this implies that M £ x(N) £ N and N £ x(M) £ M, which can only be true if M = N, contradicting the assumption that M and N are co-prime.à

 

Proposition 2:  The equality M x(M) = N x(N) is satisfied in distinct integers M,N if and only if

 

 

where m = M/gcd(M,N) and n = N/gcd(M,N).

 

Proof:  The basic equality can be written as

 

 

Dividing both sides by gcd(M,N) and expanding the x functions by the Additive Property gives

 

 

Solving for x(gcd(M,N)) gives the desired result.  The inequality x(gcd(M,N)) > 1 follows from Proposition 1 and the fact that x(k) > 1 for all k > 1 (because k must be divisible by at least one prime ³ 2). à

 

Discussion:  Proposition 2 shows that to find distinct integers M,N such that M x(M) = N x(N) we need only find two co-prime integers m and n such that the quantity

 

 

is an integer greater than 1.  Then M = km and N = kn satisfy the desired equality for any k such that x(k) equals Q(m,n).  For example, since Q(13,18) = 5, the integers M = 13k and N = 18k constitute a solution pair for any integer k such that x(k) = 5. This leads to the two solution pairs:

 

 

In general, for any two co-prime positive integers m,n such that Q(m,n) is an integer greater than 1, there is a distinct solution pair corresponding to each prime partition of Q(m,n).  We will refer to such pairs m,n as "solution kernels", and adopt the convention m < n.  It's clear that the sets of solution pairs for any two distinct kernels are disjoint, because any two integers M,N have a unique gcd.

 

Table 1 lists all the solution kernels with n < 100.  The smallest solution pair is based on the kernel 13,18 with gcd(M,N) = 5, which gives the solution pair 65,90.

 

To shorten the expressions in the next demonstration we define the function H(n) = nx(n), in terms of which we state the following lemma.

 

Lemma 2:  For any positive integers u,v we have

 

 

Proof:  The proof is immediate because

 

 

which was to be shown. à

 

Proposition 3:  There exist infinitely many pairs of distinct integers M,N such that Mx(M) = Nx(N).

 

Proof:  We prove the assertion by giving an explicit formula for an infinite sequence of such pairs.  We claim that for any prime p ³ 11 the value of

 

 

is an integer, and that the integers  M = kp  and  N = k(p+1)  satisfy the condition H(M) = H(N).  To prove that k is an integer, we need only show that the exponent of 2 in the preceding expression for k is a non-negative integer.  Since p is odd, it follows that p2 - H(p+1) - 3 is even, so the exponent is an integer.  Also, since p>1 is odd, it follows that p+1 is not a prime, so the maximum value of H(p+1) is 2q(q+2), which occurs when q = (p+1)/2  is a prime.  Therefore, the exponent in k is greater than or equal to

 

 

which is positive for every prime p ³ 11.  Applying the function H to the integer k as defined above gives

 

 

Adding pH(k) + kH(p+1) to both sides, and noting that p2 = H(p), we have

 

 

By Lemma 2 this proves that

 

 

so we have an infinite sequence of solutions, which was to be shown.à

 

Proposition 4:  The co-prime integers m,n with n > 8 constitute a solution kernel if and only if the quantity

 

 

is a positive integer.

 

Proof:  We prove this by showing that, for n > 8, the quantity Q(m,n) is an integer greater than 1 if and only if q(m,n) is a positive integer.  The fact that q is an integer iff Q is an integer follows from simple divisibility arguments involving the identity

 

 

If q is an integer then n-m divides x(m) - x(n), which implies that it divides the entire right hand side of this equation, so it also divides the left hand side.  Conversely, if Q is an integer then n-m divides the left hand side so it must divide the right hand term m(x(m) - x(n)), and since m is co-prime to n it is also co-prime to n-m, which proves that n-m must divide x(m) - x(n).

 

We now prove that if the integer q is positive and n > 8 then the integer Q is greater than 1.  First suppose that (n-m) > 1.  It follows that x(m) - x(n) is greater than 1, because it is divisible by n-m. We also have the identity

 

 

Since x(m) £ m by Lemma 1, this gives the inequality

 

 

which proves that Q > 1 if (n-m) > 1.  If (n-m) = 1 we must allow the possibility that x(m) - x(n) = 1.  In this case, suppose first that m > x(m).  It follows that Q = qm - x(n) > 1 as required.  If, however, m = x(m) then m is a prime p, and n = p + 1.  The only way for x(m) - x(n) not to exceed 1 is if x(n) = x(p+1) = p-1.  Since p is odd we can factor a 2 out of p+1 to give x(p+1) = x((p+1)/2) + 2 = p-1.  Therefore, p-3 = x((p+1)/2) £ (p+1)/2 (by Lemma 1) which gives p £ 7 and so n £ 8.

 

Conversely, if Q > 1 it follows immediately from the identity Q + x(n) = mq that q is positive. à

 

Corrollary 4.1:  For any solution kernel m,n we have  Q(m,n) ³ (n-m).

 

Proof:  Equation 11 gives Q ³ x(m) - x(n), and Proposition 3 states that the latter is positive and divisible by (n-m). à

 

Corrollary 4.2:  The relation M + x(M) = N + x(N) is satisfied if and only if M = mq(m,n) and N = nq(m,n) where {m,n} are a solution kernel or m = 7, n = 8.

 

Proof:  By Proposition 3 {m,n} constitute a solution kernel if and only if q(m,n) is a positive integer and n > 8.  By inspection, the only other case where q(m,n) is a positive integer is when m = 7, n = 8.  Therefore, these are precisely the cases when we can set gcd(M,N) = q(m,n) to give the stated solutions. à

 

Lemma 3:  For any positive integer N we have

 

Proof:  For any quantity U = x(N) the value of N can be formed by partitioning U into the sum u1 + u2 + ... + uk, where uj = ajpj for some prime pj and exponent aj.  Then

 

 

Thus uj contributes a multiplicative factor of  to N. Allowing pj and aj to take on any positive real values, we have

 

 

Taking the derivative of this with respect to pj and setting the result equal to zero shows that the minimum occurs at pj = e (the base of the natural log).  The smallest value of pj/ln(pj) for integer values of pj occurs with p = 3.  Thus the maximum contribution nj for each uj can be no greater than if pj = 3. Conversely, the smallest value of U for any given N can be no less than if N is a pure power of 3. à

 

Proposition 5:  If Mx(M) = Nx(N) with N > M then

 

where n = N/gcd(M,N).

 

Proof:  Let m = M/gcd(M,N).   Since n - m divides x(m) - x(n) by Proposition 4, and x(m) £ m by Lemma 1, we have

 

and so

 

Dividing both sides by n gives

 

 

which leads to the inequality

 

 

We maximize this ratio by minimizing x(n)/n.  Applying Lemma 3 gives the result. à

 

Discussion:  It's interesting to compare Proposition 5 to an alternative interpretation.  Suppose we consider that the maximum value of the ratio N/M occurs when N has the largest value and M has the smallest value consistent with the requirement Mx(M) = Nx(N).  For any integer n we have

 

 

by Lemmas 1 and 3.  Thus, based simply on the range of magnitudes of x(n), we could not rule out the equality Mx(M) = Nx(N) occurring with Mx(M) = M2 and  Nx(N) = 3N ln(N)/ln(3), which would give the limiting ratio

 

 

which is unbounded, in contrast to the upper limit of 2 given by Proposition 5.  This illustrates how the divisibility requirements of the discrete integer function impose significant restrictions on the solution pairs that would not be obvious from the point of view of continuous functions.

 

We've shown (Corrollary 4.1) that if m,n constitute a solution kernel then Q ³ (n-m).  We will refer to solution kernels m,n such that Q = (n-m) as maximal kernels, and to the corresponding solution pairs M,N as maximal solutions.

 

Proposition 6:  If {m,n} is a maximal kernel with n > m, then m is a prime.

 

Proof:  A maximal kernel has, by definition,

 

 

which can be written as

or

 

Clearly n must divide the right hand side of this equation, but it is co-prime to m so it must divide m - x(m).  However, n is greater than m so it is obviously greater than m - x(m). Therefore, n divides m - x(m) if and only if m - x(m) = 0, which by Lemma 1 is true if and only if m is a prime or 4. à

 

Proposition 7:  The integers m,n with n > m and n > 8 constitute a maximal kernel if and only if m is a prime and

 

 

Proof:  This follows immediately from equation (33) if we set  m - x(m) = 0, which then implies that the term 2m - x(n) - n on the left hand side also equals 0. à

 

DiscussionTable 2 lists all the maximal kernels with  n < 2000, and Table 3 lists every 100th maximal solution kernal for n less than 400,000. Letting µ(x) signify the number of maximal kernels with n £ x, the figure below shows a plot of m(x) up to x = 400,000.

 

 

It appears from this figure that  m(x) increases almost linearly with x, similar to the number of primes up to x/2. One possible form is

 

 

Corrollary 7.1:  If n,m constitute a maximal kernel then n is composite, and is either a power of 2 or is a product of at least two distinct factors.

 

Proof:  We have n > m > x(n), so n is composite by Lemma 1.  Now suppose that n = pk for some prime p > 2.  Then we have

 

which is obviously not a prime, in contradiction to Proposition 7.  Therefore, n cannot be a power of a single prime except 2. à

 

Corrollary 7.2:  If {n,m} constitute a maximal solution kernel and  n = kt for some positive integers k and t, then  gcd(n,tx(k)) £ 2.

 

Proof:  Suppose  gcd(n,tx(k)) = c > 2.  Then we have

 

 

which is clearly not a prime.  Thus, by Proposition 7, the integers {m,n} do not constitute a maximal solution kernel. à

 

Discussion:  As examples of Corrollary 7.2, we have maximal 2-kernels with n equal to the cubes (110)3, (310)3, (470)3, and (494)3.  These are all co-prime to 3, as required.

 

Table of Contents