The size of a cake

Maundy Cake is Cutcake with the cut forced to make equal pieces, and its values are all integers. The rung below found what decides the sign: the cake is worth nought exactly when $\Omega(m) = \Omega(n)$, where $\Omega$ counts prime factors with multiplicity, and otherwise the sign of the value is the sign of $\Omega(n) - \Omega(m)$. That was checked over all 1,296 cakes to 36 × 36 and holds without exception.

It closed on what $\Omega$ does not give:

The size question on its own — what function of $m$ and $n$ gives the magnitude, given that $\Omega$ gives only the sign, and whether the four values 7, 10, 13 and 16 have a closed form or only a recursion.

For a one-row cake they are a formula, and it is a short one.

The formula #

Write the prime factors of $n$ in decreasing order, $q_1 \ge q_2 \ge \dots \ge q_k$. Then the $1 \times n$ cake is worth

$$V(1, n) = 1 + q_1 + q_1q_2 + \dots + q_1q_2\cdots q_{k-1},$$

the sum of the running products, one term for each prime and the empty product first.

So a prime cake is worth 1; $1 \times 4$ is $1 + 2 = 3$; $1 \times 8$ is $1 + 2 + 4 = 7$; $1 \times 12$ is $1 + 3 + 6 = 10$; $1 \times 18$ is $1 + 3 + 9 = 13$; and $1 \times 20$ is $1 + 5 + 10 = 16$.

The order matters and $\Omega$ cannot see it. Both 8 and 12 have three prime factors, so $\Omega$ says the two cakes are worth the same against any given $m$; they are worth 7 and 10. What separates them is that a cut into three multiplies what is left by three, and a cut into two multiplies by two — so the sizes of the primes are what the value is built from, and $\Omega$ counts them without looking.

Where the formula comes from #

The Maundy rule is that a cut must make equal pieces, so cutting the $n$-side into $j$ parts — for any divisor $j$ of $n$ — leaves $j$ copies of the $m \times (n/j)$ cake, which together are worth $j$ times one of them.

A one-row cake has no Right options at all: Right cuts the $m$-side and $m$ is 1. So the value is the simplest number above every Left option, which for integers is one more than the largest of them:

$$V(1, n) = 1 + \max_{j \mid n,\; j > 1} \; j \cdot V(1, n/j).$$

That is a recursion, and the formula is what it collapses to once the maximising $j$ is known. The maximising cut is always the largest prime factor — checked on every $n$ up to two hundred, with no exception — and unrolling the recursion with that choice gives the running-product sum exactly.

The greedy rule is worth stating in words because it is not the obvious one. Cutting into many pieces multiplies by a large number and leaves each piece small; cutting into few leaves each piece large. The largest prime is the compromise that wins, and it wins because the multiplication compounds down the chain: taking the biggest factor first leaves the rest of the factorisation intact to multiply again.

The grid it produces #

The first row of that grid is the formula and every other row is a recursion. It is worth looking at the table with the factorisations in mind, because the irregularity is entirely theirs: the row for 12 and the row for 8 differ everywhere, and their Ω values are equal.

One consequence of the unrolling is worth a line, because it says how fast these values grow. The sum is dominated by its last term, which is the product of all but the smallest prime — so a cake of $2^k$ is worth $2^k - 1$ and a cake of a large prime is worth 1, and two cakes of the same size can differ by a factor of thousands. The size of a Maundy Cake is a fact about how smooth its dimension is, and the smoothest numbers are worth the most.

Where it stops #

On a cake with more than one row the greedy rule is right on 81 per cent of cakes and wrong on the rest, and the failures have a shape.

On a $4 \times 6$ cake the largest prime of 6 is 3, and cutting into 3 leaves three copies of $4 \times 2$ — worth $-1$ each, so $-3$. Cutting into 2 leaves two copies of $4 \times 3$, worth $-1$ each, so $-2$, which is better for the cutter. The greedy rule optimises the multiplication and ignores what the other player will do with the pieces.

The failures are not scattered. All 104 of them have both sides composite — no cake with a prime side or a side of 1 breaks the rule, which is asserted rather than observed: a failure with a prime side would mean the rule breaks for some reason other than having to price a reply. So the rule breaks exactly where the game becomes a game: where the cutter has to price what the pieces are worth to somebody else.

