A364721 Number of ways that n can be expressed as a sum of consecutive integers from 0 up to at most n, where any of the terms in the sum can be negated, and the partial sum from 0 is always between 0 and n inclusive.

1, 1, 0, 1, 1, 0, 1, 1, 1, 2, 2, 2, 2, 3, 2, 4, 5, 4, 6, 9, 10, 13, 15, 16, 20, 25, 28, 36, 46, 52, 65, 76, 95, 123, 138, 186, 221, 275, 322, 388, 507, 619, 739, 976, 1127, 1395, 1677, 2002, 2631, 3247, 3883, 5226, 6056, 7464, 9084, 10907, 14150, 17823, 21509, 28615, 33509, 41433, 51044

Offset

0,10

Comments

Consider two boxes, one containing n items, the other empty. On each turn t (1,2,3,...), you transfer exactly t items from one of the boxes to the other (in either direction). Then a(n) is the number of ways in which all the objects from the full box can be transferred to the empty one.

This is possible for every nonnegative integer n except for n=2 and n=5.

The sequence increases roughly exponentially from n=19.

The ratios between successive terms tend to between 1.15 and 1.37, showing a pattern with a period of 8.

Links

Stelio Passaris, Table of n, a(n) for n = 0..1000

Inspired by a puzzle set by Shonit Baradia, Moving Balls (2023).

Example

The 5 solutions for n=16 are 16 = 0+1+2+3+4+5-6+7 = 0+1+2-3+4+5+6-7+8 = 0+1+2+3-4+5-6+7+8 = 0+1+2+3-4+5+6-7+8-9+10-11+12 = 0+1+2+3+4-5+6-7+8-9+10-11+12-13+14-15+16.

Prog

(Python)
def a(n):
  paths = [[0]*(n+1) for _ in range(n+1)]
  paths[0][0] = 1
  result = paths[0][n]
  for turn in range(1, n+1):
    for value in range(n+1):
      if paths[turn-1][value] > 0:
        if value-turn >= 0:
          paths[turn][value-turn] += paths[turn-1][value]
        if value+turn <= n:
          paths[turn][value+turn] += paths[turn-1][value]
    result += paths[turn][n]
  return result

Crossrefs

Sequence in context: A058744 A366297 A323246 * A185617 A250268 A342881

Adjacent sequences: A364718 A364719 A364720 * A364722 A364723 A364724

Keyword

nonn

Author

Stelio Passaris, Aug 04 2023

Status

approved