

A008784


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


42



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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. AdamsWatters, Sep 07 2008
In appears that a(n) is the set of proper divisors of numbers of the type n^2+1.  Kaloyan Todorov (kaloyan.todorov(AT)gmail.com), Mar 25 2009. This conjecture is correct.  Franklin T. AdamsWatters, 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^(k1) 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*j1). 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 nr. When the same 2^k solutions are written as rj, it is clear that only 2^(k1) 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


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.230242.
A. Gardiner, The Mathematical Olympiad Handbook: An Introduction to Problem Solving, Oxford University Press, 1997, reprinted 2011, Problem 6 pp. 63 and 167168 (1985).
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, Ch. 20.23.


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. 129130.
P. ChoHo Lam, Representation of integers using a^2+b^2dc^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.


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]]])&] (* JeanFrançois Alcover, Jul 02 2012, after Franklin T. AdamsWatters *)


PROG

(PARI) is(n)=if(n%2==0, if(n%4, n/=2, return(0))); n==1vecmax(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(lim1), t=x^2; for(y=0, min(x1, sqrtint(limt)), 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
(Haskell)
import Data.List.Ordered (union)
a008784 n = a008784_list !! (n1)
a008784_list = 1 : 2 : union a004613_list (map (* 2) a004613_list)
 Reinhard Zumkeller, Oct 25 2015


CROSSREFS

Apart from the first term, a subsequence of A000404.
Cf. A001481, A022544, A020893, A037942, A034023, A057756, A076948, A045673, A004613, A340129.
Sequence in context: A099261 A103215 A037942 * A224450 A226828 A020893
Adjacent sequences: A008781 A008782 A008783 * A008785 A008786 A008787


KEYWORD

nonn


AUTHOR

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


EXTENSIONS

Checked by T. D. Noe, Apr 19 2007


STATUS

approved



