cp's OEIS Frontend

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

%I A181830 #48 Dec 03 2023 07:34:10
%S A181830 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,
%T A181830 22,14,14,12,20,8,27,16,20,12,32,10,34,18,18,16,42,14,32,17,26,20,46,
%U A181830 16,32,20,28,24,54,14,48,28,32,26,41,16
%N A181830 The number of positive integers <= n that are strongly prime to n.
%C A181830 k is strongly prime to n if and only if k is relatively prime to n and k does not divide n - 1.
%C A181830 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
%C A181830 a(n) is odd if and only if n is in A002522 but n <> 2. - _Robert Israel_, Jun 20 2018
%H A181830 Robert Israel, <a href="/A181830/b181830.txt">Table of n, a(n) for n = 0..10000</a>
%H A181830 Peter Luschny, <a href="/wiki/User:Peter_Luschny/StrongCoprimality">Strong coprimality</a>
%H A181830 Matthew Scroggs, <a href="http://www.mscroggs.co.uk/blog/31">Braiding, pt. 2. Two results and a conjecture</a>
%F A181830 a(n) = phi(n) - tau(n-1) for n > 1, where phi(n) = A000010(n) and tau(n) = A000005(n).
%e A181830 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.
%t A181830 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 *)
%o A181830 (PARI) a(n)=if(n<2, 0, eulerphi(n)-numdiv(n-1));
%o A181830 for (i=0, 66, print1(a(i), ", ")) \\ _Michel Marcus_, May 22 2017
%o A181830 (SageMath)
%o A181830 def isstrongprimeto(k, n): return not(k.divides(n - 1)) and gcd(k, n) == 1
%o A181830 print([sum(int(isstrongprimeto(k, n)) for k in srange(n+1)) for n in srange(67)])
%o A181830 # _Peter Luschny_, Dec 03 2023
%Y A181830 Cf. A000005, A000010, A002522, A050384, A181831, A181832, A181833, A181834, A181835, A181836.
%K A181830 nonn,easy
%O A181830 0,8
%A A181830 _Peter Luschny_, Nov 17 2010
%E A181830 Corrected a(1) to 0 by _Peter Luschny_, Dec 03 2023