A010847 Number of numbers <= n with a prime factor that does not divide n.

0, 0, 1, 1, 3, 1, 5, 4, 6, 4, 9, 4, 11, 8, 10, 11, 15, 8, 17, 12, 16, 15, 21, 13, 22, 19, 23, 20, 27, 12, 29, 26, 27, 26, 30, 22, 35, 30, 33, 29, 39, 23, 41, 35, 37, 38, 45, 33, 46, 38, 45, 43, 51, 38, 50, 45, 51, 50, 57, 34, 59, 54, 55, 57, 60, 44, 65, 58, 63, 50, 69, 54, 71

Offset

1,5

Links

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Formula

a(p) = p-2, for p prime; that is all numbers between 2 and p-1 inclusive. - Michel Marcus, May 31 2014

a(n) = n - A010846(n). - Anthony Browne, Jun 07 2016

Example

For n=5, the three numbers 2,3 and 4 have a prime factor that is not found in 5. Hence a(5) = 3.

Mathematica

Table[Sum[1-Floor[n^k/k]+Floor[(n^k-1)/k], {k, n}], {n, 100}] (* Anthony Browne, Jun 07 2016 *)

Prog

(PARI) a(n) = {pfn = factor(n)[, 1]~; nb = 0; for (i=2, n, pfi = factor(i)[, 1]~; for (j=1, #pfi, if (! vecsearch(pfn, pfi[j]), nb++; break); ); ); nb; } \\ Michel Marcus, May 31 2014

Crossrefs

Cf. A010846.

Sequence in context: A129676 A154947 A152747 * A331698 A082129 A363233

Adjacent sequences: A010844 A010845 A010846 * A010848 A010849 A010850

Keyword

nonn,easy

Author

Olivier Gérard

Status

approved