A185173 Minimum number of distinct sums from consecutive terms in a circular permutation.

1, 3, 6, 9, 13, 17, 22, 28, 35, 41, 49, 57, 65, 73, 82, 93, 103, 113, 125, 137

Offset: 1

Author

Steve Butler, Mar 12 2012

Keywords

• nonn
• nice
• more

Comments

a(n) <= n(n+1)/2, but this apparently is impossible for n >= 4. - N. J. A. Sloane, Mar 14 2012

Examples

			a(4)=9 because the circular permutation 1243 has no way to get 5 as a sum of consecutive terms.
a(5)=13 because the circular permutation 12534 has no way to get 6 or 9 as a sum of consecutive terms.
From _Bert Dobbelaere_, Jun 24 2019: (Start)
Permutations achieving the minimum number of distinct sums:
a(1) = 1: {1}
a(2) = 3: {1, 2}
a(3) = 6: {1, 2, 3}
a(4) = 9: {1, 2, 4, 3}
a(5) = 13: {1, 2, 5, 3, 4}
a(6) = 17: {1, 3, 2, 4, 6, 5}
a(7) = 22: {1, 3, 2, 5, 7, 4, 6}
a(8) = 28: {1, 4, 3, 7, 6, 2, 8, 5}
a(9) = 35: {1, 3, 2, 4, 5, 8, 9, 6, 7}
a(10) = 41: {1, 3, 10, 9, 4, 6, 7, 2, 8, 5}
a(11) = 49: {1, 3, 5, 2, 8, 7, 4, 11, 10, 9, 6}
a(12) = 57: {1, 2, 6, 11, 10, 7, 4, 8, 9, 12, 5, 3}
a(13) = 65: {1, 2, 10, 12, 11, 13, 7, 5, 8, 3, 9, 4, 6}
a(14) = 73: {1, 4, 7, 2, 9, 14, 13, 11, 12, 10, 3, 6, 5, 8}
a(15) = 82: {1, 4, 5, 2, 3, 8, 14, 11, 12, 10, 15, 7, 6, 9, 13}
a(16) = 93: {1, 3, 8, 5, 10, 13, 4, 11, 16, 12, 14, 7, 6, 15, 2, 9} (End)
From _Bert Dobbelaere_, Jul 08 2023: (Start)
a(17) = 103: {1, 10, 5, 11, 4, 12, 6, 9, 7, 8, 3, 13, 2, 16, 14, 17, 15}
a(18) = 113: {1, 3, 10, 15, 2, 12, 13, 5, 7, 18, 17, 8, 6, 11, 14, 16, 9, 4}
a(19) = 125: {1, 5, 10, 3, 13, 2, 16, 14, 4, 8, 7, 11, 19, 15, 18, 12, 6, 9, 17}
a(20) = 137: {1, 3, 15, 2, 10, 7, 14, 19, 18, 13, 8, 9, 4, 6, 11, 20, 17, 16, 5, 12} (End)
From _Chai Wah Wu_, Oct 01-09 2021: (Start)
The following permutation also achieves a(13) = 65: {1, 2, 9, 10, 5, 13, 8, 7, 11, 4, 3, 12, 6}.
Number of permutations (modulo cyclic shifts and reflections) that achieve a(n) for n = 1..15 are 1,1,1,1,2,1,1,2,11,1,13,7,24,1,4. (End)
		

Programs

Python

from itertools import permutations
def A185173(n):
    c = n*(n+1)//2
    for i in range(2,n+1):
        for j in range(i+1,n+1):
            pset = set(range(2,n+1)) - {i,j}
            for p in permutations(pset):
                q, rset, rl = [j,1,i]+list(p), set(), 0
                for k in range(n):
                    r = 0
                    for l in range(n):
                        r += q[(k+l) % n]
                        if r not in rset:
                            rset.add(r)
                            rl += 1
                        if rl >= c:
                            break
                    else:
                        continue
                    break
                else:
                    c = rl
    return c # Chai Wah Wu, Oct 01 2021

Sage

# a(n)=distinct_sum_count(n)
def distinct_sum_count(n):
    min_sum_count=n*(n+1)/2
    for p in Permutations(n=n):
        if p[0]==1 and p[1]
				

Extensions

a(12)-a(16) from Bert Dobbelaere, Jun 24 2019

a(17)-a(20) from Bert Dobbelaere, Jul 08 2023