OFFSET
1,2
COMMENTS
This sequence is bounded above by A000041.
Conjecture: A000041(n) - a(n) = 0 if and only if n is a power of 2, and
Conjecture: A000041(n) - a(n) = 1 if and only if n is an odd prime.
Order does not matter: a state containing one pile of two stones and one pile of three stones is considered the same as a state containing one pile of three stones and one pile of two stones.
A056219 is the analogous sequence when only one stone can be moved between piles, and A018819 is the analogous sequence when all stones must be moved between piles. - Peter Kagey, Sep 24 2017
Consider the inverse operation: either divide an even stack in two, or replace two stacks of equal parity with their averages. The states which have no inverse moves are precisely those with all parts equal and odd. If n is a power of two, its only odd divisor is 1 and so every state can be inverted to the all-ones state, and if n is an odd prime then the only states which cannot be inverted are the all-ones state and [n]. If n has an odd divisor d with 1 < d < n, then unreachable states include the all-d's state and any state obtainable from it by combining d's in pairs, of which there is at least one. Therefore, both conjectures are true. - Charlie Neder, Jan 28 2019
LINKS
Charlie Neder, Table of n, a(n) for n = 1..60
Reddit User _AUTOMATIC_, Questions about this combinatorial puzzle
EXAMPLE
For n = 5, the a(5) = 6 states are:
(1 1 1 1 1), (2 1 1 1), (2 2 1), (3 1 1), (3 2), and (4 1).
To reach state (3 2) starting from (1 1 1 1 1):
(1 1 1 1 1) -> (2 1 1 1) -> (2 2 1) -> (3 1 1) -> (3 2).
CROSSREFS
KEYWORD
nonn
AUTHOR
Peter Kagey, Sep 21 2017
EXTENSIONS
a(44)-a(50) from Charlie Neder, Jan 28 2019
STATUS
approved