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

Author

Olivier Gérard

Keywords

• nonn
• easy

Examples

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

Links

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

Crossrefs

Cf. A010846.

Programs

Mathematica

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

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

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