login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 9
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

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

LINKS

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000

Benoit Jubin, Proof that A101402(n) = Theta(n)

FORMULA

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

EXAMPLE

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

MATHEMATICA

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

PROG

(PARI) 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

(Haskell)

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

CROSSREFS

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

Sequence in context: A095186 A265340 A189631 * A156251 A116458 A093875

Adjacent sequences:  A101399 A101400 A101401 * A101403 A101404 A101405

KEYWORD

easy,nonn

AUTHOR

Odimar Fabeny, Jan 16 2005

EXTENSIONS

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

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

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 24 00:27 EST 2017. Contains 295164 sequences.