login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A161531 The number of reachable states in a simple two-player counting game, in which each player starts with the pair (1,1) and one move is to add one of the opponent's numbers to one of your own numbers, but no number can grow above a pre-defined maximum n. The game continues until one of the players has no legal moves left. The winner is the one having the higher sum of his numbers. 0
1, 4, 13, 34, 75, 152, 301, 482, 794, 1197, 1842, 2522, 3582, 4772, 6408, 8229, 10728, 13285, 16851, 20569, 25361, 30380, 36927, 43251, 51692, 60199, 70668, 81452, 95083, 107664, 124360, 140539, 160222, 179821, 204026, 226607, 255551, 283320 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

For many n (1 <= n <= 100), optimal play leads to a draw.

LINKS

Table of n, a(n) for n=1..38.

EXAMPLE

For n = 2 there are 4 valid states of the game: (A=1,1 B=1,1) starts the game. There is only one valid move, leading to (A=1,1 B=1,2). Now A also has only one choice (A=1,2 B=1,2), and B ends the game in the state (A=1,2 B=2,2) and wins. A has no valid move, since then one of his numbers would be larger than 2.

PROG

(Other) #include <climits> #include <iostream> #include <map> class State; typedef unsigned char byte; typedef std::map<State, int> ScoreMap; static inline int min(int a, int b) { return a < b ? a : b; } static inline int max(int a, int b) { return a > b ? a : b; } static inline int compare(int a, int b) { return a - b; }

static int MAX = 0; static ScoreMap score; struct State { byte a, b, c, d; State() : a(0), b(0), c(0), d(0) {} State(byte a, byte b, byte c, byte d) : a(min(a, b)), b(max(a, b)), c(min(c, d)), d(max(c, d)) {} int getChildren(State *children) { int n = 0; if (a + c <= MAX) children[n++ ] = State(c, d, a + c, b); if (a + d <= MAX && c != d) children[n++ ] = State(c, d, a + d, b);

if (a != b && b + c <= MAX) children[n++ ] = State(c, d, a, b + c); if (a != b && c != d && b + d <= MAX) children[n++ ] = State(c, d, a, b + d); return n; }; int getScore() { ScoreMap::iterator it = score.find(*this); if (it != score.end()) return it->second; State children[4]; int nchildren = getChildren(&children[0]); int iscore; if (nchildren == 0) { iscore = compare(a + b, c + d); } else { iscore = INT_MIN; for (int i = 0; i < nchildren; i++) iscore = max(iscore, -children[i].getScore()); } score.insert(ScoreMap::value_type(*this, iscore)); return iscore; }; };

static bool operator< (State a, State b) { if (a.a < b.a) return true; if (a.a > b.a) return false; if (a.b < b.b) return true; if (a.b > b.b) return false; if (a.c < b.c) return true; if (a.c > b.c) return false; if (a.d < b.d) return true; if (a.d > b.d) return false; return false; } int main() { std::cout << "max\tscore\tnstates" << std::endl; for (int max = 0; max < 1024; max++) { MAX = max; score.clear(); int iscore = State(1, 1, 1, 1).getScore(); std::cout << max << "\t" << iscore << "\t" << score.size() << std::endl; } return 0; }

CROSSREFS

Sequence in context: A176361 A322599 A135859 * A101946 A029860 A262200

Adjacent sequences:  A161528 A161529 A161530 * A161532 A161533 A161534

KEYWORD

nonn

AUTHOR

Roland Illig (roland.illig(AT)gmx.de), Jun 12 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 23 12:38 EDT 2019. Contains 323514 sequences. (Running on oeis4.)