login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #40 Aug 24 2023 10:41:04

%S 24,32,40,41,45,46,48,49,53,56,57,61,62,71,80,85,87,88,92,95,96,101,

%T 103,104,105,106,108,109,110,111,112,113,116,117,119,120,121,122,124,

%U 125,126,127,131,134,135,140,142,143,144

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

%C User vvg asked on Math StackExchange if this sequence is empty, by analogy with Lagrange's Four Square Theorem and Zeckendorf's Theorem (see links). As mentioned by user Empy2, 'most' of the positive integers belong to this sequence: 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 24 is a term, which can be seen as follows. The Fibonacci squares less than 24 are 0,1,4 and 9. We must use at least two 9s, as 24>9+4+4+4=21. But 24-18=6 is neither a square nor a sum of two Fibonacci squares. Hence, 24 has no representation of the required form.

%e 32 is a term, as follows. The Fibonacci squares less than 32 are 0,1,4,9, and 25. We cannot use 25 as 7 cannot be written with 3 Fibonacci squares. Therefore, we must have at least three 9s, but 32-9-9-9=5 is not a Fibonacci square. The result follows.

%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 nosWithoutReprs = (0 to max)

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

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

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

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

%K nonn

%O 1,1

%A _Calvin Khor_, Jul 20 2023