Within Fibonacci Numbers

Question

The Challenge

Given an integer input, return the first Fibonacci number that contains the input within itself along with the index of that Fibonacci number (indexes starting at 0 or 1 - up to you, but please mention which in your answer). For example, if given the input of 12, the program would return 26: 121393 as 12 is found within the number (121393) and it is at index 26 of the Fibonacci numbers.

Examples

Given the input:

45

Your program should output:

33: 3524578

Input:

72

Output:

54: 86267571272

Input:

0

Output:

0: 0

Input:

144

Output:

12: 144

Scoring

This is code-golf, so the shortest answer in each language wins.

Answer 1

Jelly, 10 bytes

0ÆḞ©w¥1#;®

Try it online!

How it works

0ÆḞ©w¥1#;®  Main link. Argument: n

0           Set the return value to 0.
       #    Call the second link to the left with arguments k = 0, 1, 2, ... until
      1     one match has been found.
     ¥        Combine the two links to the left into a dyadich chain.
 ÆḞ             Compute the k-th Fibonacci number...
   ©              and copy it to the register.
    w           Yield 1 if n occurs inside the Fibonacci number, 0 otherwise.
         ®  Yield the value stored in the register.
        ;   Concatenate the index and the Fibonacci number.

Answer 2

Python 2, 56 bytes

f=lambda n,i=0,a=0,b=1:`n`in`a`and(i,a)or f(n,i+1,b,a+b)

Try it online!

Answer 3

Perl 6, 30 bytes

{first :kv,/$_/,(0,1,*+*...*)}

Try it online!

first is a function that returns the first element of a sequence that passes a test, and it conveniently takes a :kv adverb that tells it to return both the key (index) and the matching value.

Answer 4

Batch, 104 bytes

@set/an=x=0,y=1
:l
@call set t=%%x:%1=%%
@if "%t%"=="%x%" set/an+=1,x+=y,y=x-y&goto l
@echo %n%: %x%

Works for n=0..45 due to the limited range of Batch's integer arithmetic. Explanation: Batch doesn't have a built-in match test, but it does have an operator that can replace literal strings with other literal strings, so for example if "%s:l=%"=="%s%" is true if %s% is not empty but does not contain l. The use of call is then a trick to substitute %1 (the input) into the replacement operator, however call doesn't work on control flow statements so an intermediate temporary assignment is necessary.

Answer 5

Jelly, 15 bytes

³DẇÆḞ¬
0‘Ç¿µ,ÆḞ

Try it online!

Answer 6

Javascript ES6, 68 chars

n=>eval('for(q=x=0,y=1;!`${x}`.match(n);++q)[x,y]=[y,x+y];q+": "+x')

Test:

f=n=>eval('for(q=x=0,y=1;!`${x}`.match(n);++q)[x,y]=[y,x+y];q+": "+x')
console.log([45,72,0,144].map(f).join`
`)

Answer 7

Python 3, 76 bytes

f=lambda n,l=[1,0]:str(n)in str(l[1])and(len(l)-2,l[1])or f(n,[l[0]+l[1]]+l)

Answer 8

Emojicode, 133 bytes

🐖🔢🍇🍮a 0🍮b 1🍮i 0🔁☁️🔍🔡a 10🔡🐕10🍇🍮b➕a b🍮a➖b a🍮i➕1i🍉😀🔡i 10😀🔡a 10🍉

Try it online!

Answer 9

Dyalog APL, 39 bytes

{⍺←0⋄∨/(⍕⍵)⍷⍕x←1∧+∘÷/0,⍺/1:⍺,x⋄(1+⍺)∇⍵}

Using tail recursion. Don't attempt 72, it'll break your machine because its recalculating fibonacci all over every call.

Try it online!

Answer 10

Mathematica, 119 bytes

1-indexed

