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;
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.
```

• Follow-Ups:
• References: