22
0
Challenge
You must write a program that takes a positive integer n
as input, and outputs the n
th Fibonacci number (shortened as Fib# throughout) that contains the n
th Fib# as a subtring. For the purposes of this challenge, the Fibonacci sequence begins with a 1
.
Here are some examples that you can use as test cases, or as examples to clarify the challenge (for the latter, please leave a comment down below explaining what you find unclear).
n=1
Fib#s: 1
^1 1st Fib# that contains a 1 (1st Fib#)
Output: 1
n=2
Fib#s: 1, 1
^1 ^2 2nd Fib# that contains a 1 (2nd Fib#)
Output: 1
n=3
Fib#s: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
^1 ^2 ^3 3rd Fib# that contains a 2 (3rd Fib#)
Output: 233
n=4
Output: 233
n=5
Output: 6765
n=6
Output: 28657
n=7
Output: 1304969544928657
n=8
Output: 14472334024676221
n=9
Output: 23416728348467685
n=10
Fib#s: 1, ..., 34, 55, 89, ..., 63245986, 102334155, 165580141, ..., 2880067194370816120, 4660046610375530309
^1 ^2 ^3 ^10 10th Fib# that contains a 55 (10th Fib#)
Output: 4660046610375530309
As always, this is code-golf, so go for the lowest byte count possible.
If something is confusing/unclear, please leave a comment.
(This challenge is based off another challenge I posted: Print the nth prime that contains n)
3I recommend including the
n=5
testcase, because I just made a silly error where I wrote a check which counted a number several times if it had the substring more than once.n=5
would catch that because of the55
. – Ørjan Johansen – 2017-06-15T03:11:50.040What are the constraints of n? – officialaimm – 2017-06-15T05:02:19.020
2@officialaimm I don't think it's reasonable to expect very high numbers. My solution works on TIO up to
n=25
(the output has 1186 digits), then gets killed forn=26
(3085 digits compiled on my own laptop). There seems to be a jump in difficulty wheneverfib(n)
gets one more digit (as one would expect). The next jump, 31, has 12990 digits in the final output. – Ørjan Johansen – 2017-06-15T05:52:13.1601Yes. Lol! my python solution gets stuck for n>6 because there is a recursive function which is called many times in a loop. :D – officialaimm – 2017-06-15T05:57:01.593
1@officialaimm Oh right, exponential blowup is a problem when defining Fibonacci directly with recursion. Even without that you might hit Python's recursion limit rather soon. – Ørjan Johansen – 2017-06-15T06:05:18.283
Can we consider
0
to be a Fibonacci number for the purposes of this challenge? Can we use 0-indexing? Can you add test cases for 4-9? – Shaggy – 2017-06-15T09:18:11.163@Shaggy: The standard convention these days is to consider 0 as the 0th Fibonacci number. This is consistent with the examples in the question. – ShreevatsaR – 2017-06-15T12:41:09.827
@ShreevatsaR, the test cases appear to be using 1-indexing with
1
as the first number in the sequence. – Shaggy – 2017-06-15T13:00:06.2871@Shaggy: That's what I meant by consistent: when 0 is the 0th Fibonacci number, then 1 is the first ("1th"?) Fibonacci number. – ShreevatsaR – 2017-06-15T13:07:16.143
I tried this in Taxi and got TIO to print the nth Fibonacci number with this program but is only accurate up to the 48th Fibonacci number and I have no idea why. This was going to be phase 1 in a ridiculously complicated Taxi solution but not if I can't figure out the problem first.
– Engineer Toast – 2017-06-15T17:43:57.040@Shaggy I have added test cases 4 through 9. Since you're just using them as test cases, and not challenge clarification, I only put the required output. I hope that's OK. – ericw31415 – 2017-06-15T20:56:45.763
@officialaimm You could always just use the formula if you don't want to do it recursively. That might take more bytes though. – ericw31415 – 2017-06-15T21:00:03.900
Yes. I have already posted iterative solution for python. Check it out! – officialaimm – 2017-06-15T21:37:43.597
1@officialaimm Yeah, I saw it. I meant that there's an equation to find the
n
th term. It's faster, but takes more bytes. – ericw31415 – 2017-06-15T22:25:18.793@EngineerToast That's just about the right size to break if your ints are 32 bits.
fib(48)==4807526976
,2^32==4294967296
. – Ørjan Johansen – 2017-06-15T23:46:13.583@ØrjanJohansen That makes a lot of sense, thanks. I don't know if it's Taxi or TIO with that limitation. Ah, well. – Engineer Toast – 2017-06-16T12:20:32.897