A039785 Numbers n such that phi(n) is equal to the multiplicative projection of n.

9, 16, 50, 54, 100, 108, 144, 294, 450, 588, 900

Offset: 1

Author

Olivier Gérard

Keywords

• nonn
• fini
• full

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)

Examples

			phi(50)=20, 50 = 2^1 * 5^2, 2*1*5*2 = 20.
		

Crossrefs

Cf. A000010, A000026.

Programs

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