A070003 Numbers divisible by the square of their largest prime factor.

4, 8, 9, 16, 18, 25, 27, 32, 36, 49, 50, 54, 64, 72, 75, 81, 98, 100, 108, 121, 125, 128, 144, 147, 150, 162, 169, 196, 200, 216, 225, 242, 243, 245, 250, 256, 288, 289, 294, 300, 324, 338, 343, 361, 363, 375, 392, 400, 432, 441, 450, 484, 486, 490, 500, 507

Offset: 1

Author

Labos Elemer, May 07 2002

Keywords

• nonn

Comments

Numbers n such that P(phi(n)) - phi(P(n)) = 1, where P(x) is the largest prime factor of x. P(phi(n)) - phi(P(n)) = A006530(A000010(n)) - A000010(A006530(n)).

Numbers n such that the value of the commutator of phi and P functions at n is -1.

Equivalently, n such that n and phi(n) have the same largest prime factor since Phi(p) = p-1 if p is prime. - Benoit Cloitre, Jun 08 2002

Since n is divisible by P(n)^2, n cannot divide P(n)! and so A057109 is a supersequence. Hence all A002034(a(n)) are composite. - Jonathan Sondow, Dec 28 2004

A225546 defines a self-inverse bijection between this sequence and A335740, considered as sets. - Peter Munn, Jul 19 2020

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
• Paul Erdős and Ron L. Graham, On products of factorials, Bull. Inst. Math. Acad. Sinica 4:2 (1976), pp. 337-355. [alternate link]
• Paul Erdős and Ilias Kastanas, Solution 6674:The smallest factorial that is a multiple of n, Amer. Math. Monthly 101 (1994) 179.
• A. J. Kempner, Miscellanea, Amer. Math. Monthly, 25 (1918), 201-210. See Section II, "Concerning the smallest integer m! divisible by a given integer n."
• Eric Weisstein's World of Mathematics, Greatest Prime Factor
• Eric Weisstein's World of Mathematics, Totient Function

Crossrefs

Subsequence of A057109, A122145.

Complement within A020725 of A102750.

Cf. A000010, A006530, A068211, A070777, A070812, A070002, A070004, A007283, A070813, A070814, A070815, A070816, A002034, A102067, A102068.

Related to A335740 via A225546.

A195212 is a subsequence.

Cf. A319988 (characteristic function). Positions of odd terms > 1 in A122111.

Programs

Maple

isA070003 := proc(n)
    if modp(n,A006530(n)^2) = 0 then # code re-use
        true;
    else
        false;
    end if;
end proc:
A070003 := proc(n)
    option remember ;
    if n =1 then
        4;
    else
        for a from procname(n-1)+1 do
            if isA070003(a) then
                return a
            end if;
        end do:
    end if;
end proc:
seq( A070003(n),n=1..80) ; # R. J. Mathar, Jun 27 2024

Mathematica

p[n_] := FactorInteger[n][[-1, 1]]; ep[n_] := EulerPhi[n]; fQ[n_] := p[ep[n]] == 1 + ep[p[n]]; Select[ Range[ 510], fQ] (* Robert G. Wilson v, Mar 26 2012 *)
Select[Range[500], FactorInteger[#][[-1,2]] > 1 &] (* T. D. Noe, Dec 06 2012 *)

PARI

for(n=3,1000,if(component(component(factor(n),1),omega(n))==component(component(factor(eulerphi(n)),1),omega(eulerphi(n))),print1(n,",")))

PARI

is(n)=my(f=factor(n)[,2]);f[#f]>1 \\ Charles R Greathouse IV, Mar 21 2012

PARI

sm(lim,mx)=if(mx==2,return(vector(log(lim+.5)\log(2)+1,i,1<<(i-1))));my(v=[1]);forprime(p=2,min(mx,lim),v=concat(v,p*sm(lim\p,p)));vecsort(v)
list(lim)=my(v=[]);forprime(p=2,sqrt(lim),v=concat(v,p^2*sm(lim\p^2,p)));vecsort(v) \\ Charles R Greathouse IV, Mar 27 2012

Python

from sympy import factorint
def ok(n): f = factorint(n); return f[max(f)] >= 2
print(list(filter(ok, range(4, 508)))) # Michael S. Branicky, Apr 08 2021

Formula

Erdős proved that there are x * exp(-(1 + o(1))sqrt(log x log log x)) members of this sequence up to x. - Charles R Greathouse IV, Mar 26 2012

Extensions

New name from Jonathan Sondow and Charles R Greathouse IV, Mar 27 2012