login
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
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.
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)
def A292728(n):
....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
# Bert Dobbelaere, Jul 14 2019
CROSSREFS
Cf. A000009.
Sequence in context: A008238 A218870 A264869 * A365719 A096575 A002722
KEYWORD
nonn
AUTHOR
Peter Kagey, Sep 21 2017
EXTENSIONS
a(49)-a(60) from Bert Dobbelaere, Jul 14 2019
STATUS
approved