Bill Allombert on Sat, 23 Sep 2000 12:27:04 +0200 (MET DST)

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Fibo-Problem

I agree with Peter Montgomery. IIRC F_n is never a perfect power but
for F_6=8 and F_12=144.  

IIRC the proof consist on analysing the prime decomposition of F_n and
prove that if F_n is a perfect power then F_n<=2*n^2 so you have only
to check for n<20.

If you are more interested in fast number crunching,
the following trick can do:

? install(pvaluation,lGG&)
? { fn=1;fn1=1;
? ##
  ***   last result computed in 46,410 ms.
? fn+0.
%1 = 5.451970347688415609749286915 E29132 

I have cheat a bit installing a function:                                                                 
pvaluation(x,p,&q) returns e and set q such that x=q*p^e, q prime to p.

If you don't want to use install then
? pval(x) = local(d); d=[x];until(d[2],x=d[1];d=divrem(d[1],13));x
? {fn=1;fn1=1;
? ##
  ***   last result computed in 1mn, 13,220 ms.

Do not use "fibonacci()" in this case, since it use a LR-binary style
algorithm that is fast but not good to compute consecutive values.