[Question]
  [
# 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](/questions/tagged/code-golf "show questions tagged '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](https://codegolf.stackexchange.com/questions/80379/print-the-nth-prime-that-contains-n))
  
[Answer]
# [Haskell](https://www.haskell.org/), ~~85~~ 84 bytes
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
m=show<$>l
f n|x<-m!!n=[y|y<-x:m,or[x<=s|s<-scanr(:)""y,x++":">s]]!!n
```
[Try it online!](https://tio.run/##FctBDoMgEADAu69A4kGjGG1vBPyI8UAUo@myNqyNkPh32t5nNkMvC5Cc2VHveFpv5rP4IOxoqXXmXa6tt2ap2uvwCyXQnaTZIJR11UPmNG3HpYoBspXhHZRweY56jHdUIkjXHH4MStNNSvybL2XFeWxCXXPJB5qmH0@pZw/2ZH33BQ "Haskell – Try It Online")
# How it works
* `l` is the infinite list of Fibonacci numbers, defined recursively as the partial sums of `0:1:l`. It starts with `0` because lists are 0-indexed. `m` is the same list converted to strings.
* In `f`:
	+ `n` is the input number, and `x` is the (string of the) `n`th Fibonacci number.
	+ In the outer list comprehension, `y` is a Fibonacci number tested for whether it contains `x` as a substring. The passing `y`s are collected in the list and indexed with the final `!!n` to give the output. An extra `x` is prepended to the tests to save two bytes over using `!!(n-1)` at the end.
	+ To avoid counting `y`s several times, the tests of each `y` are wrapped in `or` and another list comprehension.
	+ In the inner list comprehension, `s` iterates through the suffixes of `y`.
	+ To test whether `x` is a prefix of `s`, we check whether `x<=s` and `x++":">s`. (`":"` is somewhat arbitrary but needs to be larger than any numeral.)
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~15~~ 14 bytes
1 byte thanks to Jonathan Allan.
```
0µ³,ÆḞẇ/µ³#ÆḞṪ
```
[Try it online!](https://tio.run/##y0rNyan8/9/g0NZDm3UOtz3cMe/hrnZ9EE8Zwtu56v///8YA "Jelly – Try It Online")
[Answer]
# [Python 2](https://docs.python.org/2/), 99 86 bytes
* [Ørjan Johansen](https://codegolf.stackexchange.com/users/66041/%c3%98rjan-johansen) Saved 7 bytes: starting with `b=i=x=-1 a=1` and dropping the `x and`
* [Ørjan Johansen](https://codegolf.stackexchange.com/users/66041/%c3%98rjan-johansen) again saved 3 bytes: `f and n==2` to `f*(n>2)`
* [Felipe Nardi Batista](https://codegolf.stackexchange.com/users/66418/felipe-nardi-batista) saved 9 bytes: economic swap `a,b=a+b,a` shorthand `f-=str(x)in str(a)`, squeezed `(n<2)*f`
* [ovs](https://codegolf.stackexchange.com/users/64121/ovs)  saved 13 bytes: transition from python 3 to python 2.
```
f=n=input()
b=i=x=-1
a=1
while(n>2)*f:i+=1;a,b=a+b,a;x=[x,a][i==n];f-=`x`in`a`
print a
```
[Try it online!](https://tio.run/##BcFNCoAgEAbQvado2Y9Btky@LiKBIyQNxCRhZKe399KXj0vmWiMELOnJbacCGAWjUQSj3oPPvZV17vq48ABjSQfQEDTZAlc0bY4B2Wwc4Ytn8eRVullyQ7Wa6Qc "Python 2 – Try It Online")
Explanation:
```
f=n=int(input())                 # f is number of required numbers
b=i=x=-1                         # i is index(counter) set at -1
                                 # In Two-sided fibonacci, fib(-1) is 1 
                                 # and b(fib before it) i.e. fib(-2) is -1
                                 # Taking advantage of all -1 values, x is 
                                 # also set to -1 so that the `if str(...`
                                 # portion does not execute until x is set a 
                                 # value(i.e. the nth fibonacci) since there 
                                 # is no way -1 will be found in the number 
                                 # (ALL HAIL to Orjan's Genius Idea of using 
                                 # two-sided fibonacci)      
a=1                              # fib(-1) is 1
while(n>2)*f:                    # no need to perform this loop for n=1 and 
                                 # n=2 and must stop when f is 0
 i+=1                            # increment counter
 b,a=a,a+b                       # this might be very familiar (fibonacci 
                                 # thing ;))                         
 x=[x,a][i==n]                   # If we have found (`i==n`) the nth 
                                 # fibonacci set x to it
 f-=`x`in`a`                     # the number with required substring is 
                                 # found, decrease value of f
print a                          # print required value
```
# [Python 3](https://docs.python.org/3/), 126 120 113 112 110 101 99 bytes
```
f=n=int(input())
b=i=x=-1
a=1
while(n>2)*f:i+=1;a,b=a+b,a;x=[x,a][i==n];f-=str(x)in str(a)
print(a)
```
[Try it online!](https://tio.run/##FcwxCsMwDAXQ3afIaCXOoHaL@b1IyCBDTQRBNalL3dO7ZHvTK7@6v@zee4ZBrXq18qmeyCUoGmZ2AnbfXY@nt8eNxrzoBI4SEmRKQWLD2oJsqwK2xTzjXU/fSG24IOTKecVCvTP/AQ "Python 3 – Try It Online")
[Answer]
# Java, ~~118~~ 111 bytes
```
i->{long n=i,p=0,q,c=1;for(;--n>0;p=c,c+=q)q=p;for(n=c;i>0;q=p,p=c,c+=q)if((""+c).contains(""+n))--i;return p;}
```
I keep thinking it should be possible not to duplicate the Fibonacci bit, but all my efforts somehow result in more bytes.
Thanks to Kevin for improvements... guess it shows this was my first attempt at golfing :)
[Answer]
# [Perl 6](http://perl6.org/), 45 bytes
```
{my@f=0,1,*+*...*;@f.grep(/$(@f[$_])/)[$_-1]}
```
`$_` is the argument to the function; `@f` is the Fibonacci sequence, lazily generated.
[Answer]
# JavaScript (ES6), ~~96~~ ~~93~~ ~~92~~ ~~90~~ 86 bytes
0-indexed, with the 0th number in the sequence being `1`. Craps out at `14`.
```
f=(n,x=1,y=1)=>n?f(n-1,y,x+y):x+""
g=(n,x=y=0)=>x>n?f(y-1):g(n,x+!!f(y++).match(f(n)))
```
* ~~2~~ 6 bytes saved thanks to [Arnauld](https://codegolf.stackexchange.com/users/58563/arnauld)
---
## Try it
```
f=(n,x=1,y=1)=>n?f(n-1,y,x+y):x+""
g=(n,x=y=0)=>x>n?f(y-1):g(n,x+!!f(y++).match(f(n)))
oninput=_=>o.innerText=(v=+i.value)<14?`f(${v}) = ${f(v)}\ng(${v}) = `+g(v):"Does not compute!"
o.innerText=`f(0) = ${f(i.value=0)}\ng(0) = `+g(0)
```
```
<input id=i min=0 type=number><pre id=o>
```
---
## Explanation
Updated version to follow, when I get a minute.
```
f=...                   :Just the standard, recursive JS function for generating the nth Fibonacci number
g=(...)=>               :Recursive function with the following parameters.
n                       :  The input integer.
x=0                     :  Used to count the number of matches we've found.
y=0                     :  Incremented on each pass and used to generate the yth Fibonacci number.
x>n?                    :If the count of matches is greater than the input then
f(y-1)                  :    Output the y-1th Fibonacci number.
:                       :Else
g(...)                  :    Call the function again, with the following arguments.
n                       :      The input integer.
x+                      :      The total number of matches so far incremented by the result of...
RegExp(f(n)).test(f(y)) :        A RegEx test checking if the yth Fibonacci number, cast to a string, contains the nth Fibonacci number.
                        :        (returns true or false which are cast to 1 and 0 by the addition operator)
y+1                     :      The loop counter incremented by 1
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 65 bytes
```
ＡＩθνＡνφＡ±¹βＡβιＡβξＡ¹αＷ∧›ν²φ«Ａ⁺ι¹ιＡ⁺αβχＡαβＡχαＡ⎇⁼ιναξξＡ⁻φ›№ＩαＩξ⁰φ»Ｉα
```
[Try it online!](https://tio.run/##VZDNCoMwEITvPsUeNzRC7VUQRHotPfQF1tSfgESaaGspffY0aYTonnY@htlhRU9ajDRYWxojO4UVmQkfjINiebIyxaGN6tJ0NDWYOU8dac1B7tQSVcaBnHr1cmgAS3XHwmeemM9l8EnAzeo9oOTgs33ajpO/x0HsOYUWGyLCtQ25NVqRfuP5MdNg/AHlgsh3DD033hRbDgVW46ym8Axypv@yMLcdGQvf@CZXLaOH5dZmmU2fNjXDDw "Charcoal – Try It Online") Link to verbose code for explanation.
[Answer]
# [PHP](https://php.net/), 96 bytes
```
for($f=[0,1];$s<$a=$argn;$s+=$f[$a]&&strstr($f[$i],"$f[$a]")?:0)$f[]=$f[$i]+$f[++$i];echo$f[$i];
```
[Try it online!](https://tio.run/##JYmxCsMgFEX3fIY8gmIKZq2RDCVDl3bpFiSImJhF5SVz/7qztRUu3HPPTT7lYUw@NQ4x4oIuRTz3sNH3tDyer/ttYrIBg1tQpBdE5jUihVXNouu1hGMAo/53Ya5gncHotj1OLKG/ueuOVE3YeBWssFb14KU4LyCd9bE6mfMnxIs11rsv "PHP – Try It Online")
[Answer]
# 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
> 
> 
> 
[Answer]
# 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: 
Read 1 item
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: 
Read 1 item
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: 
Read 1 item
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: 
Read 1 item
Big Integer ('bigz') :
[1] 1387277127804783827114186103186246392258450358171783690079918032136025225954602593712568353
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 11 bytes
```
1,ÆḞw/ɗ#ÆḞṪ
```
[Try it online!](https://tio.run/##y0rNyan8/99Q53Dbwx3zyvVPTlcGsx7uXPX//38TAA "Jelly – Try It Online")
Heartbroken. [This](https://tio.run/##y0rNyan8//9w28Md88oPLVUGMx417nq4c9X///9NAA) 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
```
[Answer]
# [Husk](https://github.com/barbuz/Husk), ~~15~~ 13 bytes
```
!fȯ€d!¹İfQdİf
```
[Try it online!](https://tio.run/##yygtzv7/XzHtxPpHTWtSFA/tPLIhLTAFSPz//98cAA "Husk – 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
```
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~11~~ 9 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
µNÅfDIÅfå
```
-2 bytes thanks to *@ovs*.
[Try it online](https://tio.run/##yy9OTMpM/f//0Fa/w61pLp5A4vDS//@NAQ) or [verify the first 10 test cases](https://tio.run/##yy9OTMpM/R/i6mevpPCobZKCkr2fS@j/Q1v9DremuUQAicNL/9fq6B3a@h8A).
**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)
```
[Answer]
## 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`.
[Answer]
# 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";}
```
[Answer]
# [NewStack](https://github.com/LyamBoylan/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 `f`th Fibonacci number `[2,21,233...]`
`Ṗf⁻`: Print the `f-1`th element (-1 due to 0-based indexing) `233`
[Answer]
# [Japt](https://github.com/ETHproductions/japt/), ~~16~~ ~~15~~ 12 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
Would be 11 bytes but for a bug in Japt.
```
@µX¦skN}f!gM
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QLVYpnNrTn1mIWdN&input=OA)
]