Tu tarea:

Escriba un programa o función para verificar si un número ingresado es un número de Fibonacci . Un número de Fibonacci es un número contenido en la secuencia de Fibonacci.

La secuencia de Fibonacci se define como: F(n) = F(n - 1) + F(n - 2)

Con las semillas siendo F(0) = 0y F(1) = 1.

Entrada:

Un entero no negativo entre 0 y 1,000,000,000 que puede o no ser un número de Fibonacci.

Salida:

Un valor verdadero / falso que indica si la entrada es o no un número de Fibonacci.

Ejemplos:

0-->truthy
1-->truthy
2-->truthy
12-->falsy

Puntuación:

Este es el código de golf , gana el conteo de bytes más bajo.

Neim , 2 bytes

f𝕚

Explicación:

f       Push an infinite fibonacci list
 𝕚      Is the input in that list?

Funciona igual que mi respuesta It's Hip to be Square , pero usa una lista infinita diferente: fpara fibonacci.

¡Intentalo!

JavaScript (ES6), 34 bytes

f=(n,x=0,y=1)=>x<n?f(n,y,x+y):x==n

Genera recursivamente la secuencia de Fibonacci hasta que encuentra un elemento mayor o igual a la entrada, luego devuelve el elemento == entrada.

Retina , 23 bytes

^$|^(^1|(?>\2?)(\1))*1$

Pruébalo en línea!

Entrada en unario, salidas 0o 1.

Explicación

La secuencia de Fibonacci es un buen candidato para una solución con referencias directas, es decir, una "referencia inversa" que se refiere a un grupo circundante o uno que aparece más adelante en la expresión regular (en este caso, en realidad estamos usando ambos). Al hacer coincidir números como este, necesitamos encontrar una expresión recursiva para la diferencia entre los elementos de secuencia. Por ejemplo, para hacer coincidir números triangulares, generalmente hacemos coincidir el segmento anterior más uno. Para hacer coincidir los números cuadrados (cuyas diferencias son los números impares), hacemos coincidir el segmento anterior más dos.

Como obtenemos los números de Fibonacci agregando el penúltimo elemento al último, las diferencias entre ellos también son solo los números de Fibonacci. Por lo tanto, debemos hacer coincidir cada segmento como la suma de los dos anteriores. El núcleo de la expresión regular es este:

(         # This is group 1 which is repeated 0 or more times. On each
          # iteration it matches one Fibonacci number.
  ^1      # On the first iteration, we simply match 1 as the base case.
|         # Afterwards, the ^ can no longer match so the second alternative
          # is used.
  (?>\2?) # If possible, match group 2. This ends up being the Fibonacci
          # number before the last. The reason we need to make this optional
          # is that this group isn't defined yet on the second iteration.
          # The reason we wrap it in an atomic group is to prevent backtracking:
          # if group 2 exists, we *have* to include it in the match, otherwise
          # we would allow smaller increments.
  (\1)    # Finally, match the previous Fibonacci number and store it in
          # group 2 so that it becomes the second-to-last Fibonacci number
          # in the next iteration.
)*

Ahora esto termina la adición de los números de Fibonacci a partir de 1 , es decir, 1, 1, 2, 3, 5, ... . Los que se suman a 1, 2, 4, 7, 12, ... . Es decir, son uno menos que los números de Fibonacci, por lo que agregamos un 1al final. El único caso que esto no cubre es cero, por lo que tenemos la ^$alternativa al principio para cubrir eso.

Regex (sabor ECMAScript), 392 358 328 224 206 165 bytes

Las técnicas que deben entrar en juego para unir los números de Fibonacci con una expresión regular ECMAScript (en unario) están muy lejos de cómo se hace mejor en la mayoría de los otros sabores de expresiones regulares. La falta de referencias hacia atrás / anidadas o recursividad significa que es imposible contar directamente o mantener un total acumulado de cualquier cosa. La falta de mirar atrás hace que a menudo sea un desafío incluso tener suficiente espacio para trabajar.

Muchos problemas deben abordarse desde una perspectiva completamente diferente, y parecen irresolubles hasta la llegada de alguna idea clave. Te obliga a echar una red mucho más amplia para encontrar qué propiedades matemáticas de los números con los que estás trabajando podrían usarse para resolver un problema en particular.

