A181833 The number of positive integers <= n that are not strongly prime to n.

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

Offset: 0

Author

Peter Luschny, Nov 17 2010

Keywords

• nonn

Comments

k is strongly prime to n iff k is relatively prime to n and k does not divide n-1.

a(n) = n - phi(n) + tau(n-1) if n > 0 and a(0) = 0.

Here phi(n) = A000010(n) and tau(n) = A000005(n).

Examples

			a(11) = 11 - card({3,4,6,7,8,9}) = 5.
		

Links

• Peter Luschny, Strong coprimality.

Crossrefs

Cf. A181830, A181831, A181832, A181834, A181835, A181836, A051953.

Programs

Maple

with(numtheory):
A181833 := n -> `if`(n=0,0,n-phi(n)+tau(n-1));
A181833a := n -> n - A181830(n);

Mathematica

a[n_] := Select[Range[n], Not[CoprimeQ[#, n] && !Divisible[n-1, #]] &] // Length; a[1] = 0; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Jun 28 2013 *)