(T=ToString;If[(h=#)==0,"0:0",a=#&@@Select[k=T/@(Array[Fibonacci,9#]),StringContainsQ[#,T@h]&];Min@Position[k,a]":"a])&

Try it online!

Answer 11

Actually, 13 bytes

╗1⌠F$╜@c⌡╓i;F

Try it online!

Explanation:

╗1⌠F$╜@c⌡╓i;F
╗              save input in register 0
 1⌠F$╜@c⌡╓     smallest non-negative integer n where the following function returns truthy:
   F$            nth Fibonacci number, stringified
     ╜@c         count occurrences of input
          i;F  flatten the list, duplicate the index, and push the Fibonacci number at that index

Answer 12

R, 65 bytes

f=function(x,n=1,a=1,b=0)`if`(grepl(x,b),c(b,n-1),f(x,n+1,a+b,a))

Standard recursion to generate Fibnums, but instead of terminating based on n, terminates when b matches the regex x. This actually works surprisingly well. I assumed that using regex with numerics would require a lot of hassle converting them to strings, but that doesn't seem to be necessary :)

This also has to overshoot the recursion by 1 step, by checking on b instead of a and then substracting 1 from n. This is to make sure f(0) works properly.

This fails for most values when input exceeds 1001, because of maxint. If we replace a and b for bigints, this works for higher inputs (current testing is at x = 11451)

f=function(x,n=1,a=gmp::as.bigz(1),b=gmp::as.bigz(0))`if`(grepl(x,b),c(b,n-1),f(x,n+1,a+b,a))

Answer 13

JavaScript ES6, 79 78 75 bytes

-1 byte by Step Hen

-3 bytes by Neil

i=>eval('d=a=b=1;while(!~(a+"").indexOf(i)){c=b;b=a+b;a=c;‌​d++};d+": "+a')

Answer 14

C# (.NET Core), 99 bytes

n=>{int a=0,b=1,c,d=0;for(;b.ToString().IndexOf(n.ToString())<0;c=a,a=b,b+=c,d++);return d+": "+b;}

Try it online!

Takes input as an integer, returns a string with the output.

Answer 15

Haskell, 84 bytes

import Data.List
f=0:scanl(+)1f
g n=filter(isInfixOf(show n).show.snd)(zip[0..]f)!!0

Try it online!

Answer 16

PHP, 80 bytes

<?php for($a=1,$b=$n=0;strpos($a=-$a+$b=$a+$b,"$argv[1]")<-1;$n++);echo"$n: $a";

The script is quite straightforward, simply storing the current and next terms of the sequence in $a and $b throughout. To allow for the 0th term of 0, $a and $b are initially assigned the values for the -1th term (1) and 0th term (0) respectively.

Both values are recalculated in a single expression, which is two assignments in one; effectively:

$b = $a + $b; // The next term is the sum of the two previous terms
$a = $b - $a; // The current term is now recalculated from the next and the previous

If the input value matches the beginning of the term, the strpos() function will return 0 (which is falsey and would give a false negative), but in the Wonderphul World of PHP, although false == 0 is true and false < 0 is false, false < -1 is true! And so, using this comparison saves five bytes compared to !==false.

Answer 17

Japt, 17 14 bytes

Saved 3 bytes thanks to @JustinMariner

_ŬøU}a@[XMgX]

Try it online!

Explanation

_ŬøU}a@[XMgX]      Implicit: U = input integer
      a@            For each integer X in [0, 1, 2, ...]:
        [XMgX]        take [X, Fibonacci(X)].
_    }a             Return the first pair where
 Å                    all but the first item
  ¬                   joined on the empty string (simply returns Fibonacci(X) as a string)
   øU                 contains U.
                    Implicit: output result of last expression

Answer 18

PHP, 163 141 bytes

<?php $x=fgets(STDIN);$b=[0,1];if($x<1)$b=[0];for(;($c=count($b)-1)&&strpos($b[$c],$x)===false;){$b[]=$b[$c]+$b[$c-1];}die($c.': '.$b[$c]);?>

Try it online!

Uses $b[0] = 0; and $b[1] = 1; for the start of fib sequence

Answer 19

Perl 5, 67 + 1 (-p) = 68 bytes

@f=(0,1);push@f,$f[-1]+$f[-2]while($f[-2]!~/$_/);$_=--$#f." $f[-1]"

Try it online!

Answer 20

PHP, 93 bytes

for($a[0]=$a[1]++;!strpos(" $a[$i]","$argv[1]");$a[$i+2]=$a[$i+1]+$a[$i++]);echo"$i: $a[$i]";

Simple loop through the Fibonacci sequence. The check for our input number is done in strpos(" $a[$i]","$argv[1]"); the extra space is because strpos will return false-y if the 'needle' is found at the beginning of the string. We end if the input is found and echo out the required string.

Try it online!

Answer 21

Common Lisp, 105 bytes

(lambda(x)(do((a 0 b)(b 1(+ a b))(i 0(1+ i)))((search(#1=format()"~a"x)(#1#()"~a"a))(#1#()"~a: ~a"i a))))

Try it online!