Prime Convergents of Continued Fractions

Background

For an irrational number $\zeta = [a_0; a_1, a_2, \ldots]$, the $n$-th convergent $C_n = A_n / B_n$ has numerators and denominators that grow exponentially with $n$. In 1939, Erdos and Mahler showed that for almost all $\zeta$, the greatest prime factor $G(B_n)$ of the denominator increases rapidly:

$G(B_n) \geq e^{n / (50 \ln n)} \quad \text{for all sufficiently large } n.$

Humphreys (2013, NCUR/Boise State) extended this to the numerator via Theorem 3.5 and Corollary 3.6, showing the corresponding result for $G(A_n)$. The original experimental verification was limited to 500 convergents of $n \cdot e$ and $n \cdot \pi$ for $n \leq 500$, computed in Maple.

What This Experiment Does

This GPU experiment massively extends the computational verification:

1. Random CF sampling: Generate hundreds of thousands of random CF expansions (partial quotients drawn from the Gauss-Kuzmin distribution) and compute all convergents until overflow
2. Primality testing: GPU-parallel deterministic Miller-Rabin (12 witnesses, valid for all 64-bit integers) on every numerator and denominator
3. Greatest prime factor: Trial division by primes up to 997 plus Miller-Rabin on the cofactor
4. Doubly-prime census: Count convergents where both $A_n$ and $B_n$ are prime — extending the observation from Humphreys (2013) Section 4

Each GPU thread handles one complete CF sequence independently. The B200’s 183 GB VRAM allows millions of simultaneous sequences.

Method

• Convergent recurrence: $A_n = a_n A_{n-1} + A_{n-2}$, $B_n = a_n B_{n-1} + B_{n-2}$, computed in 128-bit arithmetic (overflow at depth ~38-42 for typical CFs with Gauss-Kuzmin partial quotients)
• Primality: Deterministic Miller-Rabin with witnesses {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}, sufficient for all $n < 3.317 \times 10^{23}$
• GPF computation: Trial division by first 168 primes (up to 997), then primality check on remainder
• Modes: Random Gauss-Kuzmin CFs, CF of $e$ (known pattern), CF of $\pi$ (50 known terms + random)

Reproduce

nvcc -O3 -arch=sm_90 -o prime_convergents scripts/experiments/prime-convergents/prime_convergents.cu -lm
./prime_convergents 100000 500 0   # 100K random CFs, depth 500
./prime_convergents 1 500 1        # CF of e, depth 500
./prime_convergents 1 500 2        # CF of pi, depth 500

References

1. Erdos, P. and Mahler, K. (1939). “Some Arithmetical Properties Of The Convergents Of A Continued Fraction.” London Math. Soc., pp. 12-18.
2. Humphreys, C. (2013). “Prime Numbers and the Convergents of a Continued Fraction.” Proceedings of NCUR 2013, University of Wisconsin La Crosse.
3. Gauss, C.F. (1812). Disquisitiones generales circa seriem infinitam.

---

Extends Humphreys (2013) with GPU computation. Human-AI collaboration (Cahlen Humphreys + Claude). All code and data open.