2023 RPN HHC Programming Contest

[Thomas Klemm]

(10-09-2023 01:24 PM)Allen Wrote:  I also respect Thomas's clever solution based on OEIS A254308!

I didn't start with a search, but I remembered that \(\frac{71}{41}\) is a pretty good approximation for \(\sqrt{3}\).
And so I tried to get smaller numbers by running the Fibonacci-like sequence backwards with:

Code:

01 ST-Y
02 X<>Y
03 END

To avoid negative values I had to swap \(x\) and \(y\) every now and then, but in the end I came up with:

y: 1
x: 1

That's a good starting point, I thought and reversed the process.
And then it occurred to me that I could make the main sequence a little shorter.

Only after I created the sequence did I look up if there was an easier way to do this.
But I couldn't find anything that would help.

We can generate increasingly better approximations for \(\sqrt{3}\) if we start with \(x = y = 1\) and iterate the following program:

Code:

01 +
02 ST+ L
03 LASTX
04 ST+ Y
05 END

y: 1
x: 1

R/S

y: 5
x: 3

R/S

y: 19
x: 11

R/S

y: 71
x: 41

R/S

y: 265
x: 153

R/S

y: 989
x: 571

R/S

y: 3,691
x: 2,131

R/S

y: 13,775
x: 7,953

Their quotient converge quite fast:

1.000000000
1.666666667
1.727272727
1.731707317
1.732026144
1.732049037
1.732050680
1.732050798
1.732050807
1.732050808
1.732050808
…

The reason is that these are the convergents of the periodic continued fraction of \(\sqrt{3} = [1;\overline{1,2}]\):

\(
\begin{align}
\frac{1}{1} &= [1;] \\
\\
\frac{5}{3} &= [1;1,2] \\
\\
\frac{19}{11} &= [1;1,2,1,2] \\
\\
\frac{71}{41} &= [1;1,2,1,2,1,2] \\
\cdots
\end{align}
\)

Thanks a lot for creating this contest and also for the many interesting contributions.