A239447 Partial sums of A030101.

0, 1, 2, 5, 6, 11, 14, 21, 22, 31, 36, 49, 52, 63, 70, 85, 86, 103, 112, 137, 142, 163, 176, 205, 208, 227, 238, 265, 272, 295, 310, 341, 342, 375, 392, 441, 450, 491, 516, 573, 578, 615, 636, 689, 702, 747, 776, 837, 840, 875, 894, 945, 956, 999, 1026, 1085

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Project Euler, Problem 463: A weird recurrence relation

Formula

a(4n) = 6 a(2n) - 5 a(n) - 3 a(n-1) - 1.

a(4n + 1) = 2 a(2n+1) + 4 a(2n) - 6 a(n) - 2 a(n-1) - 1.

a(4n + 2) = 3 a(2n+1) + 3 a(2n) - 6 a(n) - 2 a(n-1) - 1.

a(4n + 3) = 6 a(2n+1) - 8 a(n) - 1.

Mathematica

Accumulate[Table[FromDigits[Reverse[IntegerDigits[n, 2]], 2], {n, 0, 80}]] (* Harvey P. Dale, Jan 10 2023 *)

Prog

(Python) A = {0: 0, 1: 1, 2: 2, 3: 5}
.
def a(n):
....a_n = A.get(n)
....if a_n is not None:
........return a_n
.
....q, r = divmod(n, 4)
....if r == 0:
........a_n = a(q*2)*6 - a(q)*5 - a(q - 1)*3 - 1
....elif r == 1:
........a_n = a(q*2 + 1)*2 + a(q*2)*4 - a(q)*6 - a(q - 1)*2 - 1
....elif r == 2:
........a_n = a(q*2 + 1)*3 + a(q*2)*3 - a(q)*6 - a(q - 1)*2 - 1
....else:
........a_n = a(q*2 + 1)*6 - a(q)*8 - 1
.
....A[n] = a_n  # memoization
.
....return a_n

Crossrefs

Cf. A030101.

Sequence in context: A341446 A015613 A135013 * A336527 A293398 A180323

Adjacent sequences: A239444 A239445 A239446 * A239448 A239449 A239450

Keyword

nonn

Author

Olivier Pirson, Mar 18 2014

Extensions

More terms from Alois P. Heinz, May 19 2014

Status

approved