cómo determinar la base de un número?

Question

Dado un número entero y su representación en algún sistema arbitrario de números. El objetivo es encontrar la base del sistema numérico. Por ejemplo, el número es 10 y la representación es 000010, luego la base debe ser 10. Otro ejemplo: la representación del número 21 es 0010101 y luego la base es 2. Un ejemplo más es: el número es 6 y la representación es 10100 y la base es sqrt (2) . ¿Alguien tiene alguna idea de cómo resolver ese problema?

Answer 1

Un algoritmo como este debería encontrar la base si es un número entero, y al menos debe reducir las opciones para una base no entero:

• Vamos N sea su número entero y R ser su representación en la base misteriosa
• Encuentra el dígito más grande en R y llámalo r.
  • Usted sabe que su base es al menos r + 1.
• Para base == (r+1, r+2, ...), vamos I representan R interpretará en base base
  • Si IN es igual, entonces base es su base de misterio.
  • Si I es menor que N, pruebe la siguiente base.
  • Si I es mayor que N, entonces su base está en algún lugar entre base - 1 y base.

Es un método de fuerza bruta, pero debería funcionar. También puede acelerarlo un poco incrementando base en más de uno si I es significativamente más pequeño que N.

Otra cosa que podría ayudar a acelerar las cosas, sobre todo en el caso de una base no entero: Recuerde que a medida que varias personas han mencionado, un número en una base arbitraria se puede expandir como un polinomio como

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

Al evaluar las bases potenciales, no necesita convertir el número completo. Comience por convertir solo el término más grande, a[n]*base^n. Si es mayor que x, entonces ya sabe que su base es demasiado grande. De lo contrario, agregue un término a la vez (pasando del más significativo al menos significativo). De esta forma, no pierdas el tiempo calculando los términos después de saber que tu base está equivocada.

Además, hay otra forma rápida de eliminar una posible base. Observe que puede volver a organizar la expresión polinómica anterior y obtener

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

o

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

conoce los valores de x y a[0] (los "unos" dígitos, se puede interpretar que, independientemente de la base) Lo que esto le da la condición adicional de que (x - a[0]) debe ser divisible uniformemente por base (ya que todos sus valores a[] son enteros). Si calcula (x - a[0]) % base y obtiene un resultado distinto de cero, entonces base no puede ser la base correcta.

Answer 2

No estoy seguro de si esto se puede resolver de manera eficiente. Solo trataría de elegir una base aleatoria, vea si dada la base el resultado es más pequeño, más grande o igual al número. En caso de que sea más pequeño, elija una base más grande, en caso de que su mayor elija una base más pequeña, de lo contrario, tendrá la base correcta.

Answer 3

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

Usted sabe number, que conoce todas digit[i], sólo hay que saber base.

Si la resolución de esta ecuación es simple o compleja se deja como un ejercicio.

Answer 4

Esto debe darle un punto de partida:

Crear una ecuación a partir del número y representación, el número 42 y represenation "0010203" se convierte en:

1 * base^4 + 2 * base^2 + 3 = 42 

ahora a resolver la ecuación para obtener el valor de base.

Answer 5

No creo que se pueda dar una respuesta para cada caso. ¡Y de hecho tengo una razón para pensar eso! =)

Dado un número x, con representación a_6 a_5 a_4 a_3 a_2 a_1 en base b, la búsqueda de la base significa resolver

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

Esto no se puede hacer en general, como se muestra por Abel and Ruffini. Puede ser más afortunado con números más cortos, pero si hay más de cuatro dígitos involucrados, las fórmulas son cada vez más feas.

Aunque hay algoritmos de aproximación bastante buenos. Ver here.

Answer 6

Estoy pensando en que tendrá que probar y verificar diferentes bases. Para ser eficiente, su base inicial podría ser max (dígito) + 1, ya que sabe que no será menor que eso. Si es demasiado pequeño, doble hasta que lo exceda, y luego use la búsqueda binaria para reducirlo. De esta forma, su algoritmo debería ejecutarse en O (log n) para situaciones normales.

Answer 7

Varias de las otras publicaciones sugieren que la solución podría encontrarse al encontrar las raíces del polinomio que representa el número. Estos, por supuesto, generalmente funcionan, aunque tendrán una tendencia a producir bases negativas y complejas, así como enteros positivos.

Otro enfoque sería emitir esto como un problema de programación entero y resolver usando branch-and-bound.

Pero sospecho que la sugerencia de adivinar y probar será más rápida que cualquiera de las propuestas más inteligentes.

Answer 8

Solo para enteros, no es tan difícil (podemos enumerar).

Veamos 21 y su representación .

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

Vamos a generar los números de algunas bases:

base low high 
2  16 32 
3  81 162 

De manera más general, tenemos N Σ representa como una base _i^{* i}. Teniendo en cuenta I la potencia máxima para la que un _I es no nula tenemos:

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]) ] 

En el caso de una base de número entero, o si usted tiene una lista de posibles bases conocidas, dudo que van a ser muchos posibilidades, entonces solo podemos probarlas.

Tenga en cuenta que puede ser más rápido tomar el Ithroot de N/(a[I] + 1) y repetir desde aquí en lugar de calcular el segundo (que debería ser lo suficientemente cerca) ... pero necesitaría una revisión matemática en esa intuición.

Si realmente no tienes ni idea (tratando de encontrar una base flotante) ... bueno, es un poco más difícil, supongo, pero siempre puedes refinar la desigualdad (incluyendo uno o dos términos más) después de la misma propiedad.