# Marshmallow patience game math

I was thinking about the marshmallow patience game where you're given a marshmallow and you can either eat it or wait for several minutes and have two marshmallows instead. Specifically, I was thinking of a generalized n-round variant, where, in any round, you can eat as many marshmallows as you want, and the next round you start with twice what you didn't eat. I then decided on a simple strategy: every round, eat the floor of 1/4 of the marshmallows you have. I then did a bit of math and got three sequences: the number of marshmallows you start each round with, the number you eat each round, and the number you end each round with. I calculated a few values in my head:

  1  0 1
2  0 2
4  1 3
6  1 5
10  2 8
16  4 12
24  6 18
36  9 27
54 13 41
82 20 62
124 31 93
186 46 140
.  . .
.  . .
.  . .


And so I looked all three sequences up in the OEIS. The first two don't seem to be on it, unless they are but start on a different value. However, the third sequence, 1, 2, 3, 5, 8, 12, 18, 27, 41, ..., is on it, twice: A061419 and A156623. The former, A061419, had a recursive formula that at first glance didn't seem the same as mine (a(n) = ceiling(a(n-1)*3/2) vs. a(n) = ceiling(a(n-1)*2-(a(n-1)*2)/4)), but I managed to algebra mine into the OEIS one, so yes, they are the exact same sequence.

This was just me messing around with a game and getting a bit of math out of it.

These are the Fibonacci numbers!

Yes, sequences can be deceptively similar in the first few terms. I'll add more terms to make it more clear that it isn't that.

Which reminds me of a sequence 1, 2, 4, 8, 16, 31, ... (if I recall correctly). 3Blue1Brown covers it in one of his videos.

i watched it too and that's the sequence

Of course you can get any sequence you want from a hairy enough polynomial!

Any arbitrary finite-length is a subset of some polynomial, but what about infinite sequences? Are there infinite sequences that can't be represented as a polynomial?

Oh. Yes, sorry. f(n) = 2^n isn't a polynomial function, so s_i = 2^i isn't a polynomial sequence. I meant finite sequences; I thought from the context that that's what we were discussing.

All the sequences I've mentioned are infinite sequences so it isn't obvious from context that you meant finite sequences.

Oh, sorry. You only listed finitely many terms of each sequence... :~)