|
|
A022554
|
|
a(n) = Sum_{k=0..n} floor(sqrt(k)).
|
|
18
|
|
|
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, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120, 125, 131, 137, 143, 149, 155, 161, 167, 173, 179, 185, 191, 197, 203, 210, 217, 224, 231, 238, 245, 252, 259, 266, 273, 280
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
It seems that 197 is the largest prime in this sequence. Tested for n <= 10^11. - Hugo Pfoertner, Oct 26 2020
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
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
|
|
REFERENCES
|
R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd Edition, Addison-Wesley, 1994, Eq. 3.27 on page 87.
D. E. Knuth, The Art of Computer Programming, Vol. 1, 3rd Edition, Addison-Wesley, 1997, Ex. 43 of section 1.2.4.
K. H. Rosen, Discrete Mathematics and Its Application, 6th Edition, McGraw-Hill, 2007, Ex. 25 of section 2.4.
|
|
LINKS
|
|
|
FORMULA
|
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.
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
a(n) = m*(n - m^2/3 - m/2 + 5/6) where m = floor(sqrt(n)). - M. F. Hasler, Apr 23 2022
|
|
EXAMPLE
|
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 + ...
|
|
MAPLE
|
seq(add(floor(sqrt(k)), k=0..n), n=0..59);
|
|
MATHEMATICA
|
Accumulate[Floor[Sqrt[Range[0, 60]]]] (* Harvey P. Dale, Feb 16 2011 *)
Table[Sum[Floor[Sqrt[i]], {i, 0, n}], {n, 0, 50}] (* G. C. Greubel, Dec 22 2016 *)
|
|
PROG
|
(Magma) [&+[Floor(Sqrt(k)): k in [0..n]]: n in [0..50]]; // G. C. Greubel, Feb 26 2018
(Python)
from math import isqrt
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
Michel Tixier (tixier(AT)dyadel.net)
|
|
EXTENSIONS
|
More terms from Yong Kong (ykong(AT)curagen.com), Mar 10 2001
|
|
STATUS
|
approved
|
|
|
|