A080471 a(n) is the smallest Fibonacci number that is obtained by placing digits anywhere in n; a(n) = n if n is a Fibonacci number.

1, 2, 3, 34, 5, 610, 377, 8, 89, 610, 4181, 121393, 13, 144, 1597, 10946, 1597, 4181, 1597, 832040, 21, 514229, 233, 2584, 2584, 28657, 28657, 2584, 121393, 832040, 317811, 832040, 233, 34, 3524578, 46368, 377, 46368, 121393, 832040, 4181, 514229

Offset: 1

Author

Amarnath Murthy, Mar 07 2003

Keywords

• base
• nonn

Links

• Robert Israel, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A068164, A068165, A080470.

Programs

Maple

IsSubList:= proc(T, S)
  local i;
  if T = [] then return true fi;
  if S = [] then return false fi;
  i:= ListTools:-Search(T[1],S);
  if i = 0 then false else procname(T[2..-1],S[i+1..-1]) fi
end proc:
f:= proc(n) local T,S,k,v;
   T:= convert(n,base,10);
   for k from 1 do
      v:= combinat:-fibonacci(k);
      S:= convert(v,base,10);
      if IsSubList(T,S) then return v fi
   od
end proc:
map(f, [$1..100]); # Robert Israel, Mar 10 2020

Mathematica

a[n_] := Block[{p = RegularExpression[ StringJoin @@ Riffle[ ToString /@ IntegerDigits[ n], ".*"]], f, k=2}, While[! StringContainsQ[ ToString[f = Fibonacci[ k++]], p]]; f]; Array[a, 42] (* Giovanni Resta, Mar 10 2020 *)

Python

def dmo(n, t):
    if t < n: return False
    while n and t:
        if n%10 == t%10:
            n //= 10
        t //= 10
    return n == 0
def fibo(f=1, g=2):
    while True: yield f; f, g = g, f+g
def a(n):
    return next(f for f in fibo() if dmo(n, f))
print([a(n) for n in range(1, 77)]) # Michael S. Branicky, Jan 21 2023

Extensions

Corrected and extended by Ray Chandler, Oct 11 2003