Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
9  
First you get tenure... –  Asaf Karagila Feb 24 '13 at 6:18
2  
calculus7.org/2013/02/09/… –  Andres Caicedo Feb 24 '13 at 6:31
    
Ah.. it's been solved already. Pardon my lack of google. Should I leave the question or delete it? –  Cameron Fredman Feb 24 '13 at 6:36
1  
@CameronFredman - I haven't yet seen a solution - i.e. an algorithm better than brute force. –  nbubis Feb 24 '13 at 6:40
    
@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.) –  Cameron Fredman Feb 24 '13 at 6:44

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
+1 I thought this one was going to be left to the dustbin. Nice job. –  Cameron Fredman Mar 2 '13 at 0:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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