En marzo de 2014, esto es lo que sucedió con los números de Fibonacci. Mirando la página de Wikipedia, inicialmente no pude encontrar una manera, aunque una propiedad en particular parecía tentadoramente cercana. Luego, el matemático teukon describió un método que dejó bastante claro que sería posible hacerlo, utilizando esa propiedad junto con otra. Era reacio a construir realmente la expresión regular. Su reacción cuando seguí adelante y lo hice:

¡Estás loco! ... pensé que podrías hacer esto.

Al igual que con mis otras publicaciones de expresiones regulares de matemáticas unitarias de ECMAScript, daré una advertencia: recomiendo aprender a resolver problemas matemáticos unarios en expresiones regulares de ECMAScript. Ha sido un viaje fascinante para mí, y no quiero estropearlo para cualquiera que quiera probarlo ellos mismos, especialmente aquellos que estén interesados ​​en la teoría de números. Vea esa publicación para obtener una lista de problemas recomendados consecutivamente etiquetados con spoiler para resolver uno por uno.

Así que no sigas leyendo si no quieres que se te estropee la magia de expresiones regulares unarias . Si desea intentar descubrir esta magia usted mismo, le recomiendo comenzar resolviendo algunos problemas en la expresión regular de ECMAScript como se describe en la publicación vinculada anteriormente.

El desafío que enfrenté inicialmente: un número entero positivo x es un número de Fibonacci si y solo si 5x ² + 4 y / o 5x ² - 4 es un cuadrado perfecto. Pero no hay espacio para calcular esto en una expresión regular. El único espacio en el que tenemos que trabajar es el número mismo. Ni siquiera tenemos suficiente espacio para multiplicar por 5 o tomar el cuadrado, y mucho menos ambos.

La idea de teukon sobre cómo resolverlo ( originalmente publicado aquí ):

La expresión regular se presenta con una cadena de la forma ^x*$, sea z su longitud. Compruebe si z es uno de los primeros números de Fibonacci a mano (hasta 21 deberían hacerlo). Si no es:

1. Lea un par de números, a <b, de modo que b no sea mayor que 2a.
   
2. Use las miradas hacia adelante para construir a ² , ab y b ² .
   
3. Afirma que 5a ² + 4 o 5a ² - 4 es un cuadrado perfecto (por lo que debe ser F _n-1 para algunos n).
   
4. Afirma que 5b ² + 4 o 5b ² + 4 es un cuadrado perfecto (entonces b debe ser F _n ).
   
5. Verifique que z = F _{2n + 3} o z = F _{2n + 4} utilizando a ² , ab y b ² construidos anteriormente , y las identidades:
   
   • F _2n-1 = F _n ² + F _n-1 ²
     
   • F _2n = (2F _n-1 + F _n ) F _n
     

En resumen: estas identidades nos permiten reducir el problema de verificar que un número dado es Fibonacci a verificar que un par de números mucho más pequeños son Fibonacci. Un poco de álgebra mostrará que para n lo suficientemente grande (n = 3 debería hacer), F _{2n + 3} > F _n + 5F _n ² + 4, por lo que siempre debe haber suficiente espacio.

Y aquí hay una maqueta del algoritmo en C que escribí como prueba antes de implementarlo en regex.

Entonces, sin más preámbulos, aquí está la expresión regular:

^((?=(x*).*(?=x{4}(x{5}(\2{5}))(?=\3*$)\4+$)(|x{4})(?=xx(x*)(\6x?))\5(x(x*))(?=(\8*)\9+$)(?=\8*$\10)\8*(?=(x\2\9+$))(x*)\12)\7\11(\6\11|\12)|x{0,3}|x{5}|x{8}|x{21})$

Pruébalo en línea!

Y la versión comentada y muy impresa:

