Lowest base system | 4kyu

要点

  • 除法,求余,因子
  • Number.MAX_SAFE_INTEGER
  • 二分法求方程根

Details

Your task is determine lowest number base system in which the input n (base 10), expressed in this number base system, is all 1 in its digit. See an example:

‘7’ in base 2 is ‘111’ - fits! answer is 2

‘21’ in base 2 is ‘10101’ - contains ‘0’ does not fit ‘21’ in base 3 is ‘210’ - contains ‘0’ and ‘2’ does not fit ‘21’ in base 4 is ‘111’ - contains only ‘1’ it fits! answer is 4

n is always less than Number.MAX_SAFE_INTEGER.

这个题目的难度主要在于性能 performance 方面,对于数值较小的数字,通常方法很容易计算,一旦涉及到九位十位往上的大数,一般的循环方法就会耗时很久。

My Solution

function getMinBase (number) {
    if (number == 3) return 2;
    var divisor = number -1
    for (let i = 2; i != divisor; i++) {
        var k = number - 1;
        if (i > 5999) break;
        while (!(k % i)) {
            divisor = k / i
            k = divisor - 1;
            if (k == 0) return i;
        }
    }
    var _root = [2,3,4,5]
    var k = 11
    for (let i=0; i<_root.length; i++){
        var possible = parseInt(Math.pow(number, 1/_root[i]))
        var k = 10 * k + 1
        if (toTenBase(k,possible) == number) return possible
    }

    return number -1;
}


function toTenBase (number, base) {
    n = number + '';
    n = n.split('').map(a => parseInt(a));
    res = 0
    for (var i = n.length -1; i > -1; i--) {
        res += Math.pow(base,i) * n[i]
    }

    return res;
}

我的这个方法,似乎有些根据测试的数据,有些取巧。代码分成两部分,第一步是通常意义的查找,i 从 2 开始,依此类加,找到每次减 1 都能被整除的最小 i 值。这里面为了优化用了一些技巧,比如最开始一部其实是要找 number - 1 的所有因子,但注意,因为一个数的所有因子都是对称的。譬如 12 的因子:1,2,3,4,6,12。从 3 开始往后的每一个数,在之前的相除过程中都得到了。比如和 2 相除得到 6,和 3 相除得到 4。

所以我在代码的第一部分加入了变量 divisor,并把它加入了跳出循环的条件。因为一旦 i 超过了 number - 1 的一半,那么就不可能存在除了 number -1 之外的数,使得以之为 base 能得到 111...

但因为每次 i 都是类加 1,经过多次反复实验,i 超过 5000 之后,再计算速度已经很慢了。于是我写了另一个函数 toTenBase() ,给出任意 number 和 base,计算以 10 base 的数。最开始写这个函数,不过是为了去找一些规律。对于测试中出现的那些很大的数,大部分的结果都是 number - 1,然而在特殊测试部分,类似这样的 Test.assertEquals(getMinBase(2500050001), 50000); 数就很难办。

后来也是借助函数 toTenBase() 才发现,特殊测试中的数字,化成 111… 形式的话,大多都是 111111111111,再大的话就没有了。如果我们设 getMinBase() 函数所得值为 $x$,而对应 number 为 $n$,对于 111 的类型,则变成一个二次方程求解:

$$x^2 +x+1=n$$

相应的 1111 类型,则是三次方程求解:

$$x^3+x^2 +x+1=n$$

对于 11111 ,按照上述形式也可写出四次方程来。那么问题就是,针对这样的方程,该如何解呢?那么我们就要意识到,$n$ 此时已经很大了,相应 $x$ 也很大。所以它可以转化成一个球极限的问题,即:

$\lim\limits_{x \to \infty }x^3+x^2 +x+1=\lim\limits_{n \to \infty }n$
$\lim\limits_{x \to \infty }x^3=\lim\limits_{n \to \infty }n$

因此对于第一个方程,n 直接开方,对于第二个方程,n 直接开三次方。理论终究只是理论,实际检验一下,发现可以,于是就是有代码的第二部分。

Other Solutions

Voile

function getMinBase(n) {
  for(let i=Math.ceil(Math.log2(n)); i>1; i--) {
    let root=Math.round(findRoot(n,i));
    if([...'1'.repeat(i)].reduce((s,_)=>s*root+1,0)===n) return root;
  }
}

function findRoot(n,i) {
  var l=1, r=Number.MAX_SAFE_INTEGER;
  while((r-l)/l>1e-12) {
    let m=(r+l)/2, g=(Math.pow(m,i)-1)/(m-1);
    g<n?l=m:r=m;
  }
  return (r+l)/2;
}

Number.MAX_SAFE_INTEGER 是我们可以在 JavaScript 中进行 准确计算的最大数字,比之更大的数依然存在,但如果参与计算就会误差很大。

The Number.MAX_SAFE_INTEGER constant represents the maximum safe integer in JavaScript (253 - 1).

The reasoning behind that number is that JavaScript uses double-precision floating-point format numbers as specified in IEEE 754 and can only safely represent numbers between -(253 - 1) and 253 - 1.

findRoot(n,i) 正是求我上面所说 $i-1$ 阶的一元方程。

>x = findRoot(1000,4)
9.641969245752986
>Math.pow(x,3) + Math.pow(x,2) + Math.pow(x,1) + 1
999.9999999995179

关键一步:g=(Math.pow(m,i)-1)/(m-1),写成数学式是:

$g = \dfrac{m^i -1}{m-1} = m^{i-1}+m^{i-2} + … + m + 1$

求解的方程是:

$f(x) = x^{i-1}+x^{i-2} + … + x + 1 = n$

注意到 rl,分别为计算的上界和下届。求 rl 平均值,带入减 $n$,比较 0,大小,按结果分别再次带入到 rl 中。标准的二分法求根的迭代过程,bisection method。

下面看一下函数的主体部分。主要是 for 循环中 i 的初始值:i=Math.ceil(Math.log2(n))i 可能的 1 的最大位数,已知当 base 为 2 的时候,1 的位数是最多了,所以这里才会求 2 的对数。然后得到 i 值的上界,之后再依次减 1。

spiderPan

function getMinBase(number) {
  for (var b =2; b<= Math.floor(Math.sqrt(number)); b++) {
    var num = number;
    while (num % b == 1) {
      num = Math.floor(num / b);
      if (num == 1) {
        return b;
      }
    }

  }

  return number - 1;
}

LesRamer, yurak

function getMinBase(x) {
  function test(b) {
    var z = x;
    while(z % b == 1)
      z = (z - 1) / b;
    return z == 0;
  }
  for(var n = Math.ceil(Math.log2(x)); n >= 1; --n) {
    var b = Math.floor(Math.pow(x,1/n));
    if (test(b)) return b;
    if (test(b-1)) return b-1;
  }
  return -1;
}

参考文章:

分类

标签