A360029 Consider a ruler composed of n segments with lengths 1, 1/2, 1/3, ..., 1/n with total length A001008(n)/A002805(n). a(n) is the minimum number of distinct distances of all pairs of marks that can be achieved by permuting the positions of the segments.

1, 3, 6, 10, 15, 18, 25, 33, 42, 52, 63, 71, 84, 98, 107, 123, 140, 152, 171, 185, 198, 220, 243, 256, 281, 307, 334, 354, 383, 403, 434, 466, 489, 523, 552, 581, 618, 656, 695, 728

Offset

1,2

Comments

Without permutation of the arrangement of the segments, the number of distinct distances between any pair of marks is n*(n+1)/2.

Links

Table of n, a(n) for n=1..40.

Hugo Pfoertner, Examples of rulers with the minimum number of measurable distances up to n=38, Feb 01 2023.

Example

a(6) = 18: permuted segment lengths 1, 1/4, 1/2, 1/3, 1/6, 1/5 -> marks at 0, 1, 5/4, 7/4, 25/12, 9/4, 49/20 -> 18 distinct distances 1/6, 1/5, 1/4, 1/3, 11/30, 1/2, 7/10, 3/4, 5/6, 1, 13/12, 6/5, 5/4, 29/20, 7/4, 25/12, 9/4, 49/20, whereas the non-permuted ruler with marks at 0, 1, 3/2, 11/6, 25/12, 137/60, 49/20 gives 21 distinct distances 1/6, 1/5, 1/4, 1/3, 11/30, 9/20, 1/2, 7/12, 37/60, 47/60, 5/6, 19/20, 1, 13/12, 77/60, 29/20, 3/2, 11/6, 25/12, 137/60, 49/20.

Prog

(PARI) a360029(n) = {if (n<=1, 1, my (mi=oo); w = vectorsmall(n-1, i, i+1);
forperm (w, p, my(v=vector(n, i, 1/i), L=List(v)); for (m=1, n, v[m] = 1 + sum (k=1, m-1, 1/p[k]); listput(L, v[m])); for (i=1, n-1, for (j=i+1, n, listput (L, v[j]-v[i]))); mi = min(mi, #Set(L))); mi)};

Crossrefs

Cf. A000217, A001008, A002805, A003022.

Sequence in context: A282064 A029716 A284521 * A162553 A310072 A310073

Adjacent sequences: A360026 A360027 A360028 * A360030 A360031 A360032

Keyword

nonn,hard,more

Author

Hugo Pfoertner, Jan 22 2023

Extensions

a(39)-a(40) from Hugo Pfoertner, Feb 19 2023

Status

approved