25
$\begingroup$

Let an infinite sequence $S$ be a "Fibonacci-esque sequence" if, for all $n \geq 3, S(n) = S(n-1) + S(n-2).$ We can reduce $S$ modulo $1$ to get a "reduced Fibonacci sequence." These sequences can contain the element $0$, but not the element $1$. For example, the sequence $0.2, 0.6, 0.8, 0.4, 0.2, 0.6, 0.8, 0.4, ...$ is a reduced Fibonacci sequence with infimum $0.2.$ What is the largest possible infimum of a reduced Fibonacci sequence? What about reduced Fibonacci sequences containing only rational numbers?

In one of the answers, a sequence of reduced Fibonacci sequences was presented with infima approaching $\frac{1}{3}$.

The reduced Fibonacci sequence $\frac{19104}{64079}, \frac{39071}{64079}, \color{red}{\frac{58175}{64079}}, \frac{33167}{64079}, \frac{27263}{64079}, \color{red}{\frac{60430}{64079}}, \frac{23614}{64079}, \frac{19965}{64079}, \frac{43579}{64079}, \color{red}{\frac{63544}{64079}}, \frac{43044}{64079}, \frac{42509}{64079}, \frac{21474}{64079}, \color{red}{\frac{63983}{64079}}, \frac{21378}{64079}, \frac{21282}{64079}, \frac{42660}{64079}, \color{red}{\frac{63942}{64079}}, \frac{42523}{64079}, \frac{42386}{64079}, \frac{20830}{64079}, \color{red}{\frac{63216}{64079}}, \frac{19967}{64079}, \frac{19104}{64079}, \frac{39071}{64079}, …$ which contains only rational numbers, has infimum $\frac{19104}{64079}$ and period $23.$ It is best up to denominator $75000$.

The best known cases are those in this conjecture that I made.

I have highlighted all the "big" elements (above three times the infimum) in red, since they seem to have a pattern, appearing every $3$ or $4$ numbers, and this pattern seems worth analyzing.

I conjecture that for irrationals, the bound is $\frac{1}{3},$ and for rationals, the bound is $\frac{2}{3\sqrt{5}}.$

$\endgroup$
18
  • 9
    $\begingroup$ You're trying to find $a,b$ that maximize the minimum of $\{aF_n+bF_{n-1}\}$ where the $F_i$ are the Fibonacci numbers and $\{x\}$ is the fractional part. $\endgroup$ Aug 9, 2023 at 0:36
  • 7
    $\begingroup$ The Pisano period is the period of the Fibonacci sequence modulo $n$. It's tabulated at oeis.org/A001175 and the Pisano period of $682$ is $30$, which is quite small (and you have found a sequence with the smaller period, $15$). Maybe $n$ with small period are the place to look. E.g., for $n=2584$, the period is $36$. Maybe worth trying to find something with denominator $2584$. $\endgroup$ Aug 9, 2023 at 1:57
  • 1
    $\begingroup$ Based on the comments from Gerry Myerson and mine, if rational numbers are to work, then Fibonacci sequence with some starting values with a certain $q$ (my comment) or $n$ (Gerry Meyerson comment) with some Pisano period should work. $\endgroup$
    – Balaji sb
    Aug 9, 2023 at 2:20
  • 1
    $\begingroup$ Does your program output other relatively good sequences, not just a new "best"? It could be interesting to look at other examples. $\endgroup$
    – aschepler
    Aug 9, 2023 at 12:50
  • 1
    $\begingroup$ $64079$ is a Lucas number, oeis.org/A000032 $\endgroup$ Aug 12, 2023 at 23:32

6 Answers 6

13
+200
$\begingroup$

This provides an improved bound on the answer when you're allowed to have irrational values.

Let $\phi=\tfrac{1+\sqrt 5}2$ be the golden ratio. Let $S(1)=\tfrac 1 3+x$ and $S(2)=\tfrac 1 3 - \tfrac x \phi$.

Then $$ S(3)= \tfrac 2 3 + x(1-\tfrac 1\phi) = \tfrac 2 3 + x \phi^{-2}\\ S(4)=1+x(1-\tfrac 2\phi )=1-x \phi^{-3}\\ S(5)=\tfrac 5 3 +x(2-\tfrac 3\phi )=\tfrac 5 3+x \phi^{-4} $$

