A131294 a(n)=ds_3(a(n-1))+ds_3(a(n-2)), a(0)=0, a(1)=1; where ds_3=digital sum base 3.

0, 1, 1, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3

Offset: 0

Author

Hieronymus Fischer, Jun 27 2007

Keywords

• nonn
• base
• easy

Comments

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

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

a(n) and Fib(n)=A000045(n) are congruent modulo 2 which implies that (a(n) mod 2) is equal to (Fib(n) mod 2)=A011655(n). Thus (a(n) mod 2) is periodic with the Pisano period A001175(2)=3 too.

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

Examples

			a(5)=3, since a(3)=2, ds_3(2)=2, a(4)=3=10(base 3),
ds_3(3)=1 and so a(5)=2+1.
		

Links

• Index entries for Colombian or self numbers and related sequences
• Index entries for linear recurrences with constant coefficients, signature (0, 0, 1).

Crossrefs

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

Programs

Mathematica

nxt[{a_,b_}]:={b,Total[IntegerDigits[a,3]]+Total[IntegerDigits[b,3]]}; Transpose[NestList[nxt,{0,1},100]][[1]] (* Harvey P. Dale, Aug 02 2016 *)

Formula

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

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

a(n) = A002264(a(n-1))+A002264(a(n-2))+A010872(a(n-1))+A010872(a(n-2)).

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

Extensions

Incorrect comment removed by Michel Marcus, Apr 29 2018