A330038 - OEIS

%I #28 Sep 08 2022 08:46:24

%S 1,3,5,8,10,13,16,20,22,25,28,32,35,39,43,48,50,53,56,60,63,67,71,76,

%T 79,83,87,92,96,101,106,112,114,117,120,124,127,131,135,140,143,147,

%U 151,156,160,165,170,176,179,183,187,192,196,201,206,212,216,221,226,232

%N a(1) = 1, a(n) = [n/2] + a([n/2]) + a([(n+1)/2]) for n > 1, where [x] = floor(x).

%C a(n) is a sharp lower bound of the greatest whole number k such that there is a hypergraph (V, H) with |V| = k having no isolated vertices and containing no partitions of size greater than n (see Brian & Larson link, i.e. Definition 3.1, Lemma 4.2 and Proof of Theorem 4.6).

%C Partial sums of A063787. - _Robert Israel_, Nov 28 2019

%H Will Brian and Paul B. Larson, <a href="https://arxiv.org/abs/1908.10914">Choosing between incompatible ideals</a>, arXiv:1908.10914 [math.CO], 2019.

%F G.f. g(z) satisfies g(z) = z^2/((1+z)(1-z)^2) + (1+z)^2 g(z^2)/z. - _Robert Israel_, Nov 28 2019

%F From _Kevin Ryde_, Dec 16 2021: (Start)

%F a(n) = A000788(n-1) + n.

%F a(n) = (1/2) * Sum_{i=1..k} (e[i]+2*i) * 2^e[i], where binary expansion n = 2^e[1] + ... + 2^e[k] with descending exponents e[1] > e[2] > ... > e[k] (A272011).

%F (End)

%p f:= proc(n) option remember;

%p floor(n/2) + procname(floor(n/2)) + procname(floor((n+1)/2))

%p end proc:

%p f(1):= 1:

%p map(f, [$1..100]); # _Robert Israel_, Nov 28 2019

%t a[1] = 1; a[n_] := a[n] = Floor[n/2] + a[Floor[n/2]] + a[Floor[(n + 1)/2]];  Array[a, 60] (* _Amiram Eldar_, Nov 28 2019 *)

%o (Magma) I:=[1]; [n le 1 select I[n] else Floor(n/2)+Self(Floor(n/2))+Self(Floor((n+1)/2)): n in [1..60]];

%o (PARI) a(n) = my(v=binary(n),t=#v); for(i=1,#v, if(v[i],v[i]=t++,t--);); fromdigits(v,2)>>1; \\ _Kevin Ryde_, Dec 16 2021

%o (Python) # Kevin Ryde's first formula

%o def a(n): return sum(bin(i).count("1") for i in range(n)) + n

%o print([a(n) for n in range(1, 61)]) # _Michael S. Branicky_, Dec 16 2021

%o (Python) # Kevin Ryde's second formula

%o def a(n):

%o     b = list(map(int, bin(n)[2:]))

%o     e = [i for i, bi in enumerate(b[::-1]) if bi][::-1]

%o     return sum((ei + 2*i)*2**ei for i, ei in enumerate(e, 1))//2

%o print([a(n) for n in range(1, 61)]) # _Michael S. Branicky_, Dec 16 2021

%Y Cf. A004526, A063787 (first differences), A000788, A272011.

%Y Cf. A144935, A325831.

%K nonn

%O 1,2

%A _Stefano Spezia_, Nov 28 2019