|
%I #121 Jan 22 2024 06:05:20
%S 1,2,5,10,13,17,25,26,29,34,37,41,50,53,58,61,65,73,74,82,85,89,97,
%T 101,106,109,113,122,125,130,137,145,146,149,157,169,170,173,178,181,
%U 185,193,194,197,202,205,218,221,226,229,233,241,250,257,265,269,274,277,281,289
%N Numbers n such that sqrt(-1) mod n exists; or, numbers that are primitively represented by x^2 + y^2.
%C 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
%C 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]
%C If a(n) is a term of this sequence, then so too are all of its divisors (Euler). - _Ant King_, Oct 11 2010
%C From _Richard R. Forberg_, Mar 21 2016: (Start)
%C 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.
%C Record setting values for the number of solutions (i.e., the next higher k values), occur at values for a(n) given by A006278.
%C A224450 and A224770 give a(n) values with exactly one and exactly two solutions, respectively, primitively representing integers as x^2 + y^2.
%C 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)
%C 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
%C 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
%C 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
%C 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
%D B. C. Berndt & R. A. Rankin, Ramanujan: Letters and Commentary, see p. 176; AMS Providence RI 1995.
%D J. W. S. Cassels, Rational Quadratic Forms, Cambridge, 1978.
%D Leonard Eugene Dickson, History of the Theory Of Numbers, Volume II: Diophantine Analysis, Chelsea Publishing Company, 1992, pp.230-242.
%D 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).
%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, Ch. 20.2-3.
%H T. D. Noe, <a href="/A008784/b008784.txt">Table of n, a(n) for n = 1..1000</a>
%H J.-P. Allouche and F. M. Dekking, <a href="https://arxiv.org/abs/1809.03424">Generalized Beatty sequences and complementary triples</a>, arXiv:1809.03424 [math.NT], 2018.
%H British Mathematical Olympiad, <a href="https://bmos.ukmt.org.uk/home/bmo-1985.pdf">1985 - Problem 6</a>.
%H Édouard Lucas, <a href="http://www.numdam.org/item/?id=NAM_1878_2_17__129_1">Théorème sur la géométrie des quinconces</a>, Nouvelles annales de mathématiques : journal des candidats aux écoles polytechnique et normale, Série 2, Tome 17 (1878), p. 129-130.
%H P. Cho-Ho Lam, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Lam/lam2.html">Representation of integers using a^2+b^2-dc^2</a>, J. Int. Seq. 18 (2015) 15.8.6, Theorems 2 and 3.
%H Richard J. Mathar, <a href="https://arxiv.org/abs/1703.01677">Construction of Bhaskara pairs</a>, arXiv:1703.01677 [math.NT], 2017.
%H N. J. A. Sloane et al., <a href="https://oeis.org/wiki/Binary_Quadratic_Forms_and_OEIS">Binary Quadratic Forms and OEIS</a> (Index to related sequences, programs, references).
%H <a href="/index/O#Olympiads">Index to sequences related to Olympiads</a>.
%p with(numtheory); [seq(mroot(-1,2,p),p=1..300)];
%t 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 *)
%t 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_ *)
%o (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
%o (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
%o (PARI) for(n=1,300,if(issquare(Mod(-1, n)),print1(n,", "))); \\ _Joerg Arndt_, Apr 27 2020
%o (Haskell)
%o import Data.List.Ordered (union)
%o a008784 n = a008784_list !! (n-1)
%o a008784_list = 1 : 2 : union a004613_list (map (* 2) a004613_list)
%o -- _Reinhard Zumkeller_, Oct 25 2015
%Y Apart from the first term, a subsequence of A000404.
%Y Cf. A001481, A022544, A020893, A037942, A034023, A057756, A076948, A045673, A004613, A340129, A192450 (complement).
%K nonn
%O 1,2
%A _N. J. A. Sloane_, _Olivier Gérard_
%E Checked by _T. D. Noe_, Apr 19 2007
|
