# Within Fibonacci Numbers

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


33: 3524578


Input:

72


Output:

54: 86267571272


Input:

0


Output:

0: 0


Input:

144


Output:

12: 144


Scoring

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

• Can we choose to have 1-indexing instead? Jul 27, 2017 at 20:45
• Not a duplicate, but pretty close to this challenge.
– Lynn
Jul 27, 2017 at 20:49
• Thread over on math regarding whether Fibonacci sequence is normal or not (this question presumes it is). Jul 27, 2017 at 20:52
• Do we have to use a colon as a separator? Can we output an array/list? Jul 27, 2017 at 22:14
• Related question on math.SE about whether this has a solution for any x
Jul 28, 2017 at 7:58

# 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.

• You used the same trick as mine. :) Jul 28, 2017 at 8:22
• @EriktheOutgolfer As yours? Jul 28, 2017 at 15:32
• Didn't post it, but generally I didn't use D either... Jul 28, 2017 at 15:33

# Python 2, 56 bytes

f=lambda n,i=0,a=0,b=1:ninaand(i,a)or f(n,i+1,b,a+b)


Try it online!

# 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. • Assuming you can return a Pair object, you can use the :p adverb instead of :kv. Jul 28, 2017 at 2:14 ## 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. # Jelly, 15 bytes ³DẇÆḞ¬ 0‘Ç¿µ,ÆḞ  Try it online! • 43 seconds too late Jul 27, 2017 at 20:53 # 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 ) # Python 3, 76 bytes f=lambda n,l=[1,0]:str(n)in str(l)and(len(l)-2,l)or f(n,[l+l]+l)  # 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! # 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! # 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])&  # 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  # 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))  # JavaScript ES6, 7978 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')  • You can use eval() instead of { return} to save a byte, and you can drop the t= since you aren't using recursion: i=>eval('d=a=b=1;while(!~(a+"").indexOf(i+""){c=b;b=a+b;a=c;d++};d+": "+a') Jul 27, 2017 at 22:24 • String.prototype.indexOf automatically converts its parameter to a string, no need to do it explicitly. Also you appear to have copied @StepHen's typo (you have more (s than )s). – Neil Jul 28, 2017 at 8:32 • @Neil woops my bad Jul 28, 2017 at 12:54 # 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. # 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! ## PHP, 80 bytes <?php for($a=1,$b=$n=0;strpos($a=-$a+$b=$a+$b,"$argv")<-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. # 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  • 14 bytes: _Å¬øU}a@[XMgX]. Using s1 q  to get last item, which allows dropping the <space>s Jul 29, 2017 at 21:21 • @JustinMariner That's... that's genius :-) Jul 29, 2017 at 23:09 # PHP, 163 141 bytes <?php$x=fgets(STDIN);$b=[0,1];if($x<1)$b=;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; and $b = 1; for the start of fib sequence

Try it online!

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