/*
Euler #25 in Picat.
"""
The Fibonacci sequence is defined by the recurrence relation:
Fn = Fn1 + Fn2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12, is the first term to contain three digits.
What is the first term in the Fibonacci sequence to contain 1000 digits?")
"""
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
main => go.
go => time(euler25).
euler25 =>
Target = 1000,
FoundUpper = 0,
I = 1,
FibLen = 0,
Step = 30,
% Get the upper limit
while(FibLen < Target, FoundUpper == 0)
FibLen := fib_len(Step*I),
if FibLen > Target then
FoundUpper := I
end,
I := I + 1 % jump to the next step
end,
% Now check all numbers from Step*(FoundUpper-1) .. Step*FoundUpper
% The target must be in that interval.
Fib = Step*(FoundUpper-1),
FibLen := fib_len(Fib),
while(FibLen < Target, Fib <= Step*FoundUpper)
FibLen := fib_len(Fib),
Fib := Fib + 1
end,
writeln([fib=Fib,fibLen=FibLen]),
nl.
% ~28s!
% (to_string() is not very fast in Picat)
euler25b =>
F1 = 1,
F2 = 1,
Len = 1,
Ix = 2,
while (Len < 1000)
Tmp = F1,
F1 := F2,
F2 := Tmp + F1,
Len := F2.to_string().length,
Ix := Ix + 1
end,
writeln([Ix,F2,Len]),
nl.
% ~31s!
euler25c =>
I = 1,
Len = 0,
while (Len < 1000)
Fib := fib(I),
Len := Fib.to_string().length,
% Len := nlen(Fib),
I := I + 1
end,
writeln([I,Len]).
% using int_len instead: 1min 47s
euler25d =>
F1 = 1,
F2 = 1,
Len = 1,
Ix = 2,
while (Len < 1000)
Tmp = F1,
F1 := F2,
F2 := Tmp + F1,
Len := int_len(F2),
% Len := nlen(F2), % crashes for Ix=1476 (len ~ 309)
if Ix mod 100 == 0 then
writeln([i=Ix,len=Len])
end,
Ix := Ix + 1
end,
writeln([Ix,F2,Len]),
nl.
table
fib_len(I) = fib(I).to_string().length().
table
fib(0)=1.
fib(1)=1.
fib(N)=F,N>1 => F=fib(N-1)+fib(N-2).
% Dumps core after I=1475 (length 309)
nlen(N) = floor(log10(N))+1.
% table
int_len(V) = Len =>
Len1=1,
while (V > 9)
Len1 := Len1 + 1,
V := V div 10
end,
Len = Len1.