As you can see, the $x$ term keeps shrinking.

Because the period is even, the terms that are near integers (eg $S(4)$) always have a negative coefficient on $x$ -- so when you reduce modulo 1, you never get terms near 0, just terms near 1/3, 2/3, and slightly below 1.

You can set $x$ as small as you want to get the infinum as close to 1/3 as you want.

$\endgroup$
1
  • 3
    $\begingroup$ Your solution can be written succinctly as $S_n=F_n/3+x\psi^{n-1}, n\ge1$, $F_n$ is the Fibonacci number and $\psi=-1/\varphi$. $\endgroup$ Sep 4, 2023 at 21:15
6
$\begingroup$

Theorem $1$: Every reduced Fibonacci sequence contains terms less than $\frac{1}{2}$.

Proof: We proceed to prove this by contradiction. Let $S$ be a reduced Fibonacci sequence with no elements less than $\frac{1}{2}.$ Let $m$ be the least positive integer such that S contains elements less than $1 - \frac{1}{2^m}.$ Let $a_n$ be the first element less than $1 - \frac{1}{2^m}.$ Since all elements are above $\frac{1}{2}, a_n + a_{n+1} > 1,$ so $a_{n+2} = a_n + a_{n+1} - 1,$ which is less than $a_n$. Likewise, $a_{n+3}$ is also less than $a_n$. Therefore, $a_{n+4} = a_{n+2} + a_{n+3} - 1 \leq 2a_n - 1 \leq 2 - \frac{2}{2^m} - 1 = 1 - \frac{1}{2^{m-1}},$ so $a_{n+4} \leq 1 - \frac{1}{2^{m-1}}.$ This contradicts the fact that $m$ is the smallest positive integer with the above property. Thus proved.

Theorem $2$: Every reduced Fibonacci sequence consisting of only rational numbers is periodic, and therefore has a smallest element.

Proof: Let $d$ be the common denominator of the first two terms. Since subsequent terms are sums of previous terms, they all have common denominator $d.$ Therefore, the whole sequence has common denominator $d.$ Every pair of consecutive terms is preceded by a unique pair (or not preceded by a pair at all). Since there are only finitely many options for pairs of consecutive elements, one of them must be repeated at some point. If the first repeated pair is something other than the starting pair, then it has two possible preceding pairs, which is impossible. Therefore, the first pair to repeat is the starting pair. Since each pair is followed by a unique pair, the sequence keeps on repeating the same cycle of pairs. This means that the sequence is periodic, so each element appears infinitely many times. Since it contains only finitely many unique elements, it has a smallest element.

Theorem $3$: Every reduced Fibonacci sequence consisting of only rational numbers contains infinitely many terms greater than three times the infimum of the sequence ("big" elements).

Proof: Let $S$ be a reduced Fibonacci sequence. Let $a_n$ be the first occurrence of the smallest element such that $n \geq 3.$ This exists by Theorem $2.$

Case $1$: $a_{n+1} < a_n.$

This contradicts the fact that $a_n$ is the smallest element.

Case $2$: $a_n \leq a_{n+1} < 2a_n.$

In this case, $a_{n-1} = a_{n+1} - a_n < 2a_n - a_n < a_n,$ which contradicts the fact that $a_n$ is the smallest element.

Case $3$: $a_{n+1} \geq 2a_n$ and $a_n \geq \frac{1}{3}.$

In this case, since $a_n \geq \frac{1}{3}, 3a_n \geq 1,$ so $a_{n+1} + a_n \geq 1.$ Therefore, $a_{n+2} = a_n + a_{n+1} - 1,$ which is smaller than $a_n,$ contradicting the fact that $a_n$ is the smallest element. Thus proved.

Case $4$: $a_{n+1} \geq 2a_n$ and $a_n < \frac{1}{3}.$

In this case, by similar reasoning to the above, $a_{n+2}$ is a big element. Therefore, there is a big element. By Theorem $2$, this implies that there are infinitely many big elements.

