OFFSET
0,3
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..10000
Project Euler, Problem 463
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.
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
KEYWORD
nonn
AUTHOR
Olivier Pirson, Mar 18 2014
EXTENSIONS
More terms from Alois P. Heinz, May 19 2014
STATUS
approved