login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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

From Gus Wiseman, Mar 30 2019: (Start)

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)

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

Alois P. Heinz, Table of n, a(n) for n = 0..10000

R. Bean, Three problems on partial Latin squares, Problem 418 (BCC19,2), Discrete Math., 293 (2005), 314-315.

J. M. Dover, On two OEIS conjectures, arXiv:1606.08033 [math.CO], 2016.

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

a(n) = (A325104(n) - n)/2. - Gus Wiseman, Mar 30 2019

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;

[seq(f(n), n=0..100)]; # N. J. A. Sloane, Jul 01 2017

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];

Array[a, 60, 0] (* Jean-Fran├žois Alcover, Dec 09 2017, from Dover's formula *)

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

Cf. A063437.

Cf. A000120, A005061, A006218, A050315, A155609, A247935, A267610, A267700.

Cf. A325096, A325098, A325102, A325103, A325104, A325106, A325124.

Sequence in context: A299151 A023178 A334227 * A263602 A162664 A341706

Adjacent sequences:  A080569 A080570 A080571 * A080573 A080574 A080575

KEYWORD

easy,nonn

AUTHOR

Richard Bean, Feb 22 2003

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 24 17:34 EDT 2021. Contains 345418 sequences. (Running on oeis4.)