

A000037


Numbers that are not squares (or, the nonsquares).
(Formerly M0613 N0223)


103



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, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 50, 51, 52, 53, 54, 55, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Note the remarkable formula for the nth term (see the FORMULA section)!
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)mydeja.com), Apr 04 2001
Also, a(n) = largest integer m not equal to n such that n = (floor(n^2/m) + m)/2.  Alexander R. Povolotsky, Feb 10 2008
A010052(a(n)) = 0.  Reinhard Zumkeller, Jan 26 2010
A173517(a(n)) = n; a(n)^2 = A030140(n).  Reinhard Zumkeller, Feb 20 2010
Special case of formula from Farhi for positive integers which are not rth powers.  Jonathan Vos Post, May 05 2011
Union of A007969 and A007970; A007968(a(n)) > 0.  Reinhard Zumkeller, Jun 18 2011
Terms of even numbered rows in the triangle A199332.  Reinhard Zumkeller, Nov 23 2011
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
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
4*a(n) are the even members of A079896, the discriminants of indefinite binary quadratic forms.  Wolfdieter Lang, Jun 14 2013


REFERENCES

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


LINKS

N. J. A. Sloane and Ray Chandler, Table of n, a(n) for n = 1..10000 (first 9900 terms from N. J. A. Sloane)
E. R. Berlekamp, A contribution to mathematical psychometrics, Unpublished Bell Labs Memorandum, Feb 08 1968 [Annotated scanned copy]
A. J. dos Reis and D. M. Silberger, Generating nonpowers by formula, Math. Mag., 63 (1990), 5355.
Bakir Farhi, An explicit formula generating the nonFibonacci numbers, arXiv:1105.1127 [math.NT], May 05 2011.
S. R. Finch, Class number theory
Henry W. Gould, Letters to N. J. A. Sloane, Oct 1973 and Jan 1974.
S. Kaji, T. Maeno, K. Nuida, Y. Numata, Polynomial Expressions of Carries in pary Arithmetics, arXiv preprint arXiv:1506.02742 [math.CO], 20152016.
J. Lambek and L. Moser, Inverse and complementary sequences of natural numbers, Amer. Math. Monthly, 61 (1954), 454458. doi 10.2307/2308078, see example 4 (includes the formula). [Nicolas Normand (Nicolas.Normand(AT)polytech.univnantes.fr), Nov 24 2009]
R. P. Loh, A. G. Shannon, A. F. Horadam, Divisibility Criteria and Sequence Generators Associated with Fermat Coefficients, Preprint, 1980.
Cristinel Mortici, Remarks on Complementary Sequences, Fibonacci Quart. 48 (2010), no. 4, 343347.
R. D. Nelson, Sequences which omit powers, The Mathematical Gazette, Number 461, 1988, pages 208211.
M. A. Nyblom, Some curious sequences involving floor and ceiling functions, Am. Math. Monthly 109 (#6, 2002), 559564.
Rosetta Code, Sequence of nonsquares
J. Scholes, 27th Putnam 1966 Prob. A4
Aaron Snook, Augmented Integer Linear Recurrences, 2012.  From N. J. A. Sloane, Dec 19 2012
Eric Weisstein's World of Mathematics, Square Number
Eric Weisstein's World of Mathematics, Continued Fraction


FORMULA

a(n) = n + floor(1/2 + sqrt(n)).
a(n) = n + floor(sqrt( n + floor(sqrt n))).
a(n) = A000194(n) + n = floor(1/2 *(1 + sqrt(4*n3)))+ n.  Jaroslav Krizek, Jun 14 2009
a(n) = A000194(n) + n.


EXAMPLE

For example note that the squares 1, 4, 9, 16 are not included.
a(A002061(n)) = a(n^2n+1) = A002522(n) = n^2 + 1. A002061(n) = central polygonal numbers (n^2n+1). A002522(n) = numbers of the form n^2 + 1.  Jaroslav Krizek, Jun 21 2009


MAPLE

A000037 := n>n+floor(1/2+sqrt(n));


MATHEMATICA

f[n_] := (n + Floor[Sqrt[n + Floor[Sqrt[n]]]]); Table[ f[n], {n, 71}] (* Robert G. Wilson v, Sep 24 2004 *)
f[n_]:=Round[Sqrt[n]]; lst={}; Do[AppendTo[lst, n+f[n]], {n, 0, 5!}]; lst (* Vladimir Joseph Stephan Orlovsky, Oct 13 2009 *)
With[{upto=100}, Complement[Range[upto], Range[Floor[Sqrt[upto]]]^2]] (* Harvey P. Dale, Dec 02 2011 *)
a[ n_] := If[ n < 0, 0, n + Round @ Sqrt @ n]; (* Michael Somos, May 28 2014 *)


PROG

(MAGMA) [n : n in [1..1000]  not IsSquare(n) ];
(MAGMA) at:=0; for n in [1..10000] do if not IsSquare(n) then at:=at+1; print at, n; end if; end for;
(PARI) {a(n) = if( n<0, 0, n + (1 + sqrtint(4*n)) \ 2)};
(Haskell)
a000037 n = n + a000196 (n + a000196 n)
 Reinhard Zumkeller, Nov 23 2011
(Maxima) A000037(n):=n + floor(1/2 + sqrt(n))$ makelist(A000037(n), n, 1, 50); /* Martin Ettl, Nov 15 2012 */


CROSSREFS

Cf. A007412, A000005, A000290, A059269, A134986, A087153, A172151, A000196, A049068 (subsequence).
Cf. A242401 (subsequence).
Cf. A086849 (partial sums), A048395.
Sequence in context: A046841 A244218 A164514 * A028761 A028809 A028785
Adjacent sequences: A000034 A000035 A000036 * A000038 A000039 A000040


KEYWORD

easy,nonn,nice


AUTHOR

N. J. A. Sloane, Simon Plouffe


EXTENSIONS

Edited by Charles R Greathouse IV, Oct 30 2009


STATUS

approved



