cp's OEIS Frontend

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.

%I A139401 #33 Mar 21 2023 12:09:44
%S A139401 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,
%T A139401 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,
%U A139401 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
%N 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.
%C A139401 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.
%C A139401 All nonzero values in this sequence are at least 3.
%C A139401 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
%C A139401 Records of nonzero values in this sequence are in A066730.
%H A139401 Dan Uznanski, <a href="/A139401/b139401.txt">Table of n, a(n) for n = 1..10000</a>
%e A139401 a(2) = 3 because there are no squares in the sequence 2, 5, 8, 11, 14, 17, 20, ...
%o A139401 (Python)
%o A139401 import math
%o A139401 def A139401(n):
%o A139401     if int(math.sqrt(n)) == math.sqrt(n):
%o A139401         return 0
%o A139401     for pp in range(2, n + 2):  # only really need to check prime powers
%o A139401         residues = frozenset(pow(k, 2, pp) for k in range(pp))
%o A139401         if n % pp not in residues:
%o A139401             return pp  # _Dan Uznanski_, Jun 22 2021
%o A139401 (PARI) a(n) = if (issquare(n), 0, my(k=2); while (issquare(Mod(n, k)), k++); k); \\ _Michel Marcus_, Jun 25 2021
%Y A139401 Cf. A066730, A100867, A144294, A354597.
%K A139401 nonn
%O A139401 1,2
%A A139401 _J. Lowell_, Jun 09 2008, Jun 10 2008
%E A139401 More terms from _John W. Layman_, Jun 17 2008
%E A139401 New name from _Franklin T. Adams-Watters_, Jun 10 2011