Part 1: Definitions and Basic Propositions 

Among realvalued 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(p_{i}) = p_{i} for each prime p_{i} 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 righthand relation can be rewritten as 

_{} 

Since 2^{k} £ N, this relation follows from 

_{} 

which simpifies to k £ 2^{k}^{}^{1}, which is true for all integers k (with equality for k = 1 or 2). To prove the lefthand 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, k_{a}, k_{b} denote the numbers of prime factors of N, a, b respectively, so we have k = k_{a} + k_{b}. 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, 
_{} 

Rearranging 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 coprime.à 

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 coprime 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 coprime 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 nonnegative integer. Since p is odd, it follows that p^{2}  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 p^{2} = 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 coprime 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 nm 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 nm divides the left hand side so it must divide the right hand term m(x(m)  x(n)), and since m is coprime to n it is also coprime to nm, which proves that nm 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 (nm) > 1. It follows that x(m)  x(n) is greater than 1, because it is divisible by nm. We also have the identity 



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



which proves that Q > 1 if (nm) > 1. If (nm) = 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) = p1. Since p is odd we can factor a 2 out of p+1 to give x(p+1) = x((p+1)/2) + 2 = p1. Therefore, p3 = 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) ³ (nm). 

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

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 u_{1} + u_{2} + ... + u_{k}, where u_{j} = a_{j}p_{j} for some prime p_{j} and exponent a_{j}. Then 



Thus u_{j} contributes a multiplicative factor of _{} to N. Allowing p_{j} and a_{j} to take on any positive real values, we have 

_{} 

Taking the derivative of this with respect to p_{j} and setting the result equal to zero shows that the minimum occurs at p_{j} = e (the base of the natural log). The smallest value of p_{j}/ln(p_{j}) for integer values of p_{j} occurs with p = 3. Thus the maximum contribution n_{j} for each u_{j} can be no greater than if p_{j} = 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) = M^{2} 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 ³ (nm). We will refer to solution kernels m,n such that Q = (nm) 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 coprime 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. à 

Discussion: Table 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 = p^{k} 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 = k^{t} 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 2kernels with n equal to the cubes (110)^{3}, (310)^{3}, (470)^{3}, and (494)^{3}. These are all coprime to 3, as required. 
