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

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, 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, 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

Offset: 3

Author

Tom Hejda, Nov 27 2017

Keywords

• nonn

Comments

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.)

Examples

			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)
		

Links

• Tom Hejda, Table of n, a(n) for n = 3..20000
• MathOverflow user Seva, Consecutive non-quadratic residues (Proves that a(n) is unbounded.)

Crossrefs

Bounded by A000224.

Cf. A216869.

Programs

SageMath

def a(n) :
    if n in [1,2] : return Infinity
    R = quadratic_residues(n)
    return max( next( m for m in itertools.count() if (a+(b-a)*m)%n not in R ) \
      for a,b in zip(R,R[1:]+R[:1]) if gcd(b-a,n) == 1 )