miércoles, 17 de junio de 2015

Formas de ser un número equilibrado (1)

Números digitalmente equilibrados en base 10

Si se efectúa una búsqueda por Internet con la expresión “balanced number” aparecen muchos sentidos distintos para el calificativo “equilibrado” referido a los números naturales. Unos son más simples que otros y  algunos se refieren a una clase especial de números, como los primos o los triangulares. Todos ellos tienen en común que nos permiten un desarrollo en este blog, ya que el uso de algoritmos sencillos y de una hoja de cálculo permitirá aclarar algunos conceptos.

Resumiendo, nos hemos encontrado con estos significados de la palabra “equilibrado”:

Con cifras

 Un número es equilibrado en un sistema dado de numeración si (distintas definiciones):

(a) Todos sus dígitos aparecen con la misma frecuencia. Es popular el caso del sistema binario, en el que se exige que aparezcan el mismo número de 1 que de 0.
(b) Aparecen todos los dígitos posibles una vez.
(c) Posee el mismo número de dígitos pares que impares, o bien los pares figuran un número impar de veces y los impares un número par.
(d) Números de tres cifras en las una de ellas es promedio de las otras.
(e) Los primeros n dígitos tienen la misma suma que los n siguientes (en números de 2n cifras)

Con clases especiales de números:

(a) Primo equilibrado es aquel que es promedio de su primo anterior y el siguiente. Esta definición se puede extender a otras clases de números. En otra entrada lo haremos con los números esfénicos.

Habrá más casos definidos, pero con estos tenemos suficiente para trabajar un poco. No quiere decir que se desarrollen todos. En el momento de escribir esto no hemos concretado nada. Llegaremos hasta donde el cansancio o el aburrimiento nos dejen.

Comenzamos hoy con el primer caso: “Todos sus dígitos aparecen con la misma frecuencia”. Para no perder generalidad usaremos como parámetro la base de numeración. Esto nos exige que los algoritmos que usemos no se basen en el valor de los dígitos, sino en su representación tomando las cifras como símbolos.

Números digitalmente equilibrados

