How Many Ways Can You Raid The Candy Shop?

Riddler Express

Using exactly three nines and the operations add, subtract, multiply, divide, exponentiate, or write side-by-side, the biggest number is $9^{9^9}$. Now: what is the biggest number you can make with exactly four threes?

Solution

Repeated exponentiation dwarfs everything else, so the answer is a power tower, and the only question is how to spend four threes to make the tower’s top as large as possible. Building straight up gives $3^{3^{3^3}} = 3^{3^{27}}$, whose top exponent is $3^{27}\approx 7.6\times 10^{12}$. But writing two of the threes side by side as $33$ and lifting it one level gives $3^{3^{33}}$, whose top exponent is $3^{33}\approx 5.6\times 10^{15}$, larger by three orders of magnitude. Since the whole number is $3$ raised to that top, the bigger top wins: $$\boxed{3^{3^{33}}}.$$ Other arrangements ($3^{33^3}$, $33^{3^3}$, $(3^3)^{33}$) put far smaller numbers in the exponent and do not come close.

The computation

These numbers are too large to write out, so compare them by iterated logarithm: each is $3$ raised to some exponent $E$, and $\log_{10}\log_{10}(3^{E}) = \log_{10}\!\big(E\log_{10} 3\big)$ ranks them.

import math
cands = {"3^(3^33)": 3**33, "3^(3^(3^3))": 3**27,
         "3^(33^3)": 33**3, "(3^3)^33": 99, "33^(3^3)": None}
for name, E in cands.items():
    if E:                                  # the number is 3**E
        print(name, round(math.log10(E * math.log10(3)), 4))
# 3^(3^33) has the largest iterated logarithm -> the biggest number

Riddler Classic

Three kinds of candy are for sale. You want to buy at least one candy and at most 100, with no constraint on how many of each. How many distinct ways are there to make your purchase?

Solution

A purchase is a triple $(a,b,c)$ of nonnegative counts with $1 \le a+b+c \le 100$. Count the triples with $a+b+c \le 100$ by adding a slack variable $s \ge 0$ so that $a+b+c+s = 100$; the number of nonnegative solutions is the stars-and-bars count $\binom{100+3}{3} = \binom{103}{3}$. Removing the single empty purchase ($a=b=c=0$) leaves $$\binom{103}{3} - 1 = 176851 - 1 = \boxed{176850}.$$

The computation

Evaluate the closed form, and cross-check by summing the triangular counts $\binom{n+2}{2}$ for each total $n$ from $1$ to $100$.

from math import comb
print(comb(103, 3) - 1)                              # 176850
print(sum(comb(n + 2, 2) for n in range(1, 101)))    # 176850