OEIS A400659

The sequence

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

In the notation of the paper, where $Y_k(n)=p_{k-1}\mathrm{\#}\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, …

Together, the rows of the minus face form the square array A401136, read by antidiagonals. $a(n)$ is the position of the first prime in row $n$ of that array.

• $a(1)=2$: row 1 is the Mersenne numbers $2^n-1$; $Y_1(1)=1$ is not prime and $Y_1(2)=3$ is.
• $a(k)=1$ exactly when the primorial number $p_k\mathrm{\#}-1$ is prime, that is, when $k$ is in A057704.
• It is not known whether every row contains a prime. The entry would list $-1$ for a row without one; none is known.

How each term is proved

Write $N_k=\mathrm{A}002110(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<k$, either a prime $p<{10}^5$ with $p\mid N_j$ and $p<N_j$ is found, or a base $b$ with $gcd(b,N_j)=1$ and $b^{N_j-1}\not\equiv 1(\mathrm{mod}{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{A}002110(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^2\equiv D(\mathrm{mod}4)$, with $Q_q=(P_q^2-D)/4$, such that

$$gcd(2Q_q,N)=1,U_{N+1}(P_q,Q_q)\equiv 0(\mathrm{mod}N),gcd(U_{(N+1)/q}(P_q,Q_q),N)=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,\dots$ in order, proves every smaller exponent composite (for $n=1$, that $N_1=1$ is not prime) 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. These are whole-program timings for the stated runs; they do not isolate multiplication speed. 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 implement the same procedure with separate arithmetic: 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. If neither a compositeness witness nor a Lucas proof is found, the GP program reports PARI's own isprime verdict and the Python program stops with a message; neither happens for $n\le 100$.

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 (tested with PARI/GP 2.17.3 and Python 3.13). The Python program uses only the standard library; if the optional gmpy2 package is installed it runs faster. Both are free software.

Term table

The table uses the site's coordinates: order $k$ and exponent $n$. Each $a(k)$ is the first exponent with $Y_k(n)$ prime; all smaller exponents are shown nonprime by the verification programs above. In row 1, $Y_1(1)=1$ is neither prime nor composite.

All 100 terms at the OEIS (b-file). Select a prime below to compute its exact value in Explore the Grid.

Scope

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