A400659 · Yagel Numbers

The sequence

OEIS A400659: $a(n)$ is the least $k \ge 1$ such that $\mathrm{A002110}(n-1)\cdot \mathrm{prime}(n)^{k} - 1$ is prime.

In the notation of the paper, where $Y_k(n) = p_{k-1}\#\cdot p_k^{\,n} - 1$ , the OEIS index $n$ is the order $k$ and the OEIS variable $k$ is the exponent $n$ : $a(n)$ is the exponent of the first prime in row $n$ of the minus face. The first terms are 2, 1, 1, 3, 1, 1, 2, 5, 5, 4, 16, 4, 1, 12, 9, …

How each term is proved

Write $N_k = \mathrm{A002110}(n-1)\cdot \mathrm{prime}(n)^{k} - 1$ . A term $a(n) = k$ is established by two kinds of proof.

Every smaller exponent is composite. For each $j \lt k$ , either a prime $p \lt 10^5$ with $p \mid N_j$ and $p \lt N_j$ is found, or a base $b$ with $\gcd(b, N_j) = 1$ and $b^{N_j-1} \not\equiv 1 \pmod{N_j}$ is exhibited. No prime satisfies the second condition either, so $N_j$ is composite. (For $n = 1$ , $N_1 = 1$ is not prime by definition.)
$N_k$ is prime, by the Lucas $N+1$ test. It applies because $N_k + 1 = \mathrm{A002110}(n-1)\cdot \mathrm{prime}(n)^{k}$ is completely factored: its prime factors are the first $n$ primes.

The Lucas $N+1$ test (Lucas; Lehmer; Brillhart, Lehmer and Selfridge, 1975). Let $N \ge 3$ be odd with $F = N + 1$ completely factored. Suppose there is one integer $D$ with $\gcd(D, N) = 1$ and $\left(\frac{D}{N}\right) = -1$ , and for every prime $q \mid F$ an integer $P_q \equiv D \pmod 2$ , with $Q_q = (P_q^2 - D)/4$ , such that

$\gcd(2Q_q, N) = 1,\qquad U_{N+1}(P_q, Q_q) \equiv 0 \pmod N,\qquad \gcd\big(U_{(N+1)/q}(P_q, Q_q),\, N\big) = 1,$

where $U_0 = 0$ , $U_1 = 1$ , $U_{m+1} = P\,U_m - Q\,U_{m-1}$ . Then every prime $r \mid N$ satisfies $N + 1 \mid r - \left(\frac{D}{r}\right)$ , so $r \ge N$ and $N$ is prime. The discriminant $D$ must be the same for every $q$ ; only $P_q$ may change. That is what lets the conditions for the different $q$ combine into the single divisibility by $N+1$ .

Check it yourself

Two self-contained programs re-prove every term on your own computer. Neither needs any data from this site:

A400659.gp, for PARI/GP;
A400659.py, for Python.

For each $n \le 100$ , each program finds $a(n)$ by testing $k = 1, 2, \ldots$ in order, proves every smaller exponent composite and the term itself prime as described above, prints the witnesses it used, and compares the result with the 100 terms of the b-file, which are embedded in the program.

gp -q A400659.gp
python A400659.py

The last line of the output is

OK: a(1)..a(100) proved and equal to the b-file. Total 184 s.

Times measured on one core of a desktop PC: PARI/GP 2.17.3, 184 s; Python 3.13 with gmpy2, 119 s; Python 3.13 with the standard library only, 1,017 s (Python's built-in integers multiply large numbers about ten times more slowly than the GMP library behind PARI and gmpy2). Most of it is the last term: $a(100)$ needs 1,278 composites of up to 3,713 digits (543 settled by a prime factor below $10^5$ , 735 by a Fermat test) and a Lucas proof with 100 primes $q$ . Each line says how the smaller exponents were shown composite and gives $D$ , the common $P$ and any primes $q$ that needed a different $P$ . For example:

n=1  a(n)=2  digits=1  k=1 gives N=1 (not prime)  |  k=2 prime: Lucas N+1, D=5, P=1  [0 ms]
n=2  a(n)=1  digits=1  no smaller k  |  k=1 prime: Lucas N+1, D=-7, P=1  [0 ms]
n=4  a(n)=3  digits=5  k<3 composite (2 with a prime factor below 10^5)  |  k=3 prime: Lucas N+1, D=-7, P=1, except (q,P)=[[2, 7]]  [0 ms]
n=26  a(n)=65  digits=167  k<65 composite (38 with a prime factor below 10^5, 26 by a Fermat test, bases [2])  |  k=65 prime: Lucas N+1, D=-7, P=1, except (q,P)=[[83, 9]]  [47 ms]
n=100  a(n)=1279  digits=3713  k<1279 composite (543 with a prime factor below 10^5, 735 by a Fermat test, bases [2])  |  k=1279 prime: Lucas N+1, D=-7, P=1, except (q,P)=[[2, 7]]  [141891 ms]

The two programs were written independently: separate prime tables, small-factor tests, Jacobi symbols and arithmetic in the quadratic ring. They use the same search order for $D$ and $P$ , so they print the same lines apart from the timings. Each is therefore a check on the other.

Shorter runs. python A400659.py 30 checks $n \le 30$ . In gp, delete the two final lines of the file (verify(); and quit;), load it with \r A400659.gp and call verify(30). Also in gp, crossCheck(1, 60) re-proves the primes at $k = a(n)$ with PARI's own isprime, which shares nothing with the Lucas $N+1$ code. It is slower: the 900-digit term $a(56) = 329$ takes about two minutes.

Stack size. The gp program raises PARI's stack limit itself (parisizemax, 1 GB). The one-line program in the OEIS entry needs the same setting for larger $n$ : with gp's default 8 MB stack, isprime stops with “the PARI stack overflows” at $n = 31$ , whose term is a 529-digit prime. Run default(parisizemax, 2^30) first.

Requirements. PARI/GP 2.13 or later, or Python 3.8 or later. The Python program uses only the standard library; if the optional gmpy2 package is installed it runs faster. Both are free software.

Scope

The terms $a(1), \ldots, a(100)$ are proved: each is the result of the computation above, which anyone can repeat. The largest, $a(100) = 1279$ , is a 3,713-digit prime. It is not known whether $a(n)$ exists for every $n$ .