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

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.

Links

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

Example

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

Prog

(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
(PARI) a(n) = if (issquare(n), 0, my(k=2); while (issquare(Mod(n, k)), k++); k); \\ Michel Marcus, Jun 25 2021

Crossrefs

Cf. A066730, A100867, A144294, A354597.

Sequence in context: A063405 A360533 A346524 * A110061 A363804 A220956

Adjacent sequences: A139398 A139399 A139400 * A139402 A139403 A139404

Keyword

nonn

Author

J. Lowell, Jun 09 2008, Jun 10 2008

Extensions

More terms from John W. Layman, Jun 17 2008

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

Status

approved