6
$\begingroup$

I am studying the basic theory about continued fractions and also reviewed here at MSE former questions to learn more. While reviewing the questions and answers, I found references to the Fibonacci numbers and their continued fractions, so I wondered if there was some special advantage on using continued fractions for Fibonacci-Lucas ($F_n$) or Catalan ($C_n$) primality testing (or at least if there is a different new point view of the primality of a number). In other words:

Is there an advantage on testing the pattern of the continued fraction of $\frac{C_n}{n}$ instead of testing the values of ($C_n$ mod $n$)?

In the past I made a two steps primality test (link) based on a shifted version of Catalan numbers (for each odd $n$, instead of using $C_n$, testing the residues of $C_{\lfloor \frac{n}{2}\rfloor}$) and Fibonacci numbers (to verify that the pseudoprimes of the Fibonacci and Catalan primality tests are disjoint sets), both steps based on the residues of $F_n$ and $C_{\lfloor \frac{n}{2}\rfloor}$ mod $n$.

Instead of studying the residues now I wanted to know how the continued fraction of $\frac{C_{\lfloor \frac{n}{2}\rfloor}}{n}$ looks like, so I did the exercise and observed that there are two families of prime numbers ($\forall p \in \Bbb P \gt 7$), following the patterns:

$p_i \to \frac{C_{\lfloor \frac{p_i}{2}\rfloor}}{p_i}=[b_i;3,k_i,l_i]\ \ \ \{b_i,k_i,l_i\} \gt 0 \in \Bbb N\ $ and $\ (k_i+l_i) \lt (k_j+l_j)\ \forall\ p_j \gt p_i$ (same pattern).

$p_m \to \frac{C_{\lfloor \frac{p_m}{2}\rfloor}}{p_m}=[b_m;4,k_m]\ \ \ \{b_m,k_m\} \gt 0 \in \Bbb N\ $ and $\ k_m \lt k_r\ \forall\ p_r \gt p_m$ (same pattern).

... where $[a;b,c..,z]$ is the usual notation for continued fractions.

E.g.:

Examples of $p_i=[b_i;3,k_i,l_i]$:

$19 \to \frac{C_{\lfloor \frac{19}{2}\rfloor}}{19}=[75;3,1,4]$, and $\sum\{1,4\}=5$

$23 \to \frac{C_{\lfloor \frac{23}{2}\rfloor}}{23}=[730;3,1,5]$, and $\sum\{1,5\}=6$

$31 \to \frac{C_{\lfloor \frac{31}{2}\rfloor}}{31}=[86272;3,1,7]$, and $\sum\{1,7\}=8$

Examples of $p_m=[b_m;4,k_m]$:

$37 \to \frac{C_{\lfloor \frac{37}{2}\rfloor}}{37}=[3503913;4,9]$, and $k_{37}=9$

$53 \to \frac{C_{\lfloor \frac{53}{2}\rfloor}}{53}=[91734837763;4,13]$, and $k_{53}=13$

When I tested this with Python, I was very happy to observe that it works like the standard Catalan primality test ($\forall p \in \Bbb P \gt 7$), including exactly the primes and the Catalan pseudoprimes only (the first one is $5907$ OEIS A163209). So it seems that verifying the patterns above in the continued fractions is equivalent to a standard primality test based on the residues of the Catalan numbers.

Here is the Python code:

def frac():
    from gmpy2 import is_prime, mul, divexact, fac, add, c_mod, xmpz, sub

    def makefrac(vara,varb):

        a = vara
        b = varb

        mf = []

        while c_mod(a,b)!=0:
            mf.append(a//b)
            newa = add(a,-mul(a//b,b))
            temp = b
            b = newa
            a = temp

        mf.append(a//b)

        return mf

    test_init, test_limit = xmpz(9), xmpz(10000)
    catalan_number,divisible_four  = xmpz(1),True

    sumcheckl = 0
    sumchecks = 0
    for n in range (test_init,test_limit,2):

        catalan_number = divexact(mul(catalan_number, sub(n,4)), xmpz(n)>>2) if divisible_four else divexact(mul(catalan_number, sub(n,4)), xmpz(n)>>1)<<1
        divisible_four = not divisible_four

        myf = makefrac(catalan_number,n)        

        if ((len(myf)==4) and (myf[1]==3)) or ((len(myf)==3) and (myf[1]==4)):
            mysum = 0           
            if (len(myf)==4):
                mysum = myf[2]+myf[3]
                if sumcheckl == 0:
                    sumcheckl = mysum
                elif mysum < sumcheckl:
                    continue
                else:
                    sumcheckl = mysum
            else:
                mysum = myf[2]
                if sumchecks == 0:
                    sumchecks = mysum
                elif mysum < sumchecks:
                    continue
                else:
                    sumchecks = mysum

            if is_prime(n):
                print("Prime found: " + str(n)+"\t" + str(mysum))
            else:
                print("Pseudoprime found: " + str(n)+"\t" + str(mysum))

frac()

I do not understand the theory behind these observations, so please I would like to ask the following questions:

  1. Is it possible to know why the specific pattern of the continued fraction implies the same result as the Catalan primality test over the residues of the number?

  2. Could this approach be an advantage versus studying the primality of a number via residues like in Catalan and Fibonacci-Lucas primality tests? (could it be another way of defining the primality test?)

Please let me know if there are errors in the calculations or assumptions and I will update the question. Any hints are very welcomed. Thank you!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.