cp's OEIS Frontend

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.

%I A193805 #20 Aug 01 2016 01:08:04
%S A193805 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 A193805 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 A193805 3,4,3,3,2,2,1,1,1,1,12,4,9,4,5,3,6,2
%N 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.
%C A193805 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 A193805 Peter Luschny, <a href="http://oeis.org/wiki/User:Peter_Luschny/EulerTotient">Euler's totient function</a>
%e A193805 [x][1][2][3][4][5][6][7][8]
%e A193805 [1] 1, 1, 1, 1, 1, 1, 1, 1
%e A193805 [2] 1, 1, 1, 1, 1, 1, 1, 1
%e A193805 [3] 2, 1, 2, 1, 2, 1, 2, 1
%e A193805 [4] 2, 2, 1, 2, 2, 1, 2, 2
%e A193805 [5] 4, 3, 3, 2, 4, 2, 4, 2
%e A193805 [6] 2, 2, 2, 2, 1, 2, 2, 2
%e A193805 [7] 6, 5, 5, 4, 5, 3, 6, 4
%e A193805 [8] 4, 4, 3, 4, 3, 3, 3, 4
%e A193805 Triangle k=1..n, n>=1:
%e A193805 [1]           1
%e A193805 [2]          1, 1
%e A193805 [3]        2, 1, 2
%e A193805 [4]       2, 2, 1, 2
%e A193805 [5]     4, 3, 3, 2, 4
%e A193805 [6]    2, 2, 2, 2, 1, 2
%e A193805 [7]  6, 5, 5, 4, 5, 3, 6
%e A193805 [8] 4, 4, 3, 4, 3, 3, 3, 4
%e A193805 Triangle n=1..k, k>=1:
%e A193805 [1]           1
%e A193805 [2]          1, 1
%e A193805 [3]        1, 1, 2
%e A193805 [4]       1, 1, 1, 2
%e A193805 [5]     1, 1, 2, 2, 4
%e A193805 [6]    1, 1, 1, 1, 2, 2
%e A193805 [7]  1, 1, 2, 2, 4, 2, 6
%e A193805 [8] 1, 1, 1, 2, 2, 2, 4, 4
%e A193805 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 A193805 strongdivisors := n -> numtheory[divisors](n) minus {1}:
%p A193805 coprimes := n -> select(k->igcd(k,n)=1,{$1..n}):
%p A193805 S := (n,k) -> nops(coprimes(n) minus strongdivisors(k)):
%p A193805 seq(seq(S(n-k+1,k), k=1..n),n=1..13);  # Square array by antidiagonals.
%p A193805 seq(print(seq(S(n,k),k=1..n)),n=1..8); # Lower triangle.
%p A193805 seq(print(seq(S(n,k),n=1..k)),k=1..8); # Upper triangle.
%t A193805 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 A193805 (PARI) S(n,k)=eulerphi(n)-sumdiv(k,d, gcd(d,n)==1 && d<n && d>1)
%o A193805 for(s=2,15, for(k=1,s-1, print1(S(s-k,k)", "))) \\ _Charles R Greathouse IV_, Aug 01 2016
%Y A193805 Cf. A000010, A051953, A193804.
%K A193805 nonn,nice,tabl
%O A193805 1,4
%A A193805 Peter Luschny, Aug 05 2011