A342163 a(n) is the number of numbers greater than 1 and up to prime(n)^2 whose prime factors are all less than or equal to prime(n).

2, 6, 15, 29, 60, 87, 137, 176, 247, 360, 422, 568, 689, 776, 923, 1136, 1369, 1494, 1764, 1978, 2128, 2451, 2710, 3074, 3562, 3870, 4077, 4411, 4638, 4995, 6026, 6426, 6987, 7271, 8180, 8493, 9134, 9802, 10319, 11030, 11767, 12139, 13314, 13712, 14329, 14742

Offset: 1

Author

Dimitris Valianatos, Mar 03 2021

Keywords

• nonn

Examples

			For n=3, prime(3) = 5. Then the numbers up to 5^2 = 25 that have prime factors <= 5 are 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25. So a(3) = 15.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..4000

Crossrefs

Cf. A000040, A001248, A184677.

Programs

Maple

A[1]:= 2: p:= 2: P:= 1:
f:= proc(n) local x,y;
  x:= n;
  do
    y:= igcd(x,P);
    x:= x/y;
    if x = 1 then return true fi;
    if y = 1 then return false fi
  od;
end proc:
for nn from 2 to 100 do
  q:= p; p:= nextprime(p); P:= P*q;
  A[nn]:= A[nn-1] + p + numboccur(true,map(f, [$q^2+1 .. p^2-1]))
od:
seq(A[i],i=1..100); # Robert Israel, Apr 06 2021

Mathematica

Block[{nn = 46, w}, w = Array[FactorInteger[#][[All, 1]] &, Prime[nn]^2]; Table[-1 + Count[w[[1 ;; p^2]], ?(AllTrue[#, # <= p &] &)], {p, Prime@ Range@ nn}]] (* _Michael De Vlieger, Mar 13 2021 *)

PARI

forprime(n = 2, prime(35), i = 0; for(k = 2, n^2, v = factor(k)~[1,]; if(vecmax(v) <= n, i++)); print1(i", "))

PARI

a(n) = my(p=prime(n)); sum(k=2, p^2, vecmax(factor(k)[,1]) <= p); \\ Michel Marcus, Mar 03 2021

Formula

a(n) = A184677(n) - 1.

Extensions

Definition clarified by Robert Israel, Apr 06 2021