OFFSET
1,2
COMMENTS
a(n+1) - a(n) <= 1 but not bounded from below.
a(n) <= n.
FORMULA
a(1) = 1; a(k^2) = a(k); a(k+1) = a(k)+1 for k not square.
EXAMPLE
a(9) = a(3) = 3 since 9 = 3^2 and a(6) = a(5) + 1 = 4 as 6 is not a square.
a(1000) = a(31) + 39 = a(5) + 6 + 39 = a(2) + 1 + 6 + 39 = 48.
MATHEMATICA
a[1] = 1; a[n_] := a[n] = n - (s = Floor @ Sqrt[n])^2 + a[s]; Array[a, 100] (* Amiram Eldar, Sep 30 2020 *)
PROG
(Python3)
from gmpy2 import is_square, isqrt
def a(n):
if n == 1:
return 1
return a(isqrt(n)) + n - isqrt(n) ** 2
(Python3)
from gmpy2 import is_square, isqrt
a = [0, 1]
for i in range(2, n+1):
if is_square(i):
a.append(a[isqrt(i)])
else:
a.append(a[i-1]+1)
(PARI) a(n)={my(t=0); while(n > 1, my(k=sqrtint(n)); t+=(n-k^2); n=k); t+n} \\ Andrew Howroyd, Sep 29 2020
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Valentin Imbach, Sep 28 2020
STATUS
approved