OFFSET
1,2
COMMENTS
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).
Partial sums of A063787. - Robert Israel, Nov 28 2019
LINKS
Will Brian and Paul B. Larson, Choosing between incompatible ideals, arXiv:1908.10914 [math.CO], 2019.
FORMULA
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
From Kevin Ryde, Dec 16 2021: (Start)
a(n) = A000788(n-1) + n.
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).
(End)
MAPLE
f:= proc(n) option remember;
floor(n/2) + procname(floor(n/2)) + procname(floor((n+1)/2))
end proc:
f(1):= 1:
map(f, [$1..100]); # Robert Israel, Nov 28 2019
MATHEMATICA
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 *)
PROG
(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]];
(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
(Python) # Kevin Ryde's first formula
def a(n): return sum(bin(i).count("1") for i in range(n)) + n
print([a(n) for n in range(1, 61)]) # Michael S. Branicky, Dec 16 2021
(Python) # Kevin Ryde's second formula
def a(n):
b = list(map(int, bin(n)[2:]))
e = [i for i, bi in enumerate(b[::-1]) if bi][::-1]
return sum((ei + 2*i)*2**ei for i, ei in enumerate(e, 1))//2
print([a(n) for n in range(1, 61)]) # Michael S. Branicky, Dec 16 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Stefano Spezia, Nov 28 2019
STATUS
approved