A139401 If n is a square, a(n) is 0. Otherwise, a(n) is the smallest number k such that n is not a quadratic residue modulo k.

0, 3, 4, 0, 3, 4, 4, 3, 0, 4, 3, 5, 5, 3, 4, 0, 3, 4, 4, 3, 8, 4, 3, 7, 0, 3, 4, 5, 3, 4, 4, 3, 5, 4, 3, 0, 5, 3, 4, 7, 3, 4, 4, 3, 7, 4, 3, 5, 0, 3, 4, 5, 3, 4, 4, 3, 5, 4, 3, 9, 7, 3, 4, 0, 3, 4, 4, 3, 7, 4, 3, 5, 5, 3, 4, 7, 3, 4, 4, 3, 0, 4, 3, 9, 8, 3, 4, 5, 3, 4, 4, 3, 5, 4, 3, 7, 5, 3, 4, 0, 3, 4, 4, 3, 9

Offset: 1

Author

J. Lowell, Jun 09 2008, Jun 10 2008

Keywords

• nonn

Comments

I.e., if n is not a square, a(n) is the smallest number d for which a sequence that has a common difference of d contains n but that has no squares.

All nonzero values in this sequence are at least 3.

All nonzero values are prime powers, and every prime power except 2 appears in the sequence. This can be proved using the Chinese remainder theorem. - Franklin T. Adams-Watters, Jun 10 2011

Records of nonzero values in this sequence are in A066730.

Examples

			a(2) = 3 because there are no squares in the sequence 2, 5, 8, 11, 14, 17, 20, ...
		

Links

• Dan Uznanski, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A066730, A100867, A144294, A354597.

Programs

PARI

a(n) = if (issquare(n), 0, my(k=2); while (issquare(Mod(n, k)), k++); k); \\ Michel Marcus, Jun 25 2021

Python

import math
def A139401(n):
    if int(math.sqrt(n)) == math.sqrt(n):
        return 0
    for pp in range(2, n + 2):  # only really need to check prime powers
        residues = frozenset(pow(k, 2, pp) for k in range(pp))
        if n % pp not in residues:
            return pp  # Dan Uznanski, Jun 22 2021

Extensions

More terms from John W. Layman, Jun 17 2008

New name from Franklin T. Adams-Watters, Jun 10 2011