cp's OEIS Frontend

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

%I A055744 #85 Jul 02 2025 16:01:59
%S A055744 1,4,8,16,18,32,36,50,54,64,72,100,108,128,144,162,200,216,250,256,
%T A055744 288,294,324,400,432,450,486,500,512,576,578,588,648,800,864,882,900,
%U A055744 972,1000,1014,1024,1152,1156,1176,1210,1250,1296,1350,1458,1600,1728,1764
%N A055744 Numbers k such that k and phi(k) have the same prime factors.
%C A055744 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.
%C A055744 From _Ivan Neretin_, Mar 19 2015: (Start)
%C A055744 Also, numbers k that meet the following criteria for every prime p dividing k:
%C A055744   1. All prime divisors of p-1 must also divide k;
%C A055744   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.
%C A055744 Also, numbers k for which {k, phi(k), phi(phi(k))} is a geometric progression.
%C A055744 (End)
%C A055744 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
%C A055744 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.
%C A055744 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.
%C A055744 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
%C A055744 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
%C A055744 Pollack and Pomerance call these numbers "phi-perfect numbers". - _Amiram Eldar_, Jun 02 2020
%H A055744 David A. Corneth, <a href="/A055744/b055744.txt">Table of n, a(n) for n = 1..117561</a> (terms <= 10^11; first 10000 terms from T. D. Noe)
%H A055744 Paul Pollack and Carl Pomerance, <a href="http://www.emis.de/journals/INTEGERS/papers/a14self/a14self.Abstract.html">Prime-Perfect Numbers</a>, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 12a, Paper A14, 2012.
%e A055744 k = 578 = 2*17*17, phi(578) = 272 = 2*2*2*2*17 with 2 and 17 prime factors, so 578 is a term.
%e A055744 k = 588 = 2*2*3*7*7, phi(588) = 168 = 2*2*2*3*7, so 588 is a term.
%e A055744 k = 264196 = 2*2*257*257, phi(264196) = 512*257 = 131584, so 264196 is a term.
%p A055744 select(numtheory:-factorset = numtheory:-factorset @ numtheory:-phi,
%p A055744 [1, 2*i $ i=1..2000]); # _Robert Israel_, Mar 19 2015
%p A055744 isA055744 := proc(n)
%p A055744     nfs := numtheory[factorset](n) ;
%p A055744     phinfs := numtheory[factorset](numtheory[phi](n)) ;
%p A055744     if nfs = phinfs then
%p A055744         true;
%p A055744     else
%p A055744         false;
%p A055744     end if;
%p A055744 end proc:
%p A055744 A055744 := proc(n)
%p A055744     if n = 1 then
%p A055744         1;
%p A055744     else
%p A055744         for a from procname(n-1)+1 do
%p A055744             if isA055744(a) then
%p A055744                 return a;
%p A055744             end if;
%p A055744         end do:
%p A055744     end if;
%p A055744 end proc: # _R. J. Mathar_, Sep 23 2016
%t A055744 Select[Range@ 1800,
%t A055744 First /@ FactorInteger@ # == First /@ FactorInteger@ EulerPhi@ # &] (* _Michael De Vlieger_, Mar 21 2015 *)
%o A055744 (PARI) is(n)=factor(n)[,1]==factor(eulerphi(n))[,1] \\ _Charles R Greathouse IV_, Oct 31 2011
%o A055744 (PARI) is(n)=my(f=factor(n)); f[,1]==factor(eulerphi(f))[,1] \\ _Charles R Greathouse IV_, May 26 2015
%o A055744 (Haskell)
%o A055744 a055744 n = a055744_list !! (n-1)
%o A055744 a055744_list = 1 : filter f [2..] where
%o A055744    f x = all ((== 0) . mod x) (concatMap (a027748_row . subtract 1) ps) &&
%o A055744          all ((== 0) . mod (a173557 x))
%o A055744              (map fst $ filter ((== 1) . snd) $ zip ps $ a124010_row x)
%o A055744          where ps = a027748_row x
%o A055744 -- _Reinhard Zumkeller_, Jun 01 2015
%Y A055744 Intersection of A073539 and A151999. - _Amiram Eldar_, Jun 02 2020
%Y A055744 Cf. A001221, A000010, A110751, A110819, A027598, A081377.
%Y A055744 Cf. A007947, A027748, A055742, A173557, A256248, subsequence of A124240.
%K A055744 nonn
%O A055744 1,2
%A A055744 _Labos Elemer_, Jul 11 2000
%E A055744 Corrected and extended by _James Sellers_, Jul 11 2000