|
|
A080572
|
|
Number of ordered pairs (i,j), 0 <= i,j < n, for which (i & j) is nonzero, where & is the bitwise AND operator.
|
|
20
|
|
|
0, 0, 1, 2, 7, 8, 15, 24, 37, 38, 49, 62, 81, 98, 121, 146, 175, 176, 195, 216, 247, 272, 307, 344, 387, 420, 463, 508, 559, 608, 663, 720, 781, 782, 817, 854, 909, 950, 1009, 1070, 1141, 1190, 1257, 1326, 1405, 1478, 1561, 1646, 1737, 1802, 1885, 1970, 2065, 2154
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
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.
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:
(1,1) (1,1) (1,1) (1,1) (1,1)
(2,2) (1,3) (1,3) (1,3)
(2,2) (2,2) (1,5)
(2,3) (2,3) (2,2)
(3,1) (3,1) (2,3)
(3,2) (3,2) (3,1)
(3,3) (3,3) (3,2)
(4,4) (3,3)
(3,5)
(4,4)
(4,5)
(5,1)
(5,3)
(5,4)
(5,5)
(End)
a(n) is also the number of even elements in the n X n symmetric Pascal matrix. - Stefano Spezia, Nov 14 2022
|
|
REFERENCES
|
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. 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.
|
|
LINKS
|
|
|
FORMULA
|
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.
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
|
|
MAPLE
|
f:=proc(n) option remember; local t;
if n <= 1 then 0
elif (n mod 2) = 0 then 3*f(n/2)+(n/2)^2
else t:=(n-1)/2; f(t)+2*f(t+1)+t^2-1; fi; end;
|
|
MATHEMATICA
|
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];
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|