Re: Fibo-Problem

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

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;
for(i=1,69700,z=fn1;fn1+=fn;fn=z;z=fn1;fn1+=fn;fn=z;
              pvaluation(fn,13,&q);if(q==1,print(i)))
}
3
? ##
  ***   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;
  for(i=1,69700,z=fn1;fn1+=fn;fn=z;z=fn1;fn1+=fn;fn=z;
	if(pval(fn)==1,print(i)))
}
3
? ##
  ***   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.

Bill.