login
Numbers that can be expressed as the sum of the squares of four Fibonacci numbers.
1

%I #27 Aug 21 2023 19:38:34

%S 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,25,26,

%T 27,28,29,30,31,33,34,35,36,37,38,39,42,43,44,47,50,51,52,54,55,58,59,

%U 60,63,64,65,66,67,68,69,70,72,73,74,75,76,77,78,79,81,82

%N Numbers that can be expressed as the sum of the squares of four Fibonacci numbers.

%C User vvg asked on Math StackExchange if there are any natural numbers outside this list, by analogy with Lagrange's Four Square Theorem and Zeckendorf's Theorem (see links, and complementary sequence A364353). Although the first 23 positive integers belong to this sequence, as mentioned by user Empy2, 'most' numbers cannot be written in this form: there are O(log n) Fibonacci squares below n, so there are at most O( (log n)^4 ) distinct sums below n, which is asymptotically much smaller than n.

%H Math StackExchange, <a href="https://math.stackexchange.com/q/4738778/80734">Is every integer representable as the sum of four Fibonacci squares?</a>.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LagrangesFour-SquareTheorem.html">Lagrange's Four-Square Theorem</a>.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ZeckendorfsTheorem.html">Zeckendorf's Theorem</a>.

%e Write F(n) for the n-th Fibonacci number (F(0) = 0). We omit writing 0s below. Then examples of numbers that can be written as a sum of the squares of 4 Fibonacci numbers are 0 = F(0)^2, 1 = F(1)^2, 2 = F(1)^2 + F(1)^2, 3 = F(1)^2 + F(1)^2 + F(1)^2 and 4 = F(3)^2 = F(1)^2 + F(1)^2 + F(1)^2 + F(1)^2, the first number with different representations (ignoring F(1) = 1 = F(2)).

%e If we write (n,a,b,c,d) with a<=b<=c<=d to mean that n = F(a)^2 + F(b)^2 + F(c)^2 + F(d)^2, then an exhaustive list of representations for the integers in [5,23] is (5,0,0,1,3), (6,0,1,1,3), (7,1,1,1,3), (8,0,0,3,3), (9,0,0,0,4), (9,0,1,3,3), (10,0,0,1,4) or (10,1,1,3,3), (11,0,1,1,4), (12,0,3,3,3), (13,0,0,3,4) or (13,1,3,3,3), (14,0,1,3,4), (15,1,1,3,4), (16,3,3,3,3), (17,0,3,3,4), (18,0,0,4,4) or (18,1,3,3,4), (19,0,1,4,4), (20,1,1,4,4), (21,3,3,3,4), (22,0,3,4,4), and (23,1,3,4,4). Among all integers up to 100,000, the only two numbers to have three representations are 178 with (178,0,4,4,5), (178,0,2,2,6), and (178,0,0,3,6); and 196 with (196,2,5,5,5), (196,3,3,3,6), and (196,0,0,4,6).

%e In the examples of the complementary sequence A364353, it is explained why 24 and 32 have no representation.

%t fibonacci = Table[Fibonacci[n]^2, {n, 1, 22}];

%t reverseFib[n_] :=

%t SubsuperscriptBox["F", Position[fibonacci, n][[1, 1]] - 1, 2] //

%t DisplayForm

%t subsets =

%t Tuples[fibonacci, 1]~Join~Tuples[fibonacci, 2]~Join~

%t Tuples[fibonacci, 3]~Join~Tuples[fibonacci, 4];

%t DeleteDuplicates[

%t SortBy[{Total[#], Total[reverseFib /@ #]} & /@ subsets,

%t First]] // TableForm

%o (Scala)

%o @main def main(args: Int*): Unit =

%o val max = 10000

%o def fibFrom(n: Int, m: Int): LazyList[Int] =

%o n #:: m #:: fibFrom(n + m, n + 2 * m)

%o val fib = fibFrom(0, 1)

%o def computeReprs(min: Int, max: Int) = (for

%o n <- min to max

%o f1 <- fib.takeWhile(f => f * f <= n)

%o f2 <- fib.dropWhile(_ < f1).takeWhile(f => f * f <= n - f1 * f1)

%o f3 <- fib

%o .dropWhile(_ < f2)

%o .takeWhile(f => f * f <= n - f1 * f1 - f2 * f2)

%o f4 = fib

%o .dropWhile(f => f * f < n - f1 * f1 - f2 * f2 - f3 * f3)

%o .head

%o if n == f1 * f1 + f2 * f2 + f3 * f3 + f4 * f4

%o yield (n +: Seq(f1, f2, f3, f4)

%o .filter(_ != 0)

%o .map(fib.indexOf(_)))).distinct

%o val reprs = computeReprs(0, max)

%o // printing out to console for creating b-file

%o val nosWithReprs = (0 to max)

%o .filter(i => reprs.exists(k => k(0) == i))

%o ((1 to nosWithReprs.length) zip nosWithReprs)

%o .foreach((p, q) => println(s"$p $q"))

%Y Cf. A000045, A007598, A364353 (complement).

%K nonn

%O 1,3

%A _Calvin Khor_, Jul 20 2023