|
%I #48 Mar 28 2015 16:52:10
%S 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,
%T 12,12,13,13,13,14,14,15,15,15,15,16,16,16,17,17,18,18,18,19,19,19,20,
%U 20,21,21,21,21,22,22,22,23,23,23,24,24,24,25,25,26,26,26,26,27,27,27
%N 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).
%C 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
%C It appears that this sequence gives the partial sums of A164349. - _Arie Groeneveld_, Aug 27 2014
%C 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
%C a(n) = Theta(n), see link. - _Benoit Jubin_, Sep 16 2014
%C 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
%C The (10^k)-th term: 0, 3, 36, 355, 3549, 35494, 354942, ... - _Robert G. Wilson v_, Sep 19 2014
%H Charles R Greathouse IV, <a href="/A101402/b101402.txt">Table of n, a(n) for n = 0..10000</a>
%H Benoit Jubin, <a href="/A101402/a101402_1.txt">Proof that A101402(n) = Theta(n)</a>
%F For n > 1: a(n) = a(A053644(n-1)) + a(A053645(n-1)). - _Reinhard Zumkeller_, Aug 27 2014
%e a(2) = a(1) + a(0) = 1 = 1 + 0;
%e a(3) = a(2) + a(0) = 1 = 1 + 0;
%e a(4) = a(2) + a(1) = 2 = 1 + 1;
%e a(5) = a(4) + a(0) = 2 = 2 + 0;
%e a(6) = a(4) + a(1) = 3 = 2 + 1;
%e a(7) = a(4) + a(2) = 3 = 2 + 1;
%e a(8) = a(4) + a(3) = 3 = 2 + 1;
%e a(9) = a(8) + a(0) = 3 = 3 + 0; ...
%e The terms fall naturally into blocks of sizes 1,1,1,2,4,8,16,32,...:
%e 0,
%e 1,
%e 1,
%e 1, 2,
%e 2, 3, 3, 3,
%e 3, 4, 4, 4, 5, 5, 6, 6,
%e 6, 7, 7, 7, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12,
%e 12, 13, 13, 13, 14, 14, ...
%e 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).
%e The final terms of the blocks, a(2^k), appear to be given by A164363. - _N. J. A. Sloane_, Aug 27 2014
%t 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 *)
%o (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
%o (Haskell)
%o import Data.Function (on); import Data.List (genericIndex)
%o a101402 = genericIndex a101402_list
%o a101402_list = 0 : 1 : zipWith ((+) `on` a101402)
%o (tail a053644_list) a053645_list
%o -- _Reinhard Zumkeller_, Aug 27 2014
%Y Cf. A101403, A101404, A000045, A164363, A164369, A053644, A053645, A062383.
%K easy,nonn
%O 0,5
%A _Odimar Fabeny_, Jan 16 2005
%E Offset corrected by _R. J. Mathar_, Aug 17 2009
%E More terms from _Robert G. Wilson v_, Aug 17 2009
|