It seems like a variation of the proof of Theorem $4$ can be used to prove it for irrationals, too.

$\endgroup$
1
  • $\begingroup$ I think that the study of these "big" elements can help with improving bounds for reduced Fibonacci sequences of rationals. $\endgroup$
    – mathlander
    Aug 10, 2023 at 19:41
4
+50
$\begingroup$

This may not contribute too much, but I can show that the minimum can't be $1/3$.

Suppose the minimum is $1/3$. For some $x$, the first $11$ terms $a_1,a_2,\dotsc,a_{11}$ in the sequence are $$ {1\over3},\ {1\over3}+x,\ {2\over3}+x,\ 2x,\ {2\over3}+3x,\ {2\over3}+5x,\ {1\over3}+8x,\ 13x,\ {1\over3}+21x,\ {1\over3}+34x,\ {2\over3}+55x $$ where all the terms are meant to be reduced modulo one.

From $a_2=(1/3)+x$ we deduce $0\le x<2/3$.

From $a_3=(2/3)+x$ we deduce $0\le x<1/3$.

From $a_4=2x$ we deduce $1/6\le x<1/3$.

From $a_5=(2/3)+3x$ we deduce $2/9\le x<1/3$.

From $a_6=(2/3)+5x$ we deduce $2/9\le x<4/15$.

We pause to notice that we have a strict inequality $x<4/15$; that will be important.

From $a_7=(1/3)+8x$ we deduce $1/4\le x<4/15$.

From $a_8=13x$ we deduce $10/39\le x<4/15$.

From $a_9=(1/3)+21x$ we deduce $10/39\le x<4/15$ (so no improvement on $a_8$).

From $a_{10}=(1/3)+34x$ we deduce $9/34\le x<4/15$.

From $a_{11}=(2/3)+55x$ we deduce $4/15\le x<4/15$, contradiction!

Unfortunately, this only rules out $1/3$, doesn't rule out any numbers around $1/3$.

$\endgroup$
3
  • 1
    $\begingroup$ Even though I already proved that $1/3$ is unattainable for rationals, this proof looks way easier to generalize to irrationals. However, this proof assumes that there is a minimum element, and that might not be true in the case of irrationals. $\endgroup$
    – mathlander
    Aug 12, 2023 at 15:30
  • 1
    $\begingroup$ True, though I would phrase it as, it proves that if $1/3$ appears in the sequence, then a smaller number must also appear. $\endgroup$ Aug 12, 2023 at 23:27
  • $\begingroup$ A smaller number must also appear within the next 10 terms. $\endgroup$
    – mathlander
    Aug 13, 2023 at 0:35
3
$\begingroup$

Conjectured family of rational sequences achieving (in the limit) infimum $\frac{2}{3\sqrt{5}}$:

We will use the standard indexing of Fibonacci numbers: that is, $F_0 = 0$ and $F_1 = 1.$ Define $L_n$ as $F_{n-1} + F_{n+1}.$

I conjecture (based on empirical evidence) that the reduced Fibonacci sequence starting with $\frac{2F_{8n-1} - 2}{3L_{8n-1}}$ and $\frac{F_{8n+2}-F_{8n-5} + 1}{3L_{8n-1}}$ for $n \geq 1$ has infimum $\frac{2F_{8n-1} - 2}{3L_{8n-1}}.$ This approaches $\frac{2}{3\sqrt{5}}$ as $n \rightarrow \infty.$

$\endgroup$
2
$\begingroup$

Your conjecture is true.

Your conjecture : The reduced Fibonacci sequence starting with $\frac{2F_{8n-1} - 2}{3L_{8n-1}}$ and $\frac{F_{8n+2}-F_{8n-5} + 1}{3L_{8n-1}}$ for $n \geq 1$ has infimum $\frac{2F_{8n-1} - 2}{3L_{8n-1}}.$

Let us define $a_n(m),b_n(m),c_n(m)$ as follows :

$$\begin{cases}a_{n}(1)=2F_{8n-1} - 2 \\a_n(2)=F_{8n+2}-F_{8n-5} + 1 \\a_{n}(m+2)=a_{n}(m+1)+a_{n}(m)\qquad (m\ge 1) \\b_n(m)=\left\lfloor\frac{a_n(m)}{3L_{8n-1}}\right\rfloor \\c_n(m)=a_n(m)-3L_{8n-1}b_n(m)\end{cases}$$

Then, the $m$-th term of your sequence can be written as $\dfrac{c_n(m)}{3L_{8n-1}}$.

Now, I'm going to prove the following claims.

Claim 1 : $a_{n}(m)=L_{m-1}F_{8n}+2L_{m-2}F_{8n-2}-F_{m-4}$

Claim 2 : $c_n(8n)=c_n(1)$ and $c_n(8n+1)=c_n(2)$

Claim 3 : $b_n(1)=0$, and for $2\le m\le 8n-1$, $$b_n(m)=\frac 23L_m-F_m-\begin{cases}1&\text{if $m\equiv 2,6\pmod 8$} \\\\\dfrac 23&\text{if $m\equiv 1,3,4\pmod 8$} \\\\\dfrac 13&\text{if $m\equiv 0,5,7\pmod 8$}\end{cases}$$

Claim 4 : For every $m=2,3,\cdots,8n-1$, $c_n(m)\gt c_n(1)$.

From the claims, we can say that your conjecture is true.


Claim 1 : $a_{n}(m)=L_{m-1}F_{8n}+2L_{m-2}F_{8n-2}-F_{m-4}$

Proof :

We have $a_n(1)=2F_{8n}-2F_{8n-2}-2$ and $a_n(2)=F_{8n}+4F_{8n-2}+1$. Let $\{A_m\},\{B_m\},\{C_m\}$ be the sequence with $A_{m+2}=A_{m+1}+A_m,B_{m+2}=B_{m+1}+B_m$ and $C_{m+2}=C_{m+1}+C_m$ with $A_1=2,A_2=1,B_1=-2,B_2=4,C_1=-2,C_2=1$ respectively. Letting $\alpha=\frac{1-\sqrt 5}{2}$ and $\beta=\frac{1+\sqrt 5}{2}$, we have $$A_{m+1}-\alpha A_m=\beta(A_m-\alpha A_{m-1})=\cdots =\beta^{m-1}(A_2-\alpha A_1)$$ and $$A_{m+1}-\beta A_m=\alpha(A_m-\beta A_{m-1})=\cdots =\alpha^{m-1}(A_2-\beta A_1)$$ Subtracting the latter from the former, we get $$A_m=\frac{A_2(\beta^{m-1}-\alpha^{m-1})+A_1(\beta^{m-2}-\alpha^{m-2})}{\beta-\alpha}=F_{m-1}+2F_{m-2}=L_{m-1}$$ Similarly, $$\begin{align}B_m&=\frac{B_2(\beta^{m-1}-\alpha^{m-1})+B_1(\beta^{m-2}-\alpha^{m-2})}{\beta-\alpha}=4F_{m-1}-2F_{m-2}=2L_{m-2} \\\\C_m&=\frac{C_2(\beta^{m-1}-\alpha^{m-1})+C_1(\beta^{m-2}-\alpha^{m-2})}{\beta-\alpha}=F_{m-1}-2F_{m-2}=-F_{m-4}\end{align}$$ These give $$a_n(m)=L_{m-1}F_{8n}+2L_{m-2}F_{8n-2}-F_{m-4}.\ \blacksquare$$


Claim 2 : $c_n(8n)=c_n(1)$ and $c_n(8n+1)=c_n(2)$

Proof :

It is sufficient to prove that $a_n(8n)\equiv a_n(1)\pmod{3L_{8n-1}}$ and $a_n(8n+1)\equiv a_n(2)\pmod{3L_{8n-1}}$.

Letting $s=L_{8n-1}$ and $t=L_{8n}$, we have $$\begin{align}&a_{n}(8n)-a_n(1) \\\\&\equiv sF_{8n}+2L_{8n-2}F_{8n-2}-F_{8n-4}-(2F_{8n}-2F_{8n-2}-2)\pmod{3s} \\\\&\equiv (s-2)F_{8n}+(2L_{8n-2}+2)F_{8n-2}-F_{8n-4}+2\pmod{3s} \\\\&\equiv (s-2)\frac{t+2s}{5}+(2t-2s+2)\frac{3s-t}{5}-\frac{7s-4t}{5}+2\pmod{3s}\end{align}$$

