This answer currently ignores solutions involving f[1]
and f[2]
, because they are trivial to find by hand:
f[1] + 1 = f[3]
f[2] + 1 = f[3]
f[1]*f[2] + 1 = f[3]
Additionally, by prepending these three factors to any other solution you can get three more solutions. E.g. if you have f[3] + 1 = f[4]
, then 3 more solutions are:
f[1]*f[3] + 1 = f[4]
f[2]*f[3] + 1 = f[4]
f[1]*f[2]*f[3] + 1 = f[4]
In fact, it appears that these 6 are the only solutions up to $F_{50}$ (unless I made a mistake, of course).
I first tried putting a system of equations into FindInstance
, but it's incredibly slow. Instead, it's much easier here to look for possible solutions manually, by checking in how many ways we can express starting from $F_t-1$ as a product of distinct Fibonacci numbers:
Needs["Combinatorica`"];
maxN = 21;
(* Lookup table of admissible Fibonacci numbers. *)
fibs = Fibonacci@Range@maxN
solutions = {};
For[n = 4, n < maxN, ++n,
(* Get the list of (F_n-1)'s prime factors. *)
factors = Join @@ ConstantArray @@@ FactorInteger[Fibonacci@n - 1];
(* Now we get all, not necessarily contiguous partitions of the factors from
which we reconstruct all possible decompositions into factors of F_n-1. *)
decompositions = Union[Sort /@ (Times @@@ # & /@ SetPartitions[factors])];
(* We retain only those decompositions that contain only distinct numbers, all
of which have to be Fibonacci numbers, and append them to the solutions. *)
solutions = Join[
solutions, {#, Fibonacci@n} & /@
Select[decompositions,
AllTrue[#, MemberQ[fibs, #] &] && Unequal @@ # &]]
];
solutions
(* {{{2}, 3}} *)
I admit there's a lot of syntactic sugar in there, so let me know if anything is unclear.
f[1]
andf[2]
separately? That is, for any solution with2<n1
there are three more solutions that also usef[1]
,f[2]
orf[1]*f[2]
. $\endgroup$ – Martin Ender Mar 4 '16 at 13:13f[1]
andf[2]
separately $\endgroup$ – MATIRMAK Mar 4 '16 at 13:45