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.

%I #21 Nov 05 2024 18:57:40

%S 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,

%T 158,184,214,255,279,339,390,435,503,578,647,759,854,963,1099,1259,

%U 1395,1609,1804,2015,2292,2589,2870,3259,3638,4058,4568,5119,5663,6364,7090,7862,8793,9791,10795

%N 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.

%C A terminal state is one in which no more transfers can be made.

%C The sequence is bounded above by A000009.

%C Conjecture: a(n) = A000009(n) if and only if n is a power of 2.

%C Conjecture: A000009(n) - a(n) = 1 if and only if n is an odd prime.

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

%e The algorithm does not reach the other four possible terminal states: [5, 5], [7, 3], [9, 1], and [10].

%o (Python)

%o def A292728(n):

%o s_todo, s_done = set([(1, )*n]), set()

%o count=0

%o while len(s_todo) > 0:

%o s_new = set()

%o for s in s_todo:

%o last = -1 ; idx = 0 ; final = True

%o while (idx+1) < len(s):

%o h = s[idx]

%o if h!=last and s[idx+1]==h:

%o final = False

%o for q in range(1, h+1):

%o lst = list(s[:idx]) + list(s[idx+2:])

%o lst += [2*h] if h==q else [ h-q, h+q]

%o t = tuple(sorted(lst))

%o if (not t in s_todo and

%o not t in s_new and

%o not t in s_done):

%o s_new.add(t)

%o last = s[idx] ; idx += 1

%o if final: count += 1

%o s_done.update(s_todo) ; s_todo = s_new

%o return count

%o # _Bert Dobbelaere_, Jul 14 2019

%Y Cf. A000009.

%K nonn

%O 1,4

%A _Peter Kagey_, Sep 21 2017

%E a(49)-a(60) from _Bert Dobbelaere_, Jul 14 2019