A008784 Numbers k such that sqrt(-1) mod k exists; or, numbers that are primitively represented by x^2 + y^2.

1, 2, 5, 10, 13, 17, 25, 26, 29, 34, 37, 41, 50, 53, 58, 61, 65, 73, 74, 82, 85, 89, 97, 101, 106, 109, 113, 122, 125, 130, 137, 145, 146, 149, 157, 169, 170, 173, 178, 181, 185, 193, 194, 197, 202, 205, 218, 221, 226, 229, 233, 241, 250, 257, 265, 269, 274, 277, 281, 289

Offset: 1

Author

N. J. A. Sloane, Olivier Gérard

Keywords

• nonn

Comments

Numbers whose prime divisors are all congruent to 1 mod 4, with the exception of at most a single factor of 2. - Franklin T. Adams-Watters, Sep 07 2008

In appears that {a(n)} is the set of proper divisors of numbers of the form m^2+1. - Kaloyan Todorov (kaloyan.todorov(AT)gmail.com), Mar 25 2009 [This conjecture is correct. - Franklin T. Adams-Watters, Oct 07 2009]

If a(n) is a term of this sequence, then so too are all of its divisors (Euler). - Ant King, Oct 11 2010

From Richard R. Forberg, Mar 21 2016: (Start)

For a given a(n) > 2, there are 2^k solutions to sqrt(-1) mod n (for some k >= 1), and 2^(k-1) solutions primitively representing a(n) by x^2 + y^2.

Record setting values for the number of solutions (i.e., the next higher k values), occur at values for a(n) given by A006278.

A224450 and A224770 give a(n) values with exactly one and exactly two solutions, respectively, primitively representing integers as x^2 + y^2.

The 2^k different solutions for sqrt(-1) mod n can written as values for j, with j <= n, such that integers r = sqrt(n*j-1). However, the set of j values (listed from smallest to largest) transform into themselves symmetrically (i.e., largest to smallest) when the solutions are written as n-r. When the same 2^k solutions are written as r-j, it is clear that only 2^(k-1) distinct and independent solutions exist. (End)

Lucas uses the fact that there are no multiples of 3 in this sequence to prove that one cannot have an equilateral triangle on the points of a square lattice. - Michel Marcus, Apr 27 2020

For n > 1, terms are precisely the numbers such that there is at least one pair (m,k) where m + k = a(n), and m*k == 1 (mod a(n)), m > 0 and m <= k. - Torlach Rush, Oct 18 2020

A pair (s,t) such that s+t = a(n) and s*t == +1 (mod a(n)) as above is obtained from a square root of -1 (mod a(n)) for s and t = a(n)-s. - Joerg Arndt, Oct 24 2020

The Diophantine equation x^2 + y^2 = z^5 + z with gcd(x, y, z) = 1 has solutions iff z is a term of this sequence. See Gardiner reference, Olympiad links and A340129. - Bernard Schott, Jan 17 2021

Except for 1, numbers of the form a + b + 2*sqrt(a*b - 1) for positive integers a,b such that a*b-1 is a square. - Davide Rotondo, Nov 10 2024

References

• B. C. Berndt & R. A. Rankin, Ramanujan: Letters and Commentary, see p. 176; AMS Providence RI 1995.
• J. W. S. Cassels, Rational Quadratic Forms, Cambridge, 1978.
• Leonard Eugene Dickson, History of the Theory Of Numbers, Volume II: Diophantine Analysis, Chelsea Publishing Company, 1992, pp.230-242.
• A. Gardiner, The Mathematical Olympiad Handbook: An Introduction to Problem Solving, Oxford University Press, 1997, reprinted 2011, Problem 6 pp. 63 and 167-168 (1985).
• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, Ch. 20.2-3.

Links

• T. D. Noe, Table of n, a(n) for n = 1..1000
• J.-P. Allouche and F. M. Dekking, Generalized Beatty sequences and complementary triples, arXiv:1809.03424 [math.NT], 2018.
• British Mathematical Olympiad, 1985 - Problem 6.
• Édouard Lucas, Théorème sur la géométrie des quinconces, Nouvelles annales de mathématiques : journal des candidats aux écoles polytechnique et normale, Série 2, Tome 17 (1878), p. 129-130.
• P. Cho-Ho Lam, Representation of integers using a^2+b^2-dc^2, J. Int. Seq. 18 (2015) 15.8.6, Theorems 2 and 3.
• Richard J. Mathar, Construction of Bhaskara pairs, arXiv:1703.01677 [math.NT], 2017.
• N. J. A. Sloane et al., Binary Quadratic Forms and OEIS (Index to related sequences, programs, references).
• Index to sequences related to Olympiads.

Crossrefs

Apart from the first term, a subsequence of A000404.

Cf. A001481, A022544, A020893, A037942, A034023, A057756, A076948, A045673, A004613, A340129, A192450 (complement).

Programs

Haskell

import Data.List.Ordered (union)
a008784 n = a008784_list !! (n-1)
a008784_list = 1 : 2 : union a004613_list (map (* 2) a004613_list)
-- Reinhard Zumkeller, Oct 25 2015

Maple

with(numtheory); [seq(mroot(-1,2,p),p=1..300)];

Mathematica

data=Flatten[FindInstance[x^2+y^2==# && 0<=x<=# && 0<=y<=# && GCD[x,y]==1,{x,y},Integers]&/@Range[289],1]; x^2+y^2/.data//Union (* Ant King, Oct 11 2010 *)
Select[Range[289], And @@ (Mod[#, 4] == 1 & ) /@ (fi = FactorInteger[#]; If[fi[[1]] == {2, 1}, Rest[fi[[All, 1]]], fi[[All, 1]]])&] (* Jean-François Alcover, Jul 02 2012, after Franklin T. Adams-Watters *)

PARI

is(n)=if(n%2==0,if(n%4,n/=2,return(0)));n==1||vecmax(factor(n)[,1]%4)==1 \\ Charles R Greathouse IV, May 10 2012

PARI

list(lim)=my(v=List([1,2]),t); lim\=1; for(x=2,sqrtint(lim-1), t=x^2; for(y=0,min(x-1,sqrtint(lim-t)), if(gcd(x,y)==1, listput(v,t+y^2)))); Set(v) \\ Charles R Greathouse IV, Sep 06 2016

PARI

for(n=1,300,if(issquare(Mod(-1, n)),print1(n,", "))); \\ Joerg Arndt, Apr 27 2020

Extensions

Checked by T. D. Noe, Apr 19 2007