cp's OEIS Frontend

A295784 Length of the longest arithmetic progression in squares mod n with slope coprime to n.

%I A295784 #23 Mar 15 2025 02:36:36
%S A295784 2,2,3,2,3,2,2,3,3,2,4,3,2,2,5,2,4,2,2,3,5,2,3,3,2,2,4,2,4,2,2,5,3,2,
%T A295784 4,4,2,2,5,2,5,2,2,5,5,2,3,3,2,2,6,2,3,2,2,4,5,2,5,4,2,2,3,2,6,2,2,3,
%U A295784 7,2,9,4,2,2,3,2,6,2,2,5,7,2,3,5,2,2,5,2,3,2,2,5,3,2,9,3,2,2,7,2,7,2,2,6,6
%N A295784 Length of the longest arithmetic progression in squares mod n with slope coprime to n.
%C A295784 The sequence reaches 2 infinitely many times as a(4*n)=2. (If we had a(4*n)>=3, it would imply a(4)>=3, but a(4)=2. This comes from the fact that a(m*n)<=a(m) for m,n>=3.)
%H A295784 Tom Hejda, <a href="/A295784/b295784.txt">Table of n, a(n) for n = 3..20000</a>
%H A295784 MathOverflow user Seva, <a href="https://mathoverflow.net/a/161279/43387">Consecutive non-quadratic residues</a> (Proves that a(n) is unbounded.)
%e A295784 For n=17 we have residues {0,1,2,4,8,9,13,15,16} and the following arithmetic progressions of length 5: (15, 16, 0, 1, 2), (13, 15, 0, 2, 4), (9, 13, 0, 4, 8)
%o A295784 (SageMath)
%o A295784 def a(n) :
%o A295784     if n in [1,2] : return Infinity
%o A295784     R = quadratic_residues(n)
%o A295784     return max( next( m for m in itertools.count() if (a+(b-a)*m)%n not in R ) \
%o A295784       for a,b in zip(R,R[1:]+R[:1]) if gcd(b-a,n) == 1 )
%Y A295784 Bounded by A000224.
%Y A295784 Cf. A216869.
%K A295784 nonn
%O A295784 3,1
%A A295784 _Tom Hejda_, Nov 27 2017