Prueba si un número es fibonacci

Un entero positivo ω es un número de Fibonacci si y sólo si uno de 5ω² + 4 y 5ω² - 4 es un cuadrado perfecto.

Ver Los Fabulosos Números de Fibonacci para más.

Si bien varias personas señalan la solución de cuadrado perfecto, implica cuadrar un número de Fibonacci, lo que frecuentemente resulta en un producto masivo.

Hay menos de 80 números de Fibonacci que incluso se pueden mantener en un entero estándar de 64 bits.

Aquí está mi solución, que funciona completamente más pequeño que el número a probar.
(escrito en C#, usando tipos básicos como double y long. Pero el algoritmo debería funcionar bien para más grandes tipo.)

static bool IsFib(long T, out long idx)
{
    double root5 = Math.Sqrt(5);
    double phi = (1 + root5) / 2;

    idx    = (long)Math.Floor( Math.Log(T*root5) / Math.Log(phi) + 0.5 );
    long u = (long)Math.Floor( Math.Pow(phi, idx)/root5 + 0.5);

    return (u == T);
}

El parámetro #2 es el "Índice" en la secuencia de Fibonacci.
Si el valor a probar, T es un número de Fibonacci, entonces idx será el índice basado en 1 de ese número en la secuencia de Fibonacci. (con una notable excepción)

La secuencia de Fibonacci es 1 1 2 3 5 8 13, etc.
3 es el 4to número en la secuencia: IsFib(3, out idx); volverá true y valor 4.
8 es el número 6 en la secuencia: IsFib(8, out idx); devolverá true y valor 6.
13 es el número 7; IsFib(13, out idx); devolverá true y valor 7.

La única excepción es IsFib(1, out idx);, que devolverá 2, a pesar de que el valor 1 aparece tanto en el índice 1 como en el 2.

Si IsFib es pasado un número no-Fibonacci, devolverá false, y el valor de idx será el índice del mayor número de Fibonacci menor que T.

16 es no es un valor de Fibonacci.
IsFib(16, out idx); devolverá false y valor 7.
Puede usar La fórmula de Binet para convertir el índice 7 en el valor de Fibonacci 13, que es el número más grande menor que 16.

#!/bin/bash
victim="144"
curl http://aux.planetmath.org/files/objects/7680/fib.txt | sed 's/^[0-9]*//;s/[ \t]//g' | grep "^$victim$" >/dev/null 2>/dev/null
if [[ $? -eq 0 ]] ; then
    echo "$victim is a fibonacci number"
else
    echo "$victim aint"
fi

Si sus números son de tamaño limitado, que simplemente poner todos los números de fibonacci debajo del límite superior en una tabla hash y probar la contención hará el truco. Hay muy pocos números de fibonacci (por ejemplo, solo 38 por debajo de 5mln), ya que crecen exponencialmente.

Si sus números son no de tamaño limitado, entonces el truco sugerido con la prueba cuadrada será casi seguramente más lento que generar la secuencia de fibonacci hasta que se encuentre o supere el número.

Entero positivo ω es un número de Fibonacci

Si y solo si uno de 5ω² + 4 y 5ω² - 4 es un cuadrado perfecto

De Los (Fabulosos) números de FIBONACCI de Alfred Posamentier e Ingmar Lehmann

bool isFibonacci(int  w)
{
       double X1 = 5 * Math.Pow(w, 2) + 4;
       double X2 = 5 * Math.Pow(w, 2) - 4;

       long X1_sqrt = (long)Math.Sqrt(X1);
       long X2_sqrt = (long)Math.Sqrt(X2);   

       return (X1_sqrt*X1_sqrt == X1) || (X2_sqrt*X2_sqrt == X2) ;
}

Lo copié de esta fuente

Fragmento que imprime números de Fibonacci entre 1k y 10k.

for (int i = 1000; i < 10000; i++)
{
         if (isFibonacci(i))
              Console.Write(" "+i);
}

OMG Solo hay CUATRO!!!

Con otro método

from math import *

phi = 1.61803399
sqrt5 = sqrt(5)

def F(n):
    return int((phi**n - (1-phi)**n) /sqrt5)

def isFibonacci(z):
    return F(int(floor(log(sqrt5*z,phi)+0.5))) == z

print [i for i in range(1000,10000) if isFibonacci(i)]

Hacia una solución, echa un vistazo a la Fórmula de Binet.
(Busque "Expresión de forma cerrada" en Número de Fibonacci en Wikipedia)

Dice que la secuencia de números de Fibonacci es creada por una fórmula cerrada simple:

Creo que si resuelves para n, y pruebas si n es un entero, tendrás tu respuesta.

Edit Como @psmears señala, el mismo artículo de Wikipedia también tiene una sección sobre la detección de números de Fibonacci. Wikipedia es una excelente fuente.

Vea la sección "Reconociendo los números de Fibonacci" en el artículo de wikipedia sobre los números de Fibonacci.

Dado que los números de Fibonacci crecen exponencialmente, el método que sugiere es bastante rápido. Otro es este.

De Wikipedia: http://en.wikipedia.org/wiki/Fibonacci_number

Un entero positivo z es un Fibonacci número si y solo si uno de 5z^2 + 4 o 5z^2-4 es un cuadrado perfecto.

Basado en respuestas anteriores de psmears y yo, he escrito este código C#.

Pasa por los pasos lentamente, y claramente se puede reducir y optimizar:

// Input: T: number to test.
// Output: idx: index of the number in the Fibonacci sequence.
//    eg: idx for 8 is 6. (0, 1, 1, 2, 3, 5, 8)
// Return value: True if Fibonacci, False otherwise.
static bool IsFib(long T, out int idx)
{
    double root5 = Math.Sqrt(5);
    double PSI = (1 + root5) / 2;

    // For reference, IsFib(72723460248141) should show it is the 68th Fibonacci number

    double a;

    a = T*root5;
    a = Math.Log(a) / Math.Log(PSI);
    a += 0.5;
    a = Math.Floor(a);
    idx = (Int32)a;

    long u = (long)Math.Floor(Math.Pow(PSI, a)/root5 + 0.5);

    if (u == T)
    {
        return true;
    }
    else
    {
        idx = 0;
        return false;
    }
}

Las pruebas revelan que esto funciona para los primeros 69 números de Fibonacci, pero se desglosa para el número 70.

F(69) = 117,669,030,460,994 - Works
F(70) = 190,392,490,709,135 - Fails

En general, a menos que esté utilizando una biblioteca BigInt de algún tipo, probablemente sea mejor tener una simple tabla de búsqueda de los números de Fibonacci y verificarla, en lugar de ejecutar un algoritmo.

Una lista de los primeros 300 Números está disponible en línea.

Pero este código describe un algoritmo viable, siempre y cuando tenga suficiente precisión, y no rebase su sistema de representación numérica.

Re: código de Ahmad - un enfoque más simple sin recursión o punteros, bastante ingenuo, pero no requiere casi ninguna potencia computacional para nada menos que números realmente titánicos (aproximadamente 2N adiciones para verificar el Enésimo número fib, que en una máquina moderna tomará milisegundos en el peor de los casos)

// devuelve pos si encuentra algo, 0 si no (C/C++ trata cualquier valor != 0 como verdadero, por lo que el mismo resultado final)

int isFib (long n)
{
    int pos = 2;
    long last = 1;
    long current = 1;
    long temp;

    while (current < n)
    {
        temp = last;
        last = current;
        current = current + temp;
        pos++;
    }

    if (current == n)
        return pos;
    else
        return 0;

}

La expresión general para un número de Fibonacci es F(n) = [ [(1+sqrt(5))/2] sup n+1 - [(1-sqrt(5))/2] sup n+1 ]/ sqrt(5) ..... (*) El segundo exponencial va a cero para n grande y llevar a cabo la operaciones numéricas obtenemos F (n) = [(1.618) sup n+1 ] / 2.236

Si K es el número a probar log (k*2.2336) / log(1.618) debe ser un entero!

Ejemplo para K igual a 13 mi calculadora da la respuesta 7.00246 Para K igual a 14 la respuesta es 7.1564.

Puede aumentar la confianza en el resultado tomando el entero más cercano a la responder y sustituir en ( * ) para confirmar que el resultado es K

¿Qué tan grandes son los números con los que estás tratando?

¿Podría una tabla de búsqueda funcionar para usted? (una lista precalculada de números en los que puede buscar)

También hay una expresión de forma cerrada que supongo que podrías invertir para obtener la respuesta analíticamente (aunque no soy matemático, así que no puedo prometer que esta sugerencia tenga sentido)

Ejecuté algunos puntos de referencia sobre los métodos presentados aquí junto con la adición simple, pre-computar una matriz y memorizar los resultados en un hash. Para Perl, al menos, el método de cuadratura es un poco más rápido que el método logarítmico, quizás un 20% más rápido. Como señala Abelenky, es una compensación entre si tienes espacio para cuadrar números de bits.

Ciertamente, la forma más rápida es hash todos los números de Fibonacci en su espacio de dominio. A lo largo de las líneas de otro punto que abelenky hace, solo hay 94 de estos retoños que son menos de 2^64.

Solo debes pre-calcularlos, y ponerlos en un hash de Perl, diccionario Python, o lo que sea.

Las propiedades de los números de Fibonacci son muy interesantes, pero usarlos para determinar si algún entero en un programa de computadora es uno es como escribir una subrutina para calcular pi cada vez que se inicia el programa.

Esta es mi solución No estoy seguro de si se compara. Espero que esto ayude!

def is_fibonacci?(i)
  a,b=0,1
    until b >= i
        a,b=b,a+b
        return true if b == i
    end
end

Lo que a,b = b, a + b está haciendo

 0, 1 = 1, 0 +1
 1, 1 = 1, 1 + 1
 1, 2 = 2, 1 + 2
 2, 3 = 3, 2 + 3

fib1 = fib2
fib2 = fib1 + fib2

Una versión Scala -

def isFib(n: Int): Boolean = {

def checkFib(f1: Int = 1, f2: Int = 1): Boolean = {

if(n == f1 || n == f2) true
else if(n < f2) false
else checkFib(f2, f1+f2)

}

checkFib()

}

La solución Java se puede hacer de la siguiente manera. Pero aún así se puede optimizar

La siguiente solución funciona para

1. 1≤T≤10 ^5
2. 1≤N≤10 ^10

T es no.de casos de prueba, N es rango de número

    import java.util.Scanner;
    import java.math.BigDecimal;
    import java.math.RoundingMode;

    public class FibonacciTester {
        private static BigDecimal zero = BigDecimal.valueOf(0);
        private static BigDecimal one = BigDecimal.valueOf(1);
        private static BigDecimal two = BigDecimal.valueOf(2);
        private static BigDecimal four = BigDecimal.valueOf(4);
        private static BigDecimal five = BigDecimal.valueOf(5);

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            BigDecimal[] inputs = new BigDecimal[n];
            for (int i = 0; i < n; i++) {
                inputs[i] = sc.nextBigDecimal();
            }

            for (int i = 0; i < inputs.length; i++) {
                if (isFibonacci(inputs[i]))
                    System.out.println("IsFibo");
                else
                    System.out.println("IsNotFibo");
            }


        }

        public static boolean isFibonacci(BigDecimal num) {
            if (num.compareTo(zero) <= 0) {
                return false;
            }

            BigDecimal base = num.multiply(num).multiply(five);
            BigDecimal possibility1 = base.add(four);
            BigDecimal possibility2 = base.subtract(four);


            return (isPerfectSquare(possibility1) || isPerfectSquare(possibility2));
        }

        public static boolean isPerfectSquare(BigDecimal num) {
            BigDecimal squareRoot = one;
            BigDecimal square = one;
            BigDecimal i = one;
            BigDecimal newSquareRoot;
            int comparison = -1;

            while (comparison != 0) {
                if (comparison < 0) {
                    i = i.multiply(two);
                    newSquareRoot = squareRoot.add(i).setScale(0, RoundingMode.HALF_UP);
                } else {
                    i = i.divide(two);
                    newSquareRoot = squareRoot.subtract(i).setScale(0, RoundingMode.HALF_UP);
                }

                if (newSquareRoot.compareTo(squareRoot) == 0) {
                    return false;
                }

                squareRoot = newSquareRoot;
                square = squareRoot.multiply(squareRoot);
                comparison = square.compareTo(num);
            }

            return true;
        }
    }

