A155609 -id:A155609 - 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.

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

Offset: 0

Richard Bean, Feb 22 2003

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)
a(n) is also the number of even elements in the n X n symmetric Pascal matrix. - Stefano Spezia, Nov 14 2022

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.

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.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 29.

Cf. A063437.
Cf. A000120, A005061, A006218, A050315, A155609, A247935, A267610, A267700.
Cf. A325096, A325098, A325102, A325103, A325104, A325106, A325124.

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

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 *)

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

A155610 5^n - 3^n + 1.

Original entry on oeis.org

1, 3, 17, 99, 545, 2883, 14897, 75939, 384065, 1933443, 9706577, 48650979, 243609185, 1219108803, 6098732657, 30503229219, 152544843905, 762810312963, 3814309845137, 19072324066659, 95363944856225, 476826697849923

Offset: 0

Mohammad K. Azarian, Jan 26 2009

Index entries for linear recurrences with constant coefficients, signature (9,-23,15).

Cf. A155596, A155597, A155598, A155599, A155600, A155601, A155602, A155603, A155604, A155605, A155606, A155607, A155608, A155609.

Table[5^n-3^n+1,{n,0,30}] (* or *) LinearRecurrence[{9,-23,15},{1,3,17},31] (* Harvey P. Dale, Jan 06 2012 *)

a(n)=5^n-3^n+1 \\ Charles R Greathouse IV, Oct 07 2015

G.f.: 1/(1-5*x)-1/(1-3*x)+1/(1-x).
E.g.f.: e^(5*x)-e^(3*x)+e^x.
a(n) = 8*a(n-1)-15*a(n-2)+8 with a(0)=1, a(1)=3. - Vincenzo Librandi, Jul 21 2010
a(0)=1, a(1)=3, a(2)=17, a(n)=9*a(n-1)-23*a(n-2)+15*a(n-3). - Harvey P. Dale, Jan 06 2012

A155612 7^n - 3^n + 1.

Original entry on oeis.org

1, 5, 41, 317, 2321, 16565, 116921, 821357, 5758241, 40333925, 282416201, 1977149597, 13840755761, 96887416085, 678218289881, 4747547161037, 33232887522881, 232630384847045, 1628413210489961, 11398894023111677

Offset: 0

Mohammad K. Azarian, Jan 26 2009

Index entries for linear recurrences with constant coefficients, signature (11,-31,21).

Cf. A155596, A155597, A155598, A155599, A155600, A155601, A155602, A155603, A155604, A155605, A155606, A155607, A155608, A155609, A155610, A155611.

a(n)=7^n-3^n+1 \\ Charles R Greathouse IV, Oct 07 2015

G.f.: 1/(1-7*x)-1/(1-3*x)+1/(1-x).
E.g.f.: e^(7*x)-e^(3*x)+e^x.
a(n) = 10*a(n-1)-21*a(n-2)+12 with a(0)=1, a(1)=5. - Vincenzo Librandi, Jul 21 2010

A155613 8^n - 3^n + 1.

Original entry on oeis.org

1, 6, 56, 486, 4016, 32526, 261416, 2094966, 16770656, 134198046, 1073682776, 8589757446, 68718945296, 549754219566, 4398041728136, 35184357739926, 281474933663936, 2251799684545086, 18014398122061496, 144115186913594406

Offset: 0

Mohammad K. Azarian, Jan 26 2009

Index entries for linear recurrences with constant coefficients, signature (12,-35,24).

Cf. A155596, A155597, A155598, A155599, A155600, A155601, A155602, A155603, A155604, A155605, A155606, A155607, A155608, A155609, A155610, A155611, A155612.

Table[8^n-3^n+1,{n,0,20}] (* or *) LinearRecurrence[{12,-35,24},{1,6,56},20] (* Harvey P. Dale, Mar 12 2014 *)

a(n)=8^n-3^n+1 \\ Charles R Greathouse IV, Oct 07 2015

G.f.: 1/(1-8*x)-1/(1-3*x)+1/(1-x).
E.g.f.: e^(8*x)-e^(3*x)+e^x.
a(n) = 11*a(n-1)-24*a(n-2)+14 with a(0)=1, a(1)=6. - Vincenzo Librandi, Jul 21 2010

