Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Inspired by this. There is a number, given as either integer, string or array of digits (your choice). Find the base in which the representation of the number will have most "4"s and return that base.

Number    Result
624        5
444       10
 68       16

restrictions:

  • The base returned should not be greater than the input.
  • numbers less than or equal to abs(4) should not be considered valid input, so undefined returns are acceptable
share|improve this question
    
This could be either code-golf or code-challenge. Could you please detail the requirements, winning criteria and perhaps give one or more examples of input and desired output? –  air_blob Feb 1 '13 at 14:35
    
What is the highest acceptable base? –  Steven Rumbalski Feb 1 '13 at 15:34
    
I would assume 36, as it gets difficult to represent after that –  Sean Cheshire Feb 1 '13 at 15:35
2  
@SeanCheshire: You don't actually have to display the number. You can easily represent a number in any base as an array, such as [1,15,3,64,43] for some number in base 80. You're only outputting the base number, so you could technically test every base from 2 to n. –  mellamokb Feb 1 '13 at 18:27
    
What is the correct answer for 1, 2, and 3, which have the same number of "4"s (0) in every base? Also, many numbers have the same number of "4"s in many bases (e.g., 4 in any base > 5, 44 in any base > 45, 14 in base 9, or any base > 15, etc). Should the correct answer be the smallest base with the largest number of "4"s? –  mellamokb Feb 1 '13 at 18:31
show 4 more comments

13 Answers

APL (31 19)

Now tests all possible bases.

⊃⍒{+/4=K⊤⍨K⍴⍵}¨⍳K←⎕

Explanation:

  • ⍳K←⎕: read user input, store in K. Make a list from 1 to K, which are the bases to try.
  • {...: for each of these, run the following function
  • K⊤⍨K⍴⍵: encode K into that base giving a list of digits (as numbers) per base. Use K digits (a big overestimate, but it doesn't matter because the unused ones will all be zero anyway).
  • 4=: see which of these are equal to 4
  • +/: sum these, now we know how many fours per base
  • ⊃⍒: give the indices of the list if it were sorted downwards, so the index of the biggest one is at the front. Take the first item of this list.
share|improve this answer
    
I love your APL solutions. –  MrZander Feb 1 '13 at 22:10
19  
Funny how that APL expression contains the expression most people make when reading it: –  epidemian Feb 2 '13 at 1:34
    
Nice explanation. Thanks! –  Chris Cooper Feb 13 '13 at 11:41
add comment

GolfScript, 30 characters

.,{[2+.2$\base{4=},,\]}%$)~p];

Works for any base - test the code online.

Comment: This solution was based on the original version of the question. It thus may return a base larger than the input, e.g. for the input 4 it correctly returns base 5 - which is no longer valid by the new rules.

share|improve this answer
add comment

Python 2.x, 77 chars

F=lambda x:max((sum(x/b**d%b==4for d in range(99)),b)for b in range(5,99))[1]

Works up to base 98 and numbers at most 98 digits long.

share|improve this answer
add comment

J, 38 characters

f=.[:(i.>./)[:+/[:|:4=(10#"0(i.37))#:]

Usage:

   p 624
5
   p 444
10
   p 68
16
share|improve this answer
add comment

GolfScript (23 chars)

~:^,2>{^\base[4]/,~}$0=

or

~:^,2>{^\base[4]/,}$-1=

or

~:^,2>{^\base[4]/,}$)\;

Note that this takes input from stdin: for a fair comparison with Howard's GolfScript version subtract one char.


Howard points out that the rules have changed, and it's not very logical that they now exclude 4 as a possible input when it has a valid output (any integer greater than 4). To cover that case as well requires an extra 2 characters, which can be added in all kinds of ways:

~:^)),2>{^\base[4]/,}$)\;

or

~:^,{))^\base[4]/,}$)))\;

being a couple of the obvious ones.

share|improve this answer
    
Nice. But gives wrong answer for input "4". –  Howard Feb 2 '13 at 18:24
    
I just saw that they changed the rules completely and removed any special cases after I did my submission. Thus your solution conforms to the new rules. –  Howard Feb 2 '13 at 18:53
    
@Howard, the rules may say that that case doesn't need to be handled, but in the interests of completeness I'll add some variants. –  Peter Taylor Feb 2 '13 at 19:27
    
Nevertheless, I can't +1 more than once ;-) –  Howard Feb 2 '13 at 19:36
    
@Howard, you can add a bounty if you really want ;) –  Peter Taylor Feb 2 '13 at 22:04
add comment

VBA, 121

Function k(a)
For w=5 To a
Z=0:q=a:Do:c=q Mod w:Z=Z-(c=4):q=Int(q/w):Loop Until q=0
If Z>x Then x=Z:k=w
Next
End Function

usage:

  • direct window: ?k(num)
  • Excel formula: =k(A1)
share|improve this answer
    
fixed for all bases, and reduced test to simply counting 4s –  Sean Cheshire Feb 1 '13 at 19:52
add comment

Mathematica 59

Code

Sort[{Count[IntegerDigits[n, #], 4], #} & /@ Range[5, 36]][[-1, 2]]

Let's give the above function a name.

whichBase[n_] := Sort[{Count[IntegerDigits[n, #], 4], #} & /@ Range[2, 36]][[-1, 2]]

Explanation

  1. Count[IntegerDigits[n,k],4]: Count the number of fours in the base k representation of n.
  2. Sort the bases from fewest to most 4s.
  3. Return the base from the last item in the list, that is, the base that had the representation with the most 4's.

Some special numbers

Now let's apply whichBase to the following special numbers.

numbers= {1953124, 8062156, 26902404, 76695844, 193710244, 444444444, 
943179076, 1876283764, 3534833124, 6357245164, 10983816964, 
18325193796, 29646969124, 46672774204, 71708377284, 107789473684, 
158856009316, 229956041484, 327482302084, 459444789604, 635782877604, 
868720588636, 1173168843844, 1567178659764, 2072449425124, 
2714896551724, 3525282954756, 4539918979204, 5801435550244, 
7359635486844, 9272428079044, 11606852190676}

{5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, \ 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36}

If you convert each number to the corresponding base, you will see what is special about them.

share|improve this answer
add comment

C - (114 characters)

In all it's golfy glory:

x,k,c,d,n;main(v){scanf("%d",&v);for(k=5;v/k;++k){x=v;c=0;while(x)c+=x%k==4,x/=k;c>=d?n=k,d=c:0;}printf("%d",n);}

And somewhat ungolfed:

x,k,c,d,n; // declare a bunch of ints, initialized to 0
main(v){   // declare one more, without using an extra comma
    scanf("%d",&v); // get the input (v)
    for(k=5;v/k;++k){ // loop over each base (k) greater than or equal to (/)
                      // our input (v)
        x=v;          // temp value (x) set to input (v)
        c=0;          // number of 4s in the current base (c) re-initialized
        while(x)       // loop over our temp until it's used up
            c+=x%k==4, // if the next digit (x%k) is 4 (==4) increment the
                       // current count (c+=)
            x/=k;      // remove the current digit
        c>=d?n=k,d=c:0; // if the number of 4s in this base (c) is greater
                       // than the current maximum number of 4s (d), then
                       // save the new best base (n), and new maximum
                       // number of 4s
    }
    printf("%d",n);   // output the result
}

Just for fun here's the output for the numbers [0,127] (these are the largest bases under the input number itself).

0, 0, 0, 0, 0, 5, 6, 7, 8, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 5, 21, 22, 23, 6, 25, 26, 27, 7, 29, 30, 31, 8, 33, 34, 35, 9, 37, 38, 39, 10, 41, 42, 43, 11, 5, 46, 47, 12, 49, 50, 51, 13, 53, 54, 55, 14, 57, 58, 59, 15, 61, 62, 63, 16, 65, 66, 67, 17, 69, 5, 71, 18, 73, 74, 75, 19, 7, 78, 79, 20, 81, 82, 83, 21, 85, 86, 87, 22, 89, 90, 91, 23, 93, 94, 5, 24, 97, 98, 99, 25, 101, 102, 103, 26, 5, 106, 107, 27, 109, 5, 111, 28, 113, 114, 5, 29, 9, 5, 5, 5, 121, 122, 123

share|improve this answer
1  
+1 for the chosen variable names :) –  Attila O. Feb 9 '13 at 1:23
1  
@AttilaO. I was hoping someone would notice :) –  Gordon Bailey Feb 9 '13 at 16:45
add comment

C# (482 ~423 Bytes)

First attempt at a 'golfed' solution. I used basically the same algorithm as the VBA above. I could probably save some bytes inlining the conversion function, or shortening the name. Like I said this is a first attempt, so please be gentle.

With whitespace:

using System;
class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(args[0]);
        int c=0, m=0;
        string r="";
        int t = 0;
        for (int i = 5; i < 37; i++)
        {
            while (n > 0)
            {
                r = (char)((int)(n % i) + 48 + (7 * ((int)(n % i) > 9 ? 1 : 0))) + r;
                n = (int)(n / i);
            }
            t = r.Length - r.Replace("4", "").Length;
            if (t > c) { c = t; m = i; }
        }
        Console.WriteLine("Base: " + m);
    }
}
share|improve this answer
4  
I don't think the namespace is required. All names should be a single character, including Program and cBase. And yes, you should inline cBase. Also, combine declaration and initialization, i.e., int c=0,m=0. –  mellamokb Feb 1 '13 at 18:22
2  
Also, it looks like you've combined your test code with the function code that performs the logic. The spec requires an input of a number/string of digits, and the output of an integer. It would be fair to simply create a function that takes int parameter, and returns int parameter, without even a Main method, and call the character count your score. –  mellamokb Feb 1 '13 at 18:29
    
@mellamokbtheWise - I learned something new. I always assumed the namespace was required. Also, good catch on the test array, that saves me some chars, and I am now actually answering the challenge. –  Mark B. Feb 7 '13 at 1:34
add comment

R - 148 137 chars

(so, far away from the rest of the competition but still)

f=function(n){s=sapply;which.max(s(lapply(strsplit(s(4:n,function(x){q=n;r="";while(q){r=paste(q%%x,r);q=q%/%x};r})," "),`==`,4),sum))+3}

Basically transform the input from base 10 to all bases from 4 to n (using modulo %% and integer division %/%) and pick the index of the first one having the most 4s.

f(624)
[1] 5
f(444)
[1] 10
share|improve this answer
add comment

C# with Linq 273

using System;using System.Linq;class P{static void Main(){int r,z,k=int.Parse(Console.ReadLine());if(k<=4) return;Console.WriteLine(Enumerable.Range(4, k).Select(x =>{r = 0;z = k;while (z > 0){if(z % x==4){r++;}z/=x;}return new[]{r, x};}).OrderBy(n => n[0]).Last()[1]);}}

or

using System;
using System.Linq;

class P
{
    static void Main()
    {
        int r, z, k = int.Parse(Console.ReadLine());
        if (k <= 4) return;
        Console.WriteLine(
            Enumerable.Range(4, k).Select(x =>
                {
                    r = 0;
                    z = k;
                    while (z > 0)
                    {
                        if (z % x == 4)
                        {
                            r++;
                        }
                        z /= x;
                    }
                    return new[] { r, x };
                }).OrderBy(n => n[0]).Last()[1]);

    }
}

Pretty sure the number of variables can be reduced and the if's can be converted to ?s. Oh well...

share|improve this answer
add comment

J translation of @marinus' APL solution:

NB. Expression form (22 characters, not including "n" - the "argument"):
{.\:(+/@(4=$#:[)"0 i.)n
NB. Function form (24 characters, not including "f=:"):
f=:{.@\:@(+/@(4=$#:[)"0 i.)

Just for interest, here are some values:

(,.f"0)9+i.24
 9  5
10  6
11  7
12  8
13  9
14  5
15 11
16  6
17 13
18  7
19  5
20  5
21  5
22  5
23  5
24  5
25  6
26  6
27  6
28  6
29  5
30  7
31  7
32  7

It outputs the smallest base that gives a fouriest transform. For the last few values in the table, the representations look like “4n” (e.g 31 in base 7 is “43”).

share|improve this answer
add comment

Python: 7 and Θ(1)

print 1

Works with any integer number.


Given a number n you can represent it in base 1 with a sequence made of n repetitions of an arbitrarily chosen symbol. If you use 4 as a symbol you end-up with the numerical representation using the most 4s possible.

share|improve this answer
    
I think you're missing the real point ;) –  ACarter Feb 2 '13 at 17:39
1  
@ACarter I know what you mean, but since the question did not say that the base should be > 1 this is a valid answer ;) –  Bakuriu Feb 2 '13 at 18:27
    
I think this got down-voted, because it doesn't allow for user to somehow input desired numbers. or does it? I don't know that language. –  m0s Feb 4 '13 at 23:56
1  
@m0s, you could enter the number as an argument to the program –  gnibbler Feb 5 '13 at 3:36
add comment

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.