A377734 Number of integers less than n that have the same smallest prime factor as n.

0, 0, 0, 1, 0, 2, 0, 3, 1, 4, 0, 5, 0, 6, 2, 7, 0, 8, 0, 9, 3, 10, 0, 11, 1, 12, 4, 13, 0, 14, 0, 15, 5, 16, 2, 17, 0, 18, 6, 19, 0, 20, 0, 21, 7, 22, 0, 23, 1, 24, 8, 25, 0, 26, 3, 27, 9, 28, 0, 29, 0, 30, 10, 31, 4, 32, 0, 33, 11, 34, 0, 35, 0, 36, 12, 37, 2, 38, 0, 39

Offset: 1

Author

Ilya Gutkovskiy, Nov 05 2024

Keywords

• nonn

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Least Prime Factor.

Crossrefs

Cf. A020639, A038110, A038111, A047983, A078898, A334655, A335097, A377730.

Programs

Mathematica

Table[Length[Select[Range[n - 1], If[# == 1, 1, FactorInteger[#][[1, 1]]] == If[n == 1, 1, FactorInteger[n][[1, 1]]] &]], {n, 80}]
seq[len_] := Module[{t = Table[FactorInteger[n][[1,1]], {n, 1, len}], s = Table[0, {len}]}, Do[s[[i]] = Count[t[[1;;i-1]], t[[i]]], {i, 1, len}]; s]; seq[80] (* Amiram Eldar, Nov 21 2024 *)

PARI

a(n) = if (n>1, my(p=vecmin(factor(n)[,1])); sum(k=2, n-1, p == vecmin(factor(k)[,1])), 0); \\ Michel Marcus, Nov 16 2024

Formula

a(n) = |{j < n : lpf(j) = lpf(n)}|.

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

Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Sum_{k>=1} (A038110(k)/A038111(k))^2 = 0.2847976823663... . - Amiram Eldar, Nov 21 2024