A292728 - OEIS

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

(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

Table of n, a(n) for n=1..60.

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

Adjacent sequences: A292725 A292726 A292727 * A292729 A292730 A292731

KEYWORD

nonn,changed

AUTHOR

Peter Kagey, Sep 21 2017

EXTENSIONS

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

STATUS

approved