Representation of integers by d-digits using the smallest possible base

Question

I would like to create a function where, for an arbitrary integer input value (say, unsigned 32 bits) and a given number of ddigits, the return value will be ddigit Bbase number, Bis the smallest base that can be used to represent the given input in digits d.

Here is an example input - the output of what I mean for three digits:

Input   Output

    0       0 0 0
    1       0 0 1
    2       0 1 0
    3       0 1 1
    4       1 0 0
    5       1 0 1
    6       1 1 0
    7       1 1 1

    8       0 0 2
    9       0 1 2
    10      1 0 2
    11      1 1 2
    12      0 2 0
    13      0 2 1
    14      1 2 0
    15      1 2 1
    16      2 0 0
    17      2 0 1
    18      2 1 0
    19      2 1 1
    20      0 2 2
    21      1 2 2
    22      2 0 2
    23      2 1 2
    24      2 2 0
    25      2 2 1
    26      2 2 2

    27      0 0 3
    28      0 1 3
    29      1 0 3
    30      1 1 3
    ..      .....

The assignment must be 1: 1, for each input value there must be exactly one unique output value. Think of it as if the function should return a value nthfrom a list of weird sorted base numbers B.

, - B d, ( "" ) nth . , - , .

? .

Answer 1

MBo answer , , .

. : n- b (, 999 10 3 ). . . , 8 26 3, :

  8      0 0 2
  9      0 1 2
 10      0 2 0
 11      0 2 1
 12      0 2 2
 13      1 0 2
 14      1 1 2
 15      1 2 0
 16      1 2 1
 17      1 2 2
 18      2 0 0
 19      2 0 1
 20      2 0 2
 21      2 1 0
 22      2 1 1
 23      2 1 2
 24      2 2 0
 25      2 2 1
 26      2 2 2

, : .

. 0, 1 2. 2, 2. 2 9 3.

, 9 3, 4 , 4 2 - 2. 0 1. – 02, 12, 20, 21 22; , :

 4     0 2
 5     1 2
 6     2 0
 7     2 1
 8     2 2

:

• , ;
• , 2;
• - , ;
• .

Python. , 2 ^ 32 & ; 1 [307, 1290, 990].

import math

def repres(x, ndigit, base):
    """Straightforward representation of x in given base"""

    s = []

    while ndigit:
        s += [x % base]
        x /= base
        ndigit -= 1

    return s



def encode(x, ndigit):
    """Encode according to min-base, fixed-digit order"""

    if ndigit <= 1:
        return [x]

    base = int(x ** (1.0 / ndigit)) + 1

    if base <= 2:
        return repres(x, ndigit, 2)

    x0 = (base - 1) ** ndigit
    nprev = (base - 1) ** (ndigit - 1)
    ncurr = base ** (ndigit - 1)
    ndiff = ncurr - nprev

    area = (x - x0) / ndiff

    if area < base - 1:
        xx = x0 / (base - 1) + x - x0 - area * ndiff
        return [area] + encode(xx, ndigit - 1)

    xx0 = x0 + (base - 1) * ndiff
    return [base - 1] + repres(x - xx0, ndigit - 1, base)



for x in range(32):
    r = encode(x, 3)
    print x, r

Answer 2

, , :
d- B N,

B ^d > N

B > N ^1/d

, N ^1/d (, ), B.
( , )

:

d=2, N=99 => 9.95 => B=10
d=2, N=100 => 10  => B=11
d=2, N=57 => 7.55 => B=8
d=2, N=33 => 5.74 => B=6

Delphi

  function GetInSmallestBase(N, d: UInt32): string;
  const
    Digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
  var
    Base, i: Byte;
  begin
    Base := Ceil(Power(N, 1/d) + 1.0E-12);
    if Base > 36 then
      Exit('Big number, few digits...');
    SetLength(Result, d);
    for i := d downto 1 do begin
      Result[i] := Digits[1 + N mod Base]; //Delphi string is 1-based
      N := N div Base;
    end;
    Result := Result + Format(' : base [%d]', [Base]);
  end;

begin
  Memo1.Lines.Add(GetInSmallestBase(99, 2));
  Memo1.Lines.Add(GetInSmallestBase(100, 2));
  Memo1.Lines.Add(GetInSmallestBase(987, 2));
  Memo1.Lines.Add(GetInSmallestBase(1987, 2));
  Memo1.Lines.Add(GetInSmallestBase(87654321, 6));
  Memo1.Lines.Add(GetInSmallestBase(57, 2));
  Memo1.Lines.Add(GetInSmallestBase(33, 2));

99 : base [10]
91 : base [11]
UR : base [32]
Big number, few digits...
H03LL7 : base [22]
71 : base [8]
53 : base [6]