A140472 a(n) = a(n - a(n-1)) + a(floor(n/2)).

0, 1, 2, 2, 4, 3, 4, 4, 8, 5, 6, 6, 8, 7, 8, 8, 16, 9, 10, 10, 12, 11, 12, 12, 16, 13, 14, 14, 16, 15, 16, 16, 32, 17, 18, 18, 20, 19, 20, 20, 24, 21, 22, 22, 24, 23, 24, 24, 32, 25, 26, 26, 28, 27, 28, 28, 32, 29, 30, 30, 32, 31, 32, 32, 64, 33, 34, 34, 36, 35, 36, 36, 40, 37, 38

Offset: 0

Author

Roger L. Bagula and Gary W. Adamson, Jun 28 2008

Keywords

• nonn

Comments

From M. F. Hasler, Oct 20 2019: (Start)

The sequence A285326/2 is characterized by a(2n) = 2*a(n) (n >= 0) and a(2n-1) = n (n >= 1). This implies the property defining this sequence: If n = 2k, then n - a(n-1) = 2k - a(2k-1) = 2k - k = k, so a(n - a(n-1)) + a(floor(n/2)) = a(k) + a(k) = 2*a(k) = a(2k) = a(n). If n = 2k-1, then n - a(n-1) = 2k-1 - a(2k-2) = 2k-1 - 2*a(k-1), whence a(n - a(n-1)) + a(floor(n/2)) = a(2(k - a(k-1)) - 1) + a(k-1) = k - a(k-1) + a(k-1) = k = a(2k-1) = a(n). Thus, A285326/2 satisfies the definition of this sequence.

The sequence is equal to itself multiplied by 2 and interleaved with the positive integers. (This is equivalent to the above characterization.)

The sequence repeats the pattern [A, B, C, C] where in the n-th occurrence C = 2n, B = C - 1, A = C if n is even, A = C + 2 if n == 3 (mod 4), and A = 16*a((n-1)/4) otherwise. This yields a simpler formula for all terms except for indices which are multiples of 16. (End)

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A004001, A006519.

Cf. A214546 (first differences).

Same as A109168, if a(0) = 0 is omitted. - M. F. Hasler, Oct 19 2019

Programs

Haskell

a140472 n = a140472_list !! n
a140472_list = 0 : 1 : h 2 1 where
  h x y = z : h (x + 1) z where z = a140472 (x - y) + a140472 (x `div` 2)
-- Reinhard Zumkeller, Jul 20 2012

Magma

I:=[1,2]; [0] cat [n le 2 select I[n] else Self(n-Self(n-1))+Self(Floor((n) div 2)):n in [1..75]]; // Marius A. Burtea, Aug 16 2019

Mathematica

a[0] = 0; a[1] = 1;
a[n_] := a[n] = a[n - a[n - 1]] + a[Floor[n/2]];
Table[a[n], {n, 0, 200}]

PARI

a(n)=(n+bitand(n,-n))\2 \\ M. F. Hasler, Oct 19 2019

Formula

a(0) = 0; a(1) = a(2) = 1; a(n) = a(n - a(n-1)) + a(floor(n/2)).

a(n) = (n+A006519(n))/2 for n > 0 (conjectured). - Jon Maiga, Aug 16 2019

a(n) = A285326(n)/2, equivalent to the above: see comments for the proof. - M. F. Hasler, Oct 19 2019

Extensions

Offset corrected by Reinhard Zumkeller, Jul 20 2012