login
A295784
Length of the longest arithmetic progression in squares mod n with slope coprime to n.
1
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
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
KEYWORD
nonn
AUTHOR
Tom Hejda, Nov 27 2017
STATUS
approved