login
Least k >= 3 such that Fibonacci(k) == -1 (mod 3^n).
1

%I #36 Sep 08 2022 08:45:08

%S 3,6,14,38,110,326,974,2918,8750,26246,78734,236198,708590,2125766,

%T 6377294,19131878,57395630,172186886,516560654,1549681958,4649045870,

%U 13947137606,41841412814,125524238438,376572715310,1129718145926

%N Least k >= 3 such that Fibonacci(k) == -1 (mod 3^n).

%D R. L. Graham, D. E. Knuth and O. Patashnick, "Concrete Mathematics", second edition, Addison Wesley, ex. 6.59.

%H Vincenzo Librandi, <a href="/A079003/b079003.txt">Table of n, a(n) for n = 1..1000</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-3).

%F a(1) = 3; for n > 1, a(n) = 3*a(n-1)-4; a(n) = 4*3^(n-2)+2.

%F From _Colin Barker_, May 01 2012: (Start)

%F a(n) = 4*a(n-1) - 3*a(n-2) for n > 3.

%F G.f.: x*(3 - 6*x - x^2)/((1-x)*(1-3*x)). (End)

%F E.g.f.: (1/9)*(4*exp(3*x) + 18*exp(x) - 3*x - 22). - _Stefano Spezia_, Nov 10 2019

%t CoefficientList[Series[(3-6*x-x^2)/((1-x)*(1-3*x)),{x,0,40}],x] (* _Vincenzo Librandi_, Jun 23 2012 *)

%o (PARI) a(n)=if(n<0,0,x=3; while((fibonacci(x)+1)%(3^n)>0,x++); x)

%o (Magma) I:=[3, 6, 14, 38]; [n le 4 select I[n] else 4*Self(n-1) -3*Self(n-2): n in [1..30]]; // _Vincenzo Librandi_, Jun 23 2012

%K nonn,easy

%O 1,1

%A _Benoit Cloitre_, Feb 01 2003