Imprima el enésimo número de Fibonacci que contiene el enésimo número de Fibonacci.

22

Reto

Debe escribir un programa que tome un entero positivo ncomo entrada y genere el nnúmero th Fibonacci (acortado como Fib # en todo) que contiene el nth Fib # como subcadena. Para los propósitos de este desafío, la secuencia de Fibonacci comienza con a 1.

Aquí hay algunos ejemplos que puede usar como casos de prueba, o como ejemplos para aclarar el desafío (para este último, deje un comentario a continuación explicando lo que no está claro).

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

Como siempre, este es el , así que busque el menor recuento de bytes posible.

Si algo es confuso / poco claro, deje un comentario.

(Este desafío se basa en otro desafío que publiqué: imprima la enésima prima que contiene n )

ericw31415
fuente
3
Recomiendo incluir el caso de n=5prueba, porque acabo de cometer un error tonto donde escribí un cheque que contó un número varias veces si tenía la subcadena más de una vez. n=5atraparía eso por el 55.
Ørjan Johansen
2
@officialaimm No creo que sea razonable esperar números muy altos. Mi solución funciona en TIO hasta n=25(la salida tiene 1186 dígitos), luego se mata por n=26(3085 dígitos compilados en mi propia computadora portátil). Parece haber un salto en la dificultad cada vez que fib(n)obtiene un dígito más (como cabría esperar). El siguiente salto, 31, tiene 12990 dígitos en la salida final.
Ørjan Johansen
1
Sí. Jajaja mi solución de python se atasca para n> 6 porque hay una función recursiva que se llama muchas veces en un bucle. : D
officialaimm
1
@officialaimm Ah, claro, la explosión exponencial es un problema al definir Fibonacci directamente con recursión. Incluso sin eso, podría alcanzar el límite de recursión de Python bastante pronto.
Ørjan Johansen
1
@Shaggy: Eso es lo que quise decir con coherente: cuando 0 es el número 0 de Fibonacci, entonces 1 es el primer (¿"1º" número de Fibonacci).
ShreevatsaR

Respuestas:

12

Haskell , 85 84 bytes

EDITAR:

  • -1 byte: Laikoni acortado l.
  • Typo ( x>=sfor x<=s) en explicación.

ftoma un Inty devuelve un 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

Pruébalo en línea!

Cómo funciona

  • les la lista infinita de números de Fibonacci, definida recursivamente como las sumas parciales de 0:1:l. Comienza con 0porque las listas están indexadas en 0. mes la misma lista convertida en cadenas.
  • En f:
    • nes el número de entrada y xes la (cadena del) nnúmero de Fibonacci.
    • En la lista de comprensión externa, yes un número de Fibonacci probado para ver si contiene xuna subcadena. Los ys que pasan se recopilan en la lista y se indexan con el final !!npara dar el resultado. Se xantepone un extra a las pruebas para guardar dos bytes sobre el uso !!(n-1)al final.
    • Para evitar contar yvarias veces, yse envuelven las pruebas de cada una ory otra lista de comprensión.
    • En la comprensión de la lista interna, sitera a través de los sufijos de y.
    • Para probar si xes un prefijo de s, verificamos si x<=sy x++":">s. ( ":"es algo arbitrario pero debe ser más grande que cualquier número).
Ørjan Johansen
fuente
1
l=0:scanl(+)1lGuarda un byte.
Laikoni
4

Python 2 , 99 86 bytes

  • Ørjan Johansen Guardado 7 bytes: comenzando b=i=x=-1 a=1y soltando elx and
  • Ørjan Johansen volvió a guardar 3 bytes: f and n==2enf*(n>2)
  • Felipe Nardi Batista ahorró 9 bytes: a,b=a+b,ataquigrafía de intercambio económico f-=str(x)in str(a), exprimido(n<2)*f
  • los ovs guardaron 13 bytes: transición de python 3 a 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

Pruébalo en línea!

Explicación:

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)

Pruébalo en línea!

officialaimm
fuente
1
Puede deshacerse de 7 bytes más comenzando b=i=x=-1 a=1y soltando el x and . (Esencialmente comenzando 3 pasos antes en la secuencia de Fibonacci de dos lados -1, 1, 0, 1, 1, 2, ....)
Ørjan Johansen
1
Dejaste un espacio al final de -1: P
Ørjan Johansen
1
Erm se sonroja . Además, quiero deshacerme de `and n> 2` pero parece que n==2realmente necesita un tratamiento especial. Pero se puede acortar a *(n>2).
Ørjan Johansen
1
se redujo a 88 bytes , algunos cambios son exclusivos de python 2. pero el resto también funcionará en python 3
Felipe Nardi Batista
1
para python 3, todavía puedes jugar golf 9 bytes: aquí
Felipe Nardi Batista
4

Java, 118111 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;}

Sigo pensando que debería ser posible no duplicar el bit de Fibonacci, pero todos mis esfuerzos de alguna manera resultan en más bytes.

Gracias a Kevin por las mejoras ... supongo que muestra que este fue mi primer intento de jugar al golf :)

