**Observation #1**To find numbers where the low 9 digits are pandigital, we don't really have to consider the whole numbers, but only their lowest 9 digits. The higher digits don't affect the low ones in addition, so once can generate the 9 lowest digits of the Fibonacci numbers easily. These are trivially checked for being pandigital, so it's simple to generate "candidates" for the answer. This way I quickly find out the s for which has pandigital low digits.

**Observation #2**Once we have the indices of candidates, we can directly find the numbers by using the following cool formula for Fibonacci numbers: As you can see, the runtime of such a computation is logarithmic, and with some simple caching it's a very efficient algorithm for generating the th Fibonacci number. So I could just test my candidates for upper-digit pandigital this way, and the problem was solved in about a minute of runtime.

**Observation #3**I'm pretty sure this can be done even more efficiently, using the golden ratio: Since we only need the upper 9 digits, using the golden ratio with sufficient accuracy, the Fibonacci numbers can be approximated enough to see the exact upper 9 digits. I'm sure this method is much faster than the one I've used.