^(
  (?=
    (x*)                   # \2+1 = potential number for which 5*(\2+1)^2 ± 4
                           # is a perfect square; this is true iff \2+1 is a Fibonacci
                           # number. Outside the surrounding lookahead block, \2+1 is
                           # guaranteed to be the largest number for which this is true
                           # such that \2 + 5*(\2+1)^2 + 4 fits into the main number.
    .*
    (?=                    # tail = (\2+1) * (\2+1) * 5 + 4
      x{4}
      (                    # \3 = (\2+1) * 5
        x{5}
        (\2{5})            # \4 = \2 * 5
      )
      (?=\3*$)
      \4+$
    )
    (|x{4})                # \5 = parity - determined by whether the index of Fibonacci
                           #               number \2+1 is odd or even
    (?=xx (x*)(\6 x?))     # \6 = arithmetic mean of (\2+1) * (\2+1) * 5 and \8 * \8,
                           #      divided by 2
                           # \7 = the other half, including remainder
    \5
    # require that the current tail is a perfect square
    (x(x*))                # \8 = potential square root, which will be the square root
                           #      outside the surrounding lookahead; \9 = \8-1
    (?=(\8*)\9+$)          # \10 = must be zero for \8 to be a valid square root
    (?=\8*$\10)
    \8*
    (?=(x\2\9+$))          # \11 = result of multiplying \8 * (\2+1), where \8 is larger
    (x*)\12                # \12 = \11 / 2; the remainder will always be the same as it
                           #       is in \7, because \8 is odd iff \2+1 is odd
  )
  \7\11
  (
    \6\11
  |
    \12
  )
|
  x{0,3}|x{5}|x{8}|x{21}   # The Fibonacci numbers 0, 1, 2, 3, 5, 8, 21 cannot be handled
                           # by our main algorithm, so match them here; note, as it so
                           # happens the main algorithm does match 13, so that doesn't
                           # need to be handled here.
)$

El algoritmo de multiplicación no se explica en esos comentarios, pero se explica brevemente en un párrafo de mis abundantes números de expresiones regulares .

Estaba manteniendo seis versiones diferentes de la expresión regular de Fibonacci: cuatro que se mueven de la longitud más corta a la velocidad más rápida y usan el algoritmo explicado anteriormente, y otras dos que usan un algoritmo diferente, mucho más rápido pero mucho más largo, que como encontré en realidad puede volver el índice de Fibonacci como una coincidencia (explicar que el algoritmo aquí está más allá del alcance de esta publicación, pero se explica en la discusión original Gist ). No creo que vuelva a mantener tantas versiones muy similares de una expresión regular, porque en ese momento estaba haciendo todas mis pruebas en PCRE y Perl, pero mi motor de expresión regular es lo suficientemente rápido como para que las preocupaciones sobre la velocidad ya no sean tan importantes (y si una construcción en particular está causando un cuello de botella, puedo agregar una optimización), aunque probablemente volvería a mantener una versión más rápida y una versión más corta, si la diferencia en velocidad eran lo suficientemente grandes.

La versión "devolver el índice de Fibonacci menos 1 como un partido" (no muy golfizado):

Pruébalo en línea!

Todas las versiones están en github con el historial completo de las optimizaciones de golf:

regex para hacer coincidir los números de Fibonacci - corto, velocidad 0.txt (el más corto pero más lento, como en esta publicación)
regex para hacer coincidir los números de Fibonacci - corto, velocidad 1.txt
regex para hacer coincidir los números de Fibonacci - corto, velocidad 2.txt
regex para números de Fibonacci coincidentes - corto, velocidad 3.txt
regex para hacer coincidir los números de Fibonacci - más rápido.txt
regex para hacer coincidir los números de Fibonacci - return index.txt

Python 3 , 48 bytes

lambda n:0in((5*n*n+4)**.5%1,abs(5*n*n-4)**.5%1)

Pruébalo en línea!

Python 2, 48 44 bytes

f=lambda n,a=0,b=1:n>a and f(n,b,a+b)or n==a

Pruébalo en línea

_{Gracias a Jonathan Allan por guardar 4 bytes.}

05AB1E , 8 7 bytes

>ÅF¹å¹m

Explicación:

>ÅF       # Generate Fibbonacci numbers up to n+1
   ¹å     # 0 if original isn't in the list, 1 if it is
     ¹m   # 0**0 = 1 if input was 0 (hotfix for 0).
          # or 0**n if not fibb / 1**n if it is a fibb.

Pruébalo en línea!

