A164363 -id:A164363 - cp's OEIS frontend

A101402 a(0)=0, a(1)=1; for n>=2, let k = smallest power of 2 that is >= n, then a(n) = a(k/2) + a(n-1-k/2).

0, 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12, 12, 13, 13, 13, 14, 14, 15, 15, 15, 15, 16, 16, 16, 17, 17, 18, 18, 18, 19, 19, 19, 20, 20, 21, 21, 21, 21, 22, 22, 22, 23, 23, 23, 24, 24, 24, 25, 25, 26, 26, 26, 26, 27, 27, 27

Offset: 0

Odimar Fabeny, Jan 16 2005

Either a(n) = a(n-1) or a(n) = a(n-1) + 1. Proof: Suppose n is a power of 2, then a(n+1) = a(n) + a(0) = a(n). Otherwise let 2m be the largest power of 2 greater than n, so a(n) = a(m) + a(n-1-m) and a(n+1) = a(m) + a(n-m) and then proceed by induction. - Charles R Greathouse IV, Aug 27 2014
It appears that this sequence gives the partial sums of A164349. - Arie Groeneveld, Aug 27 2014
Each term other than zero appears at least twice. Suppose m is a power of 2, then a(2m) and a(4m) appear at least twice by my above comment. Otherwise suppose 3 <= k+2 <= 2m, then a(2m+k) = a(m) + a(m+k-1), a(2m+k+1) = a(m) + a(2m+k), and a(2m+k+2) = a(m) + a(m) + a(m+k+1), so a(2m+k+2) - a(2m+k) = a(m+k+1) - a(m+k-1). So if each term from a(m) to a(2m) appears at least twice then so will each term in a(2m) to a(4m). - Charles R Greathouse IV, Sep 10 2014
a(n) = Theta(n), see link. - Benoit Jubin, Sep 16 2014
The position of where n first appears: 0, 1, 4, 6, 10, 13, 15, 18, 21, 23, 27, 30, 32, 34, 37, 39, 43, 46, 48, 51, 54, 56, 60, 63, 66, 69, ... - Robert G. Wilson v, Sep 19 2014
The (10^k)-th term: 0, 3, 36, 355, 3549, 35494, 354942, ... - Robert G. Wilson v, Sep 19 2014

			a(2) = a(1) + a(0) = 1 = 1 + 0;
a(3) = a(2) + a(0) = 1 = 1 + 0;
a(4) = a(2) + a(1) = 2 = 1 + 1;
a(5) = a(4) + a(0) = 2 = 2 + 0;
a(6) = a(4) + a(1) = 3 = 2 + 1;
a(7) = a(4) + a(2) = 3 = 2 + 1;
a(8) = a(4) + a(3) = 3 = 2 + 1;
a(9) = a(8) + a(0) = 3 = 3 + 0; ...
The terms fall naturally into blocks of sizes 1,1,1,2,4,8,16,32,...:
0,
1,
1,
1, 2,
2, 3, 3, 3,
3, 4, 4, 4, 5, 5, 6, 6,
6, 7, 7, 7, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12,
12, 13, 13, 13, 14, 14, ...
Then the definition says that the k-th block is the final term of the previous block added to the sequence starting from the beginning (e.g., 34445566 = 3 + 01112233).
The final terms of the blocks, a(2^k), appear to be given by A164363. - _N. J. A. Sloane_, Aug 27 2014

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000
Benoit Jubin, Proof that A101402(n) = Theta(n)

Cf. A101403, A101404, A000045, A164363, A164369, A053644, A053645, A062383.

import Data.Function (on); import Data.List (genericIndex)
a101402 = genericIndex a101402_list
a101402_list = 0 : 1 : zipWith ((+) `on` a101402)
                       (tail a053644_list) a053645_list
-- Reinhard Zumkeller, Aug 27 2014

a[0] = 0; a[1] = 1; a[n_] := a[n] = Block[{p = 2^(Ceiling[Log[2, n]] - 1)}, a[p] + a[n - 1 - p]]; Table[ a@n, {n, 0, 100}] (* Robert G. Wilson v, Aug 17 2009 *)