So, we obtain $$\begin{align}5(a_{n}(8n)-a_n(1))&\equiv 3s(-s+ 3t-1) -s^2 -2s- 2 t^2 + 10\pmod{3s} \\\\&\equiv -s^2-2s- 2 (sL_{8n+1}+5) + 10\pmod{3s} \\\\&\equiv (-s-2-2L_{8n+1})s\pmod{3s}\end{align}$$ Since $s\equiv 2\pmod 3,L_{8n+1}\equiv 1\pmod 3$ and $\gcd(3s,5)=1$, it follows that $a_n(8n)-a_n(1)\equiv 0\pmod{3s}$.

Next, we have $$\begin{align}&a_{n}(8n+1)-a_n(2) \\\\&\equiv L_{8n}F_{8n}+2L_{8n-1}F_{8n-2}-F_{8n-3}-(F_{8n}+4F_{8n-2}+1)\pmod{3s} \\\\&\equiv (L_{8n}-1)F_{8n}+(2L_{8n-1}-4)F_{8n-2}-F_{8n-3}-1\pmod{3s} \\\\&\equiv (t-1)\frac{t+2s}{5}+(2s-4)\frac{3s-t}{5}-\frac{3t-4s}{5}-1\pmod{3s}\end{align}$$

So, we obtain $$\begin{align}5(a_{n}(8n+1)-a_n(2))&\equiv 3s(2s-3)-s+ t^2 - 5\pmod{3s} \\\\&\equiv -s+ sL_{8n+1}+5 - 5\pmod{3s} \\\\&\equiv (L_{8n+1}-1)s\pmod{3s}\end{align}$$ Since $L_{8n+1}\equiv 1\pmod 3,\gcd(3s,5)=1$, it follows that $a_n(8n+1)-a_n(2)\equiv 0\pmod{3s}$.$\ \blacksquare$


Claim 3 : $b_n(1)=0$, and for $2\le m\le 8n-1$, $$b_n(m)=\frac 23L_m-F_m-\begin{cases}1&\text{if $m\equiv 2,6\pmod 8$} \\\\\dfrac 23&\text{if $m\equiv 1,3,4\pmod 8$} \\\\\dfrac 13&\text{if $m\equiv 0,5,7\pmod 8$}\end{cases}$$

Proof :

$b_n(m)$ is defined as $b_n(m)=\left\lfloor\frac{a_n(m)}{3L_{8n-1}}\right\rfloor$. So, it is sufficient to prove that $$\begin{align}P&:=a_n(m)-3L_{8n-1}b_n(m)\ge 0 \\\\Q&:=3L_{8n-1}b_n(m)+3L_{8n-1}-a_n(m)\gt 0\end{align}$$

Writing $b_n(m)=\frac 23L_m-F_m-C$, we have $$P=3CL_{8n-1}-F_{m-4}+\bigg(L_{m-1}F_{8n}+2L_{m-2}F_{8n-2}-2L_{8n-1}L_{m}+3L_{8n-1}F_{m}\bigg)$$