-1 gracias a Jonathan Allan por la solución de 0-no-un-fibonacci-número.

Perl 6 , 23 bytes

{$_∈(0,1,*+*...*>$_)}

En serio , 3 bytes

,fu

Pruébalo en línea!

Devuelve el índice +1 en la lista de números de Fibonacci si es verdadero; de lo contrario, devuelve falso.

Explicación:

,fu
,   read input
 f  0-indexed index of that number in the fibonacci sequence (-1 if not in the sequence)
  u increment. (Makes the -1 value falsy and the 0-value truthy)

Jalea ,  8 7  6 bytes

-r‘ÆḞċ

Pruébalo en línea!

¿Cómo?

-r‘ÆḞċ - Link: non negative number, n
-      - literal -1      = -1
 r     - inclusive range = [-1,0,1,2,3,4,5,...,n]
  ‘    - increment n     = [ 0,1,2,3,4,5,6,...,n+1]
   ÆḞ  - Fibonacci       = [ 0,1,1,2,3,5,8,...,fib(n+1)]
     ċ - count occurrences of n (1 if n is a Fibonacci number, 0 otherwise)

Notas:

• el incremento, ‘se necesita por lo que esto funciona para 2 y 3 , ya que son la 3 ^ª y 4 ^ª números de Fibonacci - más allá de 3 todos los números de Fibonacci son mayores que su índice.
• la -que se necesita (y no sólo ‘R) por lo que esto funciona para 0 desde 0 es el 0 ^º número de Fibonacci;

ZX81 BÁSICO 180 151 100 ~ 94 bytes tokenized BASIC

Gracias a Moggy en los foros de SinclairZXWorld, aquí hay una solución mucho más ordenada que ahorra más bytes.

 1 INPUT I
 2 FOR F=NOT PI TO VAL "1E9"
 3 LET R=INT (VAL ".5"+(((SQR VAL "5"+SGN PI)/VAL "2")**I)/SQR VAL "5")
 4 IF R>=I THEN PRINT F=R
 5 IF R<I THEN NEXT F

Esto generará 1 si se ingresa un número de Fibonacci, o cero si no. Aunque esto ahorra bytes, es mucho más lento que las soluciones anteriores a continuación. Para la velocidad (pero más bytes BÁSICOS) elimine los VALcontenedores alrededor de los números literales de cadena. Aquí están las soluciones antiguas (er) con algunas explicaciones:

 1 INPUT A$
 2 LET A=SGN PI
 3 LET B=A
 4 LET F=VAL A$
 5 IF F>SGN PI THEN FOR I=NOT PI TO VAL "1E9"
 6 LET C=A+B
 7 LET A=B
 8 LET B=C
 9 IF B>=F THEN GOTO CODE "£"
10 IF F THEN NEXT I
12 PRINT STR$(SGN PI*(B=F OR F<=SGN PI)) AND F>=NOT PI;"0" AND F<NOT PI

Las enmiendas anteriores ahorran más bytes BÁSICOS para condensar las IFdeclaraciones en una sola PRINTen la línea 12; otros bytes se guardaron usando la VALpalabra clave y, y usando GOTO CODE "£", que en el conjunto de caracteres ZX81 es 12. Las cadenas guardan más bytes sobre los números ya que todos los valores numéricos se almacenan como flotantes, por lo que ocupan más espacio en la pila VAR.

C #, 109 bytes

bool f(int n){int[]i=new[]{0,1,0};while(i[0]<n||i[1]<n){i[i[2]%2]=i[0]+i[1];i[2]++;}return n==i[0]||n==i[1];}

Definitivamente podría mejorarse, pero no tuve tiempo.

> <> , 21 19 + 3 = 24 22 bytes

