|
|
A000196
|
|
Integer part of square root of n. Or, number of positive squares <= n. Or, n appears 2n+1 times.
|
|
335
|
|
|
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
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
|
|
REFERENCES
|
Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, p. 73, problem 23.
Lionel Levine, Fractal sequences and restricted Nim, Ars Combin. 80 (2006), 113-127.
Paul 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
|
|
|
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
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)
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
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. (End)
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
|
|
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 *)
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..]
(Python)
# from http://code.activestate.com/recipes/577821-integer-square-root-function/
if n < 0:
raise ValueError('only defined for nonnegative 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)])
(Python)
from math import isqrt
def a(n): return isqrt(n)
(Scheme)
;; 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).
;; 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.
(Julia)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|