prathams's blog

Fibonacci Entry Point (FEP)
By prathams, history, 7 years ago, In English

How to calculate the fibonacci entry point for N numbers p1, p2, p3, ...., pn. (1 <  = pi <  = 109)

FEP(pi) = j such that jth fibonacci number is the first fibonacci number Fj divisible by pi

How can we find it efficiently for N numbers.

Ex,
input = 2, output = 3
input = 5, output = 5
input = 13, output = 7

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If p is prime, the answer is divisor of p + 1 (except when p = 5). So check all p + 1 divisors with fast matrix power algorithm.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    If p = 11, answer is 10. 10 is not divisor of 12. And what if p is not prime.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Looks like it could be divisor of p − 1 too. Could be dependent on whether square root of 5 exists (that's why p = 5 is an exception) which is true if and only if p = 5n ± 1. For non-prime modulos you will need to combine answers with lcm for several powers of primes. To calculate the answer for the power of prime, you will need to check whether you need to multiply by p the answer for smaller power of prime.

      → Reply