A374166 - OEIS

%I #19 Sep 22 2025 16:01:36

%S 2,3,7,23,19207

%N 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.

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

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

%C a(6), if it exists, is greater than 4*10^8. - _Charles R Greathouse IV_, Mar 13 2025

%H Ivan Penkov and Michael Stoll, <a href="https://arxiv.org/abs/2502.11929">Prime numbers and dynamics of the polynomial x^2-1</a>, arXiv:2502.11929 [math.NT], 2025. See p. 2.

%H Michael Stoll, <a href="https://www.mathe2.uni-bayreuth.de/stoll/workshop2023/open_problems_2023.pdf">Collected Problems from the Problem Session</a>, Rational Points 2023, Workshop at Franken-Akademie Schloss Schney. See Question 13 on page 5.

%e 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.

%e For p = 2, the mod 2 sequences for m = 0, 1, are:

%e   m = 0: (b_0 mod 2, b_1 mod 2, ...) = (0, 1, 0, 1, ...)

%e   m = 1: (b_0 mod 2, b_1 mod 2, ...) = (1, 0, 1, 0, ...)

%e   Thus a(1) = 2.

%e For p = 3, the mod 3 sequences for m = 0, 1, 2, are:

%e   m = 0: (b_0 mod 3, b_1 mod 3, ...) = (0, 2, 0, 2, ...)

%e   m = 1: (b_0 mod 3, b_1 mod 3, ...) = (1, 0, 2, 0, ...)

%e   m = 2: (b_0 mod 3, b_1 mod 3, ...) = (2, 0, 2, 0, ...)

%e   Thus a(2) = 3.

%e For p = 5, the mod 5 sequence for m = 2 is:

%e   m = 2: (b_0 mod 5, b_1 mod 5, ...) = (2, 3, 3, 3, ...)

%e   which does not contain 0.  Thus a(3) > 5.

%o (SageMath)

%o def is_A374166(p):

%o     if not Integer(p).is_prime(): return False

%o     for m in range(2, p):

%o         a = m

%o         for i in range(p):

%o             if a%p==0: break

%o             a = (a^2-1)%p

%o         else: return False

%o     return True

%o print([p for p in range(1, 20000) if is_A374166(p)])

%o (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;

%o is(p)=for(k=2,p-1,if(helper(p,k),return(0))); isprime(p) \\ _Charles R Greathouse IV_, Mar 03 2025

%K nonn,hard,more

%O 1,1

%A _Robin Visser_, Jun 29 2024