a(n)=if(n<4, n>0, my(k=2^(log(n-.5)\log(2))); a(k) + a(n-1-k)) \\ Charles R Greathouse IV, Aug 25 2014

For n > 1: a(n) = a(A053644(n-1)) + a(A053645(n-1)). - Reinhard Zumkeller, Aug 27 2014

Offset corrected by R. J. Mathar, Aug 17 2009

More terms from Robert G. Wilson v, Aug 17 2009

A164362 The number of 0's in the n-th stage of A164349.

Original entry on oeis.org

1, 2, 3, 6, 11, 21, 42, 83, 166, 331, 661, 1322, 2643, 5285, 10569, 21138, 42275, 84550, 169099, 338197, 676394, 1352787, 2705573, 5411146, 10822291, 21644582, 43289163, 86578325, 173156650, 346313299, 692626597, 1385253193, 2770506386, 5541012771, 11082025542

Offset: 1

Jack W Grahl, Aug 14 2009

nonn

A164349 is generated as follows. Start with the string 01, and at each stage copy the previous string twice and remove the last symbol.

Since the number of symbols in the whole string is 2^n + 1, A164362 + A164363 = 2^n + 1.

			01 -> 010 -> 01001 -> 010010100 -> 01001010001001010 etc.
So the number of 0's in the n-th stage is the sequence 1, 2, 3, 6, 11 etc.

Paul Tek, Table of n, a(n) for n = 1..3323
Paul Tek, PERL program for this sequence

Cf. A164349, A164363, A164364.

t = Nest[ Most@ Flatten@ {#, #} &, {0, 1}, 25]; Table[ Count[ Take[t, 2^n + 1], 0], {n, 0, 25}] (* Robert G. Wilson v, Aug 17 2009 *)

A recurrence is given in terms of A164364(n) = A164349(2^n).

a(n+1) = 2*a(n) + A164364(n) - 1.

a(23)-a(26) from Robert G. Wilson v, Aug 17 2009

A164364 a(n) = A164349(2^n).

Original entry on oeis.org

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

Offset: 0

Jack W Grahl, Aug 14 2009

nonn

This is the last symbol at each stage of the method for generating A164349 using string operations.
The number of 1's in the string is given by A164363, and this number is given by the recurrence
A164363(n+1) = 2 * A164363(n) - A164364(n).
This leads to the formula A164363(n+1) = 2^n - 2^(n-1) * A164364(1) - 2^(n-2) * A164364(2) - ... - A164364(n);
for example,
A164363(5) = 16 - 8 A164364(1) - 4 A164364(2) - 2 A164364(3) - A164364(4).
This means that since the total number of symbols in the n-th string is 2**n + 1, the proportion of 0's in the first k terms of A164349, as n tends to infinity, is given by the number whose binary expansion is exactly this sequence. This number is approximately 0.6450588..

Paul Tek, Table of n, a(n) for n = 0..10000

Cf. A164349, A164362, A164363.

A053645 := proc(n) local dgs ; dgs := convert(n,base,2) ; add(op(i,dgs)*2^(i-1),i=1..nops(dgs)-1) ; end: A164349 := proc(n) option remember; if n <= 1 then n; else a := A053645(n-1) ; while a > 1 do a := A053645(a-1) ; od: a ; fi; end: A164364 := proc(n) A164349(2^n) ; end: seq(A164364(n),n=0..120) ; # R. J. Mathar, Aug 17 2009

t = Nest[ Most@ Flatten@ {#, #} &, {0, 1}, 25]; Table[ t[[2^n + 1]], {n, 0, 25}] (* Robert G. Wilson v, Aug 17 2009 *)

More terms from R. J. Mathar, Aug 17 2009

Incorrect comments removed by Jack W Grahl, Dec 26 2014

cp's OEIS Frontend

A101402 a(0)=0, a(1)=1; for n>=2, let k = smallest power of 2 that is >= n, then a(n) = a(k/2) + a(n-1-k/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A164362 The number of 0's in the n-th stage of A164349.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A164364 a(n) = A164349(2^n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions