A374166 The set of primes p such that, for all integers m, the prime p divides at least one term of the recursive sequence (b_0, b_1, b_2, ...) given by b_0 = m and b_{k+1} = b_k^2 - 1 for k >= 0.

2, 3, 7, 23, 19207

Offset

1,1

Comments

It is an open problem (proposed by Michael Stoll) whether this sequence is infinite.

a(6) (if it exists) is greater than 5*10^6.

a(6), if it exists, is greater than 4*10^8. - Charles R Greathouse IV, Mar 13 2025

Links

Table of n, a(n) for n=1..5.

Ivan Penkov and Michael Stoll, Prime numbers and dynamics of the polynomial x^2-1, arXiv:2502.11929 [math.NT], 2025. See p. 2.

Michael Stoll, Collected Problems from the Problem Session, Rational Points 2023, Workshop at Franken-Akademie Schloss Schney. See Question 13 on page 5.

Example

To determine whether the prime p is included in the above sequence, it suffices to compute (b_0, b_1, b_2, ...) modulo p for the initial terms m = 0, 1, ..., p-1, and check whether 0 is contained in each of these mod p sequences.
For p = 2, the mod 2 sequences for m = 0, 1, are:
  m = 0: (b_0 mod 2, b_1 mod 2, ...) = (0, 1, 0, 1, ...)
  m = 1: (b_0 mod 2, b_1 mod 2, ...) = (1, 0, 1, 0, ...)
  Thus a(1) = 2.
For p = 3, the mod 3 sequences for m = 0, 1, 2, are:
  m = 0: (b_0 mod 3, b_1 mod 3, ...) = (0, 2, 0, 2, ...)
  m = 1: (b_0 mod 3, b_1 mod 3, ...) = (1, 0, 2, 0, ...)
  m = 2: (b_0 mod 3, b_1 mod 3, ...) = (2, 0, 2, 0, ...)
  Thus a(2) = 3.
For p = 5, the mod 5 sequence for m = 2 is:
  m = 2: (b_0 mod 5, b_1 mod 5, ...) = (2, 3, 3, 3, ...)
  which does not contain 0.  Thus a(3) > 5.

Prog

(Sage)
def is_A374166(p):
    if not Integer(p).is_prime(): return False
    for m in range(2, p):
        a = m
        for i in range(p):
            if a%p==0: break
            a = (a^2-1)%p
        else: return False
    return True
print([p for p in range(1, 20000) if is_A374166(p)])
(PARI) helper(m, startAt)=my(power=1, len=1, tortoise=startAt, hare=(startAt^2-1)%m); while(tortoise!=hare, if(power==len, tortoise=hare; power<<=1; len=0); hare=(hare^2-1)%m; len++); tortoise=hare=startAt; for(i=1, len, hare=(hare^2-1)%m; if(hare==0, return(0))); while(tortoise!=hare, hare=(hare^2-1)%m; if(hare==0, return(0)); tortoise=(tortoise^2-1)%m); 1;
is(p)=for(k=2, p-1, if(helper(p, k), return(0))); isprime(p) \\ Charles R Greathouse IV, Mar 03 2025

Crossrefs

Sequence in context: A102710 A048824 A355015 * A099073 A129724 A358496

Adjacent sequences: A374163 A374164 A374165 * A374167 A374168 A374169

Keyword

nonn,hard,more,changed

Author

Robin Visser, Jun 29 2024

Status

approved