Problems & Puzzles: Puzzles

Puzzle 507. phi puzzle from Farideh Farideh Firoozbakht sent the following puzzle: The number 139968 has the following three nice properties. 139968 = phi( (1*3*9*9*6*8)*(1+3+9+9+6+8) ) = (1*3*9*9*6*8) * phi(1+3+9+9+6+8) = (1+3+9+9+6+8) * phi(1*3*9*9*6*8) Note that the last two relations obtain from the first relation because the set of distinct prime factors of 1+3+9+9+6+8 and 1*3*9*9*6*8 are equal. Q. Does there exist another multi-digit number with these three properties ?

---

Contribution came from Frederick Schneider

***

Fred wrote:

n is a multi-digit number
s = the sum of digits in n
p = the product of digits in n

We are looking to solve where an additional solution for n where:
n = phi(s*p) = s*phi(p) = p*phi(s)
1) Zero can't be a digit in n:

If n contains 0 as a digit, p will be 0. So, phi(s*p) = 0 /= n. Thus, n can't contain 0 as a digit.
----------------------------------------------------------------------------------------------------------

2) Five can't be a digit/factor of n:


If n is a multiple of 5, it can't be a multiple of 2 because the number would end in the digit zero which is not
allowed. But, phi(5) = 4 so p(n) where n contains 5 for a digit must be even and therefore n must be
even, a contradiction.

Compute the remaining single digit phi's:
1: phi(1) = 1
2: phi(2) = 1
3: phi(3) = 2
4: phi(4) = 2
6: phi(6) = 2
7: phi(7) = 6
8: phi(8) = 4
9: phi(9) = 6


Note that none of these phi's are divisible by any prime > 3. So, phi(p) must be of the form: 2^x*3^y*7^z where x, y and z are all integers >= 0.

----------------------------------------------------------------------------------------------------------
3) No prime > 7 can be a factor of n:

Let pp be a prime greater than 7 and suppose that pp | n.

p must always be 7-smooth because it is the product of digits < 10. phi(p) must also be 7-smooth.

Because we require n = p * phi(s) = phi(p) * s, both phi(s) and s must be a multiples of pp.

If pp^q | s, pp^(q-1) | phi(s). This alone is not satisfactory as the exponent of pp must be the same for both s
and phi(s) and n because pp divides neither p or phi(p).

So, the additional pp factor in phi(s) must come from another factor. Specifically, it must be some prime sp of the
from 2*m*pp + 1 must divide s.

As an example, let's pick pp=13 and sp = 2*m*13 + 1 = 53.

So, s = 13^t * 53 * Q and phi(s) = 12 * 13^(t-1) * 4 * 13 * R = 48 * 13^t * R (where Q and R are positive integers)

Now, we seem to have a suitable candidate for n because s, phi(s) are both multiples of 13^t.
But, we have a new problem. Neither p nor phi(p) is a multiple of 53 but because s is,
phi(s) must be a multiple of 53. Therefore some prime of the from 2*m*53 + 1 must be a factor of s.

Clearly, we are in a vicious cycle that will never resolve itself for m=2 and pp = 13.
It is clear that any choice of positive integer m and pp > 7 will cause the same vicious cycle.

Thus, n must be of the from n = 2^x * 3^y * 7^z (where x, y, z are integers >= 0)

------------------------------------------------------------------

4) There are no other multi-digit solutions.

Let n be 10^q-1 and q be a prime. phi(s*p) = phi(9*q*q*9) = 9^q*6*(q-1).

Notice that:
1) Picking n in this way results in the maximal phi(s*p) for a q-digit number
2) n grows faster than phi(s*p), meaning that at a certain point, n must always be greater than phi(p*s).

At q = 83, n has more digits than phi(9^q*q*9) = 9^q*6*(q-1). One only needs to check n = 2^x*3^y*7^z where n < 10^84.
Using PARI, I found there are no such solutions.

***