cp's OEIS Frontend

A000037 Numbers that are not squares (or, the nonsquares).

%I A000037 M0613 N0223 #169 Jul 24 2025 05:16:30
%S A000037 2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,26,27,28,29,30,
%T A000037 31,32,33,34,35,37,38,39,40,41,42,43,44,45,46,47,48,50,51,52,53,54,55,
%U A000037 56,57,58,59,60,61,62,63,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99
%N A000037 Numbers that are not squares (or, the nonsquares).
%C A000037 Note the remarkable formula for the n-th term (see the FORMULA section)!
%C A000037 These are the natural numbers with an even number of divisors. The number of divisors is odd for the complementary sequence, the squares (sequence A000290) and the numbers for which the number of divisors is divisible by 3 is sequence A059269. - Ola Veshta (olaveshta(AT)my-deja.com), Apr 04 2001
%C A000037 a(n) is the largest integer m not equal to n such that n = (floor(n^2/m) + m)/2. - _Alexander R. Povolotsky_, Feb 10 2008
%C A000037 Union of A007969 and A007970; A007968(a(n)) > 0. - _Reinhard Zumkeller_, Jun 18 2011
%C A000037 Terms of even numbered rows in the triangle A199332. - _Reinhard Zumkeller_, Nov 23 2011
%C A000037 If a(n) and a(n+1) are of the same parity then (a(n)+a(n+1))/2 is a square. - _Zak Seidov_, Aug 13 2012
%C A000037 Theaetetus of Athens proved the irrationality of the square roots of these numbers in the 4th century BC. - _Charles R Greathouse IV_, Apr 18 2013
%C A000037 4*a(n) are the even members of A079896, the discriminants of indefinite binary quadratic forms. - _Wolfdieter Lang_, Jun 14 2013
%D A000037 Titu Andreescu, Dorin Andrica, and Zuming Feng, 104 Number Theory Problems, Birkhäuser, 2006, 58-60.
%D A000037 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000037 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000037 Ray Chandler, <a href="/A000037/b000037.txt">Table of n, a(n) for n = 1..10000</a> (first 9900 terms from N. J. A. Sloane)
%H A000037 E. R. Berlekamp, <a href="/A257113/a257113.pdf">A contribution to mathematical psychometrics</a>, Unpublished Bell Labs Memorandum, Feb 08 1968 [Annotated scanned copy]
%H A000037 A. J. dos Reis and D. M. Silberger, <a href="http://www.jstor.org/stable/2691513">Generating nonpowers by formula</a>, Math. Mag., 63 (1990), 53-55.
%H A000037 Bakir Farhi, <a href="http://arxiv.org/abs/1105.1127">An explicit formula generating the non-Fibonacci numbers</a>, arXiv:1105.1127 [math.NT], May 05 2011.
%H A000037 S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Class number theory</a>
%H A000037 Steven R. Finch, <a href="/A000924/a000924.pdf">Class number theory</a> [Cached copy, with permission of the author]
%H A000037 Henry W. Gould, <a href="/A003099/a003099.pdf">Letters to N. J. A. Sloane, Oct 1973 and Jan 1974</a>.
%H A000037 S. Kaji, T. Maeno, K. Nuida, and Y. Numata, <a href="http://arxiv.org/abs/1506.02742">Polynomial Expressions of Carries in p-ary Arithmetics</a>, arXiv preprint arXiv:1506.02742 [math.CO], 2015-2016.
%H A000037 J. Lambek and L. Moser, <a href="http://www.jstor.org/stable/2308078">Inverse and complementary sequences of natural numbers</a>, Amer. Math. Monthly, 61 (1954), 454-458. doi 10.2307/2308078, see example 4 (includes the formula). [Nicolas Normand (Nicolas.Normand(AT)polytech.univ-nantes.fr), Nov 24 2009]
%H A000037 R. P. Loh, A. G. Shannon, and A. F. Horadam, <a href="/A000969/a000969.pdf">Divisibility Criteria and Sequence Generators Associated with Fermat Coefficients</a>, Preprint, 1980.
%H A000037 Cristinel Mortici, <a href="https://web.archive.org/web/20240726071814/https://www.fq.math.ca/Papers1/48-4/Mortici.pdf">Remarks on Complementary Sequences</a>, Fibonacci Quart. 48 (2010), no. 4, 343-347.
%H A000037 R. D. Nelson, <a href="http://www.jstor.org/stable/3618253">Sequences which omit powers</a>, The Mathematical Gazette, Number 461, 1988, pages 208-211.
%H A000037 M. A. Nyblom, <a href="http://www.jstor.org/stable/2695446">Some curious sequences involving floor and ceiling functions</a>, Am. Math. Monthly 109 (#6, 2002), 559-564.
%H A000037 Rosetta Code, <a href="http://rosettacode.org/wiki/Sequence_of_non-squares">Sequence of non-squares</a>
%H A000037 J. Scholes, <a href="https://mks.mff.cuni.cz/kalva/putnam/putn66.html">27th Putnam 1966 Prob. A4</a>
%H A000037 Aaron Snook, <a href="http://www.cs.cmu.edu/afs/cs/user/mjs/ftp/thesis-program/2012/theses/snook.pdf">Augmented Integer Linear Recurrences</a>, 2012. - From _N. J. A. Sloane_, Dec 19 2012
%H A000037 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SquareNumber.html">Square Number</a>
%H A000037 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ContinuedFraction.html">Continued Fraction</a>
%F A000037 a(n) = n + floor(1/2 + sqrt(n)).
%F A000037 a(n) = n + floor(sqrt( n + floor(sqrt n))).
%F A000037 A010052(a(n)) = 0. - _Reinhard Zumkeller_, Jan 26 2010
%F A000037 A173517(a(n)) = n; a(n)^2 = A030140(n). - _Reinhard Zumkeller_, Feb 20 2010
%F A000037 a(n) = A000194(n) + n. - _Jaroslav Krizek_, Jun 14 2009
%F A000037 a(A002061(n)) = a(n^2-n+1) = A002522(n) = n^2 + 1. - _Jaroslav Krizek_, Jun 21 2009
%e A000037 For example note that the squares 0, 1, 4, 9, 16 are not included.
%p A000037 A000037 := n->n+floor(1/2+sqrt(n));
%t A000037 a[n_] := (n + Floor[Sqrt[n + Floor[Sqrt[n]]]]); Table[a[n], {n, 71}] (* _Robert G. Wilson v_, Sep 24 2004 *)
%t A000037 With[{upto=100},Complement[Range[upto],Range[Floor[Sqrt[upto]]]^2]] (* _Harvey P. Dale_, Dec 02 2011 *)
%t A000037 a[ n_] :=  If[ n < 0, 0, n + Round @ Sqrt @ n]; (* _Michael Somos_, May 28 2014 *)
%o A000037 (Magma) [n : n in [1..1000] | not IsSquare(n) ];
%o A000037 (Magma) at:=0; for n in [1..10000] do if not IsSquare(n) then at:=at+1; print at, n; end if; end for;
%o A000037 (PARI) {a(n) = if( n<0, 0, n + (1 + sqrtint(4*n)) \ 2)};
%o A000037 (Haskell)
%o A000037 a000037 n = n + a000196 (n + a000196 n)
%o A000037 -- _Reinhard Zumkeller_, Nov 23 2011
%o A000037 (Maxima) A000037(n):=n + floor(1/2 + sqrt(n))$ makelist(A000037(n),n,1,50); /* _Martin Ettl_, Nov 15 2012 */
%o A000037 (Python)
%o A000037 from math import isqrt
%o A000037 def A000037(n): return n+isqrt(n+isqrt(n)) # _Chai Wah Wu_, Mar 31 2022
%o A000037 (Python)
%o A000037 from math import isqrt
%o A000037 def A000037(n): return n+(k:=isqrt(n))+int(n>=k*(k+1)+1) # _Chai Wah Wu_, Jun 17 2024
%Y A000037 Cf. A007412, A000005, A000290, A059269, A134986, A087153, A172151, A000196, A049068 (subsequence).
%Y A000037 Cf. A242401 (subsequence).
%Y A000037 Cf. A086849 (partial sums), A048395.
%K A000037 easy,nonn,nice
%O A000037 1,1
%A A000037 _N. J. A. Sloane_, _Simon Plouffe_
%E A000037 Edited by _Charles R Greathouse IV_, Oct 30 2009