My question comes courtesy of SMBC:


It's funny, yes, but it got me wondering how to actually solve for fouriest? In other words, given a number, how do you calculate the base in which that number would have the most fours?

Update: I realize you could just start at base 5, count the fours. Check base 6, count the fours, and so on. Is there a faster way?

  • 14
    $\begingroup$ First you get tenure... $\endgroup$
    – Asaf Karagila
    Feb 24, 2013 at 6:18
  • 4
    $\begingroup$ calculus7.org/2013/02/09/… $\endgroup$ Feb 24, 2013 at 6:31
  • $\begingroup$ Ah.. it's been solved already. Pardon my lack of google. Should I leave the question or delete it? $\endgroup$ Feb 24, 2013 at 6:36
  • 1
    $\begingroup$ @CameronFredman - I haven't yet seen a solution - i.e. an algorithm better than brute force. $\endgroup$
    – nbubis
    Feb 24, 2013 at 6:40
  • $\begingroup$ @nbubis Fair enough. We'll see if some brilliant SE minds have a way to do it. (Is there a logic that justifies the professor picking 8, 12, and then 5 or did he just get lucky? Would be interesting to see.) $\endgroup$ Feb 24, 2013 at 6:44

1 Answer 1


I made some plots in Mathematica to look for patterns, and I found some. I wrote an algorithm that exploits a pattern I saw. With this algorithm, the amount of brute-force tries will be reduced to about $\frac{1}{2}\sqrt{n}$, where $n$ is the number that we're trying to find a fouriest base for. I'm convinced faster algorithms can be invented for solving this problem, but this is the best I could do in the amount of time I want to spend on such a useless math problem :). Note that we can't always speak of "the" fouriest base, since there can be more than one base that is the fouriest. Even cooler, if $n=4$, we have infinitely many fouriest bases. I assumed for my algorithm that it is not important which fouriest base is found.


The algorithm works for $n \ge 44$.

  1. Check if one of the following numbers is an integer, the numbers represent a base.

    1. $n/4 - 1$
    2. $\sqrt{n} - 2$
    3. $\sqrt{n/2 - 1} - 1$
    4. $\sqrt{n/3 - 8/9} - 2/3$

    If you found one, then this base is a fouriest base unless you find a fourier one in step 2. There are two fours when $n$ is represented in this base.

    If none of the above numbers is an integer, then $n-4$ is a fouriest base unless you find a fourier one in step 2. The number $n$ has one four when it is represented in this base.

  2. Do a brute-force search for a fouriest base. The lowest base that has to be tried is $5$ and the highest base is $\left \lceil \sqrt{n/4-1} \right \rceil - 1$.


First, all those square roots have a meaning. The following table shows what the digits of $n$ are when it is written in the base given by the formula, if that base exists (is an integer). $$ \begin{array}{lcr} n-4 & \text{ gives } & (1,4) \\ n/4 - 1 & \text{ gives } & (4, 4) \\ \sqrt{n} - 2 & \text{ gives } & (1, 4, 4) \\ \sqrt{n/2 - 1} - 1 & \text{ gives } & (2, 4, 4) \\ \sqrt{n/3 - 8/9} - 2/3 & \text{ gives } & (3, 4, 4) \\ \sqrt{n/4-1} & \text{ gives } & (4,0,4) \end{array}$$ So the first step checks if there is a base such that the digits of $n$ are $(4, 4)$, $(1, 4, 4)$, $(2, 4, 4)$ or $(3, 4, 4)$. And if there isn't, it falls back to the base where $n$ is $(1,4)$.

Now the big question is: When doing the brute-force search, why shouldn't we also try bases higher than $\sqrt{n/4-1}$? So we're trying to find a base+digits which is not in the table above in which $n$ has at least two fours. Note that the five digit lists in the table that have two fours are in any base ($\ge 5$) the smallest five numbers that have two fours. For example, $(3,4,4) < (4,0,4)$ because $3b^2 + 4b + 4 < 4b^2 + 4$ for every $b \ge 5$. So, in order to find a base/digits which is not in the table, we have to find digits bigger than $(4,0,4)$. But, with higher digits you need a lower base to keep the number the same. So digits $> (4,0,4)$ means base $< \sqrt{n/4-1}$. And that's why we don't have to try higher bases.

Small thing: The formula in step 2 is $\left \lceil \sqrt{n/4-1} \right \rceil - 1$ instead of $\left \lfloor \sqrt{n/4-1} \right \rfloor$, because we don't have to check $\sqrt{n/4-1}$ itself, because if $\sqrt{n/4-1}$ is an integer, than $n/4-1$, which also yields two fours, is also, and we've already checked $n/4-1$.

Remark: I listed the five smallest digit lists that have two fours. Theoretically you could add more digit lists, but I don't think that would improve the performance.

The algorithm doesn't always work for $n < 44$. For example, when $n = 43$, base $9$ is a fouriest base with $43 = (4, 7)$. The algorithm, however, calculates $\sqrt{n/3 - 8/9} - 2/3 = 3$ and concludes that the digits of $43$ in base $3$ are $(3,4,4)$, which does make sort of sense, since $43 = 3 \cdot 3^2 + 4 \cdot 3 + 4$. For $n \ge 44$, such problems do not occur.

  • $\begingroup$ +1 I thought this one was going to be left to the dustbin. Nice job. $\endgroup$ Mar 2, 2013 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.