So the size has a formula on one side of the board and a recursion on both, and the reason is the ordinary reason a greedy rule fails in a game: it maximises a quantity rather than a position, and a position is a thing somebody answers.

Computing it without games #

There is a practical dividend, and it is the kind a closed form usually brings.

Every Maundy Cake is an integer, so the whole game can be run in integers: take the best Left cut, take the best Right cut, and let the value be the simplest integer strictly between them — which is the simplicity rule with the construction removed.

That agrees with the game evaluator on all 324 cakes of an 18 × 18 grid, and it sweeps a 60 × 60 grid in a few milliseconds. The game recursion cannot: an option there is a sum of up to $n$ copies, and the unreduced form of that sum is enormous while its value is a small integer.

That is what a closed form is for. Not elegance — the sizes it puts in reach. The formula settles the one-row cakes outright and the integer recursion settles the rest at a cost that no longer depends on the game’s machinery.

Who worked these cakes out #

Cutcake and Maundy Cake are both Conway’s, and both appear where the notation was the argument, and both appear in Winning Ways as examples of partizan games whose values are integers — which makes them unusually good teaching positions, since the arithmetic of integers is the arithmetic everybody already has.

The pair is chosen to make one point: two games one clause apart can have answers with nothing in common. Cutcake’s rule is about binary length and Maundy Cake’s is about prime factors, and no amount of familiarity with the first would suggest the second. The clause that separates them — the pieces must be equal — is the sort of small variation a player invents at a table, and it replaces a question about powers of two with a question about factorisation.

What this site adds is the size, which the literature states for neither game beyond the sign. The formula above is not deep and it does not appear in the standard account, which stops at the sign; it comes out of the greedy rule in three lines, and the greedy rule comes out of looking at which cut the recursion actually takes.

What the sign rule was hiding #

Reading the two rungs together says something about $\Omega$ that neither says alone.

$\Omega(n) - \Omega(m)$ is the sign, exactly, on every cake tested. It is also the length of the chain of cuts: a cake with $\Omega(n) = 3$ takes three cuts to reduce the $n$-side to 1, however the cuts are chosen, because every cut divides out one prime. So the sign rule is a statement that whoever has more cuts available wins, which is the ordinary reason a partizan game is won — a count of moves.

The size is what the cuts are worth, and worth is where the primes’ magnitudes enter. So the pair reads: the number of prime factors decides who wins, and the size of them decides by how much. That is a satisfying split and it is not one anybody could have guessed from $\Omega$ alone.

What a player does with it #

Two consequences that a person cutting a cake could use.

Count the prime factors first. That is the outcome question answered by arithmetic. Whoever has more of them on their own side wins, and that is the whole of the outcome question — no arithmetic, no evaluation, just factorising two numbers. A 9 × 16 cake is a Left win because $\Omega(16) = 4$ against $\Omega(9) = 2$, and neither player has to know it is worth 3.

Then cut by the largest prime, unless the opponent’s side is composite. The greedy rule is exactly right when the other side cannot be cut at all, right four times in five otherwise, and its failures are all cases where the opponent has a reply worth waiting for. That is a rule of thumb with a stated failure mode, which is the most a rule of thumb should ever claim.

There is a third thing worth saying, because it is what makes the game pleasant rather than mechanical. The value is an integer and every position is a number, so neither player ever wants to move: a Maundy Cake in a sum is a component both players avoid, and the whole tension is about who runs out of other moves first.

What this does not say #

Four limits.

The formula is for one row. $V(1, n)$ has a closed form; $V(m, n)$ has a recursion and this page has not found one. The obvious candidates fail: it is not a difference $f(n) - f(m)$, it is not a function of $\Omega$ alone, and it is not $n/m - 1$ when $m$ divides $n$.

The greedy rule is checked to two hundred, not proved. The largest prime is always the best cut on a one-row cake is a statement about every $n$ and it is verified on 199 of them. The unrolling argument makes it plausible — a large first factor leaves the remaining product intact — and a proof would be an induction somebody should write.

The integer recursion is the game’s, not a shortcut past it. It uses the fact that every value is an integer, which the rung below established over a grid rather than proving. If a cake somewhere were not an integer, the integer recursion would return a wrong answer confidently, which is why it is checked against the game evaluator on every cake where the evaluator can be run.

