如何确定一个数字的基数？

Question

给定一个整数并在某个任意数字系统中重现.目的是找到数字系统的基础.例如,数字是10,表示是000010,那么基数应该是10.另一个例子:数字21表示是0010101然后基数是2.还有一个例子是:数字是6,表示os 10100然后base是sqrt(2) .有谁知道如何解决这样的问题？

Answer 1

         ___
         \
number = /__ ( digit[i] * base ^ i )

你知道number,你知道所有digit[i],你只需要找出答案base.

解决这个方程式是简单还是复杂只是一种练习.

Answer 2

我不认为每个案件都能给出答案.我实际上有理由这样想!=)

给定数字x,a_6 a_5 a_4 a_3 a_2 a_1在基数b中表示,找到基数意味着求解

a_6 b^5 + a_5 b^4 + a_4 b^3 + a_3 b^2 + a_2 b^1 + a_1 = x.

如Abel和Ruffini所示,这一般无法做到.使用较短的数字可能会更幸运,但如果涉及的数字超过四位,则公式越来越难看.

但是,有很多很好的近似算法.看到这里.

Answer 3

对于整数,它并不困难(我们可以枚举).

让我们来看看21它的代表性10101.

1 * base^4 <= 21 < (1+1) * base^4

让我们为一些基数生成数字:

base   low   high
2      16    32
3      81    162

更一般地,我们都N表示为Σ一个_我*基础^我.考虑I到_I为非null 的最大功率,我们有:

a[I] * base^I <= N < (a[I] + 1) * base^I  # does not matter if not representable

# Isolate base term
N / (a[I] + 1) < base^I <= N / a[I]

# Ith root
Ithroot( N / (a[I] + 1) ) < base <= Ithroot( N / a[I] )

# Or as a range
base in ] Ithroot(N / (a[I] + 1)), Ithroot( N / a[I] ) ]

在整数基数的情况下,或者如果你有一个已知可能的基数列表,我怀疑它们会有很多可能性,所以我们可以试试它们.

请注意,它可能更快采取实际Ithroot的N / (a[I] + 1),从这里代替计算第二个(这应该是足够接近)的迭代...但我需要对直觉的数学复习.

如果你真的没有任何想法(试图寻找一个浮动基地)...我猜这有点困难,但你总是可以在同一属性之后改进不等式(包括一个或两个以上的术语).

Answer 4

如果它是整数，这样的算法应该找到基数，并且至少应该缩小非整数基数的选择范围：

• 设N为你的整数，并R为它在神秘基数中的表示。
• 找到 中最大的数字R并调用它r。
  • 你知道你的基础至少是r + 1。
• 对于base == (r+1, r+2, ...)，让I代表R以基数解释base
  • 如果I等于N，那么base就是你的神秘基数。
  • 如果I小于N，则尝试下一个基数。
  • 如果I大于N，那么您的基数介于base - 1和之间base。

这是一种蛮力方法，但应该有效。如果显着小于 ，您还可以通过增加base超过 1 来加快速度。IN

其他可能有助于加快速度的东西，特别是在非整数基数的情况下：请记住，正如几个人提到的那样，任意基数中的数字可以展开为多项式，例如

x = a[n]*base^n + a[n-1]*base^(n-1) + ... + a[2]*base^2 + a[1]*base + a[0]

评估潜在碱基时，您不需要转换整个数字。首先仅转换最大项a[n]*base^n。如果它大于x，那么您就已经知道您的基数太大了。否则，一次添加一项（从最重要到最不重要）。这样，当您知道您的基础错误时，您就不会浪费时间计算术语。

此外，还有另一种快速消除潜在碱基的方法。请注意，您可以重新排列上述多项式并得到

(x - a[0]) = a[n]*base^n + a[n-1]*base^(n-1) + ... + a[2]*base^2 + a[1]*base

或者

(x - a[0]) = (a[n]*base^(n-1) + a[n-1]*base^(n-2) + ... + a[2]*base + a[1])*base

x您知道和的值a[0]（“个”数字，无论基数如何，您都可以解释它）。这为您提供了(x - a[0])必须被整除的额外条件base（因为您的所有a[]值都是整数）。如果计算(x - a[0]) % base并得到非零结果，则base不能是正确的基数。