login
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
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.
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
KEYWORD
nonn,hard,more
AUTHOR
Hugo Pfoertner, Jan 22 2023
EXTENSIONS
a(39)-a(40) from Hugo Pfoertner, Feb 19 2023
STATUS
approved