Here, using $$F_aL_b=F_{a+b}+(-1)^{b}F_{a-b},\quad L_aL_b=L_{a+b}+(-1)^bL_{a-b}$$ $$F_{-c}=(-1)^{c+1}F_c,\quad L_{-c}=(-1)^cL_c$$ we obtain $$P=3CL_{8n-1}-F_{m-4}+\underbrace{F_{8n+m-1}+2F_{8n+m-4}-2L_{8n+m-1}+3F_{8n+m-1}}_{=0}+(-1)^{m-1}\bigg(\underbrace{F_{8n-m+1}-2F_{8n-m}+2L_{8n-m-1}+3F_{8n-m-1}}_{=F_{8n-m+3}}\bigg)$$ which gives $$P=3CL_{8n-1}-F_{m-4}+(-1)^{m-1}F_{8n-m+3}$$

  • For $m\equiv 2,6\pmod 8$ with $C=1$, since $-F_{m-4}\ge -F_{8n-6}$ and $(-1)^{m-1}F_{8n-m+3}\ge -F_{8n+1}$, we get $P\ge 3L_{8n-1}-F_{8n-6}-F_{8n+1}=F_{8n}+4F_{8n-2}-F_{8n-6}\ge 0$.

  • For $m=1,3,4\pmod 8$ with $C=\frac 23$, since $-F_{m-4}\ge -F_{8n-8}$ and $(-1)^{m-1}F_{8n-m+3}\ge -F_{8n-1}$, we get $P\ge 2L_{8n-1}-F_{8n-8}-F_{8n-1}=2F_{8n}+F_{8n-4}-F_{8n-8}\ge 0$.

  • For $m=0,5,7\pmod 8$ with $C=\frac 13$, since $-F_{m-4}\ge -F_{8n-5}$ and $(-1)^{m-1}F_{8n-m+3}\ge -F_{8n-5}$, we get $P\ge L_{8n-1}-2F_{8n-5}=F_{8n}+F_{8n-2}-2F_{8n-5}\ge 0$.

Similarly, we get $$\begin{align}Q&=3L_{8n-1}(1-C)+F_{m-4}+\bigg(2L_{8n-1}L_{m}-3L_{8n-1}F_{m}-L_{m-1}F_{8n}-2L_{m-2}F_{8n-2}\bigg) \\\\&=3L_{8n-1}(1-C)+F_{m-4}+\underbrace{2L_{8n+m-1}-3F_{8n+m-1}-F_{8n+m-1}-2F_{8n+m-4}}_{=0} \\&\qquad+(-1)^m\bigg(\underbrace{2L_{8n-m-1}+3F_{8n-m-1}+F_{8n-m+1}-2F_{8n-m}}_{=F_{8n-m+3}}\bigg) \\\\&=3L_{8n-1}(1-C)+F_{m-4}+(-1)^{m}F_{8n-m+3}\end{align}$$

  • For $m\equiv 2,6\pmod 8$ with $C=1$, since $F_{m-4}\ge F_{-2}=-1$ and $(-1)^mF_{8n-m+3}\ge F_{5}=5$, we get $Q\ge -1+5=4\gt 0$.

  • For $m\equiv 1,3,4\pmod 8$ with $C=\frac 23$, since $F_{m-4}\ge F_{0}=0$ and $(-1)^mF_{8n-m+3}\ge -F_{8n}$, we get $Q\ge L_{8n-1}-F_{8n}=F_{8n-2}\gt 0$.

  • For $m\equiv 0,5,7\pmod 8$ with $C=\frac 13$, since $F_{m-4}\ge F_1=1$ and $(-1)^mF_{8n-m+3}\ge -F_{8n-2}$, we get $Q\ge 2L_{8n-1}+1-F_{8n-2}=2F_{8n}+F_{8n-2}+1\gt 0$.$\ \blacksquare$


Claim 4 : For every $m=2,3,\cdots,8n-1$, $c_n(m)\gt c_n(1)$.

Proof :

In a similar way to the one used in the proof of Claim 3, we have, writing $b_n(m)=\frac 23L_m-F_m-C$,

