cp's OEIS Frontend

A000196 Integer part of square root of n. Or, number of positive squares <= n. Or, n appears 2n+1 times.

%I A000196 #201 Jul 28 2025 03:20:21
%S A000196 0,1,1,1,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,
%T A000196 5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,
%U A000196 8,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,10,10
%N A000196 Integer part of square root of n. Or, number of positive squares <= n. Or, n appears 2n+1 times.
%C A000196 Also the integer part of the geometric mean of the divisors of n. - _Amarnath Murthy_, Dec 19 2001
%C A000196 Number of numbers k (<= n) with an odd number of divisors. - _Benoit Cloitre_, Sep 07 2002
%C A000196 Also, for n > 0, the number of digits when writing n in base where place values are squares, cf. A007961; A190321(n) <= a(n). - _Reinhard Zumkeller_, May 08 2011
%C A000196 The least monotonic left inverse of squares, A000290. That is, the lexicographically least nondecreasing sequence a(n) such that a(A000290(n)) = n. - _Antti Karttunen_, Oct 06 2017
%D A000196 Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, p. 73, problem 23.
%D A000196 Lionel Levine, Fractal sequences and restricted Nim, Ars Combin. 80 (2006), 113-127.
%D A000196 Paul J. McCarthy, Introduction to Arithmetical Functions, Springer Verlag, 1986, p. 28.
%D A000196 N. J. A. Sloane and Allan Wilks, On sequences of Recaman type, paper in preparation, 2006.
%H A000196 Franklin T. Adams-Watters, <a href="/A000196/b000196.txt">Table of n, a(n) for n = 0..10000</a>
%H A000196 Krassimir Atanassov, <a href="http://www.gallup.unm.edu/~smarandache/Atanassov-SomeProblems.pdf">On Some of Smarandache's Problems</a>
%H A000196 Krassimir Atanassov, <a href="https://nntdm.net/volume-05-1999/number-3/94-96/">On the 100-th, the 101-st and 102-nd Smarandache's problems</a>, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 3, 94-96.
%H A000196 Henry Bottomley, <a href="/A000196/a000196.gif">Illustration of A000196, A048760, A053186</a>.
%H A000196 Matthew Hyatt and Marina Skyers, <a href="http://www.emis.de/journals/INTEGERS/papers/p17/p17.Abstract.html">On the Increases of the Sequence floor(k*sqrt(n))</a>, Electronic Journal of Combinatorial Number Theory, Volume 15 (2015), #A17.
%H A000196 Lionel Levine, <a href="https://arxiv.org/abs/math/0409408">Fractal sequences and restricted Nim</a>, arXiv:math/0409408 [math.CO], 2004.
%H A000196 Paul Pollack and Joseph Vandehey, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.122.8.757">Besicovitch, Bisection, and the Normality of 0.(1)(4)(9)(16)(25)....</a>, The American Mathematical Monthly 122.8 (2015): 757-765.
%H A000196 N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)
%H A000196 Florentin Smarandache, <a href="http://www.gallup.unm.edu/~smarandache/OPNS.pdf">Only Problems, Not Solutions!</a>, 1993.
%F A000196 a(n) = Card(k, 0 < k <= n such that k is relatively prime to core(k)) where core(x) is the squarefree part of x. - _Benoit Cloitre_, May 02 2002
%F A000196 a(n) = a(n-1) + floor(n/(a(n-1)+1)^2), a(0) = 0. - _Reinhard Zumkeller_, Apr 12 2004
%F A000196 From _Hieronymus Fischer_, May 26 2007: (Start)
%F A000196 a(n) = Sum_{k=1..n} A010052(k).
%F A000196 G.f.: g(x) = (1/(1-x))*Sum_{j>=1} x^(j^2) = (theta_3(0, x) - 1)/(2*(1-x)) where theta_3 is a Jacobi theta function. (End)
%F A000196 a(n) = floor(A000267(n)/2). - _Reinhard Zumkeller_, Jun 27 2011
%F A000196 a(n) = floor(sqrt(n)). - _Arkadiusz Wesolowski_, Jan 09 2013
%F A000196 Sum_{n>0} 1/a(n)^s = 2*zeta(s-1) + zeta(s), where zeta is the Riemann zeta function. - _Enrique Pérez Herrero_, Oct 15 2013
%F A000196 From _Wesley Ivan Hurt_, Dec 31 2013: (Start)
%F A000196 a(n) = Sum_{i=1..n} (A000005(i) mod 2), n > 0.
%F A000196 a(n) = (1/2)*Sum_{i=1..n} (1 - (-1)^A000005(i)), n > 0. (End)
%F A000196 a(n) = sqrt(A048760(n)), n >= 0. - _Wolfdieter Lang_, Mar 24 2015
%F A000196 a(n) = Sum_{k=1..n} floor(n/k)*lambda(k) = Sum_{m=1..n} Sum_{d|m} lambda(d) where lambda(j) is Liouville lambda function, A008836. - _Geoffrey Critzer_, Apr 01 2015
%F A000196 Sum_{n>=1} (-1)^(n+1)/a(n) = log(2) (A002162). - _Amiram Eldar_, May 02 2023
%e A000196 G.f. = x + x^2 + x^3 + 2*x^4 + 2*x^5 + 2*x^6 + 2*x^7 + 2*x^8 + 3*x^9 + ...
%p A000196 Digits := 100; A000196 := n->floor(evalf(sqrt(n)));
%t A000196 Table[n, {n, 0, 20}, {2n + 1}] //Flatten (* _Zak Seidov_ Mar 19 2011 *)
%t A000196 IntegerPart[Sqrt[Range[0, 110]]] (* _Harvey P. Dale_, May 23 2012 *)
%t A000196 Floor[Sqrt[Range[0, 99]]] (* _Alonso del Arte_, Dec 31 2013 *)
%t A000196 a[ n_] := SeriesCoefficient[ (EllipticTheta[ 3, 0, x]  - 1) / (2 (1 - x)), {x, 0, n}]; (* _Michael Somos_, May 28 2014 *)
%o A000196 (Magma) [Isqrt(n) : n in [0..100]];
%o A000196 (PARI) {a(n) = if( n<0, 0, sqrtint(n))};
%o A000196 (Haskell)
%o A000196 import Data.Bits (shiftL, shiftR)
%o A000196 a000196 :: Integer -> Integer
%o A000196 a000196 0 = 0
%o A000196 a000196 n = newton n (findx0 n 1) where
%o A000196    -- find x0 == 2^(a+1), such that 4^a <= n < 4^(a+1).
%o A000196    findx0 0 b = b
%o A000196    findx0 a b = findx0 (a `shiftR` 2) (b `shiftL` 1)
%o A000196    newton n x = if x' < x then newton n x' else x
%o A000196                 where x' = (x + n `div` x) `div` 2
%o A000196 a000196_list = concat $ zipWith replicate [1,3..] [0..]
%o A000196 -- _Reinhard Zumkeller_, Apr 12 2012, Oct 23 2010
%o A000196 (Python)
%o A000196 # from http://code.activestate.com/recipes/577821-integer-square-root-function/
%o A000196 def A000196(n):
%o A000196   if n < 0:
%o A000196     raise ValueError('only defined for nonnegative n')
%o A000196   if n == 0:
%o A000196     return 0
%o A000196   a, b = divmod(n.bit_length(), 2)
%o A000196   j = 2**(a+b)
%o A000196   while True:
%o A000196     k = (j + n//j)//2
%o A000196     if k >= j:
%o A000196       return j
%o A000196     j = k
%o A000196 print([A000196(n)for n in range(102)])
%o A000196 # _Jason Kimberley_, Nov 09 2016
%o A000196 (Python)
%o A000196 from math import isqrt
%o A000196 def a(n): return isqrt(n)
%o A000196 print([a(n) for n in range(102)]) # _Michael S. Branicky_, Feb 15 2023
%o A000196 (Scheme)
%o A000196 ;; The following implementation uses higher order function LEFTINV-LEASTMONO-NC2NC from my IntSeq-library. It returns the least monotonic left inverse of any strictly growing function (see the comment-section for the definition) and although it does not converge as fast to the result as many specialized integer square root algorithms, at least it does not involve any floating point arithmetic. Thus with correctly implemented bignums it will produce correct results even with very large arguments, in contrast to just taking the floor of (sqrt n).
%o A000196 ;; Source of LEFTINV-LEASTMONO-NC2NC can be found under https://github.com/karttu/IntSeq/blob/master/src/Transforms/transforms-core.ss and the definition of A000290 is given under that entry.
%o A000196 (define A000196 (LEFTINV-LEASTMONO-NC2NC 0 0 A000290)) ;; _Antti Karttunen_, Oct 06 2017
%o A000196 (Julia)
%o A000196 a(n) = isqrt(n) # _Paul Muljadi_, Jun 03 2024
%Y A000196 Cf. A000290, A002162, A003056, A028391, A048760, A048766, A074704, A079051.
%Y A000196 Column k=1 of A281871.
%K A000196 nonn,easy,nice
%O A000196 0,5
%A A000196 _N. J. A. Sloane_