2
$\begingroup$

How can I find the $c$ such

 Max[Fibonacci[Range[c]]] = 13

I tried Reduce but there is an error message

Reduce[Max[Fibonacci[Range[c]]] == 13, c, Integers]

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Select[Fibonacci[Range[100]], # < =13 &] // Length $\endgroup$ – bill s Oct 8 '17 at 15:09
  • $\begingroup$ if you are sure that the number belong to the sequence 'Solve[Fibonacci[x] == 13, x]' works, even if mathematica gives you a warning message that some solutions may not be found( there is only 1 solution anyway). $\endgroup$ – Alucard Oct 8 '17 at 15:46
  • 1
    $\begingroup$ @Alucard - Fibonacci is not limited to integer arguments. Fibonacci is real-valued for all real x. For example, Plot[{Fibonacci[x], 13}, {x, -13, 10}, PlotRange -> All] $\endgroup$ – Bob Hanlon Oct 8 '17 at 17:39
4
$\begingroup$
$Version

(* "11.2.0 for Mac OS X x86 (64-bit) (September 11, 2017)" *)

@Alucard suggested using Solve

Solve[Fibonacci[x] == 13, x]

(* Solve::ifun: Inverse functions are being used by Solve, so some solutions may 
  not be found; use Reduce for complete solution information.

{{x -> Root[{-13 + Fibonacci[#1] &, -12.5223655802437480606062641933}]}} *)

Although not the desired solution, this is a solution of the equation.

Fibonacci[-12.5223655802437480606062641933]

(* 13.0000000000000000000000000 *)

Restricting x to a positive range

Solve[{Fibonacci[x] == 13, 1 <= x <= 13}, x]

(* Solve::nint: Warning: Solve used numeric integration to show that the solution 
  set found is complete.

{{x -> 7}} *)

Restricting x to also be an integer eliminates the warning message

Solve[{Fibonacci[x] == 13, 1 <= x <= 13}, x, Integers]

(* {{x -> 7}} *)
$\endgroup$
  • $\begingroup$ This fails for large Fibonacci numbers like 31940434634990099905. $\endgroup$ – bbgodfrey Oct 8 '17 at 17:40
  • 1
    $\begingroup$ Solve[{Fibonacci[x] == 31940434634990099905, 1 <= x <= 200}, x, Integers] $\endgroup$ – Bob Hanlon Oct 8 '17 at 17:51
  • $\begingroup$ I see that I used too large a bound on x. Thanks. $\endgroup$ – bbgodfrey Oct 8 '17 at 17:57
  • $\begingroup$ @BobHanlon when i run Solve[Fibonacci[x] == 13, x] i get x->7 , why your solution is different? i am using version 11.1 $\endgroup$ – Alucard Oct 8 '17 at 19:18
  • $\begingroup$ @Alucard - it is a version difference. As stated in my answer, I used v11.2.0. I just checked with v11.1.1 and v10.4.1 and obtained the same result as you did with v11.1. The answer with v11.2.0 is not wrong ("some solutions may not be found"), merely different. There is nothing in the statement Solve[Fibonacci[x] == 13, x] that requires x to be integer. $\endgroup$ – Bob Hanlon Oct 8 '17 at 20:23
4
$\begingroup$

It seems simpler to calculate rather than solve:

Clear[invFib];
invFib::notFib = "`` is not a Fibonacci number";
invFib[F_Integer] := With[{ans = Round@Log[GoldenRatio, F Sqrt[5]]},
  ans /; Fibonacci[ans] == F]
invFib[F_Integer] := Null /; (Message[invFib::notFib, F]; False);

invFib[13]
(*  7  *)

invFib[Fibonacci[10^3]]
(*  1000  *)

invFib[Fibonacci[10^2] + 1]
(*
  invFib::notFib: 354224848179261915076 is not a Fibonacci number

  invFib[354224848179261915076]
*)

It only gives one solution to Fibonacci[c] == 1, though. But that could be made a hard-coded special case if desired.

$\endgroup$
3
$\begingroup$

One straightforward way is:

Select[Fibonacci[Range[100]], # <= 13 &] // Length 
7

If you don't want to calculate the whole range, reformulate as a minimization problem:

NMinimize[Abs[Max[Fibonacci[x]] - 13], x]
{8.40155*10^-10, {x -> 7.}}
$\endgroup$
  • $\begingroup$ The second solution fails for large Fibonacci numbers like 31940434634990099905. $\endgroup$ – bbgodfrey Oct 8 '17 at 17:41
  • $\begingroup$ In the minimization, Max is not needed. NMinimize[Abs[Fibonacci[x] - 13], x] suffices. $\endgroup$ – Bob Hanlon Oct 8 '17 at 17:42
  • 1
    $\begingroup$ @bbgodfrey - use the WorkingPrecision option: NMinimize[Abs[Fibonacci[x] - 31940434634990099905], x, WorkingPrecision -> 75] $\endgroup$ – Bob Hanlon Oct 8 '17 at 17:47
3
$\begingroup$

We can extend @MichaelE2's approach to work for all reals greater than 1 as follows. First construct an interpolating function for small values:

InverseFibonacciIF = NDSolveValue[
    {Fibonacci'[n[x]] n'[x] == 1, n[1] == 2},
    n,
    {x, 1, 100}
]

InverseFibonacciIF will return the inverse for the domain $1\leq x\leq 100$. For values of $x$ larger than 100 we can just use @MichaelE2's approximation. So, an approximate answer to the inverse of the Fibonacci is given by the following ansatz function:

ansatz[x_Integer] := If[x<100,
    With[{r=InverseFibonacciIF[x]}, If[Fibonacci[Round[r]]===x, Round[r], SetPrecision[r, 5]]],
    With[{r=Log[GoldenRatio, x Sqrt[5]]}, If[Fibonacci[Round[r]]===x, Round[r], SetPrecision[r, Min[2+Log10[x], 10]]]]
]
ansatz[x_] := If[x<100,
    SetPrecision[InverseFibonacciIF[x], 5],
    SetPrecision[Log[GoldenRatio, x Sqrt[5]], Min[2+Log10[x], 10]]
]

Now, that we have an approximate answer for all reals $x\geq 1$, we can use this in Root:

InverseFibonacci[x_?(GreaterEqualThan[1])] := Root[
    {Fibonacci[#] - x&, ansatz[x]}
]

Here are a few examples:

InverseFibonacci[13] //RepeatedTiming
InverseFibonacci[354224848179261915075] //RepeatedTiming
InverseFibonacci[354224848179261915076] //RepeatedTiming
InverseFibonacci[1234123019284712039487123048712304871234012384701238471203498712309487123048172034] //RepeatedTiming
N[Last @ %, 100]
Fibonacci[%]

{0.00001165, 7}

{0.000041, 100}

{0.000052, Root[{-354224848179261915076 + Fibonacci[#1] &, 100.0000000}]}

{0.000051, Root[{-1234123019284712039487123048712304871234012384701238471203498712309487123048172034 + Fibonacci[#1] &, 389.6921529}]}

389.6921528840252057657462642235668545582808149772397887018651599941173630555046083968116712648392913

1.2341230192847120394871230487123048712340123847012384712034987123094871230481720340000000000000000*10^81

And a plot:

Plot[InverseFibonacci[x], {x, 1, 1000}]

enter image description here

$\endgroup$
1
$\begingroup$

These also work.

CountsBy[Fibonacci[Range[10]], # <= 13 &] // First
(* 7 *)

c = 1; While[Fibonacci[c] <= 13, c++]; c - 1
(* 7 *)

So does this, if 13 is a Fibonacci number.

Position[Fibonacci[Range[10]], 13][[1, 1]]
(* 7 *)

Addendum: Timing

Out of curiosity, I timed the methods provided in the three answers here, but with the much larger upper bound, 31940434634990099905, the ninety-fifth Fibonacci number. Not surprisingly Position is fastest but works only when the upper bound is a Fibonacci number.

RepeatedTiming[Position[Fibonacci[Range[100]], 31940434634990099905][[1, 1]]]
(* {0.000015, 95} *)

Three other methods that also involve only computing and testing an array of Fibonacci numbers require almost identical times, 0.000070.

RepeatedTiming[c = 1; While[Fibonacci[c] <= 31940434634990099905, c++]; c - 1]

RepeatedTiming[CountsBy[Fibonacci[Range[100]], # <= 31940434634990099905 &] // First]

RepeatedTiming[Select[Fibonacci[Range[100]], # <= 31940434634990099905 &] // Length]

The last two perform algebraic computations and so, while elegant, are much slower.

RepeatedTiming[Solve[{Fibonacci[x] == 31940434634990099905, 1 <= x <= 100}, x, 
    Integers][[1, 1, 2]]]
(* {0.0036, 95} *)

RepeatedTiming[Round[NMinimize[Abs[Max[Fibonacci[x]] - 31940434634990099905], x, 
    WorkingPrecision -> 45][[2, 1, 2]]]]
(* {0.100, 95} *)

My thanks to Bob Hanlon for generalizing the last two methods to accommodate large numbers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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