Marshmallow patience game math

Computer Science Math
1

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.

2

These are the Fibonacci numbers!

3

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.

4

i watched it too and that's the sequence

5

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

6

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?

7

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.

8

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

9

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