A292726 -id:A292726 - cp's OEIS frontend

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.

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

Offset: 1

Peter Kagey, Sep 22 2017

nonn

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).
Both A121924 and A011371 are lower bounds for this sequence.

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

Cf. A011371, A121924, A292726, A292728.

def A292729(n):
    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
# Bert Dobbelaere, Jul 14 2019

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

A292727 a(n) is the number of states that cannot be achieved when starting from n piles each containing one stone, where stones can be transferred between piles only when they start with the same number of stones.

Original entry on oeis.org

0, 0, 1, 0, 1, 3, 1, 0, 3, 4, 1, 7, 1, 5, 9, 0, 1, 14, 1, 9, 17, 7, 1, 26, 7, 8, 30, 11, 1, 55, 1, 0, 58, 10, 21, 83, 1, 11, 103, 30, 1, 150, 1, 15, 203, 13, 1, 239, 15, 52, 299, 17, 1, 394, 62, 34, 492, 16, 1, 707, 1, 17, 819, 0, 107, 1021, 1, 21, 1257, 187, 1, 1587

Offset: 1

Peter Kagey, Sep 21 2017

nonn

Note that more than one stone can be moved during a single move.
Conjecture: a(n) = 0 if and only if n is a power of 2.
Conjecture: a(n) = 1 if and only if n is an odd prime.

			For n = 10, the a(10) = 4 partitions of 10 that cannot be generated from transferring stones are: [5, 5], [7, 3], [9, 1], and [10].

Bert Dobbelaere, Table of n, a(n) for n = 1..100

Cf. A000041, A292726.

a(n) = A000041(n) - A292726(n).
From Charlie Neder, Jan 26 2019: (Start)
a(2^k) = 0.
For p an odd prime, a(p) = 1 and a(2p) = (p+3)/2.
Conjecture: a(4p) = p+4, a(8p) = 2p+20. (End)

More terms from Charlie Neder, Jan 26 2019
a(61)-a(64) from Pontus von Brömssen, Sep 18 2022
More terms from Bert Dobbelaere, Feb 22 2023

A292836 a(n) is the minimum number of steps to a terminal state during the following procedure: start with n piles each containing one stone; any number of stones can be transferred between piles of equal size.

Original entry on oeis.org

0, 1, 1, 3, 3, 4, 4, 6, 7, 7, 8, 10, 10, 11, 11, 13, 14, 14, 15, 17, 17, 18, 18, 20, 21, 22, 23, 24, 24, 25, 26, 28, 29, 29, 30, 31, 32, 33, 33, 35, 36, 37, 38, 39, 39, 40, 41, 43, 44, 44, 45, 46, 47, 48, 48, 50, 51, 52, 53, 54, 54, 55, 56, 58, 59, 59, 60, 62, 62

Offset: 1

Peter Kagey, Sep 24 2017

nonn

A terminal state is one in which all pile sizes are different, that is, there are no legal remaining ways to move stones.
A121924 is the analogous sequence for when only one stone can be moved at a time.
A011371 is the analogous sequence for when all stones must be moved at once.
Both A011371 and A121924 are upper bounds for this sequence.

			For n = 6, two examples of a a(6) = 4 step walks to a terminal state are:
[1 1 1 1 1 1] -> [2, 1, 1, 1, 1] -> [2, 2, 1, 1] -> [3, 1, 1, 1] -> [3, 2, 1], and
[1 1 1 1 1 1] -> [2, 1, 1, 1, 1] -> [2, 2, 1, 1] -> [2, 2, 2] -> [4, 2].

Bert Dobbelaere, Table of n, a(n) for n = 1..100

Cf. A011371, A121924, A292726, A292729.

a(46) onwards from Bert Dobbelaere, Apr 07 2024

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Extensions

A292727 a(n) is the number of states that cannot be achieved when starting from n piles each containing one stone, where stones can be transferred between piles only when they start with the same number of stones.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A292836 a(n) is the minimum number of steps to a terminal state during the following procedure: start with n piles each containing one stone; any number of stones can be transferred between piles of equal size.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions