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
X any number and
Y any string of alphanumerics, then J will interpret
Y as a base
X number, where
9 have their usual meaning and
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.
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
Nbetween 1 and 4,294,967,295 (= 232-1) as input, and outputs/returns the shortest representation of the form
Xis a positive integer,
Yis a string consisting of alphanumerics (0-9 and a-z, case insensitive), and
Yinterpreted in base
If the length of every representation
XbYrepresentation is greater than or equal to the number of digits of
N, then output
Ninstead. In all other ties, you may output any nonempty subset of the shortest representations.
This is code golf, so shorter is better.
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
Nless 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,
Nwill 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
35bzzzzzzfor 1,892,332,260 uses an unusual digit for that base, but
36bvan8x0has the same length.