A079882 -id:A079882 - cp's OEIS frontend

A079945 Partial sums of A079882.

1, 3, 4, 5, 7, 9, 10, 11, 12, 13, 15, 17, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 31, 33, 35, 37, 39, 41, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103

Offset: 0

N. J. A. Sloane, Feb 21 2003

Hsien-Kuei Hwang, S Janson, TH Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016; http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585

Robert Israel, Table of n, a(n) for n = 0..10000
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions

Apart from initial terms, same as A080596.

A079882:= [seq(op([1$(2^n),2$(2^n)]),n=0..6)]:
ListTools:-PartialSums(A079882); # Robert Israel, Oct 26 2020

See A080596 for an explicit formula.
a(n) = (3*n+3-2^(A000523((n+2)/2))-(-1)^A079944(n)*(n+3-3*2^(A000523((n+2)/2))))/2. - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 23 2003
Also a(n) = n+2^A000523((n+2)/2)*(1-3*A079944(n))+A079944(n)*(n+3) - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 23 2003

A079944 A run of 2^n 0's followed by a run of 2^n 1's, for n=0, 1, 2, ...

Original entry on oeis.org

0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1

Offset: 0

N. J. A. Sloane, Feb 21 2003

With offset 2, this is the second bit in the binary expansion of n. - Franklin T. Adams-Watters, Feb 13 2009

a(n) = A173920(n+2,2); in the sequence of nonnegative integers (cf. A001477) substitute all n by 2^floor(n/2) occurrences of (n mod 2). - Reinhard Zumkeller, Mar 04 2010

Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. See Example 1.34.

R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions

Cf. A086694, A079882, A079945, A173922, A173923.

a079944 n = a079944_list !! n
a079944_list =  f [0,1] where f (x:xs) = x : f (xs ++ [x,x])
-- Reinhard Zumkeller, Oct 14 2010, Mar 28 2011

Table[IntegerDigits[n + 2, 2][[2]], {n, 0, 100}] (* Jean-François Alcover, Jul 26 2019 *)

a(n)=binary(n+2)[2] \\ Charles R Greathouse IV, Nov 07 2016

a(n) = floor(log[2](4*(n+2)/3)) - floor(log[2](n+2)). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 22 2003
For n >= 2, a(n-2)=1+floor(log[2](n/3))-floor(log[2](n/2)) - Benoit Cloitre, Mar 03 2003
G.f.: 1/x^2/(1-x) * (1/x + sum(k>=0, x^(3*2^k)-x^2^(k+1))). - Ralf Stephan, Jun 04 2003
a(n) = A000035(A004526(A030101(n+2))). - Reinhard Zumkeller, Mar 04 2010

A080637 a(n) is the smallest positive integer which is consistent with the sequence being monotonically increasing and satisfying a(1)=2, a(a(n)) = 2n+1 for n > 1.

Original entry on oeis.org

2, 3, 5, 6, 7, 9, 11, 12, 13, 14, 15, 17, 19, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33, 35, 37, 39, 41, 43, 45, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 96, 97, 98, 99, 100, 101, 102

Offset: 1

N. J. A. Sloane and Benoit Cloitre, Feb 28 2003

Sequence is the unique monotonic sequence satisfying a(a(n)) = 2n+1.

Except for the first term, numbers (greater than 2) whose binary representation starts with 11 or ends with 1. - Yifan Xie, May 26 2022

			From _Yifan Xie_, May 02 2022: (Start)
a(8) = 12 because 2*2^2 <= 8 < 3*2^2, hence a(8) = 8 + 2^2 = 12;
a(13) = 19 because 3*2^2 <= 13 < 4*2^2, hence a(13) = 2*(13 - 2^2) + 1 = 19. (End)

Yifan Xie, Table of n, a(n) for n = 1..10000
Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, J. Integer Seqs., Vol. 6 (2003), #03.2.2.
Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, arXiv:math/0305308 [math.NT], 2003.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Index entries for sequences of the a(a(n)) = 2n family

Except for first term, same as A079905. Cf. A079000.
A007378, A079905, A080637, A080653 are all essentially the same sequence.
Equals A007378(n+1)-1. First differences give A079882.
Unique monotonic sequence of positive integers satisfying a(a(n)) = k*(n-1) + 3: this sequence (k=2), A003605 (k=3), A353651 (k=4), A353652 (k=5), A353653 (k=6).

t := []; for k from 0 to 6 do for j from -2^k to 2^k-1 do t := [op(t), 4*2^k - 1 + 3*j/2 + abs(j)/2]; od: od: t;

b[n_] := b[n] = If[n<4, n+1, If[OddQ[n], b[(n-1)/2+1]+b[(n-1)/2], 2b[n/2]]];
a[n_] := b[n+1]-1;
a /@ Range[70] (* Jean-François Alcover, Oct 31 2019 *)

a(3*2^k - 1 + j) = 4*2^k - 1 + 3*j/2 + |j|/2 for k >= 0, -2^k <= j < 2^k.
a(2n+1) = 2*a(n) + 1, a(2n) = a(n) + a(n-1) + 1.
From Yifan Xie, May 02 2022: (Start)
For n in the range 2*2^i <= n < 3*2^i, for i >= 0:
  a(n) = n + 2^i.
  a(n) = 1 + a(n-1).
Otherwise, for n in the range 3*2^i <= n < 4*2^i, for i >= 0:
  a(n) = 2*(n - 2^i) + 1.
  a(n) = 2 + a(n-1). (End)

A173920 Triangle read by rows: T(n,k) = convolution of n with k in binary representation, 0<=k<=n.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 0, 1, 1, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 0, 1, 1, 2, 1, 2, 2, 3, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 2, 0, 1, 0, 1, 1, 2, 1, 2, 0, 1, 0, 0, 1, 0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2