$$\begin{align}c_n(m)-c_n(1)&=3CL_{8n-1}-2F_{8n-1}-F_{m-4}+2 \\&\qquad +\bigg(L_{m-1}F_{8n}+2L_{m-2}F_{8n-2}-2L_mL_{8n-1}+3L_{8n-1}F_m\bigg) \\\\&=3CL_{8n-1}-2F_{8n-1}-F_{m-4}+2 \\&\qquad +\underbrace{F_{8n+m-1}+2F_{8n+m-4}-2L_{8n+m-1}+3F_{8n+m-1}}_{=0} \\&\qquad +(-1)^{m-1}\bigg(\underbrace{F_{8n-m+1}-2F_{8n-m}+2L_{8n-m-1}+3F_{8n-m-1}}_{=F_{8n-m+3}}\bigg) \\\\&=3CL_{8n-1}-2F_{8n-1}+(-1)^{m-1}F_{8n-m+3}-F_{m-4}+2\end{align}$$

  • For $m\equiv 2,6\pmod 8$ with $C=1$, since $(-1)^{m-1}F_{8n-m+3}\ge -F_{8n+1}$ and $-F_{m-4}\ge -F_{8n-6}$, we get $c_n(m)-c_n(1)\ge 3L_{8n-1}-2F_{8n-1}-F_{8n+1}-F_{8n-6}+2=3F_{8n-2}+F_{8n-4}-F_{8n-6}+2\gt 0$.

  • For $m\equiv 1,3,4\pmod 8$ with $C=\frac 23$, since $(-1)^{m-1}F_{8n-m+3}\ge -F_{8n-1}$ and $-F_{m-4}\ge -F_{8n-8}$, we get $c_n(m)-c_n(1)\ge 2L_{8n-1}-2F_{8n-1}-F_{8n-1}-F_{8n-8}+2=2F_{8n-2}+F_{8n-4}-F_{8n-8}+2\gt 0$.

  • For $m\equiv 0\pmod 8$ with $C=\frac 13$, since $(-1)^{m-1}F_{8n-m+3}\ge -F_{8n-5}$ and $-F_{m-4}\ge -F_{8n-12}$, we get $c_n(m)-c_n(1)\ge L_{8n-1}-2F_{8n-1}-F_{8n-5}-F_{8n-12}+2=F_{8n-6}-F_{8n-12}+2\gt 0$.

  • For $m\equiv 5,7\pmod 8$ with $C=\frac 13$, since $(-1)^{m-1}F_{8n-m+3}\ge F_{4}=3$ and $-F_{m-4}\ge -F_{8n-5}$, we get $c_n(m)-c_n(1)\ge L_{8n-1}-2F_{8n-1}+3-F_{8n-5}+2=F_{8n-6}+5\gt 0$.$\ \blacksquare$

$\endgroup$
0
$\begingroup$

Here is the Python program that I used to find the lower bound for rational numbers presented in the main post (now outdated):

import math

target = 203/682 # the previous best

def reduce(i,n):
    if i < n:
        return i
    else:
        return i - n

def checksuccess(n):
    b = math.floor(target*n) + 1
    for i in range(b, n//2 - 1):
        for j in range(2*i+1, n):
            current_1 = i
            current_2 = j
            while current_1 != -1:
                if current_2 < i:
                    break
                elif current_2 == i and reduce(current_1 + i, n) == j:
                    print(i,j,n)
                    break
                else:
                    current_2 = current_1 + current_2
                    current_1 = current_2 - current_1
                    current_2 = reduce(current_2, n)
            else:
                continue
    return 0

for i in range(1000, 10000):
    checksuccess(i)
    if i % 100 == 0:
        print(i)

It finds sequences of rational numbers with denominators between $1000$ and $10000$ that do better than the sequence $\frac{203}{682}, \frac{416}{682}, \color{red}{\frac{619}{682}}, \frac{353}{682}, \frac{290}{682}, \color{red}{\frac{643}{682}}, \frac{251}{682}, \frac{212}{682}, \frac{463}{682}, \color{red}{\frac{675}{682}}, \frac{456}{682}, \frac{449}{682}, \frac{223}{682}, \color{red}{\frac{672}{682}}, \frac{213}{682}, \frac{203}{682}, \frac{416}{682} ...,$ the previous best. It also prints its progress for every $100$ denominators that it completes.

Again, I have highlighted terms in red for pattern finding.

$\endgroup$
4
  • $\begingroup$ If you ignore 0's, can you do any better than 1/3? $\endgroup$
    – Alex K
    Aug 9, 2023 at 4:22
  • $\begingroup$ @AlexK It seems hard to make a version of my program which does that, but I don't think we can. $\endgroup$
    – mathlander
    Aug 9, 2023 at 19:04
  • 1
    $\begingroup$ @AlexK Isn't $0,1/2,1/2,0, 1/2, 1/2,\ldots$ repeating with a period of three the best if we ignor zeros? $\endgroup$ Aug 12, 2023 at 16:18
  • $\begingroup$ I think he meant ignore $0$'s at even positions, which looks relevant to his answer. $\endgroup$
    – mathlander
    Aug 12, 2023 at 16:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .