login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000196 Integer part of square root of n. Or, number of positive squares <= n. Or, n appears 2n+1 times. 245

%I

%S 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 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 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 Integer part of square root of n. Or, number of positive squares <= n. Or, n appears 2n+1 times.

%C Also the integer part of the geometric mean of the divisors of n. - _Amarnath Murthy_, Dec 19 2001

%C Number of numbers k (<= n) with an odd number of divisors. - _Benoit Cloitre_, Sep 07 2002

%C 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 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

%C 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 T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, p. 73, problem 23.

%D K. Atanassov, On the 100th, 101st and the 102th Smarandache Problems, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 3, 94-96.

%D L. Levine, Fractal sequences and restricted Nim, Ars Combin. 80 (2006), 113-127.

%D P. J. McCarthy, Introduction to Arithmetical Functions, Springer Verlag, 1986, p. 28.

%D N. J. A. Sloane and Allan Wilks, On sequences of Recaman type, paper in preparation, 2006.

%H Franklin T. Adams-Watters, <a href="/A000196/b000196.txt">Table of n, a(n) for n = 0..10000</a>

%H K. Atanassov, <a href="http://www.gallup.unm.edu/~smarandache/Atanassov-SomeProblems.pdf">On Some of Smarandache's Problems</a>

%H H. Bottomley, <a href="/A000196/a000196.gif">Illustration of A000196, A048760, A053186</a>

%H Matthew Hyatt, 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 #A17.

%H L. Levine, <a href="http://arXiv.org/abs/math.CO/0409408">Fractal sequences and restricted Nim</a>, arXiv:math/0409408 [math.CO], 2004.

%H Paul Pollack, 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 F. Smarandache, <a href="http://www.gallup.unm.edu/~smarandache/OPNS.pdf">Only Problems, Not Solutions!</a>.

%F 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 a(n) = a(n-1) + floor(n/(a(n-1)+1)^2), a(0) = 0. - _Reinhard Zumkeller_, Apr 12 2004

%F a(n) = Sum_{k=1..n} A010052(k). 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. - _Hieronymus Fischer_, May 26 2007

%F a(n) = floor(A000267(n)/2). - _Reinhard Zumkeller_, Jun 27 2011

%F a(n) = floor(sqrt(n)). - _Arkadiusz Wesolowski_, Jan 09 2013

%F From _Wesley Ivan Hurt_, Dec 31 2013: (Start)

%F a(n) = Sum_{i=1..n} (A000005(i) mod 2), n > 0.

%F a(n) = (1/2)*Sum_{i=1..n} (1 - (-1)^A000005(i)), n > 0. (End)

%F a(n) = sqrt(A048760(n)), n >= 0. - _Wolfdieter Lang_, Mar 24 2015

%F 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 a(n) = round(1 + (1/2)*(-3 + sqrt(n) + sqrt(1 + n))). - _Mats Granvik_, Feb 21 2016

%e 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 Digits := 100; A000196 := n->floor(evalf(sqrt(n)));

%t Table[n, {n, 0, 20}, {2n + 1}] //Flatten (* _Zak Seidov_ Mar 19 2011 *)

%t IntegerPart[Sqrt[Range[0, 110]]] (* _Harvey P. Dale_, May 23 2012 *)

%t Floor[Sqrt[Range[0, 99]]] (* _Alonso del Arte_, Dec 31 2013 *)

%t a[ n_] := SeriesCoefficient[ (EllipticTheta[ 3, 0, x] - 1) / (2 (1 - x)), {x, 0, n}]; (* _Michael Somos_, May 28 2014 *)

%o (MAGMA) [Isqrt(n) : n in [0..100]];

%o (PARI) {a(n) = if( n<0, 0, floor(sqrt(n)))};

%o (PARI) {a(n) = if( n<0, 0, sqrtint(n))};

%o (Haskell)

%o import Data.Bits (shiftL, shiftR)

%o a000196 :: Integer -> Integer

%o a000196 0 = 0

%o a000196 n = newton n (findx0 n 1) where

%o -- find x0 == 2^(a+1), such that 4^a <= n < 4^(a+1).

%o findx0 0 b = b

%o findx0 a b = findx0 (a `shiftR` 2) (b `shiftL` 1)

%o newton n x = if x' < x then newton n x' else x

%o where x' = (x + n `div` x) `div` 2

%o a000196_list = concat $ zipWith replicate [1,3..] [0..]

%o -- _Reinhard Zumkeller_, Apr 12 2012, Oct 23 2010

%o (Python 2.7)

%o # from http://code.activestate.com/recipes/577821-integer-square-root-function/

%o def A000196(n):

%o if n < 0:

%o raise ValueError('only defined for non-negative n')

%o if n == 0:

%o return 0

%o a, b = divmod(n.bit_length(), 2)

%o j = 2**(a+b)

%o while True:

%o k = (j + n//j)//2

%o if k >= j:

%o return j

%o j = k

%o print [A000196(n)for n in range(102)]

%o # _Jason Kimberley_, Nov 09 2016

%o (Scheme)

%o ;; 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 ;; 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 (define A000196 (LEFTINV-LEASTMONO-NC2NC 0 0 A000290)) ;; _Antti Karttunen_, Oct 06 2017

%Y Cf. A000290, A003056, A028391, A048760, A048766, A074704, A079051.

%Y Column k=1 of A281871.

%K nonn,easy,nice

%O 0,5

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 15 03:08 EST 2017. Contains 296020 sequences.