A155614 9^n - 3^n + 1.

Original entry on oeis.org

1, 7, 73, 703, 6481, 58807, 530713, 4780783, 43040161, 387400807, 3486725353, 31380882463, 282429005041, 2541864234007, 22876787671993, 205891117745743, 1853020145805121, 16677181570526407, 150094634909578633

Offset: 0

Mohammad K. Azarian, Jan 26 2009

Index entries for linear recurrences with constant coefficients, signature (13,-39,27).

Cf. A155599, A155600, A155601, A155602, A155603, A155604, A155605, A155606, A155607, A155608, A155609, A155610, A155611, A155612, A155613.

Table[9^n-3^n+1,{n,0,20}]  (* Harvey P. Dale, Feb 03 2011 *)

a(n)=9^n-3^n+1 \\ Charles R Greathouse IV, Oct 07 2015

G.f.: 1/(1-9*x)-1/(1-3*x)+1/(1-x).
E.g.f.: e^(9*x)-e^(3*x)+e^x.
a(n) = 12*a(n-1)-27*a(n-2)+16 with a(0)=1, a(1)=7. - Vincenzo Librandi, Jul 21 2010

A155615 a(n) = 10^n - 3^n + 1.

Original entry on oeis.org

1, 8, 92, 974, 9920, 99758, 999272, 9997814, 99993440, 999980318, 9999940952, 99999822854, 999999468560, 9999998405678, 99999995217032, 999999985651094, 9999999956953280, 99999999870859838, 999999999612579512

Offset: 0

Mohammad K. Azarian, Jan 26 2009

Index entries for linear recurrences with constant coefficients, signature (14,-43,30).

Cf. A155599, A155600, A155601, A155602, A155603, A155604, A155605, A155606, A155607, A155608, A155609, A155610, A155611, A155612, A155613, A155614.

a(n)=10^n-3^n+1 \\ Charles R Greathouse IV, Oct 07 2015

G.f.: 1/(1-10*x)-1/(1-3*x)+1/(1-x).
E.g.f.: e^(10*x)-e^(3*x)+e^x.
a(n) = 13*a(n-1)-30*a(n-2)+18 with a(0)=1, a(1)=8. - Vincenzo Librandi, Jul 21 2010

A155616 5^n + 4^n - 1.

Original entry on oeis.org

1, 8, 40, 188, 880, 4148, 19720, 94508, 456160, 2215268, 10814200, 53022428, 260917840, 1287811988, 6371951080, 31591319948, 156882857920, 780119322308, 3883416742360, 19348364235068, 96466943268400, 481235204714228

Offset: 0

Mohammad K. Azarian, Jan 27 2009

Index entries for linear recurrences with constant coefficients, signature (10,-29,20).

Cf. A155588, A155599, A155607, A155608, A155609, A155610, A155611, A155612, A155613, A155614, A155615.

a(n)=5^n+4^n-1 \\ Charles R Greathouse IV, Oct 16 2015

G.f.: 1/(1-5*x)+1/(1-4*x)-1/(1-x).
E.g.f.: e^(5*x)+e^(4*x)-e^x.
a(n) = 9*a(n-1)-20*a(n-2)-12 with a(0)=1, a(1)=8 - Vincenzo Librandi, Jul 21 2010

A155617 a(n) = 6^n + 4^n - 1.

Original entry on oeis.org

1, 9, 51, 279, 1551, 8799, 50751, 296319, 1745151, 10339839, 61514751, 366991359, 2193559551, 13127802879, 78632599551, 471258726399, 2825404874751, 16943839313919, 101628676145151, 609634617917439, 3657257951690751

Offset: 0

Mohammad K. Azarian, Jan 27 2009

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (11,-34,24).

Cf. A155588, A155599, A155607, A155608, A155609, A155610, A155611, A155612, A155613, A155614, A155615, A155616.

[6^n+4^n-1: n in [0..20]]; // Vincenzo Librandi, Feb 16 2013

