OFFSET
1,1
COMMENTS
Next term if it exists is greater than 1000000. - C. Ronaldo (aga_new_ac(AT)hotmail.com), Dec 29 2004
From Lambert Herrgesell (zero815(AT)googlemail.com), Oct 18 2006: (Start)
There is a simple proof that there are no other terms. Let m(n) be the multiplicative projection of n.
The key point is that if a prime in the factorization of n has a "big" power, either phi(n) > m(n) or omega(n) is "big", so a solution would be "more difficult".
It is easy to show that 3^2 and 2^4 are the only solutions of the form p^k.
Consider solutions of the form 2^x * 3^y: phi(2^x * 3^y) = 2^x * 3^(y-1) = 2*x*3*y.
Since p^k is done, assume x >= 1, y >= 2 and simplify to (*) 2^(x-1) * 3^(y-2) = xy.
A quick search yields the only solutions 2^1 * 3^3, 2^2 * 3^3 and 2^4 * 3^2.
Now try adding a third prime p and assume phi(p) of the form 2^m * 3^k:
phi(2^x * 3^y * p^z) = 2^(x+m) * 3^(y-1+k) * p^(z-1). We find 2^(x+m) * 3^(y-1+k) * p^(z-1) = 2*x*3*y*p*z and, dividing by 2*3*p, 2^(x-1+m) * 3^(y-2+k) * p^(z-2) = xyz.
So z >= 2, but by the above remark we may assume z=2. We get 2^(x-1+m) * 3^(y-2+k) * p^0 = x*y*2 and (**) 2^(x-2+m) * 3^(y-2+k) = xy.
(**) is independent of p and reduces to solving the 2^x * 3^y case in (*), but additional powers of 2 and 3 are needed.
Using the bounds for phi(p^z), the only possible values for p are 5 or 7 and the only solutions are 2^1 * 5^2, 2^2 * 5^2, 2^1 * 3^2 * 5^2, 2^2 * 3^2 * 5^2 and 2^1 * 3^1 * 7^2, 2^2 * 3^1 * 7^2.
Now adding a further prime q, the difficulty from (*) and (**) is that both q has to be small and phi(q) has to produce a lot of factors for the next (**) like expression.
If we also spare no effort and try this for all the remaining numbers of step (**), we see that there are no more results.
More generally: If n is a member, omega(n) > 2 and n = Product(p_i^e_i)q^e, p_i, q primes, then Product(p_i^e_i) is also a member up to some powers e^i of some p_i, which have to be greater. Also, for omega(n) >= 2, if 2^2 is a factor of n, then n/2 is also in a(n).
All in all this implies that there are no other terms. (End)
EXAMPLE
phi(50)=20, 50 = 2^1 * 5^2, 2*1*5*2 = 20.
PROG
(PARI) for(n=1, 1000000, f=factor(n); l=#f[, 1]; if( eulerphi(n)==prod(i=1, l, f[i, 1]) * prod(i=1, l, f[i, 2]), print1(n, ", "))) \\ C. Ronaldo
CROSSREFS
KEYWORD
nonn,fini,full
AUTHOR
STATUS
approved