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

%I #20 Jun 16 2016 07:17:36

%S 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,

%T 20,27,12,29,26,27,26,30,22,35,30,33,29,39,23,41,35,37,38,45,33,46,38,

%U 45,43,51,38,50,45,51,50,57,34,59,54,55,57,60,44,65,58,63,50,69,54,71

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

%H Alois P. Heinz, <a href="/A010847/b010847.txt">Table of n, a(n) for n = 1..10000</a>

%F a(p) = p-2, for p prime; that is all numbers between 2 and p-1 inclusive. - _Michel Marcus_, May 31 2014

%F a(n) = n - A010846(n). - _Anthony Browne_, Jun 07 2016

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

%t Table[Sum[1-Floor[n^k/k]+Floor[(n^k-1)/k], {k,n}],{n,100}] (* _Anthony Browne_, Jun 07 2016 *)

%o (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

%Y Cf. A010846.

%K nonn,easy

%O 1,5

%A _Olivier GĂ©rard_