A217871 a(n)=b(n,1) where b(0,m)=m, b(n,m)=b(floor(n/4),m*2).

1, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16

Offset

0,2

Comments

Part of the Newton integer square-root finding process. Establishes the upper bound a(n) >= A000196(n) for all n >= 0.

Links

Table of n, a(n) for n=0..90.

Formula

a(n)=b(n,1) where b(0,m)=m; b(n,m)=b(floor(n/4),m*2).

a(n)=2^ceiling(A029837(n+1)/2).

Prog

(Common Lisp)
(defun A217871 (n)
  (labels ((rec (n guess)
           (if (zerop n)
               guess
               (rec (floor n 4) (* guess 2)))))
    (rec n 1))) ; James Spahlinger, Oct 14 2012

Crossrefs

Cf. A000196

Sequence in context: A195051 A219654 A096491 * A362872 A306390 A106160

Adjacent sequences: A217868 A217869 A217870 * A217872 A217873 A217874

Keyword

nonn

Author

James Spahlinger, Oct 13 2012

Status

approved