Problem 104

[MaJJ]

Given that Fk is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.

How to interpret it? I can think of at least three ways:

1. Find k for which (isPandigital(First9Digits(Fib(k))) && isPandigital(Last9Digits(Fib(k)))) == true.
That's how I understood the problem at first. I'm unable to do it by bruteforce, it's probably HUGE number and has to be determined by some math tricks.

2. Find k for which isPandigital(First9Digits(Fib(k)) * 10⁹ + Last9Digits(Fib(k))) == true.
This procedure would turn number of any length to number that had only first 9 and last 9 digits of the former. k is then 175 (and Fib(k) = 167244575 9041379840132227567 949787325). The answer form says this is wrong.

3. Find k for which isPandigital(First9Digits(Fib(k)) & Last9Digits(Fib(k))) == true.
This interprets the AND in the problem statement as bitwise AND. k is then 4633, Fib(k) is 776698159...(950 more digits)...138529553, and 776698159 & 138529553 = 138496257, which is pandigital. The answer form says this is also wrong.

Sooo ... how should I understand the question?

[TripleM]

Your first interpretation is correct.

[MaJJ]

Damn, I hoped not to hear that Well, let's study Fibonacci numbers...

[denshade]

What order of magnitude is this number k?
I just would like to know if it is worth waiting for my algorithm or not...

[jaap]

It has 6 digits.

[SoboLAN]

I used your first interpretation too. I started the program and, after about 30 minutes it reached k = 100 thousand. The result was still not found.

I just have no idea how to solve this in another way. Maybe I should just let it run for 2 hours or so and get the result.

EDIT: I did it in 115 seconds. However, I don't understand the (fast and genious) solutions posted on the problem's thread. Those people just explain what solution they used, not WHY that solution WORKS. Don't just assume everyone understands those things...

[whakamaru]

I wonder why PE didn't set the question to find all ten digits? That is what I was looking for, until... I read the question again! I think the first f(n) with the last TEN digits pan, is around the 11,000 mark.

[pimspelier]

Could someone confirm these values:
for the last 9 digits, these are pandigital:
F_996271,F_997031,F_998987

for the first 9 digits:
F_992229,F_994961,F_997942

As first values I do get 541 and 2749, but I'm worried it's not exact enough... Also, is it true that

It has six digits

, because my first value is around 4.5 million

[dawghaus4]

It is true that the answer is 6 digits long.

If I understand you correctly, only one of your "last" values is correct. The last 9 digits of F₉₉₆₂₇₁ are 1-9 pandigital. All of your ""first values are correct.

There are two Fibonacci numbers with 7-digit indices that have the desired properties, but both indices are greater than 6,000,000. The fourth such number has an index of almost 17,000,000.

On edit: Corrected serious misstatement in second paragraph. See two posts down.

[pimspelier]

Thanks!
EDIT: I've checked again, and are the rest of the values (for first and last digits) off by one?
EDIT: The values of k when the last 9 digits are pandigital, were off by one when k was even... stupid mistake, one i++ was where it shouldn't be.

[dawghaus4]

I agree that the last digits of F₉₉₇₀₃₂ and F₉₉₈₉₈₈ are 1-9 pandigital.

I must also confess a stupid error that resulted from my asking my program to do something it wasn't designed to do.

Your three Fibonacci number candidates that for the first 9 digits to be 1-9 pandigital are in fact just that. I hope that I haven't caused you much delay or undue work. I'm surprised no one jumped in to correct my mistake. Perhaps, like my program, their programs are designed to do that.

(My error, the program didn't correctly calculate the first 9 digits until the last 9 digits were pandigital. I just went back and isolated that part of the code to confirm your original claim.)

I reverified my statements about the first 4 numbers that are 1-9 pandigital at the beginning and end. The program is design to do that.

Again, my apologies.

[RishadanPort]

How long is this solution suppose to take to solve?

I have the correct solution, and I am using correct operations on C# BigIntegers -- but takes looooooong time.

[RishadanPort]

hm oh well I solved it in 233 seconds

[dawghaus4]

My program solves the problem in 0.048722 seconds (2.6 GHz Intel core I7). It doesn't use big integers.