I believe you have a typo. From http://projecteuler.net/problem=463, the recurrence is: f(1)=1 f(3)=3 f(2n)=f(n) f(4n+1)=2f(2n+1)-f(n) f(4n+3)=3f(2n+1)-2f(n) ("-", not "+"). And this is indeed a recurrence for A030101, as can readily be seen expanding the recurrence into binary strings and reversals. -Dave