20
\$\begingroup\$

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 , so the shortest answer in each language wins.

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

21 Answers 21

8
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ You used the same trick as mine. :) \$\endgroup\$ – Erik the Outgolfer Jul 28 '17 at 8:22
  • \$\begingroup\$ @EriktheOutgolfer As yours? \$\endgroup\$ – Dennis Jul 28 '17 at 15:32
  • \$\begingroup\$ Didn't post it, but generally I didn't use D either... \$\endgroup\$ – Erik the Outgolfer Jul 28 '17 at 15:33
4
\$\begingroup\$

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!

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

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.

\$\endgroup\$
  • \$\begingroup\$ Assuming you can return a Pair object, you can use the :p adverb instead of :kv. \$\endgroup\$ – Brad Gilbert b2gills Jul 28 '17 at 2:14
3
\$\begingroup\$

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.

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

Jelly, 15 bytes

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

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ 43 seconds too late \$\endgroup\$ – Noah Cristino Jul 27 '17 at 20:53
2
\$\begingroup\$

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

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

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

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!

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

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!

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

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!

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

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

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

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')
\$\endgroup\$
  • 1
    \$\begingroup\$ 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') \$\endgroup\$ – Stephen Jul 27 '17 at 22:24
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – Neil Jul 28 '17 at 8:32
  • \$\begingroup\$ @Neil woops my bad \$\endgroup\$ – Stephen Jul 28 '17 at 12:54
1
\$\begingroup\$

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.

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

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!

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

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.

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

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
\$\endgroup\$
  • \$\begingroup\$ 14 bytes: _ŬøU}a@[XMgX]. Using s1 q to get last item, which allows dropping the <space>s \$\endgroup\$ – Justin Mariner Jul 29 '17 at 21:21
  • \$\begingroup\$ @JustinMariner That's... that's genius :-) \$\endgroup\$ – ETHproductions Jul 29 '17 at 23:09
0
\$\begingroup\$

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

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

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!

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

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!

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

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!

\$\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.