19
$\begingroup$

My question comes courtesy of SMBC:

Comic

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?

$\endgroup$
6
  • 14
    $\begingroup$ First you get tenure... $\endgroup$
    – Asaf Karagila
    Commented Feb 24, 2013 at 6:18
  • 4
    $\begingroup$ calculus7.org/2013/02/09/… $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented Feb 24, 2013 at 6:44

1 Answer 1

19
$\begingroup$

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

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

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .