A193805 - OEIS

%I #20 Aug 01 2016 01:08:04

%S 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,

%T 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,

%U 3,4,3,3,2,2,1,1,1,1,12,4,9,4,5,3,6,2

%N 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.

%C 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.

%H Peter Luschny, <a href="http://oeis.org/wiki/User:Peter_Luschny/EulerTotient">Euler's totient function</a>

%e [x][1][2][3][4][5][6][7][8]

%e [1] 1, 1, 1, 1, 1, 1, 1, 1

%e [2] 1, 1, 1, 1, 1, 1, 1, 1

%e [3] 2, 1, 2, 1, 2, 1, 2, 1

%e [4] 2, 2, 1, 2, 2, 1, 2, 2

%e [5] 4, 3, 3, 2, 4, 2, 4, 2

%e [6] 2, 2, 2, 2, 1, 2, 2, 2

%e [7] 6, 5, 5, 4, 5, 3, 6, 4

%e [8] 4, 4, 3, 4, 3, 3, 3, 4

%e Triangle k=1..n, n>=1:

%e [1]           1

%e [2]          1, 1

%e [3]        2, 1, 2

%e [4]       2, 2, 1, 2

%e [5]     4, 3, 3, 2, 4

%e [6]    2, 2, 2, 2, 1, 2

%e [7]  6, 5, 5, 4, 5, 3, 6

%e [8] 4, 4, 3, 4, 3, 3, 3, 4

%e Triangle n=1..k, k>=1:

%e [1]           1

%e [2]          1, 1

%e [3]        1, 1, 2

%e [4]       1, 1, 1, 2

%e [5]     1, 1, 2, 2, 4

%e [6]    1, 1, 1, 1, 2, 2

%e [7]  1, 1, 2, 2, 4, 2, 6

%e [8] 1, 1, 1, 2, 2, 2, 4, 4

%e 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}.

%p strongdivisors := n -> numtheory[divisors](n) minus {1}:

%p coprimes := n -> select(k->igcd(k,n)=1,{$1..n}):

%p S := (n,k) -> nops(coprimes(n) minus strongdivisors(k)):

%p seq(seq(S(n-k+1,k), k=1..n),n=1..13);  # Square array by antidiagonals.

%p seq(print(seq(S(n,k),k=1..n)),n=1..8); # Lower triangle.

%p seq(print(seq(S(n,k),n=1..k)),k=1..8); # Upper triangle.

%t 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 *)

%o (PARI) S(n,k)=eulerphi(n)-sumdiv(k,d, gcd(d,n)==1 && d<n && d>1)

%o for(s=2,15, for(k=1,s-1, print1(S(s-k,k)", "))) \\ _Charles R Greathouse IV_, Aug 01 2016

%Y Cf. A000010, A051953, A193804.

%K nonn,nice,tabl

%O 1,4

%A Peter Luschny, Aug 05 2011