cp's OEIS Frontend

A054248 Binary entropy: a(n) = n + min { a(k)+a(n-k) : 1 <= k <= n-1 }.

%I A054248 #30 Mar 30 2023 01:59:39
%S A054248 1,2,6,8,13,16,21,24,30,34,40,44,50,54,60,64,71,76,83,88,95,100,107,
%T A054248 112,119,124,131,136,143,148,155,160,168,174,182,188,196,202,210,216,
%U A054248 224,230,238,244,252,258,266,272,280,286,294,300,308,314,322,328,336
%N A054248 Binary entropy: a(n) = n + min { a(k)+a(n-k) : 1 <= k <= n-1 }.
%D A054248 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, p. 374.
%H A054248 Alois P. Heinz, <a href="/A054248/b054248.txt">Table of n, a(n) for n = 1..10000</a>
%H A054248 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint 2016.
%H A054248 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
%F A054248 a(n) = A123753(n-1) - (n-1) mod 2. - _Peter Luschny_, Nov 30 2017
%p A054248 A054248 := proc(n) local i,j; option remember; if n<=2 then n else j := 10^10; for i from 1 to n-1 do if A054248(i)+A054248(n-i) < j then j := A054248(i)+A054248(n-i); fi; od; n+j; fi; end;
%p A054248 # second Maple program:
%p A054248 a:= proc(n) option remember; `if`(n<3, n,
%p A054248       n + min(seq(a(k)+a(n-k), k=1..n/2)))
%p A054248     end:
%p A054248 seq(a(n), n=1..80);  # _Alois P. Heinz_, Aug 29 2015
%t A054248 a[n_] := n + n IntegerLength[n, 2] - 2^IntegerLength[n, 2] + Mod[n, 2];
%t A054248 Table[a[n], {n, 1, 54}] (* _Peter Luschny_, Dec 02 2017 *)
%o A054248 (Python)
%o A054248 def A054248(n):
%o A054248     s, i, z = n - (n-1) % 2, n-1, 1
%o A054248     while 0 <= i: s += i; i -= z; z += z
%o A054248     return s
%o A054248 print([A054248(n) for n in range(1, 55)]) # _Peter Luschny_, Nov 30 2017
%o A054248 (Python)
%o A054248 def A054248(n): return n*(1+(m:=(n-1).bit_length()))-(1<<m)+(n&1) # _Chai Wah Wu_, Mar 29 2023
%Y A054248 Cf. A003314, A123753.
%K A054248 nonn
%O A054248 1,2
%A A054248 _N. J. A. Sloane_, May 04 2000