|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
LINKS
|
|
|
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));
(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)])
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|