login
Number of nonzero elements in the n X n Redheffer matrix.
6

%I #12 Oct 10 2021 06:11:36

%S 1,4,7,11,14,19,22,27,31,36,39,46,49,54,59,65,68,75,78,85,90,95,98,

%T 107,111,116,121,128,131,140,143,150,155,160,165,175,178,183,188,197,

%U 200,209,212,219,226,231,234,245,249,256,261,268,271,280,285,294,299,304

%N Number of nonzero elements in the n X n Redheffer matrix.

%F a(n) = A006590(n)+A000005(n)-1. [_Enrique Pérez Herrero_, Sep 28 2009]

%F a(n) = A006218(n)+n-1. [_Enrique Pérez Herrero_, Sep 25 2009]

%F a(1) = 1, a(n) = a(n-1) + A000005(n) + 1 for n > 1. a(1) = 1, a(n) = A006218(n+1) - A000005(n+1) + n - 1 = A006218(n+1) + A049820(n+1) - 2 = A006590(n+1) - 2 for n > 1. [_Jaroslav Krizek_, Nov 08 2009]

%e The 4x4 Redheffer matrix:

%e 1,1,1,1

%e 1,1,0,0

%e 1,0,1,0

%e 1,1,0,1

%e contains 11 nonzero elements.

%t A161886[n_] := Plus @@ Table[DivisorSigma[0, i], {i, 1, n}] + n - 1 (* _Enrique Pérez Herrero_, Sep 25 2009 *)

%t A161886[n_] := Total[Table[ Boole[Divisible[i, j] || (i == 1)], {i, 1, n}, {j, 1, n}], Infinity] (* _Enrique Pérez Herrero_, Sep 25 2009 *)

%t A161889[n_] := Plus @@ Plus @@ Table[Boole[Divisible[i, j] || (i == 1)], {i, 1, n}, {j, 1, n}] (* _Enrique Pérez Herrero_, Sep 28 2009 *)

%t A161889[n_] := Sum[Ceiling[n/i], {i, 1, n}] + DivisorSigma[0, n] - 1 (* _Enrique Pérez Herrero_, Sep 28 2009 *)

%o (Python)

%o from math import isqrt

%o def A161886(n): return (lambda m: 2*sum(n//k for k in range(1, m+1))+n-1-m*m)(isqrt(n)) # _Chai Wah Wu_, Oct 09 2021

%Y Cf. A143104, A006590, A000005.

%K nonn

%O 1,2

%A _Mats Granvik_, Jun 21 2009

%E Edited by _N. J. A. Sloane_, Jun 26 2009