22
\$\begingroup\$

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.

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)

\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Ørjan Johansen Jun 15 '17 at 3:11
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – Ørjan Johansen Jun 15 '17 at 5:52
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – officialaimm Jun 15 '17 at 5:57
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Ørjan Johansen Jun 15 '17 at 6:05
  • 1
    \$\begingroup\$ @Shaggy: That's what I meant by consistent: when 0 is the 0th Fibonacci number, then 1 is the first ("1th"?) Fibonacci number. \$\endgroup\$ – ShreevatsaR Jun 15 '17 at 13:07

14 Answers 14

12
\$\begingroup\$

Haskell, 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!

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) nth Fibonacci number.
    • In the outer list comprehension, y is a Fibonacci number tested for whether it contains x as a substring. The passing ys 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 ys 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.)
\$\endgroup\$
  • 1
    \$\begingroup\$ l=0:scanl(+)1l saves a byte. \$\endgroup\$ – Laikoni Jun 15 '17 at 6:54
10
\$\begingroup\$

Jelly, 15 14 bytes

1 byte thanks to Jonathan Allan.

0µ³,ÆḞẇ/µ³#ÆḞṪ

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Python 2, 99 86 bytes

  • Ørjan Johansen Saved 7 bytes: starting with b=i=x=-1 a=1 and dropping the x and
  • Ørjan Johansen again saved 3 bytes: f and n==2 to f*(n>2)
  • 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 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!

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, 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!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can get rid of 7 more bytes by starting with b=i=x=-1 a=1 and dropping the x and . (Essentially starting 3 steps earlier in the two-sided Fibonacci sequence -1, 1, 0, 1, 1, 2, ....) \$\endgroup\$ – Ørjan Johansen Jun 15 '17 at 7:01
  • 1
    \$\begingroup\$ You left a space at the end of -1 :P \$\endgroup\$ – Ørjan Johansen Jun 15 '17 at 7:16
  • 1
    \$\begingroup\$ Erm blush. Also, I want to get rid of ` and n>2` but it seems n==2 really needs special treatment. But it can be shortened to *(n>2). \$\endgroup\$ – Ørjan Johansen Jun 15 '17 at 8:12
  • 1
    \$\begingroup\$ golfed it down to 88 bytes, some changes are exclusive to python 2. but the rest will work in python 3 as well \$\endgroup\$ – Felipe Nardi Batista Jun 15 '17 at 11:07
  • 1
    \$\begingroup\$ for python 3, you can still golf 9 bytes: here \$\endgroup\$ – Felipe Nardi Batista Jun 15 '17 at 11:24
4
\$\begingroup\$

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 :)

\$\endgroup\$
  • 2
    \$\begingroup\$ Snippets are not allowed. You should turn this into a lambda like so: i->{long n=i,p=0,q,c=1;while(--n>0){q=p;p=c;c+=q;}n=c;while(i>0){if((""+c).contains(""+n))--i;q=p;p=c;c+=q;}return p;} (118 bytes) \$\endgroup\$ – Okx Jun 15 '17 at 9:40
  • 1
    \$\begingroup\$ Welcome to PPCG! After you've changed it to a lambda as @Okx pointed out, I must say it's an impressive answer. I tried to do this challenge about an hour ago just before lunch, and gave up. So +1 from me. Some small things to golf: while(--n>0){q=p;p=c;c+=q;} can be for(;--n>0;p=c,c+=q)q=p; and n=c;while(i>0){if((""+c).contains(""+n))--i;q=p;p=c;c+=q;} can be for(n=c;i>0;q=p,p=c,c+=q)if((""+c).contains(""+n))--i;. (In total: 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;} (111 bytes) \$\endgroup\$ – Kevin Cruijssen Jun 15 '17 at 11:02
2
\$\begingroup\$

Perl 6, 45 bytes

{my@f=0,1,*+*...*;@f.grep(/$(@f[$_])/)[$_-1]}

$_ is the argument to the function; @f is the Fibonacci sequence, lazily generated.

\$\endgroup\$
2
\$\begingroup\$

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

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
\$\endgroup\$
  • \$\begingroup\$ Your answer seems to provide different output from the examples. \$\endgroup\$ – ericw31415 Jun 15 '17 at 22:33
  • \$\begingroup\$ @ericw31415, that's because it's 0-indexed. \$\endgroup\$ – Shaggy Jun 15 '17 at 22:48
  • \$\begingroup\$ I wrote specifically wrote this though: "For the purposes of this challenge, the Fibonacci sequence begins with a 1." \$\endgroup\$ – ericw31415 Jun 16 '17 at 0:25
  • \$\begingroup\$ @ericw31415: And my sequence does begin with 1, it's just 0-indexed; the 0th and 1st numbers in the sequence are 1, the 2nd is 2, the 3rd is 3, the 4th is 5, the 5th is 8, and so on, and so forth. \$\endgroup\$ – Shaggy Jun 16 '17 at 8:07
2
\$\begingroup\$

Charcoal, 65 bytes

AIθνAνφA±¹βAβιAβξA¹αW∧›ν²φ«A⁺ι¹ιA⁺αβχAαβAχαA⎇⁼ιναξξA⁻φ›№IαIξ⁰φ»Iα

Try it online! Link to verbose code for explanation.

\$\endgroup\$
1
\$\begingroup\$

PHP, 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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ 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])& \$\endgroup\$ – JungHwan Min Jun 15 '17 at 3:29
  • \$\begingroup\$ Just a heads up, declaring global variables separately is completely fine. My bad. \$\endgroup\$ – JungHwan Min Jun 15 '17 at 15:15
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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";}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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..) \$\endgroup\$ – Dada Jun 19 '17 at 9:53
0
\$\begingroup\$

NewStack, 14 bytes

N∞ ḟᵢfi 'fif Ṗf⁻

The breakdown:

N∞              Add all natural numbers to the stack
   ḟᵢ           Define new function will value of input
     fi          Get the n'th Fibonacci number for ever element n
       'fif      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...]

'fif: 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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Ørjan Johansen Jun 27 '17 at 0:11
  • \$\begingroup\$ @ØrjanJohansen, Ahah thanks for reminding me. I forgot to upload that! It'll be up in a minute. \$\endgroup\$ – Graviton Jun 27 '17 at 4:48
  • \$\begingroup\$ 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. \$\endgroup\$ – Ørjan Johansen Jun 27 '17 at 7:10
  • \$\begingroup\$ @ØrjanJohansen Touché, I'm in the works of distributing a table for it's own encoding as we speak. \$\endgroup\$ – Graviton Jun 27 '17 at 21:50
0
\$\begingroup\$

Japt, 16 15 bytes

_søNg)«´U}a@MgX

Try it

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.