1
$\begingroup$

I need to find the value different to 0 when evaluating

Fibonacci[x,2]mod(8417525)=0

How can I set up that with an iterative process, trying subsequent natural numbers till it finds the target value?

I'm quite new, so sorry if it's just a banal question.

Thanks

$\endgroup$
6
  • $\begingroup$ Welcome to the Mathematica Stack Exchange. Please include Mathematica code that you have tried so far. You can copy from your notebook's input cell and paste into the edit window where a braces icon { } can be used to format code. Could you include a simple example (with say x=2) and a smaller Mod value that has a known result? $\endgroup$
    – Syed
    Feb 21, 2022 at 11:31
  • $\begingroup$ Thanks for your comment, till now I just tried Table[Fibonacci[x,2]mod(8417525)=0,{x,a,b}] with various intervals [a,b], and just tried to find if for any of those value is "True". I just want to try an iterative process that stop when the mod is 0 and gives me the corresponding x value $\endgroup$
    – user967210
    Feb 21, 2022 at 11:46
  • $\begingroup$ Mathematica function Fibonacci[n,x] provides the polynomials. Please show your code ( "Table[Fibonacci[x,2]mod(8417525)=0,{x,a,b}]" doesn't evaluate ) . $\endgroup$ Feb 21, 2022 at 11:50
  • $\begingroup$ Your syntax for Fibonacci polynomial is wrong. Should be Fibonacci[n,x] as stated above. First type in FindInstance, hover over it, click the I and study the examples. Go down the examples to Scope/Integer domain and study those. Then study the construct for example: FindInstance[Mod[Fibonacci[3,x],8417525,x,Integers] $\endgroup$
    – josh
    Feb 21, 2022 at 12:37
  • $\begingroup$ Well no, because I want to find the right Fibonacci Polynomial of (x-1) degree, such that when I insert 2 as a value I will get the number P and taking P mod(8417525) I will get 0. That's why I thought about a cycle over the naturals that will stop when the Mod will be 0, meaning I will get the right degree of the polynomial $\endgroup$
    – user967210
    Feb 21, 2022 at 12:51

3 Answers 3

3
$\begingroup$
$Version

(* "13.0.1 for Mac OS X x86 (64-bit) (January 28, 2022)" *)

Clear["Global`*"]

x = 1; While[Mod[Fibonacci[x, 2], 8417525] != 0, x++]; x

(* 127380 *)

Verifying,

Mod[Fibonacci[x, 2], 8417525]

(* 0 *)
$\endgroup$
1
  • $\begingroup$ Thank you! That's exactly what I needed $\endgroup$
    – user967210
    Feb 22, 2022 at 13:52
3
$\begingroup$

Here are a couple of approaches which speed the solution dramatically for large indices.

The following code answers the question with a straight-forward While loop (@BobHanlon) giving the solution $n=127380$. Running this on a fresh kernel requires 31 s on my machine.

Block[{n = 1},
   AbsoluteTiming[ While[Mod[Fibonacci[n, 2], 8417525] != 0, n++]; n]
]

{31.7111, 127380}

FibPoly2Mod[n,m] finds Mod[Fibonacci[n,2],m], by using the recursion matrix $\{\{0,1\},\{1,2\}\}$ and code similar to FibonacciMod in this question.

FibPoly2Mod[n_, m_] :=
   Block[{b = {{0, 1}, {1, 2}}, d = IntegerDigits[n, 2]},
      Do[
         b = If[d[[i]] == 0, Mod[b . b, m], 
         Mod[b . b . {{0, 1}, {1, 2}}, m]],
         {i, 2, Length[d]}];
      b[[1, 2]]
   ]

For large indices, FibPoly2Mod[n,m] is much faster than Mod[Fibonacci[n,2],m].

For Fibonacci numbers, the Pisano period $k[m]$ of Mod[Fibonacci[n],m] is the LCM of the periods of the prime powers in the modulus $m$. That is, $k[m]={\rm LCM}[k[p_ 1^{e_ 1}],k[p_ 2^{e_ 2}],...,k[p_j^{e_j}]]$, where $m=p_ 1^{e_ 1}p_ 2^{e_ 2}...p_j^{e_j}$.

Therefore, I conjecture that the period of Mod[Fibonacci[n,x],m] equals the least common multiple of the periods of the prime powers making up the modulus $m$.

FibPoly2Mod0[m_Integer] :=
   Block[{p, f, n},
      p = FactorInteger[m];
      f = Table[
         n = 1;
         While[FibPoly2Mod[n, p[[i, 1]]^p[[i, 2]]] != 0, n++];
         n,
         {i, 1, Length[p]}];
      LCM @@ f
   ]

The code takes only 0.03 s, compared with 31 s for the While loop.

RepeatedTiming[FibPoly2Mod0[8417525], 10]

{0.0294806, 127380}

My tests so far suggest the conjecture is true...

$\endgroup$
1
$\begingroup$

Shorter:

NestWhile[#+1&,1,Mod[Fibonacci[#,2],8417525]!=0&]

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.