Find the sum of all primes p, such that p divides up, where up is the p- th Fibonacci number.
please tell me the answer it's urgent about this..///
If we use binets formula for the fibonacci numbers we can trivially see that Fp=5^(p-1)/2 mod p implying that the only prime p such that p divides Fp is 5 divides F5=5.
To find the sum of all primes p that divide the p-th Fibonacci number (up), we need to first determine the p-th Fibonacci number for each prime number p. Then, we sum up all the primes p.
To start, let's generate the Fibonacci sequence up to a certain limit, ensuring that the sequence has enough terms to include all possible p:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
Next, we need to check which numbers in the Fibonacci sequence are prime. One approach is to implement a primality test for each number in the sequence and keep track of the prime numbers:
- Set an initial value for the sum of primes, let's call it "sumPrimes," and set it to zero.
- For each Fibonacci number (let's call it "fibNum") in the sequence:
- Implement a primality test to check if fibNum is prime.
- If fibNum is prime, add it to sumPrimes.
- After processing all Fibonacci numbers, the sumPrimes will be the sum of all the primes p that divide the p-th Fibonacci number.
Since this process involves generating the Fibonacci sequence and performing a primality test, it may take some time, especially for larger values of p.
To expedite the process, you can use an optimized primality test, such as the Miller–Rabin primality test or the Sieve of Eratosthenes, to check for primality efficiently.
Once you have the list of primes and have computed the sum, you will have your answer.