|
%I #23 Oct 01 2023 16:03:18
%S 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,
%T 52,65,76,95,123,138,186,221,275,322,388,507,619,739,976,1127,1395,
%U 1677,2002,2631,3247,3883,5226,6056,7464,9084,10907,14150,17823,21509,28615,33509,41433,51044
%N 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.
%C 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.
%C This is possible for every nonnegative integer n except for n=2 and n=5.
%C The sequence increases roughly exponentially from n=19.
%C The ratios between successive terms tend to between 1.15 and 1.37, showing a pattern with a period of 8.
%H Stelio Passaris, <a href="/A364721/b364721.txt">Table of n, a(n) for n = 0..1000</a>
%H Inspired by a puzzle set by Shonit Baradia, <a href="https://www.reddit.com/r/mathriddles/comments/15eeqf7/moving_balls/">Moving Balls</a> (2023).
%e 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.
%o (Python)
%o def a(n):
%o paths = [[0]*(n+1) for _ in range(n+1)]
%o paths[0][0] = 1
%o result = paths[0][n]
%o for turn in range(1,n+1):
%o for value in range(n+1):
%o if paths[turn-1][value] > 0:
%o if value-turn >= 0:
%o paths[turn][value-turn] += paths[turn-1][value]
%o if value+turn <= n:
%o paths[turn][value+turn] += paths[turn-1][value]
%o result += paths[turn][n]
%o return result
%K nonn
%O 0,10
%A _Stelio Passaris_, Aug 04 2023
|
