A131295 a(n)=ds_4(a(n-1))+ds_4(a(n-2)), a(0)=0, a(1)=1; where ds_4=digital sum base 4.

0, 1, 1, 2, 3, 5, 5, 4, 3, 4, 4, 2, 3, 5, 5, 4, 3, 4, 4, 2, 3, 5, 5, 4, 3, 4, 4, 2, 3, 5, 5, 4, 3, 4, 4, 2, 3, 5, 5, 4, 3, 4, 4, 2, 3, 5, 5, 4, 3, 4, 4, 2, 3, 5, 5, 4, 3, 4, 4, 2, 3, 5, 5, 4, 3, 4, 4, 2, 3, 5, 5, 4, 3, 4, 4, 2, 3, 5, 5, 4, 3, 4, 4, 2, 3, 5, 5, 4, 3, 4, 4, 2, 3, 5, 5, 4, 3, 4, 4, 2, 3

Offset: 0

Author

Hieronymus Fischer, Jun 27 2007

Keywords

• nonn
• base

Comments

The digital sum analog (in base 4) of the Fibonacci recurrence.

When starting from index n=3, periodic with Pisano period A001175(3)=8.

Also a(n)==A004090(n) modulo 3 (A004090(n)=digital sum of Fib(n)).

For general bases p>2, the inequality 2<=a(n)<=2p-3 holds for n>2. Actually, a(n)<=5=A131319(4) for the base p=4.

a(n) and Fib(n)=A000045(n) are congruent modulo 3 which implies that (a(n) mod 3) is equal to (Fib(n) mod 3)=A082115(n-1) (for n>0). Thus (a(n) mod 3) is periodic with the Pisano period = A001175(3)=8 too. - Hieronymus Fischer

Examples

			a(8)=3, since a(6)=5=11(base 4), ds_4(5)=2,
a(7)=4=10(base 4), ds_4(4)=1 and so a(8)=2+1.
		

Links

• Harvey P. Dale, Table of n, a(n) for n = 0..1000
• Index entries for Colombian or self numbers and related sequences

Crossrefs

Cf. A000045, A010073, A010074, A010075, A010076, A010077, A131294, A131296, A131297, A131318, A131319, A131320.

Programs

Mathematica

nxt[{a_,b_}]:={b,Total[IntegerDigits[a,4]]+Total[IntegerDigits[b,4]]}; NestList[ nxt,{0,1},110][[All,1]] (* Harvey P. Dale, Jul 30 2018 *)

Formula

a(n)=a(n-1)+a(n-2)-3*(floor(a(n-1)/4)+floor(a(n-2)/4)).

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

a(n)=A002265(a(n-1))+A002265(a(n-2))+A010873(a(n-1))+A010873(a(n-2)).

a(n)=Fib(n)-3*sum{1A000045(n).