Most mind-blowing program for your favorite calculator

[Thomas Klemm]

(07-01-2022 02:12 PM)Pälzer Wrote:  is such a calculation also possible with a solver like the HP-17bII ?

I came up with the following equation:

GCD:GCD=0×(A+B+Σ(I:1:LN(SQRT(5)×A)÷LN((SQRT(5)+1)÷2):1:IF(B<>0:L(R:MOD(A:B))+L(A:B)+L(B:G(R)):0)))+A

To make it more readable we can format it like so:

GCD:GCD=0×(
  A+B+Σ(
    I:
    1:
    LN(SQRT(5)×A)÷LN((SQRT(5)+1)÷2):
    1:
    IF(B<>0:
      L(R:MOD(A:B))+L(A:B)+L(B:G(R)):
      0
    )
  )
)
+A

We can use the Σ function instead of a for-loop.
But gcd is usually implemented with a while-loop:

Code:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

What should be used as limits in the for-loop?
Of course we could just loop from 1 to a.
But can we do better?

The worst case is to have two consecutive Fibonacci numbers.
From this we can make a better estimate for the needed number of loops.

There's a closed formula:

\(
F_{n}=\frac{\varphi^{n}-\psi^{n}}{\sqrt {5}},
\)

where

\(
\varphi = \frac{1+\sqrt{5}}{2}\approx 1.61803\,39887\ldots
\)

is the golden ratio, and \(\psi\) is its conjugate:

\(
\psi = \frac{1-\sqrt {5}}{2}=1-\varphi =-{1 \over \varphi }\approx -0.61803\,39887\ldots .
\)

But for \(n\) big enough we can ignore \(\psi^{n}\) as it goes to \(0\).

We end up with:

\(
a=\frac{\varphi^{n}}{\sqrt {5}},
\)

This can be solved for \(n\):

\(
n = \frac{\log(\sqrt{5} a)}{\log(\varphi)}
\)

Only if \(B \ne 0\) the remainder \(R\) is calculated:

    IF(B<>0:
      L(R:MOD(A:B))+L(A:B)+L(B:G(R)):
      0
    )

The equivalent code in Python would be:

Code:

if b != 0:
    r = a % b
    a = b
    b = r

But we are not interested in that sum, but only in A.
Thus the expression is multiplied by \(0\) and we end up with:

GCD=0×(…)+A

After verifying the equation you should end up with a menu like this:

[ GCD ][  A  ][  B  ]

Examples

112 A
63 B

GCD
CALCULATING...
GCD=7


144 A
89 B

GCD
CALCULATING...
GCD=1