

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(n1k/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(n1) or a(n) = a(n1) + 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(n1m) and a(n+1) = a(m) + a(nm) and then proceed by induction.  Charles R Greathouse IV, 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+k1), 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+k1). 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
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



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 kth block is the final term of the previous block added to the sequence starting from the beginning (e.g., 34445566 = 3 + 01112233).


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

(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


CROSSREFS



KEYWORD

easy,nonn


AUTHOR



EXTENSIONS



STATUS

approved



