Big base, small digits

Question

The J language has a very silly syntax for specifying constants. I want to focus on one cool feature in particular: the ability to write in arbitrary bases.

If you write XbY for X any number and Y any string of alphanumerics, then J will interpret Y as a base X number, where 0 through 9 have their usual meaning and a through z represent 10 through 35.

And when I say X any number, I mean any number. For the purposes of this question, I'll constrain X to be a positive integer, but in J you can use anything: negative numbers, fractions, complex numbers, whatever.

The thing that's weird is that you can only use the numbers from 0 to 35 as your base-whatever digits, because your collection of usable symbols consists only of 0-9 and a-z.

The problem

I want a program to help me golf magic numbers like 2,933,774,030,998 using this method. Well, okay, maybe not that big, I'll go easy on you. So...

Your task is to write a program or function which takes a (usually large) decimal number N between 1 and 4,294,967,295 (= 2³²-1) as input, and outputs/returns the shortest representation of the form XbY, where X is a positive integer, Y is a string consisting of alphanumerics (0-9 and a-z, case insensitive), and Y interpreted in base X equals N.

If the length of every representation XbY representation is greater than or equal to the number of digits of N, then output N instead. In all other ties, you may output any nonempty subset of the shortest representations.

This is code golf, so shorter is better.

Test cases

      Input | Acceptable outputs (case-insensitive)
------------+-------------------------------------------------------
          5 | 5
            |
   10000000 | 79bkmom  82bibhi  85bgo75  99bauua  577buld
            | 620bq9k  999baka
            |
   10000030 | 85bgo7z
            |
   10000031 | 10000031
            |
   12345678 | 76bs9va  79bp3cw  82bmw54  86bjzky  641buui
            |
   34307000 | 99bzzzz
            |
   34307001 | 34307001
            |
 1557626714 | 84bvo07e  87brgzpt  99bglush  420blaze
            |
 1892332260 | 35bzzzzzz  36bvan8x0  37brapre5  38bnxkbfe  40bij7rqk
            | 41bgdrm7f  42bek5su0  45bablf30  49b6ycriz  56b3onmfs
            | 57b38f9gx  62b244244  69b1expkf  71b13xbj3
            |
 2147483647 | 36bzik0zj  38br3y91l  39bnvabca  42bgi5of1  48b8kq3qv
 (= 2^31-1) | 53b578t6k  63b2akka1  1022b2cof  1023b2661  10922bio7
            | 16382b8wv  16383b8g7  32764b2gv  32765b2ch  32766b287
            | 32767b241
            |
 2147483648 | 512bg000  8192bw00
            |
 4294967295 | 45bnchvmu  60b5vo6sf  71b2r1708  84b12mxf3  112brx8iv
 (= 2^32-1) | 126bh5aa3  254b18owf  255b14640  1023b4cc3  13107bpa0
            | 16383bgwf  21844b9of  21845b960  32765b4oz  32766b4gf
            | 32767b483  65530b1cz  65531b1ao  65532b18f  65533b168
            | 65534b143  65535b120

If you're ever unsure about whether some representation is equal to some number, you can use any J interpreter, like the one on Try It Online. Just type in stdout 0":87brgzpt and J will spit back out 1557626714. Note that J only accepts lowercase, even though this problem is case-insensitive.

Some possibly helpful theory

• For all N less than 10,000,000, the decimal representation is as short as any other and hence is the only acceptable output. To save anything you would need to be at least four digits shorter in the new base, and even more if the base is greater than 99.
• It suffices to check bases up to the ceiling of the square root of N. For any larger base B, N will be at most two digits in base B, so the first time you'll get something with a valid first digit is at around B ≈ N/35. But at that size you will always be at least as large as the decimal representation, so there's no point in trying. That in mind, ceil(sqrt(largest number I'll ask you to solve this problem for)) = 65536.
• If you have any representation in a base less than 36, then the base 36 representation will be at least as short. So you don't have to worry about accidentally short solutions in bases less than 36. For example, the representation 35bzzzzzz for 1,892,332,260 uses an unusual digit for that base, but 36bvan8x0 has the same length.

Answer 1

JavaScript (ES6), 103 101 bytes

Takes input as a string.

n=>[...Array(7e4)].reduce(p=>p[(r=++b+(g=x=>x?g(x/b|0)+(x%b).toString(36):'b')(n)).length]?r:p,n,b=2)

Test cases

NB: The number of iterations in the snippet function is limited to 600 so that the test cases complete faster. (It would take a few seconds otherwise.)

let f =

n=>[...Array(6e2)].reduce(p=>p[(r=++b+(g=x=>x?g(x/b|0)+(x%b).toString(36):'b')(n)).length]?r:p,n,b=2)

console.log(f("5"))
console.log(f("10000000"))
console.log(f("10000030"))
console.log(f("10000031"))
console.log(f("12345678"))
console.log(f("34307000"))
console.log(f("34307001"))
console.log(f("1557626714"))
console.log(f("1892332260"))
console.log(f("2147483647"))
console.log(f("2147483648"))
console.log(f("4294967295"))

Answer 2

Ruby, 118 bytes

This was linked in another question and I noticed there aren't many answers here, so I decided to give it a shot.

Walk through all bases up to and including the input to construct all valid J number constructions. It skips 1-8 though, because there's no way those will be shorter than the base-10 representation anyways. It's a pretty naive solution, all things considered, since it calls the digits builtin to get the digits, but since that starts with the least significant digit first we have to reverse it to get the actual number, so it could possibly be improved.

It's slow. So, soooooo incredibly slow. TIO times out on 34307000, for example. We could go with the square root or even Arnauld's choice of 7e4 to save time, but that costs extra bytes, so why bother?

->n{([n.to_s]+(9..n).map{|b|d=n.digits b;"#{b}b"+d.reverse.map{|i|i.to_s 36}*''if d.all?{|i|i<36}}-[p]).min_by &:size}

Try it online!

Try it online w/ sqrt so everything finishes on time

Answer 3

05AB1E, 37 bytes

[¼35ݾãvtîEyNβQižhA«yèJ'bìNìDgIg@i\}q

Should work in theory, but times out for all non-trivial test cases, even 10000000. The cartesian product builtin ã is extremely slow for \$\geq4\$..

Without the final if-statement DgIg@i\} it can still be tested for lower values, to verify that it does in fact work: Try it online.

Will see if I can come up with a (probably much longer but) more efficient solution later on.

Explanation:

[              # Start an infinite loop:
 ¼             #  Increase the counter variable by 1 (0 by default)
 35Ý           #  Push a list in the range [0, 35]
 ¾ã            #  Take the cartesian product of this list with itself,
               #  with chunks-sizes equal to the counter variable
 v             #  Loop `y` over each of these lists:
  t            #   Take the square-root of the (implicit) input-integer
   î           #   Ceil it
  E            #   Loop `N` in the range [1, ceil(square(input))]:
   yNβ         #    Convert list `y` to base-`N`
   Qi          #    If it's equal to the (implicit) input-integer:
     žh        #     Push string "0123456789"
       A«      #     Append the lowercase alphabet
     yè        #     Index each value in list `y` into this string
     J         #     Join the characters to a single string
     'bì      '#     Prepend a "b"
        Nì     #     Prepend the number `N`
     D         #     Duplicate it
      g        #     And pop and push the length of this string
       Ig      #     Also push the length of the input
         @i }  #     If the length of the string is >= the input-length:
           \   #      Discard the duplicated string
     q         #     Stop the program
               #     (after which the result is output implicitly;
               #      or if the string was discarded and the stack is empty, it will
               #      implicitly output the implicit input as result instead)