Introduction

Testing whether a number belongs to the Fibonacci sequence is a classic problem in number theory and algorithm design. The sequence starts with 0 and 1, and every next term is the sum of the previous two terms. In real software, you usually want a method that is both mathematically correct and efficient for large inputs.

Method 1: Perfect-Square Test

A non-negative integer n is Fibonacci if and only if at least one of these values is a perfect square:

• 5 * n * n + 4
• 5 * n * n - 4

This gives an O(1) arithmetic test, ignoring integer bit complexity.

1import math
2
3
4def is_perfect_square(x: int) -> bool:
5    if x < 0:
6        return False
7    r = math.isqrt(x)
8    return r * r == x
9
10
11def is_fibonacci_square_test(n: int) -> bool:
12    if n < 0:
13        return False
14    a = 5 * n * n + 4
15    b = 5 * n * n - 4
16    return is_perfect_square(a) or is_perfect_square(b)
17
18
19for value in [0, 1, 2, 3, 4, 5, 13, 14, 21, 22]:
20    print(value, is_fibonacci_square_test(value))

This is usually the best general-purpose check in Python because math.isqrt works with arbitrarily large integers.

Method 2: Iterative Generation

If you want a simple logic path without number theory identities, generate Fibonacci terms until you reach or pass n.

1def is_fibonacci_iterative(n: int) -> bool:
2    if n < 0:
3        return False
4    a, b = 0, 1
5    while a < n:
6        a, b = b, a + b
7    return a == n
8
9
10for value in [34, 35, 55, 56]:
11    print(value, is_fibonacci_iterative(value))

This method is O(k) where k is the index of the closest Fibonacci term, so runtime grows with n. It is still fast for many practical values and is easy to reason about in interviews or teaching.

Method 3: Membership in a Precomputed Set

If you need repeated lookups within a bounded range, precompute once and use set membership.

1def fibonacci_set(limit: int) -> set[int]:
2    vals = set()
3    a, b = 0, 1
4    while a <= limit:
5        vals.add(a)
6        a, b = b, a + b
7    return vals
8
9
10lookup = fibonacci_set(1_000_000)
11print(832040 in lookup)  # True
12print(832041 in lookup)  # False

This approach trades memory for speed. After precomputation, checks are effectively constant time.

Choosing the Right Approach

Use the perfect-square method when:

• You need a one-off check.
• Inputs can be very large.
• You want concise and mathematically strong logic.

Use iterative generation when:

• You need maximum readability.
• Input values are moderate.
• You do not want to rely on a formula.

Use precomputed sets when:

• You perform many checks in the same bounded range.
• You can afford memory for a lookup table.

JavaScript Version

JavaScript number precision can be tricky for large integers. Use BigInt for safer behavior.

1function isPerfectSquareBigInt(x) {
2  if (x < 0n) return false;
3  if (x < 2n) return true;
4
5  let low = 1n;
6  let high = x;
7  while (low <= high) {
8    const mid = (low + high) / 2n;
9    const sq = mid * mid;
10    if (sq === x) return true;
11    if (sq < x) low = mid + 1n;
12    else high = mid - 1n;
13  }
14  return false;
15}
16
17function isFibonacci(n) {
18  if (n < 0n) return false;
19  const fiveN2 = 5n * n * n;
20  return (
21    isPerfectSquareBigInt(fiveN2 + 4n) ||
22    isPerfectSquareBigInt(fiveN2 - 4n)
23  );
24}
25
26console.log(isFibonacci(144n));
27console.log(isFibonacci(145n));

This avoids floating-point rounding issues that appear if you use Math.sqrt on large values.

Common Pitfalls

• Forgetting that negative numbers are not part of the standard Fibonacci sequence in most programming contexts.
• Using floating-point square root checks on large integers and getting false results due to precision limits.
• Assuming iterative generation is constant time for very large inputs.
• Precomputing a lookup set without enforcing an upper limit, leading to unnecessary memory use.
• Confusing sequence index with sequence value, especially when handling base cases 0 and 1.

Summary

• The perfect-square identity provides a robust and efficient Fibonacci membership test.
• Iterative generation is simple and reliable for moderate input sizes.
• Precomputed sets are ideal for repeated checks in bounded ranges.
• For JavaScript, prefer BigInt implementations for high numeric accuracy.
• Handle edge cases explicitly, especially negative inputs and the two base values.