A045673 -id:A045673 - cp's OEIS frontend

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

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

nonn

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

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.

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.

Apart from the first term, a subsequence of A000404.

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

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

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

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 *)

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

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

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

Checked by T. D. Noe, Apr 19 2007

A189226 Curvatures in the nickel-dime-quarter Apollonian circle packing, ordered first by generation and then by size.

Original entry on oeis.org

-11, 21, 24, 28, 40, 52, 61, 157, 76, 85, 96, 117, 120, 132, 181, 213, 237, 376, 388, 397, 132, 156, 160, 189, 204, 205, 216, 237, 253, 285, 288, 309, 316, 336, 349, 405, 412, 421, 453, 460, 469, 472, 517, 544, 565, 616, 628, 685, 717, 741, 1084, 1093, 1104, 1125, 1128, 1140

Offset: 1

Jonathan Sondow, Apr 18 2011

For a circle, curvature = 1/radius. The curvatures of a quarter, nickel, and dime are approximately proportional to 21, 24, and 28, respectively. Three mutually tangent circles with curvatures 21, 24, 28 can be inscribed in a circle of curvature 11.
Apollonius's and Descartes's Theorems say that, given three mutually tangent circles of curvatures a, b, c, there are exactly two circles tangent to all three, and their curvatures are a + b + c +- 2*sqrt(ab + ac + bc). (Here negative curvature of one of the two circles means that the three circles are inscribed in it.)
Fuchs (2009) says "An Apollonian circle packing ... is made by repeatedly inscribing circles into the triangular interstices in a Descartes configuration of four mutually tangent circles. Remarkably, if the original four circles have integer curvature, all of the circles in the packing will have integer curvature as well." That is because if a + b + c - 2s*qrt(ab + ac + bc) is an integer, then so is a + b + c + 2*sqrt(ab + ac + bc).
For n > 1, the n-th generation of the packing has 4*3^(n-2) circles.
Infinitely many of the curvatures are prime numbers A189227. In fact, in any integral Apollonian circle packing that is primitive (i.e., the curvatures have no common factor), the prime curvatures constitute a positive fraction of all primes (Bourgain 2012) and there are infinitely many pairs of tangent circles both of whose curvatures are prime (Sarnak 2007, 2011).
Fuchs and Sanden (2012) report on experiments with the nickel-dime-quarter Apollonian circle packing, which they call the coins packing P_C.

			The 1st-generation curvatures are -11, 21, 24, 28, the 2nd are 40, 52, 61, 157, and the 3rd are 76, 85, 96, 117, 120, 132, 181, 213, 237, 376, 388, 397. The 4th generation begins 132, 156, 160, 189, 204, 205, 216, ....
As 21 + 24 + 28 +- 2*sqrt(21*24 + 21*28 + 24*28) = 157 or -11, the sequence begins -11, 21, 24, 28, ... and 157 is in it.
The primes 157 and 397 are the curvatures of two circles that are tangent.

D. Austin, When Kissing Involves Trigonometry, AMS feature column March 2006.
J. Bourgain, Integral Apollonian circle packings and prime curvatures, arXiv:1105.5127 [math.NT], 2011-2012.
J. Bourgain and A. Kontorovich, On the Strong Density Conjecture for Integral Apollonian Circle Packings, arXiv:1205.4416 [math.NT], 2012-2013. See figure 1.
S. Butler, R. Graham, G. Guettler and C. Mallows, Irreducible Apollonian configurations and packings, Discrete & Computational Geometry, 44 (2010), 487-507.
E. Fuchs, Arithmetic Properties of Apollonian Circle Packings, Ph.D. thesis 2009.
E. Fuchs and K. Sanden, Some experiments with integral Apollonian circle packings, Experiment. Math. 20 (2011), 380-399.
R. L. Graham, J. C. Lagarias, C. L. Mallows, Allan Wilks, and C. H. Yan, Apollonian Circle Packings: Number Theory, J. Number Theory, 100 (2003), 1-45.
R. L. Graham, J. C. Lagarias, C. L. Mallows, Allan Wilks, and C. H. Yan, Apollonian Circle Packings: Geometry and Group Theory I. The Apollonian Group., Discrete & Computational Geometry, 34 (2005), no. 4, 547-585.
K. E. Hirst, The Apollonian Packing of Circles, J. London Math. Soc. s1-42(1) (1967), 281-291.
E. Kasner and F. Supnick, The Apollonian packing of circles, Proc. Nat. Acad. Sci. U.S.A. 29 (1943), 378-384.
A. Kontorovich, From Apollonius to Zaremba: Local-global phenomena in thin orbits, Bull. Amer. Math. Soc., 50 (2013), 187-228.
J. C. Lagarias, C. L. Mallows, and Allan Wilks, Beyond the Descartes Circle Theorem, Amer. Math Monthly, 109 (2002), 338-361.
L. Levine, W. Pegden, C. K. Smart, Apollonian Structure in the Abelian Sandpile, arXiv:1208.4839 [math.AP], 2012-2014.
D. Mackenzie, A Tisket, a Tasket, an Apollonian Gasket, American Scientist, 98 (2010).
C. L. Mallows, Growing Apollonian Packings, J. Integer Sequences, 12 (2009), article 09.2.1.
I. Peterson, Circle game, Science News, 4/21/01.
I. Peterson, Temple circles, Math Trek, 4/23/01.
P. Sarnak, Letter to Lagarias on integral Apollonian packings, June, 2007.
P. Sarnak, Integral Apollonian packings, MAA Lecture, Jan 2009.
P. Sarnak, Integral Apollonian packings, Amer. Math. Monthly, 118 (2011), 291-306.
K. E. Stange, The sensual Apollonian circle packing, arXiv:1208.4836 [math.NT], 2012-2014.
Wikipedia, Integral Apollonian circle packings
Wikipedia, Descartes' theorem

Cf. A042944, A042946, A042945, A045506, A045673, A045864, A052483, A060790, A135849, A137246, A154636, A154637, A154638, A171090, A189227, A218155, A248938, A265495, A294510.

root = {-11, 21, 24, 28};
triples = Subsets[root, {3}];
a = {root};
Do[
  ng = Table[Total@t + 2 Sqrt@Total[Times @@@ Subsets[t, {2}]], {t, triples}];
  AppendTo[a, Sort@ng];
  triples = Join @@ Table[{t, r} = tr; Table[Append[p, r], {p, Subsets[t, {2}]}], {tr, Transpose@{triples, ng}}]
  , {k, 3}];
Flatten@a (* Andrey Zabolotskiy, May 29 2022 *)

a(n) == 0, 4, 12, 13, 16, or 21 (mod 24).

Terms a(28) and beyond from Andrey Zabolotskiy, May 29 2022

cp's OEIS Frontend

A045679 Numbers congruent to 0,1,4,9 mod 12 missing from A045673 (conjectured to be finite).

Views

Author

Keywords

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Extensions

A189226 Curvatures in the nickel-dime-quarter Apollonian circle packing, ordered first by generation and then by size.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions