Simplification of numbers

How, you can’t remember the 6 or 7-digit phone number that appeared on the TV screen for a second?! Using the special technique described below, you will turn into a walking phonebook!

Obviously, the number 402 is easier to remember than the number 110010010, and the number 337377 is easier to remember than the number 957472. This means that the memorized number, on the one hand, should contain as few digits as possible, and on the other hand, it is desirable that the number contains as many repeating numbers as possible.

As a criterion for the difficulty of remembering, we take the sum of the number of digits in number and the number of different digits in number. A memorized number can be written in another number system, perhaps then it will be easier to remember. For example, the number 65535 in the hexadecimal notation looks like FFFF.

You need to write a program for selecting the base of the number system to minimize the complexity criterion. The base of the number system must be selected in the range from 2 to 36, then the numbers 0-9 and the English letters A-Z can be used to represent the number.

Input

The input contains a decimal integer from 1 to 999999999.

Output

The output must contain the base of the number system (from 2 to 36), minimizing the criterion of memorization complexity, and the number in the selected number system, separated by one space. If several bases give the same value for the criterion, then choose the smallest among them.

Notes

• The letters must be uppercase(A-Z).

Test Cases

Input       Output

1              2 1

2              3 2

65535       16 FFFF

123          12 A3

• Great challenge, but it needs more test cases. Aug 12 '19 at 11:18
• Also, the output format is a bit too strict, you might want to allow e.g. an array of two elements, the base and the string, or allowing them in reverse order or separated by another character. Also, I assume that you add the sum of the digits to the number of digits, but you may want to clarify that. Aug 12 '19 at 11:37
• Can I use a-z instead of A-Z?
– Neil
Aug 12 '19 at 11:46
• Can we just use the corresponding numbers instead of A-Z? Aug 12 '19 at 11:57
• @VerNick Next time you write a similar challenge I would suggest allowing both these requests, as they are just an unnecessary complication which are discouraged: see e.g. here. Aug 12 '19 at 14:11

Perl 6, 55 54 bytes

-1 byte thanks to Jo King.

{~map({$^b,.base($b)},2..36).min:{@$_+.Set}o*[1].comb} Try it online! • You can replace @$_ with @_ and it still works. Jan 26 '20 at 20:51
• @SirBogman This just happens to work with the very few test cases. Jan 27 '20 at 13:12
• That makes sense. It didn't feel quite right. Jan 27 '20 at 17:00

Python 2, 150149127 144 bytes

lambda n:min((len(c(n,b))+len(set(c(n,b))),b,c(n,b))for b in range(2,37))[1:]
c=lambda n,b,s='':n and c(n/b,b,chr(n%b+48+7*(n%b>9))+s)or s or'0'

Try it online!

Python 3, 136 bytes

lambda n:min((len((*c(n,b),*{*c(n,b)})),b,c(n,b))for b in range(2,37))[1:]
c=lambda n,b,s='':n and c(n//b,b,chr(n%b+48+7*(n%b>9))+s)or s

Try it online!

Python 3.8 (pre-release), 131 bytes

lambda n:min((len((*(x:=c(n,b)),*{*x})),b,x)for b in range(2,37))[1:]
c=lambda n,b,s='':n and c(n//b,b,chr(n%b+48+7*(n%b>9))+s)or s

Try it online!

c converts a base 10 number to any base (2-36), and the first (anonymous) function finds the smallest result.

05AB1E, 16 14 bytes

-1 byte thanks to Kevin Cruijssen

₆LBāøΣнDÙìg}1è

Try it online!

Or add R)» at the end to conform exactly to the specified output format, but most other answers didn't bother.

Explanation:

₆L          # range 1..36
B         # convert the input to each of those bases
āø       # enumerate (pair each element with its 1-based index)
Σ     }     # sort by
g      # length
н          # of the first element
ì       # concatenated to
DÙ        # itself, uniquified
1è          # take the second entry (first will always be base 1)
• -1 byte by using ₆L©B®ø instead of ₆LεBy‚} Aug 12 '19 at 12:11
• @KevinCruijssen Thanks! Another -1 by using ā, seems like you always forget about that one. Aug 12 '19 at 12:16
• Lol, I indeed do.. I remembered it with this challenge earlier today, not that it helped in any way, haha xD Aug 12 '19 at 12:17
• @recursive you don't seem to have read the answer. I link a version that complies with the strict output requirements, and explain why I didn't make that the main version. Aug 13 '19 at 10:12
• @Grimy guilty as charged. Sorry to bother you. Aug 13 '19 at 14:52

