domingo, 28 de junio de 2015

Formas de ser un número equilibrado (2)

Otros números digitalmente equilibrados

Continuamos el tema de la entrada anterior. Ahora pasamos a equilibrados en bases distintas de 10 y otros tipos de equilibrados.

Equilibrados en otras bases

Estudiábamos en la anterior entrada los números digitalmente equilibrados en base 10. Descubrimos que su distribución es lineal en tramos entre múltiplos de potencias de 10, y presentamos funciones para descubrir si un número es equilibrado o no y poder contarlos. Ampliamos ahora el concepto a digitalmente equilibrados en otras bases.

Equilibrados binarios

Serán aquellos que presenten los unos y ceros con la misma frecuencia (y también todo unos o todo ceros). Seguimos aquí con el problema de los ceros a la izquierda, que no nos deben confundir. Con la función presentada en la anterior entrada, esquilibrado(N,2) podremos encontrar los primeros:



Vemos que presentan o todo 1 o la mitad 1 y la otra mitad 0. Obsérvese que este concepto es más general que el presentado en http://oeis.org/A031443

Si contamos los equilibrados anteriores a un número con la función CEQ (ver entrada anterior) observamos que la distribución es lineal a trozos, con intervalos constantes. Lo vemos en el siguiente gráfico, construido sobre periodos de 100 en 100:



Los periodos constantes se corresponden con intervalos que van desde una potencia par de 2 a otra impar, porque entonces los números tendrían un número impar de cifras y sólo admitirían la solución 1111… En el gráfico se distinguen los comprendidos entre 256 y 512, y más arriba el que va de 1024 a 2048.

Idéntico fenómeno se percibe en otras bases. Por ejemplo, en base 3 la distribución sería




Y en base 4:




Con pares e impares

Hemos leído otra definición de equilibrado en base 10: es aquel número que contiene el mismo número de dígitos pares que de impares. También es un problema combinatorio.

En primer lugar hay que considerar que el número total de dígitos de estos números ha de ser par. Tal como consideramos en el primer caso de esta serie, habrá que comenzar por contar las distintas distribuciones de PAR  e IMPAR que se pueden dar. Por ejemplo, con seis cifras se pueden presentar así: PPPIII, PPIPPII, PPIIPI, PPIIIP, PIPPII, PIPIIP, PIIPPI,….Son permutaciones con repetición de dos símbolos tomados de seis en seis, es decir: 6!/(3!3!)=20, y después rellenar los elementos P e I con los cinco casos de cada clase, es decir con variaciones con repetición de cinco elementos tomados las veces necesarias. Aquí sería 20*53*53=312500

En general, para n pares y n impares:


Por ejemplo, con cuatro cifras nos resultaría 24/(2*2)*54=3750 y con dos: 2/(1*1)*52=50.

Estas fórmulas contienen los casos en los que el cero es la cifra inicial y el número de cifras disminuye en una unidad. La comprobación y en su caso corrección de esto la podemos efectuar contando los equilibrados entre dos números.

Descubrimiento de equilibrados

Otro enfoque es el de descubrir si un número de 2n cifras es equilibrado en este sentido. Podríamos recorrer sus dígitos y ver si el carácter PAR y el IMPAR se equilibran. Llegaríamos a un algoritmo semejante al siguiente:

Public Function esequilibradop(n) As Boolean 
Dim par, impar
Dim i, nc, co
Dim s$, ca$

par = 0: impar = 0 ‘Contadores de cifras pares e impares
s$ = Str$(n) ‘En las cuatro líneas siguientes convertimos el número en string
nc = Len(s$)
s$ = Right$(s$, nc - 1)
nc = nc - 1
If nc / 2 <> nc \ 2 Then esequilibradop = False: Exit Function ‘Número impar de cifras
For i = 1 To nc
ca$ = Mid$(s$, i, 1)
co = Asc(ca$) – 48 ‘Se halla el valor del dígito
If co / 2 = co \ 2 Then par = par + 1 Else impar = impar + 1 ‘Se acumula el contador
Next i
If par = impar Then esequilibradop = True Else esequilibradop = False
End Function

Con esta función es fácil contar equilibrados en un intervalo

Public Function contareq(m, n)
Dim a, c
If m > n Then a = m: m = n: n = a
c = 0
For a = m To n
If esequilibradop(a) Then c = c + 1
Next a
contareq = c
End Function

Por el problema del cero inicial, esta función contará menos casos que la anterior de tipo combinatorio. Lo vemos en esta tabla:



