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

1, 3, 5, 8, 10, 13, 16, 20, 22, 25, 28, 32, 35, 39, 43, 48, 50, 53, 56, 60, 63, 67, 71, 76, 79, 83, 87, 92, 96, 101, 106, 112, 114, 117, 120, 124, 127, 131, 135, 140, 143, 147, 151, 156, 160, 165, 170, 176, 179, 183, 187, 192, 196, 201, 206, 212, 216, 221, 226, 232

Offset: 1

Author

Stefano Spezia, Nov 28 2019

Keywords

• nonn

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.

Crossrefs

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

Cf. A144935, A325831.

Programs

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]];

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 *)

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

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)