JavaScript (ES6),  87 85  101 bytes

Edit: +16 useless bytes to comply with the strict output format

n=>(g=m=>--b>2?g(m<(v=new Set(s=n.toString(b)).size+s.length)?m:(o=b+' '+s.toUpperCase(),v)):o)(b=37)

Try it online!

• Ah, I missed that part Aug 12 '19 at 12:26

Japt v2.0a0 -gS, 24 23 bytes

Not pretty, but it does the job. +2 bytes for the completely unnecessary requirement that output be uppercase.

37o2@sX u ¸iXÃñÈÌiXÌâ)l

Try it

37o2@sX u ¸iXÃñÈÌiXÌâ)l     :Implicit input of integer
37o2                        :Range [2,37)
@                       :Map each X
sX                     :  Convert the input to a base-X string
u                   :  Uppercase
¸                 :  Split on spaces (there are none, so this returns a singleton array)
iX               :  Prepend X
Ã              :End map
ñ             :Sort by
È            :Pass each X through the following function
Ì           :  Last element of X
i          :  Prepend
XÌâ       :    Last element of X, deduplicated
)      :  End prepend
l     :  Length
:Implicit output of the first sub-array, joined with spaces
• Yes, it works nice, but the letters must be uppercase. Aug 12 '19 at 16:36
• @VerNick, why? That adds absolutely nothing to the challenge. Aug 12 '19 at 16:53
• ...I guess the next thing will be "separated by one space". Seems the output format has been made very strict on this challenge, and from the comments does not look like it will change. Aug 12 '19 at 17:23
• @JonathanAllan, luckily I can "fix" that one with a change of flag. Aug 12 '19 at 17:27

