/* 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.