The Fast And The Fouriest

Computer Science Level 4

Define the Fouriest Transform of a number $n$ to be the base- $b$ representation of $n$ whose digits contain the most $4$ 's of all representations such that $b$ is minimized. If you wrote out the Fouriest Transform of all positive integers up to and including $9952$ , let $N$ be the total number of $4$ 's you would count in all of their digits. What are the last three digits of $N$ ?

Details and Assumptions

As an explicit example, the Fouriest Transform of $224$ is $1344$ (base- $5$ ) which contains $2$ fours. Although its base- $7$ representation, $440$ , also contains $2$ fours, $5$ is the smaller base.
If there does not exists a base $b$ that $n$ can be represented in that has any fours, define the Fouriest Transform of that number $n$ to be its base- $10$ representation.
This problem was inspired by the following Saturday Morning Breakfast Cereal Cartoon .

The answer is 444.

2 solutions

Logan Dymond
Dec 21, 2013

My solution in python:

"""Convert n to base b"""
def BaseConvert(n, b):
    k = 1
    x = []
    while b**(k-1) < n:
        d = (n % b**k)
        n -= d
        x.append(d/b**(k-1))
        k += 1
    return x
"""Note this base convert function returns a list where each digit is an item in the list. in addition, the digits are backwards, but that doesnt matter since we are only counting the number of digits that are a 4"""

def FouriestTransform(n):
    maxfours = 0
    """Start from base 5 since a number in base 2, 3, or 4 cant have 4 as a digit"""
    b = 5
    while 4*b**(maxfours) < n and b < n:
        fours = BaseConvert(n,b).count(4)
        if fours > maxfours:
            maxfours = fours
        b += 1
return maxfours
"""Note that my while loop has 4*b**(maxfours) < n as a bound. If a number n has x fours     in some base lower than b and in base b n can only have x digits, we know that higher     bases can only have less than or equal to that many fours, so we've already found our     max. If it can have x+1 digits, they all have to be fours or else we wont find a higher   max"""

"""t=1 to count 4 itself. FouriestTransform(4) returns 0 as per the b < n condition,      however that condition is necessary for higher numbers and 4 is the only exception"""
t=1
for i in range(5,9953):
    t+= FouriestTransform(i)
print t

I added comments to explain parts of the code that may have been unclear or little pieces that make the algorithm run more efficiently.

Result = $18444$ . This gave me about an 11 second runtime. And yes, I did choose $9952$ so the answer would come out to $444$

Sorry, the linebreaks in the preview did not match the line breaks as they look now, so the comments may be a little hard to read.

Logan Dymond - 7 years, 5 months ago

Hi Logan, I've replaced your last four lines with this:

" print FouriestTransform(1524) "

And the output gave $2$

But because $1524 = 444_{19}$ , shouldn't the output be $3$ ?

And another question, why do you need to specify that "If there does not exists a base that can be represented in that has any fours, define the Fouriest Transform of that number to be its base- representation."? Because any number above $8$ has a Fouriest Transform of at least $1$ . We just set $n_{10} = 14_{n-4}$ , for example, $66 = 14_{62}$ , so I'm expecting " print FouriestTransform(66) " to print out a value of at least $1$ , but the output is $0$ . Did you mean that all the bases UP to $10$ ?

Pi Han Goh - 7 years, 5 months ago

hmm. You've interpreted my problem correctly. I mean to check all possible bases. I included that base 10 condition to take care of the cases 8 and below which have no FouriestTransform, and I wasn't sure if there was a case above 8 with the same issue (i checked up to $10^8$ and there were no other cases like that) but your reasoning is correct in that every number above 8 should return at least 1.

As for the issues your having with specific cases, I'm not sure what the problem is. I checked 1524 and 66 myself and both returned the correct value. Here is the pastebin of my code without the comments and here is that code running on an online interpretter and returning the correct values .

Logan Dymond - 7 years, 5 months ago

I guess CodePad.org can't be trusted then....

Thanks for the insight!

Pi Han Goh - 7 years, 5 months ago

@Pi Han Goh – Aha! I found the error

you tabbed "return maxfours" one too many times. In your code you are returning before the while loop ends (and before you find the true answer). This explains why your answers are 1 less than they should be.

Logan Dymond - 7 years, 5 months ago

@Logan Dymond – Curses! Thanks again! =D

Pi Han Goh - 7 years, 5 months ago

Nice problem!

Also, I knew my answer was right when I saw 444 :D

Daniel Chiu - 7 years, 5 months ago

Bob Smith
Jan 1, 2014

C++

#include <iostream>
using namespace std;

int fourcount(int num, int base)
{
    int result = 0;
    while(num)
    {
        if(num%base == 4)
        {
            result++;
        }
        num /= base;
    }
    return result;
}

int main() {
    int ans = 0;
    for(int i = 1; i <= 9952; i++)
    {
        int record = 0;
        for(int b = 2; b <= i+1; b++)
        {
            if(fourcount(i,b) > record)
            {
                record = fourcount(i,b);
            }
        }
        ans += record;
    }
    cout << ans;
    return 0;
}

The Fast And The Fouriest

The answer is 444.

2 solutions

0 pending reports