A109964 - OEIS

%I #27 Sep 03 2024 21:01:03

%S 1,1,1,1,2,2,2,3,3,4,4,4,5,5,6,6,7,7,8,8,8,9,9,10,10,11,11,12,12,13,

%T 13,14,14,15,15,16,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,

%U 24,25,25,26,26,27,27,28,28,29,29,30,30,31,31,32,32,32,33,33,34,34,35,35

%N a(n) = floor(sqrt(Sum_{i<n} a(i))), with a(0)=1.

%D Related problem was offered at XXIX Moscow Mathematical Olympiad (1966).

%F a(n) = floor(sqrt(A109965(n))) = A109965(n+1)-A109965(n). Roughly (n-log_2(n))/2. 1 appears four times, other powers of 2 appear three times, other numbers appear twice.

%F From _Paul Weisenhorn_, Jun 22, Jun 26 2010: (Start)

%F For n>1, a(n)=2^j+k where j=floor(log_2(n))-1 and k=(n-2^(j+1)-j) mod 2.

%F a(2^(j+1)+j+2*k) = a(2^(j+1)+j+2*k+1) = 2^j+k; a(2^(j+1)+j-1) = 2^j for all j=0..infinity, k=0..(2^j-1).

%F (End)

%e a(5) = floor(sqrt(1+1+1+1+2)) = floor(sqrt(8)) = 2.

%e From _Paul Weisenhorn_, Jun 22, Jun 26 2010: (Start)

%e n=21; j=3; k=1; a(21)=2^3+1=9;

%e j=3; k=4; a(27)=a(28)=12.

%e (End)

%p sumr:=0: a(0):=1: for n from 1 to 1000 do sumr:=sumr+a(n-1): a(n):=floor(sqrt(sumr)): end do: # _Paul Weisenhorn_, Jun 22 2010

%p a(0..1)=1; for n from 2 to 100 do j:=floor(log[2](n))-1: k:=iquo(n-2^(j+1)-j,2): a(n):=2^j+k: end do: # _Paul Weisenhorn_, Jun 26 2010

%t lst={1};Nest[AppendTo[lst,Floor[Sqrt[Total[lst]]]]&,1,85] (* _Harvey P. Dale_, May 24 2012 *)

%K nonn

%O 0,5

%A _Henry Bottomley_, Jul 06 2005

%E Formulas corrected by _Paul Weisenhorn_, Aug 11 2010

%E Formula a(0..3)=1; a(n)=iquo(n+1-floor(log[2](n-2)),2); n=4..infinity; deleted and second Maple program changed _Paul Weisenhorn_, Aug 22 2010