1
vote
2answers
67 views

nth convolved Fibonacci numbers of order 6 modulo m

Problem: Find the coefficient of xk in (1−x−x2)-6 modulo m. Constraints: k≤264 m≤105, m can be a composite number. I have 10^5 such queries to process in 2 sec, so O(log k) for each query ...
-6
votes
0answers
107 views

Solve fibonacci equation

Given two numbers M and N we need to solve : ( ∑ ( 6 * x * y * z * Fibo[x] * Fibo[y] * Fibo[z] ) ) % M , where x + y + z = N. Here x, y, z ≥ 0 and are integers. ...
3
votes
2answers
89 views

Fibonaaci Recurrence

This is an interesting question where we are trying to solve another recursion which has same tree structure as the given recursion and also has term similarities Given Data in question ...
2
votes
1answer
53 views

What's the Lucas version of the Möbius test for Fibonacci numbers?

I recently came across the following, attributed to Möbius: $$(a\in\mathbb N)=F_n\iff\left[\varphi a-\tfrac{1}{a},\varphi a+\tfrac{1}{a}\right]\ni(b\in\mathbb N)$$ It is the lesser-known test used to ...
2
votes
2answers
91 views

How do I apply the $\pm4$ part of the equation $5F_n^2\pm~4=L_n^2$ without knowing $n$?

I'm trying to test a great many numbers $a^3+b^3$ to see if any of them are Fibonacci using the formula $$a^3+b^3=F_n \iff 5(a^3+b^3)^2\pm~4=L_n^2$$ I want to make my search more efficient by having ...
0
votes
1answer
41 views

Understanding Recursive algorithm using FIB

I am studying for an exam, and I came across this question, I think I got the answer correct, just need some validation. ...
1
vote
1answer
40 views

How do I calculate the number of members in a limited Fibonacci series? [duplicate]

Looking for an algorithm that will give me the number of members that will result from calculating a Fibonacci series, given a particular limit. For example, if I start the series at 1 and limit my ...
1
vote
1answer
126 views

Calculate Number of ways to make the grid

We wish to tile a grid of size Nx2 with rectangles (dominoes) of 2x1 (in either orientation).For given N I need to find the number of different ways to tile the grid. EXAMPLE : For N=1 answer is 1 ...
6
votes
5answers
282 views

Fibonacci-like sequence

Today I have to deal with something which reminds Fibonacci sequence. Let's say I have a certain number k, which is n-th number of certain sequence. This sequence however is created by recursive ...
1
vote
1answer
134 views

Register Machine on Fibonacci Numbers

This problem is easy to understand but I am struggling to come up with any solutions. According to Wikipedia a register machine is a generic class of abstract machines used in a manner similar to a ...
1
vote
0answers
117 views

Is this “Elegant” algorithm for logarithm by Zeckendorf representation, the same as an 'efficient' algorithm?

The algorithm here which computes the exponent $b$ given a base $a$, and given $n$ = $a$^$b$, appears no better to me than simply counting the number of times we divide $n$ through by the base $a$ ...
3
votes
5answers
223 views

Translating matrix fibonacci into c++ (how can we determine if a number is fibonacci?)

Is it possible to determine if a number is a fibonacci number in less than N time (where N is the Nth fibonacci number) using the matrix method? I'm trying to exclude external libraries like cmath or ...
5
votes
2answers
422 views

Computing nth term of fibonacci-like sequence for large n

Sum up to nth term of fibonacci sequence for very large n can be calculated in O($\log n$) time using the following approach: $$A = \begin{bmatrix} 1&1 \\\\1&0\end{bmatrix}^n$$ ...
0
votes
1answer
1k views

How to solve tribonacci series [duplicate]

Possible Duplicate: Fibonacci, tribonacci and other similar sequences Suppose my Tribonacci series is like this: \begin{equation} T(n) = T(n-1) + T(n-2) +T(n-3) \end{equation} with initial ...
1
vote
1answer
1k views

Smallest Fibonacci number having a common factor with a given number

We have a number $k$ and we have to find the smallest Fibonacci number that has common factor with it(except $1$). We also have $2 \leq k \leq 1,000,000$. The required Fibonacci number is guaranteed ...
4
votes
1answer
463 views

Finding the smallest prime number that divides $Fib(n)$ but not any other $Fib(k)$ smaller than $Fib(n)$

Let $F(n)$ be $n$-th Fibonacci number.$$F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3 \text{ and so on. }$$Given a positive integer $n \gt 2$,Find the smallest prime number $P$ such that $P$ ...
2
votes
2answers
1k views

Finding index of a Fibonacci number: any mathematical solution possible?

The problem: Given a Fibonacci number,find its index. I am aware of the standard solution 'generate-hash-find'. I am just curious if there is ...