OFFSET
0,3
COMMENTS
Erdős asked whether this sequence is o(n^2), motivated by A234813.
Konieczny proved the answer is "no", both by constructing an explicit permutation with n^2/4 distinct consecutive sums, and also showing that a random permutation has ~n^2(1+e^-2)/4 distinct consecutive sums.
REFERENCES
P. Erdős, Problems in number theory and combinatorics. Proceedings of the Sixth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1976) (1977), 35-58.
P. Erdős, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72.
P. Erdős and R. Graham, Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique (1980).
LINKS
Thomas Bloom, Problem 34, Erdős Problems.
Erdős problems database contributors, Issue #95 linking Erdős problems to the OEIS.
J. Konieczny, On consecutive sums in permutations. arXiv:1504.07156 [math.CO], 2015-2021.
EXAMPLE
For n=5, {1, 2, 3, 5, 4} is one of many having 13 distinct consecutive sums, namely 1, 2, 3=1+2, 4, 5=2+3, 1+2+3, 3+5, 5+4, 2+3+5, 1+2+3+5, 3+5+4, 2+3+5+4, and 1+2+3+5+4.
For n=8, {1, 3, 8, 4, 6, 7, 2, 5} and its reversal are the unique permutations that have 32 distinct consecutive sums.
PROG
(Python)
from itertools import combinations, permutations
def f(p): return len(set(sum(p[i:j]) for i, j in combinations(range(len(p)+1), 2)))
def a(n): return max(f(p) for p in permutations(range(1, n+1)))
print([a(n) for n in range(10)]) # Michael S. Branicky, Oct 07 2025
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Boris Alexeev, Sep 26 2025
STATUS
approved