A292729 - OEIS

A292729

a(n) is the maximum number of steps that can occur during the following procedure: start with n piles each containing one stone; any number of stones can be transferred between piles of equal size.

%I #25 Nov 05 2024 18:56:52

%S 0,1,1,3,4,4,8,10,11,12,16,20,22,24,27,31,35,38,43,45,47,52,57,62,67,

%T 71,74,79,83,90,95,101,106,111,114,118,126,132,138,146,152,156,161,

%U 167,172,180,189,194,204,208,216,221,228,234,242,249,258,264,274,282

%N a(n) is the maximum number of steps that can occur during the following procedure: start with n piles each containing one stone; any number of stones can be transferred between piles of equal size.

%C Note that more than one stone can be moved during a single move.

%C A121924 is the analogous sequence if only one stone can be transferred between piles of equal size.

%C A011371 is the analogous sequence if all stones must be transferred between piles of equal size (i.e., the number of stones in each pile must be a power of two).

%C Both A121924 and A011371 are lower bounds for this sequence.

%e For n = 7, an 8-move sequence is:

%e (1 1 1 1 1 1 1) -> (2 1 1 1 1 1) -> (2 2 1 1 1) -> (3 1 1 1 1) -> (3 2 1 1) -> (3 2 2) -> (3 3 1) -> (5, 1, 1) -> (5 2).

%o (Python)

%o def A292729(n):

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

%o count=-1

%o while len(s_in) > 0:

%o s_out = set()

%o for s in s_in:

%o last = -1 ; idx = 0

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

%o h = s[idx]

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

%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_out:

%o s_out.add(t)

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

%o count += 1

%o s_in = s_out

%o return count

%o # _Bert Dobbelaere_, Jul 14 2019

%Y Cf. A011371, A121924, A292726, A292728.

%K nonn

%O 1,4

%A _Peter Kagey_, Sep 22 2017

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