フィボナッチ数の計算なので、順に足し合わせていくしか無いのだろうと思います。
pythonだとInt型は制限が無いので、どんどん足し合わせていきます。
その上で、頭の9桁が｛1,2,3,4,5,6,7,8,9｝で構成されているか、
また、末尾の9桁も｛1,2,3,4,5,6,7,8,9｝で構成されているか、確認していきます。
ただ、桁の大きい数字をそのまま扱うのはやっぱり大変です。
末尾の9桁については10桁目以上を切り捨ててフィボナッチ数を計算しても大丈夫なので、
まずはここから計算することを考えます。要は、
fib1,fib2 = fib2, (fib1+fib2)%1000000000
というように計算していけば、末尾9桁がPandigitalになるものは簡単に見つけられます。
その上で、頭9桁を考えるのですが、こっちは末尾を切り捨てるわけには行きません。
一緒に末尾の計算とともにちゃんとしたフィボナッチ数も計算します。そして、
fib2//(10**(int(log10(fib2))-8)
で頭9桁を切り取ってPandigitalの判定をします。
Pandigitalの判定は
{x for x in str(n)}=={"1","2","3","4","5","6","7","8","9"}
が速そうです。
2.1秒で答えがでました。
頭が「245681739」、末尾が「352786941」でした。