Offset: 0

Reinhard Zumkeller, Mar 04 2010

T(n,k) = SUM(bn(i)*bk(L-i-1): 0<=iA070939(n), n=SUM(bn(i)*2^i:0<=i

T(n,2*k+1) = T(n,2*k) + 1;

T(n,k) <= MIN{A000120(n),A000120(k)};

row sums give A173921; central terms give A159780;

T(n,0) = A000004(n);

T(n,1) = A000012(n) for n>0;

T(n,2) = A079944(n-2) for n>1;

T(n,3) = A079882(n-2) for n>2;

T(n,4) = A173922(n-4) for n>3;

T(n,8) = A173923(n-8) for n>7;

T(n,n) = A159780(n).

			T(13,10) = T('1101','1010') = 1*0 + 1*1 + 0*0 + 1*1 = 2;
T(13,11) = T('1101','1011') = 1*1 + 1*1 + 0*0 + 1*1 = 3;
T(13,12) = T('1101','1100') = 1*0 + 1*0 + 0*1 + 1*1 = 1;
T(13,13) = T('1101','1101') = 1*1 + 1*0 + 0*1 + 1*1 = 2.
Triangle begins:
  0;
  0, 1;
  0, 1, 0;
  0, 1, 1, 2;
  0, 1, 0, 1, 0;
  0, 1, 0, 1, 1, 2;
  ...

T[n_, k_] := Module[{bn, bk, lg},
     bn = IntegerDigits[n, 2];
     bk = IntegerDigits[k, 2];
     lg = Max[Length[bn], Length[bk]];
     ListConvolve[PadLeft[bn, lg], PadLeft[bk, lg]]][[1]];
Table[T[n, k], {n, 0, 13}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 19 2021 *)

T(n,k) = c(A030101(n),k,0) with c(x,y,z) = if y=0 then z else c([x/2],[y/2],z+(x mod 2)*(y mod 2)).

A079948 First differences of A079000.

Original entry on oeis.org

3, 2, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

N. J. A. Sloane, Feb 22 2003

nonn

Alternate description of sequence: start with a(1)=3; apply 1->2, 2->11, 3->21; iterate. - Matthew Vandermast, Mar 08 2003

N. J. A. Sloane, Seven Staggering Sequences, in Homage to a Pied Puzzler, E. Pegg Jr., A. H. Schoen and T. Rodgers (editors), A. K. Peters, Wellesley, MA, 2009, pp. 93-110.

B. Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, J. Integer Seqs., Vol. 6 (2003), #03.2.2.
B. Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, arXiv:math/0305308 [math.NT], 2003.
N. J. A. Sloane, Seven Staggering Sequences.

b[1] = 1; b[n_] := (k = Floor[Log[2, (n+3)/6]]; j = n - (9*2^k-3); 12*2^k - 3 + 3*j/2 + Abs[j]/2); Array[b, 106] // Differences (* Jean-François Alcover, Sep 02 2018 *)

After first two terms, a run of length 3*2^k 1's followed by a run of length 3*2^k 2's, for k = 0, 1, ...
a(n) = floor(log_2(8*(floor((n+3)/3))/3)) - floor(log_2(floor((n+3)/3))) for n>2; with a(1)=3 and a(2)=2. - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 22 2003
Also a(n) = A079882(A002264(n+3)) for n>2, where A002264=floor(n/3). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 22 2003

A086694 A run of 2^n 1's followed by a run of 2^n 0's, for n=0, 1, 2, ...

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Ralf Stephan, Sep 12 2003

First differences of A006165 and, likely, of A078881.

Robert Israel, Table of n, a(n) for n = 1..10000
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A005942, A079944.

seq(op([1$(2^n),0$(2^n)]),n=0..6); # Robert Israel, Jul 27 2017

Table[{PadRight[{},2^n,1],PadRight[{},2^n,0]},{n,0,5}]//Flatten (* Harvey P. Dale, May 29 2017 *)
Table[{Array[1&,2^n],Array[0&,2^n]},{n,0,5}]//Flatten (* Wolfgang Hintze, Jul 27 2017 *)

a(n)=if(n<3,if(n<2,1,0),if(n%2==0,a(n/2-1),a((n-1)/2)))

a(n) = 1-A079944(n-1) = 2-A079882(n-1) = A080791(n+1)-A083661(n+1).
a(n) = 1 - floor(log_2(4*(n+1)/3)) + floor(log_2(n+1)).
a(1) = 1, a(2) = 0, a(2n+1) = a(n), a(2n) = a(n-1).
G.f.: Sum_{k>=1} (x^(2^k)-x^(3*2^(k-1)))/(x-x^2). - Robert Israel, Jul 27 2017
G.f.: g(x) = (1/(1 - x))*( Sum_{n >= 1} x^(2^n-1)*(1 - x^2^(n-1)) ). Functional equation: g(x) = x + x*(1+x)*g(x^2). - Wolfgang Hintze, Aug 05 2017

Showing 1-6 of 6 results.

cp's OEIS Frontend

A079945 Partial sums of A079882.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Formula

A079944 A run of 2^n 0's followed by a run of 2^n 1's, for n=0, 1, 2, ...

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A080637 a(n) is the smallest positive integer which is consistent with the sequence being monotonically increasing and satisfying a(1)=2, a(a(n)) = 2n+1 for n > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A173920 Triangle read by rows: T(n,k) = convolution of n with k in binary representation, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

Formula

A079948 First differences of A079000.

Views

Author

Keywords

Comments

References

Links

Programs

Mathematica

Formula

A086694 A run of 2^n 1's followed by a run of 2^n 0's, for n=0, 1, 2, ...

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula