login
A181830
The number of positive integers <= n that are strongly prime to n.
14
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,8
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
FORMULA
a(n) = phi(n) - tau(n-1) for n > 1, where phi(n) = A000010(n) and tau(n) = A000005(n).
EXAMPLE
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.
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 *)
PROG
(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
KEYWORD
nonn,easy
AUTHOR
Peter Luschny, Nov 17 2010
EXTENSIONS
Corrected a(1) to 0 by Peter Luschny, Dec 03 2023
STATUS
approved