cp's OEIS Frontend

A080572 Number of ordered pairs (i,j), 0 <= i,j < n, for which (i & j) is nonzero, where & is the bitwise AND operator.

%I A080572 #45 Nov 19 2022 20:26:49
%S A080572 0,0,1,2,7,8,15,24,37,38,49,62,81,98,121,146,175,176,195,216,247,272,
%T A080572 307,344,387,420,463,508,559,608,663,720,781,782,817,854,909,950,1009,
%U A080572 1070,1141,1190,1257,1326,1405,1478,1561,1646,1737,1802,1885,1970,2065,2154
%N A080572 Number of ordered pairs (i,j), 0 <= i,j < n, for which (i & j) is nonzero, where & is the bitwise AND operator.
%C A080572 Conjectured to be less than or equal to lcs(n) (see sequence A063437). The value of a(2^n) is that given in Stinson and van Rees and the value of a(2^n-1) is that given in Fu, Fu and Liao. This function gives an easy way to generate these two constructions.
%C A080572 From _Gus Wiseman_, Mar 30 2019: (Start)
%C A080572 Also the number of ordered pairs of positive integers up to n with at least one binary carry. A binary carry of two positive integers is an overlap of the positions of 1's in their reversed binary expansion. For example, the a(2) = 1 through a(6) = 15 ordered pairs are:
%C A080572   (1,1)  (1,1)  (1,1)  (1,1)  (1,1)
%C A080572          (2,2)  (1,3)  (1,3)  (1,3)
%C A080572                 (2,2)  (2,2)  (1,5)
%C A080572                 (2,3)  (2,3)  (2,2)
%C A080572                 (3,1)  (3,1)  (2,3)
%C A080572                 (3,2)  (3,2)  (3,1)
%C A080572                 (3,3)  (3,3)  (3,2)
%C A080572                        (4,4)  (3,3)
%C A080572                               (3,5)
%C A080572                               (4,4)
%C A080572                               (4,5)
%C A080572                               (5,1)
%C A080572                               (5,3)
%C A080572                               (5,4)
%C A080572                               (5,5)
%C A080572 (End)
%C A080572 a(n) is also the number of even elements in the n X n symmetric Pascal matrix. - _Stefano Spezia_, Nov 14 2022
%D A080572 C. Fu, H. Fu and W. Liao, A new construction for a critical set in special Latin squares, Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, Florida, 1995), Congressus Numerantium, Vol. 110 (1995), pp. 161-166.
%D A080572 D. R. Stinson and G. H. J. van Rees, Some large critical sets, Proceedings of the Eleventh Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, Manitoba, 1981), Congressus Numerantium, Vol. 34 (1982), pp. 441-456.
%H A080572 Alois P. Heinz, <a href="/A080572/b080572.txt">Table of n, a(n) for n = 0..10000</a>
%H A080572 R. Bean, <a href="http://dx.doi.org/10.1016/j.disc.2005.02.006">Three problems on partial Latin squares</a>, Problem 418 (BCC19,2), Discrete Math., 293 (2005), 314-315.
%H A080572 J. M. Dover, <a href="http://arxiv.org/abs/1606.08033">On two OEIS conjectures</a>, arXiv:1606.08033 [math.CO], 2016.
%H A080572 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, p. 29.
%F A080572 a(2^n) = 4^n-3^n = A005061(n); a(2^n+1) = 4^n-3^n+1 = A155609(n); a(2^n-1) = 4^n-3^n-2^(n+1)+3.
%F A080572 a(0)=a(1)=0, a(2n) = 3a(n)+n^2, a(2n+1) = a(n)+2a(n+1)+n^2-1. This was proved by Jeremy Dover. - _Ralf Stephan_, Dec 08 2004
%F A080572 a(n) = (A325104(n) - n)/2. - _Gus Wiseman_, Mar 30 2019
%p A080572 f:=proc(n) option remember; local t;
%p A080572 if n <= 1 then 0
%p A080572 elif (n mod 2) =  0 then 3*f(n/2)+(n/2)^2
%p A080572 else t:=(n-1)/2; f(t)+2*f(t+1)+t^2-1; fi; end;
%p A080572 [seq(f(n),n=0..100)]; # _N. J. A. Sloane_, Jul 01 2017
%t A080572 a[0] = a[1] = 0; a[n_] := a[n] = If[EvenQ[n], 3*a[n/2] + n^2/4, 2*a[(n-1)/2 + 1] + a[(n-1)/2] + (1/4)*(n-1)^2 - 1];
%t A080572 Array[a, 60, 0] (* _Jean-François Alcover_, Dec 09 2017, from Dover's formula *)
%t A080572 Table[Length[Select[Tuples[Range[n-1],2],Intersection[Position[Reverse[IntegerDigits[#[[1]],2]],1],Position[Reverse[IntegerDigits[#[[2]],2]],1]]!={}&]],{n,0,20}] (* _Gus Wiseman_, Mar 30 2019 *)
%Y A080572 Cf. A063437.
%Y A080572 Cf. A000120, A005061, A006218, A050315, A155609, A247935, A267610, A267700.
%Y A080572 Cf. A325096, A325098, A325102, A325103, A325104, A325106, A325124.
%K A080572 easy,nonn
%O A080572 0,4
%A A080572 _Richard Bean_, Feb 22 2003