|
|
A292728
|
|
a(n) is the number of terminal states that can be achieved via the following algorithm: start with n piles each containing one stone; stones can be transferred between piles only when the piles start with the same number of stones.
|
|
2
|
|
|
1, 1, 1, 2, 2, 2, 4, 6, 6, 7, 11, 11, 17, 18, 23, 32, 37, 39, 53, 58, 70, 83, 103, 112, 139, 158, 184, 214, 255, 279, 339, 390, 435, 503, 578, 647, 759, 854, 963, 1099, 1259, 1395, 1609, 1804, 2015, 2292, 2589, 2870, 3259, 3638, 4058, 4568, 5119, 5663, 6364, 7090, 7862, 8793, 9791, 10795
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
A terminal state is one in which no more transfers can be made.
The sequence is bounded above by A000009.
Conjecture: a(n) = A000009(n) if and only if n is a power of 2.
Conjecture: A000009(n) - a(n) = 1 if and only if n is an odd prime.
|
|
LINKS
|
|
|
EXAMPLE
|
For n = 10, the a(10) = 7 terminal states are: [4, 3, 2, 1], [5, 3, 2], [5, 4, 1], [6, 3, 1], [6, 4], [7, 2, 1], and [8, 2].
The algorithm does not reach the other four possible terminal states: [5, 5], [7, 3], [9, 1], and [10].
|
|
PROG
|
(Python)
....s_todo, s_done = set([(1, )*n]), set()
....count=0
....while len(s_todo) > 0:
........s_new = set()
........for s in s_todo:
............last = -1 ; idx = 0 ; final = True
............while (idx+1) < len(s):
................h = s[idx]
................if h!=last and s[idx+1]==h:
....................final = False
....................for q in range(1, h+1):
........................lst = list(s[:idx]) + list(s[idx+2:])
........................lst += [2*h] if h==q else [ h-q, h+q]
........................t = tuple(sorted(lst))
........................if (not t in s_todo and
............................not t in s_new and
............................not t in s_done):
............................s_new.add(t)
................last = s[idx] ; idx += 1
............if final: count += 1
........s_done.update(s_todo) ; s_todo = s_new
....return count
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|