for($i=36;$b=strtoupper(base_convert($argn,10,--$i));$o[strlen($b.count_chars($b,3))]="$i $b");krsort($o);echo end($o); Try it online! A shame about the +12 bytes in PHP to uppercase the output... but... anyway. Zsh, 85 bytes for b ({36..2})x=$[[#$b]$1]&&x=${x#*\#}&&a[$#x+${#${(us::)x}}]=$b\$x
a=($a) <<<$a[1]

For this number of statements inside the for loop, using ...&&...&&... is shorter than {...;...;...;}.

for b ({36..2})                   # order decreasing: smaller bases overwrite larger ones
x=$[[#$b]$1] && \ # set x to [base]#[num] x=${x#*\#} && \               # strip leading [base]#
a[$#x+${#${(us::)x}}]=$b\ $x # use score as index to store "[base] [number]" #${(us::) }           # (s::)plit into characters, take (u)nique
a=($a) # remove empty elements from array <<<$a[1]                          # print out the first element (smallest score)

Try it online!

Here's an 81-byte solution which prints in the form [base]#[num] instead:

for b ({36..2})x=$[[#$b]$1]&&y=${x#*\#}&&a[$#y+${#${(us::)y}}]=$x
a=($a) <<<$a[1]

Try it online!

J, 67 bytes

(];'0123456789ABCDEF'{~b)[:(2+]i.<./)](#+#@~.)@(b=:#.inv~)"+2+i.@35

Try it online!

Charcoal, 38 bytes

Ｎθ≔ＥＥ³⁴↨θ⁺²ιＬ⁺ιΦι⁼λ⌕ικη≔⁺²⌕η⌊ηηＩη ↥⍘θη

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input the integer.

≔ＥＥ³⁴↨θ⁺²ι

Convert it from base 2 to base 36...

Ｌ⁺ιΦι⁼λ⌕ικη

... deduplicate, concatenate, and take the length.

≔⁺²⌕η⌊ηη

Take the index of the minimum complexity and add 2 to get the base.

Ｉη ↥⍘θη

Print the base and the integer converted to that base in upper case.

Stax, 19 bytes

Ç╛;ⁿY3█↕(╖S♪*ò▌?½╦l

Run and debug it

No fancy algorithm, just straightforward brute force. About a third of the program is format-wrangling for the precise output rules.

Bonus program: Output for [1..1000]

Jelly, 25 bytes

bⱮ36µQL+LN)Mḟ1Ḣ,ị‘ịØBʋ¥⁸K

Try it online!

A monadic link taking an integer as its argument and returning a Jelly string of the desired format. If a two-item list was acceptable output (as per most challenges), could save 2 bytes. If base 1 were acceptable for the edge case of 1 as input, could save a further 2 bytes.

Brachylog, 44 bytes

∧Y≜∧36≥Xℕ₂≜&ḃ↙X Zd,Zl≡Y∧XwṢwZ{-₁₀;Ạụᵗ∋₍|}ᵐwᵐ

Try it online!

This hurt a bit to write.

Perl 5, 161 bytes

sub f{$X=99;for$b(2..36){$_=c($_[0],$b);$x=uniq(/./g)+y///c;($X,$B,$C)=($x,$b,$_)if$x<$X}$B,$C}
sub c{my($n,$b)=@_;$n?c(int$n/$b,$b).chr(48+$n%$b+7*($n%$b>9)):''}

Try it online!

Python 2, 140 135 bytes

lambda n:min([(b,g(n,b))for b in range(2,36)],key=lambda(b,s):len(s)+len(set(s)))
g=lambda n,b:n and g(n/b,b)+chr(n%b+48+7*(n%b>9))or''

Try it online!

$"=$,;map{@r=();$t="@F";do{unshift@r,(0..9,A..Z)[$t%$_]}while$t/=$_;$a[@r+uniq@r]||="$_ @r"}2..36;$_=first{$_}@a Try it online! Wolfram Language (Mathematica), 109 111 bytes Print[a=OrderingBy[#~IntegerDigits~Range@36,Tr[1^#]+Tr[1^Union@#]&,1][[1]]," ",ToUpperCase[#~IntegerString~a]]& +2: fixed. Thanks for the catch @Roman OrderingBy was introduced in Mathematica 12.0, which TIO does not seem to have updated to yet. • "If several bases give the same value for the criterion, then choose the smallest among them.": OrderingBy doesn't conform to this requirement. Aug 12 '19 at 18:30 • Maybe something with MinimalBy, like this? Aug 12 '19 at 18:38 • @Roman doesn't it? As far as I can tell, it preserves the relative order of two indices that have the same value.. – att Aug 13 '19 at 2:52 • With the argument 123, your solution prints 36 3F instead of the required 12 A3. From OrderingBy[123~IntegerDigits~Range@36, Tr[1^#] + Tr[1^Union@#] &] I get the answer {36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 6, 5, 11, 10, 9, 8, 7, 4, 3, 2, 1}, so the usual assumption of no re-ordering equivalent entries seems to be ignored here. My$Version is "12.0.0 for Mac OS X x86 (64-bit) (April 7, 2019)". Aug 13 '19 at 7:04
• Ah, you're right. My bad for not noticing that.
– att
Aug 14 '19 at 2:39

Japt v2.0a0, 31 bytes

2o37 ñ@sX Ê+UsX â ÊÃÎ
+S+NÎsU u

Try it

Scala, 105 97 bytes

n=>{val(b,x)=2.to(36)map(b=>b->n.toString(b))minBy((_,x)=>(x++x.toSet).size);b+" "+x.toUpperCase}

Try it online!

C (clang), 165 161 bytes

j,r,m,x,*_;t(n){for(char*g,b[74][37]={},i=1,p=99;g=b[++i],i<37;r=j<p?_=g,p=j,i:r)for(j=0,m=n;m;m/=i,*--g=x+=x>9?87:48)j-=~!b[i+36][x=m%i]++;printf("%i,%s",r,_);}

Try it online!

• Shortened and improved by @ceilingcat
n//input

,i=2//iterator from base 2 to 36

,j//current complexity

,p=99//best complexity

,r//result = iterator

,m// temp copy of n

,x ;// m%i

char*g // current string ptr

,*_ // best str ptr

,b[74][37];//buffer

/* [37+37] = [strings obtained +
test for used characters  ]
*/

t(n){

for(; g=b[i], // move ptr

i<37 ;
r=j<p?_=g,p=j,i:r, // save best solution

++i){//for every base

for( j=0,m=n; m ; m/=i, // extract digit

*--g=x+=x>9?87:48)
// move ptr backward for printf use and transform to ascii value

j+=b[i+36][x=m%i]++?1:2;
// increment byte relative to the character

// and if it was 0 increments j by 2 : 1 for the new character used and 1 for digit count

// else incr only digits count + move pointer

//printf("%s - ",g);// test

// printf("r%i p%i j%i\n",r,p,j);// test

}

printf("%i,%s",r,_);//output

}