Si en una base dada de numeración un número se representa con unos dígitos tomados todos con la misma frecuencia, diremos que es “digitalmente equilibrado” Por ejemplo, 172712 es equilibrado en base 10 y 50 lo es en base 3, ya que 50(10=1212(3, equilibrado en el 1 y el 2.

Estudiaremos algunas cuestiones sobre ellos:
  •  Número total de equilibrados con un número dado de cifras.
  •  Función que nos devuelva si un número es equilibrado o no.
  •  Uniremos después los dos conceptos para comprobar cálculos o para averiguar cuantos equilibrados hay en un intervalo.

Si tomamos un número de dígitos determinado (divisor en este caso del total de dígitos), el número de posibles equilibrados no es difícil de calcular, pues es una cuestión combinatoria. En el caso de no concretar qué dígitos son, las formas equilibradas de llenar un número de m cifras con n dígitos equilibrados será un caso de permutaciones con repetición, en el que cada dígito se repite m/n veces.

Lo representaremos con la función FEQ (formas equilibradas de aparecer). Su expresión es fácil de conseguir:



Por ejemplo, con 6 dígitos en total y el uso de sólo 3 resultarán

FEQ(6,3)=(6!)/(6/3)!3 =720/8=90 formas

En el caso del ejemplo lo hemos comprobado con nuestra hoja Combimaq, resultando, efectivamente, 90 casos





Desarrollo de esta función con hoja de cálculo

Con este código se evita el uso de factoriales:

Function feq(m, n)
Dim q, i
Dim a, p

q = m \ n: If q <> m / n Then feq = 0: Exit Function
a = m: p = a

For i = 1 To n
For j = q To 2 Step -1
vale = False
While Not vale
If p / j = p \ j Then
p = p / j: vale = True
Else
a = a - 1: p = p * a
End If
Wend
Next j
Next i

If a > 1 Then For i = a - 1 To 2 Step -1: p = p * i: Next i
feq = p
End Function

Estas son las formas de aparecer, pero existe otra variable, y es el número de dígitos totales que usaremos. En el ejemplo hemos usado implícitamente los dígitos 1, 2, 3, pero pueden ser otros. Si deseamos estudiar el problema en base diez, esos serían los dígitos totales a considerar. Por tanto, la función FEQ se deberá multiplicar ahora por todas las combinaciones de k dígitos tomados de n en n.

 Es decir, el número total, NEQ será



Nótese que k ha de ser mayor o igual que n, lo que producirá algunos huecos en la distribución de estos números equilibrados. Lo veremos en otra entrada.

Desafortunadamente este valor incluye el cero como primer dígito en algunos casos, por lo que lo que solemos entender siempre como número de dígitos se puede falsear, pero el resultado es bastante aproximado al del uso común. La solución pasa por considerar sólo tramas de números con el mismo número de dígitos. Lo vemos:

Por ejemplo, desde 1000 hasta 9999 (cuatro dígitos), existen 4788 equilibrados (ya veremos más adelante cómo se han contado), y esta fórmula, aplicada a m=4, n=1, 2 o 4 (sus divisores) y k=10 nos da como resultado

NEQ(4;4;10)+NEQ(4;2;10)+NEQ(4;1;10) = 5040+270+10= 5320

La discrepancia consiste en que este segundo cálculo incluye ceros a la izquierda, y el otro no. Por tanto, bastará repartir 5320 entre 10 dígitos y después multiplicar por 9:
5320*9/10 = 4788

Algoritmo para distinguir si un número es digitalmente equilibrado.

Lo construiremos para bases de numeración entre 2 y 16, pues los casos de bases mayores no tienen el mismo interés. Trabajaremos con caracteres, y no con números, para poder usar los dígitos ABCDEF del sistema hexadecimal. Disponemos desde hace tiempo de la función que expresa un número en cualquier base. Por si no la hemos publicado nunca, la copiamos aquí. Es el primer paso para averiguar si un entero es equilibrado o no, expresarlo en una base dada:

Public Function exprebase(n, b) As String

Dim c$(16)
Dim m, p, r
Dim expre$

c$(0) = "0"
c$(1) = "1"
c$(2) = "2"
c$(3) = "3"
c$(4) = "4"
c$(5) = "5"
c$(6) = "6"
c$(7) = "7"
c$(8) = "8"
c$(9) = "9"
c$(10) = "A"
c$(11) = "B"
c$(12) = "C"
c$(13) = "D"
c$(14) = "E"
c$(15) = "F"
c$(16) = "G"

expre$ = ""
m = n

While m > 0
p = Int(m / b)
r = m - p * b
expre$ = c$(r) + expre$
m = p
Wend

exprebase = expre$
End Function

No la explicamos con detalle. Basta recordar la forma de pasar un número de base decimal a otra base. Lo importante es que para saber si un número es equilibrado hemos de usar sus dígitos uno a uno, y esta función lo consigue.

Una vez expresado un número en la base deseada, el problema de saber si es equilibrado o no es una cuestión de estructura de un conjunto de símbolos, independientemente de si son números o no. El algoritmo para averiguarlo puede ser el siguiente (en Basic de las hojas de cálculo):

(Está preparado para bases del 2 al 16, las más usuales, y no más de 16 dígitos)

Public Function esequilibrado(n, b) As Boolean ‘n es el número y b la base
Dim c(17)  ‘memorias para recoger los contadores de dígitos
Dim i, nc, co, cc, j
Dim s$, ca$
Dim esq As Boolean

For i = 0 To 16: c(i) = 0: Next i  ‘Pone las memorias a cero
s$ = exprebase(n, b)  ‘Expresa el número en la base dada, como cadena de caracteres
nc = Len(s$)

For i = 1 To nc  ‘Recorre todos los dígitos
ca$ = Mid$(s$, i, 1)
co = Asc(ca$) ‘carácter a estudiar
If co >= 48 And co <= 57 Then co = co – 47 ‘Convierte símbolos en códigos del 1 al 16
If co >= 65 And co <= 70 Then co = co - 54
c(co) = c(co) + 1  ‘Añade el código a su memoria
Next i
es = True
j = 1
While c(j) = 0: j = j + 1: Wend ‘se salta las memorias vacías
i = j
cc = c(j)
While es And i <= 16
If c(i) > 0 And cc <> c(i) Then es = False ‘Si dos frecuencias son distintas, ya no es equilibrado
i = i + 1
Wend
esequilibrado = es
End Function


Con esta función podemos crear listas de números equilibrados. Aquí tienes los primeros en base 2:



También se puede usar una función de N que cuente los equilibrados hasta N. Podría ser esta:

Public Function ceq(m, n)
Dim i, c
c = 0
For i = 1 To m
If esequilibrado(i, n) Then c = c + 1
Next i
ceq = c
End Function

No necesita explicación.


Equilibrados en base 10

Con la función CEQ podemos investigar cuántos equilibrados existen en base 10 en los distintos tramos de números:

Hasta el 99 todos son equilibrados. Lo son los de una cifra, y todos los de dos. Basta recorrerlos.
El 100 es el primer número no equilibrado en base 10.

En cada centena del 100 al 1000 aparecen 73 equilibrados, o lo que es lo mismo, hay 27 que no lo son. La razón es clara: el primer dígito es obligado en una centena, y un número será equilibrado si todos sus dígitos son iguales, es decir, un solo caso (por ejemplo, de 300 a 400 será el 333), o bien todos son diferentes, y como tenemos uno obligado, los otros dos aparecerán de 9*8=72 formas distintas, lo que suma 73.

Así que del 100 al 1000 contaremos 73*9=657 equilibrados. Ya llevamos del 1 al 1000 657+99=756.

Compruébalo con la función CEQ(1000;10)=756

Observa cómo resultaría el 73 de la función NEQ:

(NEQ(3;3;10)+NEQ(3;1;10))/10 = (720+10)/10=73

En cada millar aparecen 532 equilibrados

Para reproducir este número usamos la función NEQ:


Ahora bastará aplicarla a m=4, n=4,2,1 (divisores del 4) y k=10:

NEQ(4,4,10)+NEQ(4,2,10)+NEQ(4,1,10)=5040+270+10=5320, y como en cada tramo el primer dígito es obligado, dividiremos entra 10, quedando 5320/10=532.

El mismo desarrollo admitirían los tramos de 10000 en 10000. Dejamos solo el desarrollo numérico:
NEQ(5,5,10)+NEQ(5,1,10)=30240+10=30250 y dividiendo entre 10: 3025 por tramo.
Lo puedes comprobar en un tramo concreto con la función que cuenta equilibrados:

CEQ(30000;10)-CEQ(20000;10)=11594-8569=3025

Comprueba que los tramos de 100000 poseen 16291 equilibrados.

Hemos descubierto que la función que cuenta los equilibrados menores o iguales a un número en base 10 es lineal a trozos, pues presenta el mismo incremento en los tramos que poseen igual número de cifras.