The one-row formula says nothing about play. It gives the value of the cake and not the sequence of cuts, and the greedy rule that produces it is a rule for the first cut in a chain where nobody answers. A player facing a real cake needs the two-sided answer, which is the recursion.

And Maundy Cake is not Cutcake. The two games differ in one clause and their rules have nothing in common: Cutcake’s zero cells are where $\lfloor\log_2 m\rfloor = \lfloor\log_2 n\rfloor$ and Maundy’s are where $\Omega(m) = \Omega(n)$. Nothing here transfers, and the sizes are a different problem again.

One more thing the formula settles is worth a line. The rung below established that every Maundy Cake value is an integer by checking a grid; for the first row the formula proves it, since a sum of products of primes is an integer by construction. That is a small piece of the general claim turned from a measurement into an argument, and it is the only piece this page can turn.

The convention, named #

Normal play, and Left cuts the $n$-side while Right cuts the $m$-side.

A cut divides one side into $j$ equal pieces for some divisor $j > 1$, leaving $j$ copies of the smaller cake; the copies are a disjunctive sum, so their value is $j$ times one copy’s. A player who cannot cut loses.

$\Omega(k)$ counts the prime factors of $k$ with multiplicity, so $\Omega(12) = 3$ and $\Omega(1) = 0$. The primes taken largest first in the formula are the multiset of prime factors sorted downward, so $12$ contributes $3, 2, 2$ and $18$ contributes $3, 3, 2$.

Every value here is an integer and the figures refuse to draw a cake whose value is not one.

The pair of results is worth holding in one sentence. The number of prime factors says who wins and their sizes say by how much — one question answered by counting and the other by multiplying, in a game whose whole rule is that a cut must be even.

What is left of the two-variable picture #

One more thing is worth flagging before the ladder, because it is what the rungs above turn over.

A cake is described by two numbers and the natural expectation is that its value needs both. Everything on this page reads that way: a grid indexed by $m$ and $n$, a rule about which of the two to cut, a sign that depends on both. That is the picture a reader carries away and it is not the picture the answer has.

The asymmetry is already visible here and this page does not press it. The cut is made along one side and the pieces are stacked along the other, so the two sides are doing different jobs from the first move — one supplies the divisors a player may choose between and the other supplies the number of pieces those choices produce. A formula that treated them alike would be a formula ignoring the rules.

Which is worth saying because it makes the rung above less surprising than it looks. Finding that one side contributes a sequence of numbers and the other contributes only a length is not a coincidence discovered in a table; it is the move rule, followed through to the end.

Where the ladder goes next #

The cutcake anchor has three rungs to here: the game and its binary-length rule, the equal-cut variant with its $\Omega$ rule, and now the size.

The rung above takes the 104 cakes this page leaves as a target and finds them to be not a residue but a rule. The rule for which prime to cut at reports that on all 104 the best cut is at the smallest prime — the exact opposite of greedy, not some third thing — that a middle divisor is never needed anywhere in a sixty by sixty grid, and that which of the two extremes wins is decided by $\Omega$ alone: cut small when $\Omega(m) + 1 \ge \Omega(n)$ and large otherwise, exact on all 3,540 cakes.

So the greedy rule was not four-fifths of a rule with an untidy remainder. It was one half of a two-case rule, and the case split is a comparison of two counts of prime factors — the same quantity the equal-cut variant’s whole theory is built on, arriving again where nobody put it.

The short side only says how many then closes the size question this page opened. With the cut settled the recursion becomes a walk, the walk unrolls, and what it unrolls into is the running products of the long side’s prime factors taken largest first. The short side contributes nothing to the products at all: it decides how many of them there are and nothing else, which is why sixty-two different short sides give one value.

That is as complete an answer as this site gets. A game whose values looked like they would need a two-variable formula turns out to need one sequence and a length, and the second variable was only ever a count.

Two neighbours are worth the trip. Cutcake is the game one clause away, where the answer is about binary length rather than primes and the sizes are much easier. And numbers avoid numbers is why a cake full of integers is a strange kind of game to play: every position is a number, so neither player ever wants to move in it, and the whole game is about being the one who does not have to.