# Challenge

You must write a program that takes a positive integer n as input, and outputs the nth Fibonacci number (shortened as Fib# throughout) that contains the nth 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 , so go for the lowest byte count possible.

(This challenge is based off another challenge I posted: Print the nth prime that contains n)

• I 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 the 55. – Ørjan Johansen Jun 15 '17 at 3:11
• @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 for n=26 (3085 digits compiled on my own laptop). There seems to be a jump in difficulty whenever fib(n) gets one more digit (as one would expect). The next jump, 31, has 12990 digits in the final output. – Ørjan Johansen Jun 15 '17 at 5:52
• Yes. 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 Jun 15 '17 at 5:57
• @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 Jun 15 '17 at 6:05
• @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 Jun 15 '17 at 12:41

EDIT:

• -1 byte: Laikoni shortened l.
• Typo (x>=s for x<=s) in explanation.

f takes an Int and returns a String.

l=0:scanl(+)1l

Try it online!

# Mathematica, 85 bytes

(i=ToString;f=Fibonacci;For[n=t=0,t<#,If[i@f@n++~StringContainsQ~i@f@#,t++]];f[n-1])&

input

[10]

-4 bytes from @JungHwan Min

output

4660046610375530309

• Looks weird but f@i@n++ is totally valid, decreasing 1 byte. Using For instead of While reduces 3 bytes. 85 bytes: (i=ToString;f=Fibonacci;For[n=t=0,t<#,If[i@f@n++~StringContainsQ~i@f@#,t++]];f[n-1])& – JungHwan Min Jun 15 '17 at 3:29
• Just a heads up, declaring global variables separately is completely fine. My bad. – JungHwan Min Jun 15 '17 at 15:15

# R, 77 72 bytes

F=gmp::fibnum;i=0;d=n=scan();while(n)if(grepl(F(d),F(i<-i+1)))n=n-1;F(i)

This makes use of the gmp library for the Fibonacci number. Fairly straight foward implementation of the question.

F=gmp::fibnum;          # Alias Fibonacci function to F
i=0;                    # intitalise counter
d=n=scan();             # get n assign to d as well
while(n)               # loop while n
if(grepl(F(d),F(i<-i+1)))  # use grepl to determine if Fib of input is in Fib# and increment i
n=n-1;             # decrement n
F(i)                  # output result

Some tests

> F=gmp::fibnum;i=0;d=n=scan();while(n)if(grepl(F(d),F(i<-i+1)))n=n-1;F(i)
1: 2
2:
Big Integer ('bigz') :
[1] 1
> F=gmp::fibnum;i=0;d=n=scan();while(n)if(grepl(F(d),F(i<-i+1)))n=n-1;F(i)
1: 3
2:
Big Integer ('bigz') :
[1] 233
> F=gmp::fibnum;i=0;d=n=scan();while(n)if(grepl(F(d),F(i<-i+1)))n=n-1;F(i)
1: 10
2:
Big Integer ('bigz') :
[1] 4660046610375530309
> F=gmp::fibnum;i=0;d=n=scan();while(n)if(grepl(F(d),F(i<-i+1)))n=n-1;F(i)
1: 15
2:
Big Integer ('bigz') :
[1] 1387277127804783827114186103186246392258450358171783690079918032136025225954602593712568353

# Jelly, 11 bytes

1,ÆḞw/ɗ#ÆḞṪ

Try it online!

Heartbroken. This is a 9 byte version that unfortunately fails for $$\n = 2\$$ which otherwise, I'm really proud of due to the weird chain rules and the byte saves.

## How they work

1,ÆḞw/ɗ#ÆḞṪ - Main link. Takes n on the left
ɗ     - Group the previous three links into a dyad f(k, n):
,          -   Pair; [k, n]
ÆḞ        -   n'th Fib; [fib(k), fib(n)]
/      -   Run the previous dyad over the list
with fib(k) on the left and fib(n) on the right:
w       -     Index of fib(n) in fib(k)'s digits or 0

1      #    - Count up k = 1, 2, 3, ..., until n integers return
true for f(k, n) and return those k
ÆḞ  - n'th Fib for each
Ṫ - Return the last value

And the version that fails for $$\n = 2\$$:

ÆḞw¥#ÆḞ⁺Ṫ - Main link. Takes n on the left
ÆḞ   - Yield the n'th Fibonacci number, x
¥      - Group the previous 2 links together as a dyad f(k, x):
ÆḞ        -   k'th Fibonacci number
w       -   Index of x in fib(k)'s digits else 0
#     - Count up k = n, n+1, n+2, ... until n integers return true
for f(k, x) and return those k
⁺  - Redo the previous link (ÆḞ), yielding the k'th Fibonacci
number for each k returned by #
Ṫ - Take the last k
• Somehow a bug prevents both japt and jelly from having really short answers here. – Razetime Nov 12 '20 at 2:23

# Husk, 15 13 bytes

!fȯ€d!¹İfQdİf

Try it online!

!⁰fȯ€od!⁰İfQdİf
!⁰                  # get the input-th element of
f          İf     # fibonacci numbers that satisfy:
ȯ€      Qd       # one of the subsets of their digits is
od             # the digits of
!⁰           # the input-th element of
İf         # the fibonacci series

# 05AB1E, 11 9 bytes

µNÅfDIÅfå

-2 bytes thanks to @ovs.

Explanation:

µ          # Loop until the counter_variable is equal to the (implicit) input:
# (the counter_variable is 0 by default)
N         #  Push the loop index
Åf       #  Pop and push the index'th Fibonacci number
D      #  Duplicate it
IÅf   #  Get the input'th Fibonacci number
å  #  Check that the index'th Fibonacci nr contains the input'th Fibonacci nr
#  (if this is truthy, implicitly increase the counter_variable by 1)
# (after the loop, the top of the stack - the last index'th Fibonacci number
#  we've duplicated - is output implicitly as result)
• You don’t need to close the loop if you flood the stack with Fibonacci numbers: µNÅfDIÅfå – ovs Nov 11 '20 at 19:02
• @ovs Thanks for the -2. :) – Kevin Cruijssen Nov 12 '20 at 7:41

## Clojure, 99 bytes

(def s(lazy-cat[0 1](map +(rest s)s)))#(nth(filter(fn[i](.contains(str i)(str(nth s %))))s)(dec %))

A basic solution, uses an infinite sequence of Fibonacci numbers s.

# C#, 35 bytes

int u=1,b=1;for(;b<n;){b+=u;u=b-u;}

Try it

int n=int.Parse(t2.Text);int u=1,b=1;for(;b<n;){b+=u;u=b-u;t.Text+=b.ToString()+" ";}if(b==n){t.Text+="true";}
• Welcome on Programming Puzzle and Code-Golf. Answers need to be either a full program or a function, while you only provided a snippet. In particular, you are assuming that the input is in n and you just put the output in b (I think). You could write that take n as arguments and returns b... Also, I'm pretty sure you are not computing what the challenges asks for. Actually, I have no idea what you are computing. Could you please provide use with some code that we can run to verify your solution? (your "Try it" can't be run as is..) – Dada Jun 19 '17 at 9:53

# NewStack, 14 bytes

N∞ ḟᵢﬁ 'ﬁf Ṗf⁻

## The breakdown:

N∞              Add all natural numbers to the stack
ḟᵢ           Define new function will value of input
ﬁ          Get the n'th Fibonacci number for ever element n
'ﬁf      Remove all elements that don't contain the (input)'th Fibonacci number
Ṗf⁻  Print the (input-1)'th element

In English: (with example of an input of 3)

N∞: Make a list of the natural numbers [1,2,3,4,5,6...]

ḟᵢ: Store the input in the variable f [1,2,3,4,5,6...]

: Convert the list to Fibonacci numbers [1,1,2,3,5,8...]

'ﬁf: Keep all elements that contain the fth Fibonacci number [2,21,233...]

Ṗf⁻: Print the f-1th element (-1 due to 0-based indexing) 233

• The GitHub seems to contain only a readme and a tutorial. An implementation is referred to, but it's not linked. Although PPCG now allows languages newer than the challenge, I believe we still require a publically available implementation. – Ørjan Johansen Jun 27 '17 at 0:11
• @ØrjanJohansen, Ahah thanks for reminding me. I forgot to upload that! It'll be up in a minute. – Graviton Jun 27 '17 at 4:48
• Your implementation seems to use UTF-8, in which case that's actually 28 bytes (don't mind the Haskell setting, I'm only using TIO to count bytes). Languages like Jelly etc. have their own code pages for this reason. – Ørjan Johansen Jun 27 '17 at 7:10
• @ØrjanJohansen Touché, I'm in the works of distributing a table for it's own encoding as we speak. – Graviton Jun 27 '17 at 21:50

# Japt, 1615 12 bytes

Would be 11 bytes but for a bug in Japt.

@µX¦skN}f!gM

Try it