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