|
|
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.
|
|
2
|
|
|
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, 71, 74, 79, 83, 90, 95, 101, 106, 111, 114, 118, 126, 132, 138, 146, 152, 156, 161, 167, 172, 180, 189, 194, 204, 208, 216, 221, 228, 234, 242, 249, 258, 264, 274, 282
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Note that more than one stone can be moved during a single move.
A121924 is the analogous sequence if only one stone can be transferred between piles of equal size.
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).
|
|
LINKS
|
|
|
EXAMPLE
|
For n = 7, an 8-move sequence is:
(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).
|
|
PROG
|
(Python)
....s_in = set([(1, )*n])
....count=-1
....while len(s_in) > 0:
........s_out = set()
........for s in s_in:
............last = -1 ; idx = 0
............while (idx+1) < len(s):
................h = s[idx]
................if h!=last and s[idx+1]==h:
....................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_out:
............................s_out.add(t)
................last = s[idx] ; idx += 1
........count += 1
........s_in = s_out
....return count
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|