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.

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

Author

Peter Kagey, Sep 21 2017

Keywords

• nonn

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.

Examples

			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].
		

Crossrefs

Cf. A000009.

Programs

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

Extensions

a(49)-a(60) from Bert Dobbelaere, Jul 14 2019