A350102 Number of self-measuring subsets of the initial segment of the natural numbers strictly below n. Number of subsets S of [n] with S = distset(S).

1, 2, 3, 5, 7, 10, 12, 16, 18, 22, 25, 29, 31, 37, 39, 43, 47, 52, 54, 60, 62, 68, 72, 76, 78, 86, 89, 93, 97, 103, 105, 113, 115, 121, 125, 129, 133, 142, 144, 148, 152, 160, 162, 170, 172, 178, 184, 188, 190, 200, 203, 209, 213, 219, 221, 229, 233, 241, 245

Offset: 0

Author

Peter Luschny, Dec 14 2021

Keywords

• nonn

Comments

We use the notation [n] = {0, 1, ..., n-1}. If S is a subset of [n] then we define the distset of S (set of distances of S) as {|x - y|: x, y in S}. We call a subset S of the natural numbers self-measuring if and only if S = distset(S).

Examples

			a(0) = 1 = card({}).
a(4) = 7 = card({}, {0}, {0, 1}, {0, 2}, {0, 3}, {0, 1, 2}, {0, 1, 2, 3}).
a(6) = 12 = card({}, {0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 1, 2}, {0, 2, 4}, {0, 1, 2, 3}, {0, 1, 2, 3, 4}, {0, 1, 2, 3, 4, 5}).
		

Links

• Winston de Greef, Table of n, a(n) for n = 0..10000
• Peter Luschny, Illustrating self-measuring subsets of {0, 1, 2, 3}.

Crossrefs

Cf. A350103, A349976, A006218, A054519, A000005.

Programs

Maple

A350102 := n -> ifelse(n = 0, 1, 2 + add(iquo(n-1, k), k = 1 .. n-1)):
seq(A350102(n), n = 0 .. 58);

Mathematica

a[0] = 1; a[1] = 2; a[n_] := a[n] = a[n - 1] + DivisorSigma[0, n - 1];
Table[a[n], {n, 0, 58}]

Formula

a(n) = a(n - 1) + tau(n - 1) for n >= 2, tau = A000005.

a(n) = 2 + Sum_{k=1..n-1} floor((n - 1)/k) for n >= 1.

a(n) = 2 + A006218(n - 1) for n >= 1.

a(n) = 1 + A054519(n - 1) for n >= 1.

Row sums of A350103.

a(n) >= n + floor(n/2) + floor(n/3).