A336860 a(n) = 1 + the total remainder when repeatedly taking integer square roots until 1 is reached.

1, 2, 3, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 8, 9, 2, 3, 4, 5, 6, 7, 8, 9, 10, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22

Offset

1,2

Comments

a(n+1) - a(n) <= 1 but not bounded from below.

a(n) <= n.

Links

Table of n, a(n) for n=1..80.

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

Cf. A053186.

Sequence in context: A256992 A261323 A134986 * A216209 A289172 A215653

Adjacent sequences: A336857 A336858 A336859 * A336861 A336862 A336863

Keyword

nonn,easy

Author

Valentin Imbach, Sep 28 2020

Status

approved