login
Euler's "numerus idoneus" (or "numeri idonei", or idoneal, or suitable, or convenient numbers).
(Formerly M0476 N0176)
52

%I M0476 N0176 #108 Oct 21 2024 17:18:00

%S 1,2,3,4,5,6,7,8,9,10,12,13,15,16,18,21,22,24,25,28,30,33,37,40,42,45,

%T 48,57,58,60,70,72,78,85,88,93,102,105,112,120,130,133,165,168,177,

%U 190,210,232,240,253,273,280,312,330,345,357,385,408,462,520,760,840,1320,1365,1848

%N Euler's "numerus idoneus" (or "numeri idonei", or idoneal, or suitable, or convenient numbers).

%C There are many equivalent definitions of these numbers. Based on Cox, Theorem 3.22 and Proposition 3.24 and a comment by Eric Rains (rains(AT)caltech.edu), we can say that a positive number n belongs to this sequence if and only if any of the following equivalent statements is true:

%C (1) Let m > 1 be an odd number relatively prime to n which can be written in the form x^2 + n*y^2 with x, y relatively prime. If the equation m = x^2 + n*y^2 has only one solution with x, y >= 0, then m is a prime number. [Euler]

%C (2) Every genus of quadratic forms of discriminant -4n consists of a single class. [Gauss]

%C (3) If a*x^2 + b*x*y + c*y^2 is a reduced quadratic form of discriminant -4n, then either b=0, a=b or a = c. [Cox]

%C (4) Two quadratic forms of discriminant -4n are equivalent if and only if they are properly equivalent. [Cox]

%C (5) The class group C(-4n) is isomorphic to (Z/2Z)^m for some integer m. [Cox]

%C (6) n is not of the form ab+ac+bc with 0 < a < b < c. (See proof in link below.) [Rains]

%C It is conjectured that the list given here is complete. Chowla showed that the list is finite and Weinberger showed that there is at most one further term.

%C If an additional term exists it is > 100000000. - _Jud McCranie_, Jun 27 2005

%C The terms shown are the union of {1,2,3,4,7}, A033266, A033267, A033268 and A033269 (corresponding to class numbers 1, 2, 4, 8 and 16 respectively).

%C Note that for n in this sequence, n+1 is either a prime, twice a prime, the square of a prime, 8 or 16. - _T. D. Noe_, Apr 08 2004. [This is a general theorem that is not hard to prove using genus theory. The "32" in the original comment was an error. - Tom Hagedorn (hagedorn(AT)tcnj.edu), Dec 29 2008]

%C Also numbers n such that for all primes p such that p is a quadratic residue (mod 4*n) and p-n is a quadratic residue (mod 4*n), p can be uniquely written into the form as x^2+n*y^2. - _V. Raman_, Nov 25 2013

%D Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966. See Table 97 at p. 272.

%D Z. I. Borevich and I. R. Shafarevich, Number Theory. Academic Press, NY, 1966, pp. 425-430.

%D David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989, Section 3.

%D J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 1848, p. 146, Ellipses, Paris 2008.

%D C. F. Gauss, Disquisitiones Arithmeticae, 1801. English translation: Yale University Press, New Haven, CT, 1966, Sections 329-334.

%D G. B. Mathews, Theory of Numbers, Chelsea, no date, p. 263.

%D P. Ribenboim, 'My Numbers, My Friends', Chap.11 Springer-Verlag 2000 NY

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D A. Weil, Number theory: an approach through history; from Hammurapi to Legendre, Birkhäuser, Boston, 1984; see pp. 188, 219-226.

%H S. Chowla, <a href="http://qjmath.oxfordjournals.org/content/os-5/1/304.extract">An extension of Heilbronn's class number theorem</a>, Quart. J. math., 5 (1934), 304-307.

%H K. S. Brown, Mathpages, <a href="http://www.mathpages.com/home/kmath058.htm">Numeri Idonei</a>

