login
A193805
Square array read by antidiagonals: S(n,k) is the number of m which are prime to n and are not strong divisors of k.
4
1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 4, 2, 2, 1, 1, 2, 3, 1, 1, 1, 1, 6, 2, 3, 2, 2, 1, 1, 4, 5, 2, 2, 2, 1, 1, 1, 6, 4, 5, 2, 4, 1, 2, 1, 1, 4, 5, 3, 4, 1, 2, 2, 1, 1, 1, 10, 4, 6, 4, 5, 2, 4, 2, 2, 1, 1, 4, 9, 3, 4, 3, 3, 2, 2, 1, 1, 1, 1, 12, 4, 9, 4, 5, 3, 6, 2
OFFSET
1,4
COMMENTS
We say d is a strong divisor of n iff d is a divisor of n and d > 1. Let phi(n) be Euler's totient function. Then phi(n) = S(n,1) = S(n,n). Thus S(n,k) can be regarded as a generalization of the totient function.
EXAMPLE
[x][1][2][3][4][5][6][7][8]
[1] 1, 1, 1, 1, 1, 1, 1, 1
[2] 1, 1, 1, 1, 1, 1, 1, 1
[3] 2, 1, 2, 1, 2, 1, 2, 1
[4] 2, 2, 1, 2, 2, 1, 2, 2
[5] 4, 3, 3, 2, 4, 2, 4, 2
[6] 2, 2, 2, 2, 1, 2, 2, 2
[7] 6, 5, 5, 4, 5, 3, 6, 4
[8] 4, 4, 3, 4, 3, 3, 3, 4
Triangle k=1..n, n>=1:
[1] 1
[2] 1, 1
[3] 2, 1, 2
[4] 2, 2, 1, 2
[5] 4, 3, 3, 2, 4
[6] 2, 2, 2, 2, 1, 2
[7] 6, 5, 5, 4, 5, 3, 6
[8] 4, 4, 3, 4, 3, 3, 3, 4
Triangle n=1..k, k>=1:
[1] 1
[2] 1, 1
[3] 1, 1, 2
[4] 1, 1, 1, 2
[5] 1, 1, 2, 2, 4
[6] 1, 1, 1, 1, 2, 2
[7] 1, 1, 2, 2, 4, 2, 6
[8] 1, 1, 1, 2, 2, 2, 4, 4
S(15, 22) = card({1,4,7,8,13,14}) = 6 because the coprimes of 15 are {1,2,4,7,8,11,13,14} and the strong divisors of 22 are {2, 11, 22}.
MAPLE
strongdivisors := n -> numtheory[divisors](n) minus {1}:
coprimes := n -> select(k->igcd(k, n)=1, {$1..n}):
S := (n, k) -> nops(coprimes(n) minus strongdivisors(k)):
seq(seq(S(n-k+1, k), k=1..n), n=1..13); # Square array by antidiagonals.
seq(print(seq(S(n, k), k=1..n)), n=1..8); # Lower triangle.
seq(print(seq(S(n, k), n=1..k)), k=1..8); # Upper triangle.
MATHEMATICA
s[n_, k_] := Complement[ Select[ Range[n], GCD [#, n] == 1 &], Rest[ Divisors[k]]] // Length; Table[ s[n-k+1, k], {n, 1, 13}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 25 2013 *)
PROG
(PARI) S(n, k)=eulerphi(n)-sumdiv(k, d, gcd(d, n)==1 && d<n && d>1)
for(s=2, 15, for(k=1, s-1, print1(S(s-k, k)", "))) \\ Charles R Greathouse IV, Aug 01 2016
CROSSREFS
KEYWORD
nonn,nice,tabl
AUTHOR
Peter Luschny, Aug 05 2011
STATUS
approved