Para dos cifras el desfase es de 5, correspondiente a los casos 01, 03, 05, 07, 09.

Para cuatro cifras es de 375, que coincide con este cálculo: 3!/(2!1!)*53=375 y para seis cifras con 5!/(3!2!)*55=31250. Te dejamos razonar esto y descubrir una relación existente en la tabla.

Otras definiciones

Aún hemos encontrado más definiciones de números equilibrados. Las dejamos ahí por si las deseas estudiar:


  1. Un número es equilibrado cuando el número de veces que aparece en él una cifra par es IMPAR, y el número de cifras impares es PAR.
  2. Un número de tres cifras es equilibrado si la de las decenas es el promedio de las otras dos.
  3. La misma definición anterior, pero sin exigir que sean las decenas.


Hasta es posible que te inventes alguna nueva definición. Esto es como un juego.

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.

lunes, 8 de junio de 2015

La función de Smarandache y los números de Kempner (3)


Asociado Kempner de un número entero

En las dos entradas anteriores llamamos S(n) al menor número tal que su factorial sea múltiplo de n. Estudiamos los algoritmos para encontrar valores de esa función y algunas de sus propiedades. Nos basaremos en éstas para desarrollar el concepto de “asociado Kempner” de un número. Lo definiremos así:

A(n)=S(n)!/n

Es fácil ver que A(n) es el número que multiplicado por n lo convierte en el factorial mínimo que es divisible por él. Si disponemos de S(n), bastará encontrarle el factorial, que será múltiplo de n y por tanto podremos dividir.

Los resultados de esta operación los tienes en http://oeis.org/A007672

1, 1, 2, 6, 24, 1, 720, 3, 80, 12, 3628800, 2, 479001600, 360, 8, 45, 20922789888000, 40, 6402373705728000, 6, 240, 1814400, 1124000727777607680000, 1, 145152, 239500800, 13440, 180, 304888344611713860501504000000…

Sólo con recorrerlos brevemente descubrimos las oscilaciones enormes que existen entre cada término y el siguiente. La razón es obvia, y está basada en las propiedades de S(n), de las que se derivan las de A(n):

El asociado de un número primo p es A(p)=(p-1)!

Porque S(p)=p, luego A(p)=p!/p=(p-1)!

En la sucesión puedes comprobarlo: A(7)=720=6!, A(11)=3628800=10!

Esto nos indica que la sucesión no está acotada. Dada una constante cualquiera, existe un factorial que la sobrepasa.

El asociado de un factorial es igual a 1

Es evidente, porque S(n!)/n=n/n=1

Ya tenemos aquí uno de los orígenes de las oscilaciones que se descubren en la sucesión.

Algoritmo de cálculo

La existencia de términos muy grandes en la sucesión nos aconseja un algoritmo que no tenga, en lo posible, que usar factoriales. Aquí está muy indicado el que propusimos del MCD en la entrada anterior. Para un valor n, recorremos el conjunto 1, 2, 3, 4,…n y dividimos n entre el MCD de n y un elemento del conjunto, hasta convertirlo en 1. Aquí recorreremos los mismos pasos, pero acumulando los cocientes obtenidos multiplicados entre sí en una variable. Al final del proceso tendremos el producto de todos los factores que multiplicados por n lo convierten en S(n)! Sólo hay que cambiar unas líneas en el algoritmo que propusimos. Destacamos en rojo los cambios:

Public Function asoc(x)
Dim n, x1, m, a

If x < 3 Then asoc = 1: Exit Function
n = 1: x1 = x: a = 1 ‘Introducimos una variable que recoja los cocientes n/m
While x1 > 1 ‘Estructura de algoritmo idéntica a la del cálculo de S(x)
n = n + 1
m = mcd(n, x1)
x1 = x1 / m
a = a * n / m ‘Se van multiplicando los cocientes para formar A(x)
Wend
asoc = a
End Function

Con Excel el cálculo es prácticamente instantáneo para los primeros números naturales:



Al igual que procedimos con el algoritmo primitivo, podemos traducir también a PARI para poder llegar a números mayores sin el estorbo de la notación exponencial:

a(n)={local(m=1,x=n,as=1,p);while(x>1,m++;p=gcd(x,m);x=x/p;as*=m/p);as}

Destacamos en rojo las novedades. Los resultados para los primeros números los tienes en esta imagen