%H Günther Frei, <a href="http://www.numdam.org/item/10.5802/pmb.a-37.pdf">Les nombres convenables de Leonhard Euler</a>, Publications Université de Besançon, 1983-1984.

%H Günther Frei, <a href="https://doi.org/10.1007/BF03025809">Euler's convenient numbers</a>, Math. Intell. Vol. 7 No. 3 (1985), 55-58 and 64.

%H E. Hertel, C. Richter, <a href="http://dx.doi.org/10.1007/s00454-014-9576-7">Tiling Convex Polygons with Congruent Equilateral Triangles</a>, Discrete & Computational Geometry, 2014, DOI 10.1007/s00454-014-9576-7. Mentions this sequence. - _N. J. A. Sloane_, Mar 17 2014

%H O.-H. Keller, <a href="http://www.digizeitschriften.de/dms/img/?PPN=PPN301416052_0016&amp;DMDID=dmdlog23">Über die "Numeri idonei" von Euler</a>, Beitraege Algebra Geom., 16 (1983), 79-91. [Math. Rev. 85m:11019]

%H Robert Krzyzanowski, <a href="http://homepages.math.uic.edu/~robertk/files/number_theory_project2.pdf">Euler's Convenient Numbers</a>

%H David Masser, <a href="https://arxiv.org/abs/2010.10256">Alan Baker</a>, arXiv:2010.10256 [math.HO], 2020. See p. 24.

%H Eric Rains, <a href="/A000926/a000926.txt">Comments on A000926</a>

%H P. Ribenboim, <a href="http://www.jstor.org/stable/2690773">Galimatias Arithmeticae</a>, in Mathematics Magazine 71(5) 339 1998 MAA.

%H Rick L. Shepherd, <a href="http://libres.uncg.edu/ir/uncg/f/Shepherd_uncg_0154M_11099.pdf">Binary quadratic forms and genus theory</a>, Master of Arts Thesis, University of North Carolina at Greensboro, 2013.

%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 J. Steinig, <a href="http://dx.doi.org/10.5169/seals-24651">On Euler's ideoneal numbers</a>, Elemente Math., 21 (1966), 73-88.

%H M. Waldschmidt, <a href="http://arXiv.org/abs/math.NT/0312440">Open Diophantine problems</a>, arXiv:math/0312440 [math.NT], 2003-2004

%H P. Weinberger, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa22/aa2221.pdf">Exponents of the class groups of complex quadratic fields</a>, Acta Arith., 22 (1973), 117-124.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IdonealNumber.html">Idoneal Number</a>

%t noSol={}; Do[lim=Ceiling[(n-2)/3]; found=False; Do[If[n>a*b && Mod[n-a*b, a+b]==0 && Quotient[n-a*b, a+b]>b, found=True; Break[]], {a, 1, lim-1}, {b, a+1, lim}]; If[ !found, AppendTo[noSol, n]], {n, 10000}]; noSol (* _T. D. Noe_, Apr 08 2004 *)

%o (PARI) A000926(Nmax=1e9)={for(n=1,Nmax,for(a=1,sqrtint(n\3),for(b=a+1,(n-a)\(3*a+2),n-a<(2*a+1+b)*b & break;(n-a*b)%(a+b)==0 & next(3)));print1(n", "))} \\ _M. F. Hasler_, Dec 04 2007

%o (PARI) ok(n)=!#select(k->k<>2, quadclassunit(-4*n).cyc) \\ _Andrew Howroyd_, Jun 08 2018

%Y Sequence A025052 is a subsequence.

%Y Cf. A014556, A026501, A093669, A094376, A094377, A094378.

%Y Cf. A139642 (congruences for idoneal quadratic forms).

%K nonn,fini,full,nice,changed

%O 1,2

%A _N. J. A. Sloane_

%E Edited by _N. J. A. Sloane_, Dec 07 2007