A000267 Integer part of square root of 4n+1.

1, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice
• tabf

Comments

1^1, 2^1, 3^2, 4^2, 5^3, 6^3, 7^4, 8^4, 9^5, 10^5, ...

Start with n, repeatedly subtract the square root of the previous term; a(n) gives number of steps to reach 0. - Robert G. Wilson v, Jul 22 2002

Triangle A094727 read by diagonals. - Philippe Deléham, Mar 21 2014

Partial sums of A240025; a(n) = number of quarter squares <= n. - Reinhard Zumkeller, Jul 05 2014

Every number k is present consecutively (floor((2*k+3)/4)) times. - Bernard Schott, Jun 08 2019

Examples

			From _Philippe Deléham_, Mar 21 2014: (Start)
Triangle A094727 begins:
  1;
  2,  3;
  3,  4,  5;
  4,  5,  6,  7;
  5,  6,  7,  8,  9;
  6,  7,  8,  9, 10, 11; ...
Read by diagonals:
   1;
   2;
   3,  3;
   4,  4;
   5,  5,  5;
   6,  6,  6;
   7,  7,  7,  7;
   8,  8,  8,  8;
   9,  9,  9,  9,  9;
  10, 10, 10, 10, 10; (End)
G.f. = 1 + 2*x + 3*x^2 + 3*x^3 + 4*x^4 + 4*x^5 + 5*x^6 + 5*x^7 + 5*x^8 + 6*x^9 + ...
		

References

• Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 73, problem 20.
• Bruce C. Berndt, Ramanujan's Notebooks Part IV, Springer-Verlag, 1994, see p. 77, Entry 23.

Links

• T. D. Noe, Table of n, a(n) for n = 0..10000
• Gal Cohensius, Urban Larsson, Reshef Meir, and David Wahlstedt, Cumulative subtraction games, arXiv:1805.09368 [math.CO], 2018-2020.
• S. Ramanujan, Question 723, J. Ind. Math. Soc., Vol. 7 (1915), p. 240, Vol. 10 (1918), pp. 357-358.

Crossrefs

Cf. A055086, A080037, A227368.

Cf. A000196, A002620, A016813, A070939, A094727, A240025.

Programs

Haskell

a000267 = a000196 . a016813  -- Reinhard Zumkeller, Dec 13 2012

Magma

[Floor(Sqrt(4*n+1)): n in [0..100]]; // Vincenzo Librandi, Jun 08 2019

Maple

A000267:=seq(floor(sqrt(4*n+1)), n=0..100); // Bernard Schott, Jun 08 2019

Mathematica

Table[Floor[Sqrt[4*n + 1]], {n, 0, 100}] (* T. D. Noe, Jun 19 2012 *)

PARI

{a(n) = if( n<0, 0, sqrtint(4*n + 1))};

Python

from math import isqrt
def A000267(n): return isqrt((n<<2)|1) # Chai Wah Wu, Nov 23 2024

Formula

floor(a(n)/2) = A000196(n).

a(n) = 1 + a(n - floor(n^(1/2))), if n>0. - Michael Somos, Jul 22 2002

a(n) = floor( 1 / ( sqrt(n + 1) - sqrt(n) ) ). - Robert A. Stump (bob_ess107(AT)yahoo.com), Apr 07 2003

a(n) = |{floor(n/k): k in Z+}|. - David W. Wilson, May 26 2005

a(n) = ceiling(2*sqrt(n+1) - 1). - Mircea Merca, Feb 03 2012

a(n) = A000196(A016813(n)). - Reinhard Zumkeller, Dec 13 2012

a(n) = A070939(A227368(n+1)), conjectured. - Antti Karttunen, Dec 28 2013

a(n) = floor( sqrt(n) + sqrt(n+2) ). [Bruno Berselli, Jan 08 2015]

a(n) = floor( sqrt(4*n + k) ) where k = 1, 2, or 3. - Michael Somos, Mar 11 2015

G.f.: (Sum_{k>0} x^floor(k^2 / 4)) / (1 - x). - Michael Somos, Mar 11 2015

a(n) = 1 + A055086(n). - Michael Somos, Sep 02 2017

a(n) = floor(sqrt(n+1)+1/2) + floor(sqrt(n)). - Ridouane Oudra, Jun 07 2019

Sum_{k>=0} (-1)^k/a(k) = Pi/8 + log(2)/4. - Amiram Eldar, Jan 26 2024

Extensions

More terms from Michael Somos, Jun 13 2000