How to solve for the fouriest number? 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?
 A: 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.
Algorithm
The algorithm works for $n \ge 44$.


*

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


*

*$n/4 - 1$

*$\sqrt{n} - 2$

*$\sqrt{n/2 - 1} - 1$

*$\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.

*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$.
Explanation
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.