I:=[1,9,51]; [n le 3 select I[n] else 11*Self(n-1)-34*Self(n-2)+24*Self(n-3): n in [1..25]]; // Vincenzo Librandi, Feb 16 2013

Table[(6^n + 4^n - 1^n), {n, 0, 30}] (* Vincenzo Librandi, Feb 16 2013 *)
LinearRecurrence[{11,-34,24},{1,9,51},30] (* Harvey P. Dale, Mar 30 2019 *)

a(n)=6^n+4^n-1 \\ Charles R Greathouse IV, Oct 16 2015

G.f.: 1/(1-6*x)+1/(1-4*x)-1/(1-x).
E.g.f.: exp(6*x) + exp(4*x) - exp(x).
a(n) = 10*a(n-1)-24*a(n-2) -15, n>1 - Gary Detlefs, Jun 21 2010
a(n) = 11*a(n-1)-34*a(n-2)+24*a(n-3). - Vincenzo Librandi, Feb 16 2013

A155618 a(n) = 7^n+4^n-1^n.

Original entry on oeis.org

1, 10, 64, 406, 2656, 17830, 121744, 839926, 5830336, 40615750, 283523824, 1981521046, 13858064416, 96956119270, 678491508304, 4748635251766, 33237225536896, 232647693856390, 1628482317387184, 11399170063280086

Offset: 0

Mohammad K. Azarian, Jan 27 2009

nonn

Index entries for linear recurrences with constant coefficients, signature (12,-39,28).

A155588, A155599, A155607, A155608, A155609, A155610, A155611, A155612, A155613, A155614, A155615, A155616, A155617

A155618:=n->7^n+4^n-1: seq(A155618(n), n=0..30); # Wesley Ivan Hurt, Apr 11 2017

Table[7^n+4^n-1,{n,0,20}] (* or *) LinearRecurrence[{12,-39,28},{1,10,64},20] (* Harvey P. Dale, Feb 04 2014 *)

G.f.: 1/(1-7*x)+1/(1-4*x)-1/(1-x). E.g.f.: e^(7*x)+e^(4*x)-e^x.
a(n) = 11*a(n-1)-28*a(n-2)-18 with a(0)=1, a(1)=10 [Vincenzo Librandi, Jul 21 2010]
a(0)=1, a(1)=10, a(2)=64, a(n) = 12*a(n-1)-39*a(n-2)+28*a(n-3). - Harvey P. Dale, Feb 04 2014

A155619 8^n+4^n-1^n.

Original entry on oeis.org

1, 11, 79, 575, 4351, 33791, 266239, 2113535, 16842751, 134479871, 1074790399, 8594128895, 68736253951, 549822922751, 4398314946559, 35185445830655, 281479271677951, 2251816993554431, 18014467228958719, 144115462953762815

Offset: 0

Mohammad K. Azarian, Jan 27 2009

nonn

Index entries for linear recurrences with constant coefficients, signature (13,-44,32).

A155588, A155599, A155607, A155608, A155609, A155610, A155611, A155612, A155613, A155614, A155615, A155616, A155617, A155618

Table[8^n+4^n-1,{n,0,30}] (* or *) LinearRecurrence[{13,-44,32},{1,11,79},30] (* Harvey P. Dale, Jun 19 2013 *)

G.f.: 1/(1-8*x)+1/(1-4*x)-1/(1-x). E.g.f.: e^(8*x)+e^(4*x)-e^x.
a(n)=12*a(n-1)-32*a(n-2)-21 with a(0)=1, a(1)=11 [From Vincenzo Librandi, Jul 21 2010]
a(0)=1, a(1)=11, a(2)=79, a(n)=13*a(n-1)-44*a(n-2)+32*a(n-3). - Harvey P. Dale, Jun 19 2013

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A155610 5^n - 3^n + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A155612 7^n - 3^n + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A155613 8^n - 3^n + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A155614 9^n - 3^n + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A155615 a(n) = 10^n - 3^n + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A155616 5^n + 4^n - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A155617 a(n) = 6^n + 4^n - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Magma

Mathematica