Como era de esperar, coinciden con los publicados en A007672, y llegan más lejos. Hemos incorporado este algoritmo a esta sucesión http://oeis.org/A007672

Iteración de la función A(n)

Con lo expuesto hasta ahora podemos esperar que si iteramos la función desde un valor inicial dado, la órbita que se produzca será totalmente oscilante. Sin embargo, ocurre lo contrario, que para cualquier número entero, la iteración sólo puede presentar uno de dos finales posibles: o termina teniendo todos sus términos iguales a la unidad, o se convierte en periódica de periodo 2. Lo estudiamos:

Dado un número natural cualquiera N, el valor de la función A(N) es divisor de S(N)!, ya que por definición, A(N)=S(N)!/N. Quiere decir que S(N)! es un factorial múltiplo de A(N). Por tanto, si calculamos S(A(N)) nos dará S(N) o un número menor, si existe un factorial múltiplo de A(N) que sea menor que S(N). Por tanto:

S(N)>=S(A(N))

Pueden ocurrir dos casos

(1) Si para un N se da que S(N)=S(A(N)), al iterar y calcular A(A(N)) resultará A(A(N))=S(A(N))!/A(N)=S(N)!/(S(N)!/N)=N

Si S(N)=S(A(N)), resultará A(A(N))=N y la sucesión de iteraciones será periódica.

Esto ocurre, por ejemplo, para N=25, pues A(25)=145152 y A(145152)=25. Los dos asociados tienen el mismo factorial mínimo común a ambos. La sucesión será periódica. Lo podemos ver con la hoja de cálculo y la función ASOC:



(2) Si en un conjunto de iteraciones se da que S(N)>S(A(N)), los factoriales mínimos irán decreciendo, con lo que, o bien llegaremos a un número que produzca periodicidad como en el primer caso, o bien desembocaremos en 1!=1, y a partir de él todos serán iguales a la unidad, porque S(1)=1.

Esto se da en todos los números primos, porque entonces A(P)=(P-1)! Y A(A(P))=A((P-1)!)=1.

También en otros que no son primos, como el 21: A(21)=240, que es el cociente entre 7! Y 21. A(240)=3, es decir 6!/240. Seguimos iterando: A(3)=2 y por último, A(2)=1

Con la hoja:



La mayoría de números desemboca en la unidad al iterar la función A(N). Los únicos números que producen periodos de 2 términos son:

9, 16, 25, 45, 49, 63, 75, 80, 81, 99, 112, 117, 121, 125, 128, 147, 153, 169, 171, 175, 176, 207, 208, 225, 243, 245, 250, 256, 261, 275, 279, 289, 304, 315, 325, 333, 343, 361, 363, 368, 369, 375, 387, 405, 423, 425, 441, 464, 475, 477, 486, 495, 496, 500, 507, 512, 525, 529, 531, 539, 549, 560, 567, 575, 585, 592, 603, 605, 625, 637, 639, 640, …

Los hemos generado con el programa PARI siguiente:

a(n)={local(m=1,x=n,as=1,p);while(x>1,m++;p=gcd(x,m);x=x/p;as*=m/p);as}
{for(i=1,10^3,m=i;v=1;while(m>1&&v,n=a(m);if(m==a(n),v=0;print1(i,", "));m=n))}

Publicados en http://oeis.org/A256705

No hemos encontrado regularidades en estos números y sus asociados. Unos son cuadrados y otros no, en la mayoría de las veces un número y su asociado son coprimos, pero en otras tienen MCD mayor que 1, como MCD(495,80640)=3. Según hemos explicado anteriormente, ninguno es primo.

Lo que sí poseen todos es una parte cuadrada mayor que 1. Si fueran libres de cuadrados, se descompondrían en un producto de primos elevados todos a la unidad. Si los ordenamos de menor a mayor tendríamos  N=p1p2p3…pk  y según lo explicado en entradas anteriores, S(N)=pk!, con lo que A(N) carecería de ese factor pk, pero el factorial en que se basa ha de ser el mismo pk! o inferior. El mismo no es, porque al carecer de ese factor primo, no es necesario llegar hasta pk!. Por tanto, S(N)>S(A(N)) y no puede pertenecer al conjunto. Como la relación es recíproca, A(N) tampoco puede ser libre de cuadrados:

Si N pertenece a la sucesión que estamos estudiando, ni él ni su asociado serán números libres de cuadrados.

No existe la propiedad contraria. Existen números no libres de cuadrados, como el 12, que no pertenecen a la sucesión.