int isfib(int n /* number */, int &pos /* position */)
{
   if (n == 1)
   {
      pos=2;  // 1 1
      return 1;
   }
   else if (n == 2)
   {
      pos=3;  // 1 1 2
      return 1;
   }
   else
   {
      int m = n /2;
      int p, q, x, y;
      int t1=0, t2 =0;
      for (int i = m; i < n; i++)
      {
        p = i;
        q = n -p;    // p + q = n
        t1 = isfib(p, x);
        if (t1) t2 = isfib(q, y);
        if (t1 && t2 && x == y +1)
        {
           pos = x+1;
           return 1; //true
        }
      }
      pos = -1;
      return 0; //false
   }
}

¿Qué tal esto?

#include <stdio.h>
#include <math.h>

int main()
{
int number_entered, x, y;

printf("Please enter a number.\n");
scanf("%d", &number_entered);
x = y = 5 * number_entered^2 + 4;        /*Test if 5N^2 + 4 is a square number.*/
x = sqrt(x);
x = x^2;
if (x == y)
{
        printf("That number is in the Fibonacci sequence.\n");
    }
x = y = 5 * number_entered^2 - 4;        /*Test if 5N^2 - 4 is a square number.*/
x = sqrt(x);
x = x^2;
if (x == y)
{
    printf("That number is in the Fibonacci sequence.\n");
}
else
{
    printf("That number isn't in the Fibonacci sequence.\n");
}
return 0;
}

¿Funcionará esto?