cp's OEIS Frontend

A022554 a(n) = Sum_{k=0..n} floor(sqrt(k)).

%I A022554 #87 Mar 12 2025 18:12:19
%S A022554 0,1,2,3,5,7,9,11,13,16,19,22,25,28,31,34,38,42,46,50,54,58,62,66,70,
%T A022554 75,80,85,90,95,100,105,110,115,120,125,131,137,143,149,155,161,167,
%U A022554 173,179,185,191,197,203,210,217,224,231,238,245,252,259,266,273,280
%N A022554 a(n) = Sum_{k=0..n} floor(sqrt(k)).
%C A022554 Partial sums of A000196. - _Michel Marcus_, Mar 01 2016
%C A022554 It seems that a(47) = 197 is the largest prime in this sequence. Tested for n <= 10^11. - _Hugo Pfoertner_, Oct 26 2020 [This is true. See A214036]
%C A022554 By drawing a picture of the sum Integral_{x=0..n} ceiling(sqrt(x)) dx, one easily sees that it is equal to n*m - Sum_{k=1..m} (k^2 - 1) with m = floor(sqrt(n)), whence the formula. - _M. F. Hasler_, Apr 23 2022
%C A022554 We can prove that 197 is the largest prime in this sequence. From the formula, 6*a(n) = m*(6n - 2m^2 - 3m + 5) where m = floor(sqrt(n)). Therefore 6*a(n) is divisible by m, which means that a(n) is divisible by A060789(m). For n>48, we have m>6, so A060789(m)>1, so a(n) is not prime; testing all n up to 48, we see that a(47)=197 is the last prime. - _Mikhail Lavrov_, Dec 09 2023
%D A022554 R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd Edition, Addison-Wesley, 1994, Eq. 3.27 on page 87.
%D A022554 D. E. Knuth, The Art of Computer Programming, Vol. 1, 3rd Edition, Addison-Wesley, 1997, Ex. 43 of section 1.2.4.
%D A022554 K. H. Rosen, Discrete Mathematics and Its Application, 6th Edition, McGraw-Hill, 2007, Ex. 25 of section 2.4.
%H A022554 David A. Corneth, <a href="/A022554/b022554.txt">Table of n, a(n) for n = 0..9999</a> (first 1001 terms from G. C. Greubel)
%H A022554 M. Griffiths, <a href="http://www.jstor.org/stable/3621862">More sums involving the floor function</a>, Math. Gaz., 86 (2002), 285-287.
%H A022554 Michael Penn, <a href="https://www.youtube.com/watch?v=kpW2V0hD0Ro">Wringing out one more result.</a>, YouTube video, 2021.
%F A022554 a(0)=0, a(1)=1; a(n) = 2*a(n-1) - a(n-2) if n is not a perfect square; a(n) = 2*a(n-1) - a(n-2) + 1 if n is a perfect square.
%F A022554 a(n) = floor(sqrt(n)) * (n-1/6*(2*floor(sqrt(n))+5)*(floor(sqrt(n))-1)). - Yong Kong (ykong(AT)curagen.com), Mar 10 2001
%F A022554 a(n) = (2/3)*n^(3/2) - (1/2)*n + O(sqrt(n)). - _Charles R Greathouse IV_, Jan 12 2012
%F A022554 G.f.: Sum_{k>=1} x^(k^2)/(1 - x)^2. - _Ilya Gutkovskiy_, Dec 22 2016
%F A022554 a(n) = m*(n - m^2/3 - m/2 + 5/6) where m = floor(sqrt(n)). - _M. F. Hasler_, Apr 23 2022
%F A022554 a(n) = n*t(n) - A000330(t(n)), where t(n) = floor(sqrt(n)). - _Ridouane Oudra_, Mar 05 2025
%e A022554 G.f. = x + 2*x^2 + 3*x^3 + 5*x^4 + 7*x^5 + 9*x^6 + 11*x^7 + 13*x^8 + 16*x^9 + ...
%p A022554 seq(add(floor(sqrt(k)), k=0..n), n=0..59);
%t A022554 Accumulate[Floor[Sqrt[Range[0,60]]]] (* _Harvey P. Dale_, Feb 16 2011 *)
%t A022554 Table[Sum[Floor[Sqrt[i]], {i,0,n}], {n,0,50}] (* _G. C. Greubel_, Dec 22 2016 *)
%o A022554 (PARI) a(n)=sum(k=1,n,sqrtint(k)) \\ _Charles R Greathouse IV_, Jan 12 2012
%o A022554 (PARI) a(n)=my(k=sqrtint(n));k*(n-(2*k+5)/6*(k-1)) \\ _Charles R Greathouse IV_, Jan 12 2012
%o A022554 (Magma) [&+[Floor(Sqrt(k)): k in [0..n]]: n in [0..50]]; // _G. C. Greubel_, Feb 26 2018
%o A022554 (Python)
%o A022554 from math import isqrt
%o A022554 def A022554(n): return (m:=isqrt(n))*(m*(-(m<<1)-3)+6*n+5)//6 # _Chai Wah Wu_, Aug 03 2022
%Y A022554 Cf. A000196 (first differences), A025224, A214036, A000330.
%K A022554 nonn,easy
%O A022554 0,3
%A A022554 Michel Tixier (tixier(AT)dyadel.net)
%E A022554 More terms from Yong Kong (ykong(AT)curagen.com), Mar 10 2001