i1\{=n;
?!\:@+:{:}(

Se espera que la entrada esté en la pila al inicio del programa, por lo que +3 bytes para el -vindicador.

Pruébalo en línea!

Esto funciona generando números de Fibonacci hasta que sean mayores o iguales que el número de entrada, luego verificando el último número generado para la igualdad con la entrada. Salidas 1si era un número de Fibonacci, de lo 0contrario.

Para garantizar que 0se maneja correctamente, la semilla es -1 1: el primer número generado será en 0lugar de 1.

Gracias a @cole por señalar que ise puede usar para empujar -1a la pila cuando STDIN está vacío. ¡Muy inteligente!

Versión previa:

01-1\{=n;
}(?!\:@+:{:

Mathematica, 37 bytes

!Fibonacci@n~Table~{n,0,#+1}~FreeQ~#&

-4 bytes de @ngenisis

MATL (16 bytes)

2^5*4-t8+hX^tk=s

Pruébalo en línea!

No es la solución más elegante, pero quería usar el método directo para verificar si "5 * x ^ 2 +/- 4" es un cuadrado perfecto .

Explicación:

2^5*    % 5 times the input squared
4-      % push the above minus 4
t8+     % push the above plus 8 (+4 overall)
hX^     % concatenate them into an array and then take the sqrt().
tk      % push a copy of the array that is rounded using floor().
=       % test if the sqrt's were already integers
s       % sum the results, returns 0 if neither was a perfect square.

Nota:

En el caso "0" devuelve "2" porque 4 y -4 son cuadrados perfectos, lo mismo con 1 que produce "1 1". Considere cualquier salida que no sea cero como "verdadero" y 0 como "falso".

Pari / GP , 32 bytes

n->!prod(x=0,n+1,fibonacci(x)-n)

Pruébalo en línea!

PHP , 44 bytes

for(;0>$s=$x-$argn;)$x=+$y+$y=$x?:1;echo!$s;

Pruébalo en línea!

PHP , 58 bytes

for($x=0,$y=1;$x<$argn;$x=$y,$y=$t)$t=$x+$y;echo$x==$argn;

Pruébalo en línea!

Java, 72 69 68 63 59 55 50 49 bytes

n->{int a=0,b=1;for(;a<n;a=b-a)b+=a;return a==n;}

¡Pruébalo tú mismo!

Alternativa (todavía 49 bytes)

n->{int a=0,b=1;for(;a<n;b=a+(a=b));return a==n;}

No muy original: es la versión iterativa simple y básica.

Esto funciona para números hasta 1,836,311,903 (número 47 de Fibonacci) incluido. Por encima de eso, el resultado es indefinido (incluido un bucle infinito potencial).

Gracias a Kevin Cruijssen y David Conrad por ayudar al golf :)

C # (.NET Core) , 51 bytes

bool f(int n,int a=0,int b=1)=>a<n?f(n,b,a+b):a==n;

Pruébalo en línea!

-6 bytes gracias a @Oliver!

Esta solución utiliza una función recursiva bastante sencilla.

• La variable nes el número a probar.
• Las variables ay bson los 2 números más recientes en la secuencia.
• Comprueba si el primero de los 2 números más recientes es menor que la entrada. Cuando este es el caso, se realiza una llamada recursiva a los siguientes números de la serie.
• De lo contrario, verifique si el primer número es igual a la entrada y devuelva el resultado.

El enlace TIO demuestra que esto funciona para 1134903170 que excede el valor máximo requerido por el desafío.

Alquimista , 205134 bytes

^{¡Muchas gracias a ASCII-only por la fusión de estados bastante inteligente, ahorrando 71 bytes!}

_->In_x+c+u
u+b->u+a+d
u+0b->v
v+c->v+b+d
v+0c->w
w+a+x->w+y
w+0a+0x->Out_"1"
w+a+0x->Out_"0"
w+0a+x+y->w+2x
w+0a+0y+d->w+c
w+0d+0a->u

¡Pruébelo en línea o verifique en lote!

Sin golf

# read input, initialize (c = 1)
_ -> In_x + c + s0

# a,d <- b
s0 +  b -> s0 + a + d
s0 + 0b -> s1

# b,d <- c
s1 +  c -> s1 + b + d
s1 + 0c -> s2

s2 +  a +  x -> s2 + y            # y <- min(a,x)
s2 + 0a + 0x -> Out_"1"           # if (a == x): was Fibonacci
s2 +  a + 0x -> Out_"0"           # if (a >  x): stop (we exceeded target)
s2 + 0a +  x +  y -> s2 + 2x      # if (a <  x): x += a (since y = a) / restore x
s2 + 0a      + 0y +  d -> s2 + c  # once that's done; c <- d
s2 + 0a           + 0d->s0        # and finally loop

Jalea , 5 bytes

ȷḶÆḞi

Pruébalo en línea!

Devuelve 0 para números que no son de Fibonacci y la posición indexada en 1 del número en la secuencia de Fibonacci para números de Fibonacci.

Explicación:

ȷḶÆḞi
ȷ        The literal number 1000
 Ḷ       Range [0,1,...,999]
  ÆḞ     Get the ith Fib number; vectorizes [1,1,2,3,5,...,<1000th Fib number>]
    i    Get the first index of element in list, or 0 if not found

Dyalog APL, 17 bytes

0∊1|.5*⍨4 ¯4+5××⍨

Pruébalo en línea!

R, 43 40 bytes

pryr::f(x%in%DescTools::Fibonacci(0:45))  

pryr::f crea una función:

function (x) 
x %in% DescTools::Fibonacci(0:45)

Se utiliza DescTools::Fibonaccipara crear los primeros x+1números de Fibonacci y se verifica su inclusión. x+1porque el tercer fibno es 2, y eso no sería suficiente para verificar la inclusión de 3.

Afortunadamente Desctools::Fibonacci(0)=0, ese es un lindo regalo.

-3 bytes gracias a MickyT

Haskell , 31 bytes

f=0:scanl(+)1f
(`elem`take 45f)

Pruébalo en línea! Esto explota el hecho de que la entrada estará en el rango de 0 a 1,000,000,000, por lo tanto, necesitamos verificar solo los primeros 45 números de Fibonacci.f=0:scanl(+)1fgenera una lista infinita de números de Fibonacci, take 45fes la lista de los primeros 45 números de Fibonacci y elemcomprueba si la entrada está en esta lista.

Versión sin restricciones: 36 bytes

f=0:scanl(+)1f
g n=n`elem`take(n+3)f

Pruébalo en línea! Para cualquiern , tomar los primeros n+3números de Fibonacci garantizará que nestarán en esta lista si se trata de un número de Fibonacci.

Tenga en cuenta que este enfoque es increíblemente ineficiente para los números altos que no son números de Fibonacci, porque todos los n+3números de Fibonacci deben calcularse.

Javascript (ES6 sin el operador **), 44 bytes

f=(x,c=x*(Math.sqrt(5)-1)/2%1)=>x*(c-c*c)<.5

Se basa en la relación entre los sucesivos números de Fibonacci que se aproximan a la proporción áurea. El valor de c es la parte fraccionaria de la entrada dividida por la proporción áurea; si la entrada es Fibonacci, entonces será muy cercana a 1 y el valor de c-c² será muy pequeño.

No es tan corto como algunas de las otras respuestas de JS, pero se ejecuta en tiempo O (1).

Julia 0.4 , 29 bytes

!m=in(0,sqrt(5*m*m+[4,-4])%1)

Pruébalo en línea!

Si no es así como respondes a Julia, avísame. No estoy seguro de cómo funciona la entrada en TIO.

R, 32 31 bytes

Toma información de stdin, devuelve TRUEo FALSEsegún corresponda.

any(!(5*scan()^2+-1:1*4)^.5%%1)

Lisp común, 61 54 bytes

(defun f(x)(do((a 0 b)(b 1(+ a b)))((>= a x)(= a x))))

Pruébalo en línea!

La reducción de tamaño con respecto a la versión anterior:

(defun f(x)(do((a 0 b)(b 1 c)(c 1(+ b c)))((>= a x)(= a x))))

fue provocado por la idea de que para generar la secuencia de los números de Fibonacci solo son necesarias dos variables, no tres.

Mathematica, 33 bytes

AtomQ@*InverseFunction[Fibonacci]

JS (ES6), 57 bytes

n=>(y=y=>((5*(n**2)+y)**0.5),~~y(4)==y(4)|~~y(-4)==y(-4))

Utiliza el método de carusocomputing . Mucho más golfier que mi otra respuesta .

Sin golf

n=>{
    y=y=>((5*(n**2)+y)**0.5);//carusocomputing's method in a function
    return ~~y(4) === y(4) || ~~y(-4) === y(-4);//~~x === Math.floor(x)
}