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,2

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

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.

Example

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.

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 *)

Prog

(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
(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

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.

Sequence in context: A312783 A312784 A070738 * A141718 A195382 A211413

Adjacent sequences: A055741 A055742 A055743 * A055745 A055746 A055747

Keyword

nonn

Author

Labos Elemer, Jul 11 2000

Extensions

Corrected and extended by James A. Sellers, Jul 11 2000

Status

approved