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

%I #20 Dec 01 2017 15:20:20

%S 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 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 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 Length of the longest arithmetic progression in squares mod n with slope coprime to n.

%C The sequence reaches 2 infinitely many times as a(4n)=2. (If we had a(4n)>=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 Tom Hejda, <a href="/A295784/b295784.txt">Table of n, a(n) for n = 3..20000</a>

%H MathOverflow user Seva, <a href="https://mathoverflow.net/a/161279/43387">Consecutive non-quadratic residues</a> (Proves that a(n) is unbounded.)

%e 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 (SageMath)

%o def a(n) :

%o if n in [1,2] : return Infinity

%o R = quadratic_residues(n)

%o return max( next( m for m in itertools.count() if (a+(b-a)*m)%n not in R ) \

%o for a,b in zip(R,R[1:]+R[:1]) if gcd(b-a,n) == 1 )

%Y Bounded by A000224.

%Y Cf. A216869.

%K nonn

%O 3,1

%A _Tom Hejda_, Nov 27 2017