login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 04:59 EDT 2024. Contains 371264 sequences. (Running on oeis4.)