Mersenne, Fibonacci... are there other cases in which the existence of a given prime implies the existence of another prime?

There seems to be infinitely more such sequences.

I. Particular

Starting with $n=0$, note that for the Fibonacci numbers,

$$F_n = 0,1,1,2,\color{red}3,5,8,13,\dots\tag1$$

and $F_4=3$ does not have a prime index. Similarly for the Jacobsthal numbers,

$$J_n = 0, 1, 1, 3, \color{red}5, 11, 21, 43,\dots\tag2$$

with the similar exception $J_4=5$. (Indices for prime $J_n$ is A107036.). We also have the Pell numbers,

$$P_n = 0, 1, 2, 5, 12, 29, 70, 169,\dots\tag3$$

and if $P_n$ is prime, then $n$ is prime.

II. General

If we define the first family of the Lucas sequence,

$$U_n(P,Q) \equiv \frac{a^n-b^n}{a-b}$$

where $a,b$ are the roots of $x^2-Px+Q=0$, then,

$$U_n(1,-1) = \text{Fibonacci}\\ U_n(1,-2) = \text{Jacobsthal}\\ U_n(1,-3) = \text{A006130}\\ \vdots\\ U_n(2,-1) = \text{Pell}\\ U_n(3,-1) = \text{A006190}\\\vdots$$

so presumably appropriate members of the family behave similarly.


There is a prime-generating formula, but not a practical one.

Ghandhi's formula for the next prime: Let $Q$ be the product of the primes less than the odd prime $p$.(If $p=3$ then $Q=2.$)$$\text {Let }\quad S=-\frac {1}{2}+\sum_{d|Q}\frac {\mu (d)}{2^d-1}$$ where $\mu$ is the Mobius function.$$\text {Then }\quad 1<2^pS<2.$$ Since $2^{p-1}<1$ and $2<2^{p+1}$ this uniquely defines the natural number $p$.

To prove it write each term $\mu (d)/(2^d-1)=\mu (d)\sum_{n=1}^{\infty}2^{-n d}.$ Collect powers of $2$ in the sum over $d|Q.$ Using the property of $\mu$ that $\sum_{e|n}\mu(e)=0$ for $n>1$ we obtain $$S=\sum_{n\in T}2^{-n}$$ where $T=\{m:m>1\land \gcd (m,Q)=1\}.$ From the def'n of $Q$ we have $\min T=p$, and all members of $T$ are odd, so $$2^{-p}<S\leq 2^{-p}(1+1/2^2+1/2^4+...)=2^{-p}(4/3)<2^{1-p}.$$

This is about as inefficient a way as possible for generating primes.E.g. to to find the least prime greater than $1,000,000$ with this formula, you need to know all the primes less than $1,000,000$, and sum all the terms in the formula. Since there are about $72,000$ primes below $1,000,000$ this means adding about $2^{72,000}$ terms to get $S$.