How to solve for the fouriest number?
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.