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

0, 0, 0, 0, 0, 1, 0, 2, 2, 2, 1, 6, 2, 6, 4, 4, 4, 11, 4, 12, 6, 6, 6, 18, 6, 12, 9, 14, 8, 22, 6, 22, 14, 14, 12, 20, 8, 27, 16, 20, 12, 32, 10, 34, 18, 18, 16, 42, 14, 32, 17, 26, 20, 46, 16, 32, 20, 28, 24, 54, 14, 48, 28, 32, 26, 41, 16

Offset: 0

Author

Peter Luschny, Nov 17 2010

Keywords

• nonn
• easy

Comments

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

It is conjectured (see Scroggs link) that a(n) is also the number of cardboard braids that work with n slots. - Matthew Scroggs, Sep 23 2017

a(n) is odd if and only if n is in A002522 but n <> 2. - Robert Israel, Jun 20 2018

Examples

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

Links

• Robert Israel, Table of n, a(n) for n = 0..10000
• Peter Luschny, Strong coprimality
• Matthew Scroggs, Braiding, pt. 2. Two results and a conjecture

Crossrefs

Cf. A000005, A000010, A002522, A050384, A181831, A181832, A181833, A181834, A181835, A181836.

Programs

Mathematica

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

PARI

a(n)=if(n<2, 0, eulerphi(n)-numdiv(n-1));
for (i=0, 66, print1(a(i), ", ")) \\ Michel Marcus, May 22 2017

SageMath

def isstrongprimeto(k, n): return not(k.divides(n - 1)) and gcd(k, n) == 1
print([sum(int(isstrongprimeto(k, n)) for k in srange(n+1)) for n in srange(67)])
# Peter Luschny, Dec 03 2023

Formula

a(n) = phi(n) - tau(n-1) for n > 1, where phi(n) = A000010(n) and tau(n) = A000005(n).

Extensions

Corrected a(1) to 0 by Peter Luschny, Dec 03 2023