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

 

Logo


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. 228
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

Also the integer part of the geometric mean of the divisors of n. - Amarnath Murthy, Dec 19 2001

Number of numbers k (<= n) with an odd number of divisors. - Benoit Cloitre, Sep 07 2002

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

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

REFERENCES

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, p. 73, problem 23.

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.

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

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

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

LINKS

Franklin T. Adams-Watters, Table of n, a(n) for n = 0..10000

K. Atanassov, On Some of Smarandache's Problems

H. Bottomley, Illustration of A000196, A048760, A053186

Matthew Hyatt, Marina Skyers, On the Increases of the Sequence floor(k*sqrt(n)), Electronic Journal of Combinatorial Number Theory, Volume 15 #A17.

L. Levine, Fractal sequences and restricted Nim, arXiv:math/0409408 [math.CO], 2004.

Paul Pollack, Joseph Vandehey, Besicovitch, Bisection, and the Normality of 0.(1)(4)(9)(16)(25)....,, The American Mathematical Monthly 122.8 (2015): 757-765.

F. Smarandache, Only Problems, Not Solutions!.

FORMULA

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

a(n) = a(n-1) + floor(n/(a(n-1)+1)^2), a(0) = 0. - Reinhard Zumkeller, Apr 12 2004

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

a(n) = [A000267(n)/2]. - Reinhard Zumkeller, Jun 27 2011

a(n) = floor(sqrt(n)). - Arkadiusz Wesolowski, Jan 09 2013

From Wesley Ivan Hurt, Dec 31 2013: (Start)

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

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

a(n) = n - Sum_{i=0..n} sign(sqrt(i)).

(End)

a(n) = sqrt(A048760(n)), n >= 0. - Wolfdieter Lang, Mar 24 2015

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

a(n) = round(1 + (1/2)*(-3 + sqrt(n) + sqrt(1 + n))). - Mats Granvik, Feb 21 2016

EXAMPLE

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 + ...

MAPLE

Digits := 100; A000196 := n->floor(evalf(sqrt(n)));

MATHEMATICA

Table[n, {n, 0, 20}, {2n + 1}] //Flatten (* Zak Seidov Mar 19 2011 *)

IntegerPart[Sqrt[Range[0, 110]]] (* Harvey P. Dale, May 23 2012 *)

Floor[Sqrt[Range[0, 99]]] (* Alonso del Arte, Dec 31 2013 *)

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

PROG

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

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

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

(Haskell)

import Data.Bits (shiftL, shiftR)

a000196 :: Integer -> Integer

a000196 0 = 0

a000196 n = newton n (findx0 n 1) where

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

   findx0 0 b = b

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

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

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

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

-- Reinhard Zumkeller, Apr 12 2012, Oct 23 2010

(Python 2.7)

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

def A000196(n):

  if n < 0:

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

  if n == 0:

    return 0

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

  j = 2**(a+b)

  while True:

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

    if k >= j:

      return j

    j = k

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

# Jason Kimberley, Nov 09 2016

CROSSREFS

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

Column k=1 of A281871.

Sequence in context: A227581 A263846 A178786 * A111850 A059396 A108602

Adjacent sequences:  A000193 A000194 A000195 * A000197 A000198 A000199

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

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 June 25 00:41 EDT 2017. Contains 288708 sequences.