A055744 Numbers k such that k and phi(k) have the same prime factors.

1, 4, 8, 16, 18, 32, 36, 50, 54, 64, 72, 100, 108, 128, 144, 162, 200, 216, 250, 256, 288, 294, 324, 400, 432, 450, 486, 500, 512, 576, 578, 588, 648, 800, 864, 882, 900, 972, 1000, 1014, 1024, 1152, 1156, 1176, 1210, 1250, 1296, 1350, 1458, 1600, 1728, 1764

Offset: 1

Author

Labos Elemer, Jul 11 2000

Keywords

• nonn

Comments

Contains products of suitable powers of 2 and Fermat primes. For x = 2^u*3^w, phi(x) = 2^u*3^(w-1) with suitable exponents. Analogous constructions are possible with {2,3,7} prime divisors, etc.

From Ivan Neretin, Mar 19 2015: (Start)

Also, numbers k that meet the following criteria for every prime p dividing k:

1. All prime divisors of p-1 must also divide k;

2. If k has no prime divisors of the form m*p+1, and k is divisible by p, then k must be divisible by p^2.

Also, numbers k for which {k, phi(k), phi(phi(k))} is a geometric progression.

(End)

All terms > 1 are even. An even number k is in the sequence iff 2*k is in the sequence. - Robert Israel, Mar 19 2015

For n > 1, the largest prime factor of a(n) has multiplicity >= 2. For all prime factors more than half of the largest prime factor of a(n), the multiplicity differs from 1.

If k = p1^a1 * p2^a2 * ... * pm^am is in the sequence, then so is p1^b1 * p2^b2 * ... * pm^bm for 1 <= i <= m and prime pi and bi >= ai.

If m * p^2 is not in the sequence, for a prime p and some m > 0, then neither is m * p^3. - David A. Corneth, Mar 22 2015

A027748(a(n),j) = A027748(A000010(a(n)),j) for j=1..A001221(a(n)); also numbers k such that k and phi(k) have the same squarefree kernel: A007947(a(n)) = A007947(A000010(a(n))). - Reinhard Zumkeller, Jun 01 2015

Pollack and Pomerance call these numbers "phi-perfect numbers". - Amiram Eldar, Jun 02 2020

Examples

			k = 578 = 2*17*17, phi(578) = 272 = 2*2*2*2*17 with 2 and 17 prime factors, so 578 is a term.
k = 588 = 2*2*3*7*7, phi(588) = 168 = 2*2*2*3*7, so 588 is a term.
k = 264196 = 2*2*257*257, phi(264196) = 512*257 = 131584, so 264196 is a term.
		

Links

• David A. Corneth, Table of n, a(n) for n = 1..117561 (terms <= 10^11; first 10000 terms from T. D. Noe)
• Paul Pollack and Carl Pomerance, Prime-Perfect Numbers, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 12a, Paper A14, 2012.

Crossrefs

Intersection of A073539 and A151999. - Amiram Eldar, Jun 02 2020

Cf. A001221, A000010, A110751, A110819, A027598, A081377.

Cf. A007947, A027748, A055742, A173557, A256248, subsequence of A124240.

Programs

Haskell

a055744 n = a055744_list !! (n-1)
a055744_list = 1 : filter f [2..] where
   f x = all ((== 0) . mod x) (concatMap (a027748_row . subtract 1) ps) &&
         all ((== 0) . mod (a173557 x))
             (map fst $ filter ((== 1) . snd) $ zip ps $ a124010_row x)
         where ps = a027748_row x
-- Reinhard Zumkeller, Jun 01 2015

Maple

select(numtheory:-factorset = numtheory:-factorset @ numtheory:-phi,
[1, 2*i $ i=1..2000]); # Robert Israel, Mar 19 2015
isA055744 := proc(n)
    nfs := numtheory[factorset](n) ;
    phinfs := numtheory[factorset](numtheory[phi](n)) ;
    if nfs = phinfs then
        true;
    else
        false;
    end if;
end proc:
A055744 := proc(n)
    if n = 1 then
        1;
    else
        for a from procname(n-1)+1 do
            if isA055744(a) then
                return a;
            end if;
        end do:
    end if;
end proc: # R. J. Mathar, Sep 23 2016

Mathematica

Select[Range@ 1800,
First /@ FactorInteger@ # == First /@ FactorInteger@ EulerPhi@ # &] (* Michael De Vlieger, Mar 21 2015 *)

PARI

is(n)=factor(n)[,1]==factor(eulerphi(n))[,1] \\ Charles R Greathouse IV, Oct 31 2011

PARI

is(n)=my(f=factor(n)); f[,1]==factor(eulerphi(f))[,1] \\ Charles R Greathouse IV, May 26 2015

Extensions

Corrected and extended by James Sellers, Jul 11 2000