laszlok
fuente
2
Los fragmentos no están permitidos. Debería convertir esto en una lambda así: 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)
Okx
1
Bienvenido a PPCG! Después de haberlo cambiado a un lambda como señaló @Okx, debo decir que es una respuesta impresionante. Traté de hacer este desafío hace aproximadamente una hora justo antes del almuerzo, y me di por vencido. Entonces +1 de mi parte. Algunas cosas pequeñas para el golf: while(--n>0){q=p;p=c;c+=q;}puede ser for(;--n>0;p=c,c+=q)q=p;y n=c;while(i>0){if((""+c).contains(""+n))--i;q=p;p=c;c+=q;}puede ser for(n=c;i>0;q=p,p=c,c+=q)if((""+c).contains(""+n))--i;. (En 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 )
Kevin Cruijssen
2

Perl 6 , 45 bytes

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

$_es el argumento de la función; @fes la secuencia de Fibonacci, generada perezosamente.

Sean
fuente
2

JavaScript (ES6), 96 93 92 90 86 bytes

0 indexado, con el número 0 en la secuencia 1. Mierda a las 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 guardados gracias a Arnauld

Intentalo

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>


Explicación

Versión actualizada a seguir, cuando tenga un minuto.

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
Lanudo
fuente
Su respuesta parece proporcionar una salida diferente de los ejemplos.
ericw31415
@ ericw31415, eso es porque está indexado en 0.
Shaggy
Sin embargo, escribí esto específicamente: "A los efectos de este desafío, la secuencia de Fibonacci comienza con un 1".
ericw31415
@ ericw31415: Y mi secuencia comienza con 1, solo está indexada en 0; los números 0 y 1 en la secuencia son 1, el 2 es 2, el 3 es 3, el 4 es 5, el 5 es 8 y así sucesivamente.
Shaggy
2

Carbón , 65 bytes

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

Pruébalo en línea! Enlace al código detallado para explicación.

Solo ASCII
fuente
1

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];

Pruébalo en línea!

Jörg Hülsermann
fuente
1

Mathematica, 85 bytes

(i=ToString;f=Fibonacci;For[n=t=0,t<#,If[i@f@n++~StringContainsQ~i@f@#,t++]];f[n-1])&

entrada

[10]

-4 bytes de @JungHwan Min

salida

4660046610375530309

J42161217
fuente
2
Parece extraño pero f@i@n++es totalmente válido, disminuyendo 1 byte. Usar en Forlugar de Whilereduce 3 bytes. 85 bytes:(i=ToString;f=Fibonacci;For[n=t=0,t<#,If[i@f@n++~StringContainsQ~i@f@#,t++]];f[n-1])&
JungHwan Min
1

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)

Esto hace uso de la gmpbiblioteca para el número de Fibonacci. Implementación bastante directa de la pregunta.

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

Algunas pruebas

> 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
MickyT
fuente
0

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

Una solución básica, utiliza una secuencia infinita de números de Fibonacci s.

NikoNyrh
fuente
0

C #, 35 bytes

int u=1,b=1;for(;b<n;){b+=u;u=b-u;}

Intentalo

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";}
Erlantz Calvo
fuente
1
Bienvenido a Programming Puzzle y Code-Golf. Las respuestas deben ser un programa completo o una función, mientras que solo proporcionó un fragmento. En particular, está asumiendo que la entrada está adentro ny simplemente pone la salida en b(creo). Podrías escribir esa toma ncomo argumentos y devoluciones b... Además, estoy bastante seguro de que no estás calculando lo que los desafíos te piden. En realidad, no tengo idea de lo que estás computando. ¿Podría utilizar algún código que podamos ejecutar para verificar su solución? (su "Pruébelo" no se puede ejecutar como está ..)
Dada
0

NewStack , 14 bytes

N∞ ḟᵢfi 'fif Ṗf⁻

La caida:

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

En inglés: (con ejemplo de una entrada de 3)

N∞: Haz una lista de los números naturales [1,2,3,4,5,6...]

ḟᵢ: Almacenar la entrada en la variable f [1,2,3,4,5,6...]

: Convierta la lista a números de Fibonacci [1,1,2,3,5,8...]

'fif: Mantenga todos los elementos que contengan el fnúmero de Fibonacci[2,21,233...]

Ṗf⁻: Imprime el f-1elemento th (-1 debido a la indexación basada en 0)233

Graviton
fuente
El GitHub parece contener solo un archivo Léame y un tutorial. Se hace referencia a una implementación, pero no está vinculada. Aunque PPCG ahora permite idiomas más nuevos que el desafío, creo que aún necesitamos una implementación disponible públicamente.
Ørjan Johansen
@ ØrjanJohansen, Ahah, gracias por recordármelo. ¡Olvidé subir eso! Se levantará en un minuto.
Graviton
Su implementación parece usar UTF-8, en cuyo caso eso es en realidad 28 bytes (no importa la configuración de Haskell, solo estoy usando TIO para contar bytes). Los idiomas como Jelly, etc. tienen sus propias páginas de códigos por este motivo.
Ørjan Johansen
@ ØrjanJohansen Touché, estoy trabajando en la distribución de una tabla para su propia codificación mientras hablamos.
Graviton