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

Comments

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.

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

Example

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)

Prog

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

Crossrefs

Bounded by A000224.

Cf. A216869.

Sequence in context: A349197 A225416 A369871 * A275803 A060131 A343391

Adjacent sequences: A295781 A295782 A295783 * A295785 A295786 A295787

Keyword

nonn

Author

Tom Hejda, Nov 27 2017

Status

approved