jueves, 26 de abril de 2012

Enfoque elemental del problema de Hamming

 (Con esta entrada participamos en la edición 3.141 del Carnaval de Matemáticas coordinado en esta ocasión por el blog  DesEquiLIBROS)

Reciben el nombre de números regulares o 5-lisos aquellos números naturales que son divisibles entre 2,3 y 5 y ningún otro factor primo. Presentan una factorización prima del tipo  2n3m5p. También puedes identificarlos como aquellos que son divisores de una potencia de 60 (¿por qué?)

Los tienes presentados en estas páginas

http://en.wikipedia.org/wiki/Regular_number

https://oeis.org/A051037

En esta última puedes consultar cuáles son


1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48,…

Si se les añade el número 1 como primer elemento, forman la llamada sucesión de Hamming.

El mayor interés que presentan estos números es el estudio de la formación ordenada de la sucesión, formándola a partir de los elementos ya descubiertos. Esto último es importante, pues si no, bastaría con ir recorriendo los números naturales para quedarnos sólo con los del tipo 2n3m5p.

Los posibles algoritmos, como el de Dijkstra, se estudian frecuentemente en programación funcional, como puedes ver en esta página de José_A_Alonso.

Nosotros, como siempre en este blog, optaremos por un enfoque elemental, didáctico y ¡cómo no!, usando una hoja de cálculo.

Generación del siguiente número de Hamming

Una vez que tienes escritos los primeros números de la sucesión 1,2,3,4,5,6,8,…(veremos que en realidad sólo hay que escribir 1), para obtener el siguiente bastará multiplicar uno de ellos por 2,3 o 5, pero, ¿cuál? En la sucesión 1,2,3,4,5,6,8,… no me sirve multiplicar por 2 el número 3, porque me daría 6 que ya lo tengo. Sí me convendría multiplicar por 2 el 5, con lo que obtendría el 10, o al revés, multiplicar 5 por 2. Esto no tiene nada de sistemático, por lo que deberemos ordenarlo un poco:

Dada una sucesión de Hamming con varios elementos, para formar el siguiente nos basaremos en estos criterios:

(1) Multiplicamos por 2, 3 o 5 todos los elementos que ya tenemos, y nos quedamos con el resultado menor que aún no esté incorporado a la sucesión. En el caso del ejemplo, el 9.

(2) Para guiarnos en este proceso, escribimos todos los números del tipo 2H, 3H y 5H, (representando H los números de Hamming que ya tenemos) en tres columnas.

H     2H     3H     5H
1      2       3        5
2      4       6        10
3      6       9        15
4      8       12      20
5      10     15      25
6      12     18      30
8      16     24      40

(3) En cada columna señalamos aquel número que cumple que todos los de arriba no superan el número que ya tenemos (8)  y él es el primero que sí lo sobrepasaría.

En la siguiente tabla los tienes señalados en este caso.


H     2H     3H     5H
1      2       3        5
2      4       6        10
3      6       9        15
4      8       12      20
5      10     15      25
6      12     18      30
8      16     24      40


(4) Por último, de los tres candidatos elegimos el menor, 9, y ese será el siguiente elemento de la sucesión de Hamming.

Reiteramos estas operaciones y los obtendremos todos de forma ordenada. Este procedimiento tiene la ventaja de que una vez elegido un número de la columna quedan desechados los anteriores, por lo que es posible mantener unos punteros que nos indiquen por dónde vamos.

El algoritmo con hoja de cálculo

Podemos traducirlo a hoja de cálculo. Lo hemos intentado sin usar macros, pero aparecían referencias circulares muy molestas, por lo que hemos acudido al uso de rutinas y botones. Se inicia el proceso con el botón Inicio, que escribe el primer término 1 y sus tres múltiplos 2,3 y 5.



Después, cada vez que pulsemos sobre el botón Paso se irán eligiendo los múltiplos adecuados desechando los anteriores y los iguales. En la imagen puedes ver el estado del proceso después de obtener el 9:



Se han dejado en blanco los múltiplos usados. La hoja elige después el mínimo (sería 10), elimina sus iguales, lo incorpora a la lista, crea sus múltiplos y borra los innecesarios.



El cómo lo consigue lo podrás estudiar descargando la hoja en Excel desde

http://hojamat.es/blog/hamming.xlsm

(A OpenOffice lo tenemos en la nevera hasta ver qué pasa con él, y de LibreOffice estamos esperando la nueva versión)

Estudio mediante funciones

Para ver si un número es regular o 5-liso bastaría con esta definición de función:

Public Function es_regular(n) As Boolean
Dim nn


nn = n
While nn = 2 * Int(nn / 2): nn = nn / 2: Wend
While nn = 3 * Int(nn / 3): nn = nn / 3: Wend
While nn = 5 * Int(nn / 5): nn = nn / 5: Wend
If nn = 1 Then es_regular = True Else es_regular = False
End Function

Observa cómo lo detecta: mientras el número sea par, lo va dividiendo entre 2, con lo que al final deja de serlo. Mientras sea múltiplo de 3 y de 5 también va dividiendo. Si el número es regular se agotarán todos los factores y quedará sólo un 1 y el valor de la función será VERDADERO. Si no es regular es porque o no se puede dividir entre 2,3 o 5, o al final del proceso queda un factor mayor que 1, y la función devuelve FALSO.

Con esta función puedes iniciar la sucesión de Hamming en el punto que desees. Basta ir recorriendo números y eligiendo los que sean regulares. También es muy sencillo usar la función proximo_regular:

Public Function proximo_regular(n)
Dim p


p = n + 1
While Not es_regular(p): p = p + 1: Wend
proximo_regular = p
End Function

Con esta función puedes descubrir, por ejemplo, que el primer regular de siete cifras es 1012500.

viernes, 20 de abril de 2012

Recuento y suma de cuadrados divisores de N

Como otro ejemplo de función multiplicativa, veremos hoy una muy simple: a cada número natural le hacemos corresponder la suma de todos los divisores cuadrados (SDC) que posea. Por ejemplo. SDC(28)=1+4=5, SDC(1000)=1+4+25+100 = 130. También es multiplicativa la cuenta de esos divisores (NDC)

Es evidente que para algunos, como 15 o 33, el resultado es 1.

No se debe confundir con la suma de las partes cuadradas vista en la entrada

http://hojaynumeros.blogspot.com/2011/12/emparedado-de-cuadrados-3.html      

Esta de hoy presenta valores menores, pues solo entran los divisores con parte libre igual a 1 es decir, cuadrados perfectos. En la anterior algunos cuadrados se repetían, por ejemplo en 4*3 y 4*7 como divisores de 4*3*7.

Además del muy conveniente método de calcular manualmente, con hoja de cálculo puedes evaluar fácilmente esta función

Con el Buscador de Naturales












El Buscador te resuelve el problema con las condiciones DIVISOR DE…, CUADRADO y   EVALUAR N y después se cuentan y se suman los divisores en el evaluador. En la parte superior de la imagen leemos que 4410 tiene 4 divisores cuadrados que suman 500. Luego NDC(4410)=4 y SDC(4410)=500

Como función en Basic

Se supone que ya poseemos las funciones ESMULTIPLO y ESCUAD, que ya se han usado varias veces en este blog. Con ellas se puede diseñar la función que deseamos:

Public Function sumadivcuad(n)
Dim i, s
s = 0
For i = 1 To n
If esmultiplo(n, i) And escuad(i) = 1 Then s = s + i
Next i
sumadivcuad = s
End Function

Con esta función se puede descubrir qué valores presenta la suma de divisores cuadrados para los primeros números naturales:

1, 1, 1, 5, 1, 1, 1, 5, 10, 1, 1, 5, 1, 1, 1, 21, 1, 10, 1, 5, 1, 1, 1, 5, 26, 1, 10…,

La tienes publicada en http://oeis.org/A035316

Si sustituyes la orden s=s+i por la de s=s+1, en lugar de sumar contará los divisores cuadrados con lo que generará la unción NDC. Los resultados son:

1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 3, 1, 2, 1, 2, 1, 1, 1, 2, 2, 1, 2, 2

http://oeis.org/A046951

En ambas páginas, la A035316 y la A046951 puedes aprender detalles teóricos muy interesantes. Aquí nos detendremos sólo en algunos aspectos.

Son multiplicativas

Basta considerar que ambas provienen de productos de este tipo


siendo p,q y r divisores primos del número.

En un producto de dos números coprimos lo que ocurrirá es que se unirán paréntesis de este tipo pero con primos distintos, con lo que tanto la cuenta de divisores como la suma se convertirán en producto de esas mismas funciones en los factores.

En algún momento de este año relacionaremos estas y otras multiplicativas similares con la función de Moebius, pero hay que ir paso a paso. Si te quieres adelantar, investiga.

Como en todas las multiplicativas, basta dar la operación que efectúan sobre los factores primarios pe con p factor primo del número y e su exponente. Se ve a la primera reflexión.
Los divisores de pe forman el conocido conjunto 1   p   p2   p3   p4   p5   p6 … pe-1   pe


De ellos sólo nos servirán los pares: 1   p2   p4   p6 …   pc, siendo c el máximo par contenido en e, es decir e – e MOD 2. Así que el número de divisores cuadrados NDC(pe) será:


 El corchete representa la parte entera. En el caso del ejemplo del primer párrafo, el número 4410=2*32*5*72 tendrá tantos divisores cuadrados como indica el cálculo

NDC(N)=(1+0)(1+1)(1+0)(1+1)= 4

En efecto, en la imagen del Buscador correspondiente hemos visto sólo cuatro divisores: 1, 9, 49 y 441.
Es interesante destacar que, como ocurre en casos similares, el valor de esta función no depende de los divisores primos, sino tan sólo de sus exponentes (su signatura prima)

La suma tampoco requiere mucho estudio. Sabemos sumar potencias mediante un cociente de diferencias. Así, si usamos c, el máximo número par contenido en e, es decir e – e MOD 2, nos resultará la fórmula para SDC(pe)


La aplicamos 4410=2*32*5*72

SDC(4410)=((2^2-1)/(2^2-1))*((3^4-1)/(3^2-1))*(5^2-1)/(5^2-1))*(7^4-1)/(7^2-1))=
1*10*1*50=500

que fue el resultado obtenido con el Buscador.

Ya conoces otras dos funciones multiplicativas, pero esto no ha acabado. Nos quedan al menos dos muy interesantes ¿Cuáles?

jueves, 12 de abril de 2012

A propósito de Ormiston

Un algoritmo de comparación de cifras

En la entrada anterior señalábamos, un poco de pasada, que los pares de Ormiston están formados por dos números primos consecutivos que presentan las mismas cifras, aunque en distinto orden. El primer par está formado por 1913 y 1931. Todo esto está estudiado y puedes consultar estas secuencias en OEIS:

Pares de Ormiston: https://oeis.org/A072274

Tripletes: https://oeis.org/A075093

Conjuntos de cuatro primos consecutivos: https://oeis.org/A161160

Pares que sólo se diferencian en las dos últimas cifras: https://oeis.org/A162765

No vamos a seguir la teoría de estos números, no muy interesante, sino las posibles búsquedas de los mismos con hoja de cálculo. Como de hecho ya están encontrados, nuestro interés se dirigirá al procedimiento de búsqueda.

Si se piensa un poco en la misma se pueden distinguir tres fases:

  • Identificar los números primos
  • Para cada uno de ellos encontrar el siguiente primo
  • Comparar las cifras de ambos para ver si son las mismas.


Como los dos primeros presentan menos novedad, los abordaremos al final. Comenzaremos con la detección de igualdad en el conjunto de cifras.

1) Las mismas cifras en distinto orden

Aquí tenemos el problema que deseábamos resolver hoy:

¿Qué algoritmo podemos usar para saber si dos números enteros tienen las mismas cifras, con el mismo número de repeticiones, y posiblemente en distinto orden?

El problema está en las repeticiones, porque saber si un número contiene a las cifras del otro es fácil, pero el que el número de repeticiones coincida, ya es más difícil de averiguar (para la máquina). Por ejemplo, 51613 y 51631 forman un par de Ormiston y el algoritmo ha de detectar que el 1 aparece dos veces en ambos números. Si no, no serían de Ormiston. ¿Cómo hacerlo?

Se nos ha ocurrido ir tachando una cifra cada vez que comprobemos que también está en el otro par. Leemos la primera cifra del primer número y la buscamos en el otro, y si la encontramos se tacha. Así seguimos hasta que exista una discrepancia o el agotamiento de las cifras. En el caso del ejemplo:

51613   1613   613   13   3
51631   1631   631   31   3

Expresado en pseudocódigo:

Se leen los números m y n
Se convierten en texto (para que el manejo de las cifras sea más rápido)
* Mientras no se agoten las cifras de m se hace lo siguiente:
    Buscamos una coincidencia de la primera cifra de m con cualquiera de n
    Si se da la coincidencia, se tacha esa cifra tanto en m como en n
    Si no hay coincidencia se para el bucle y se avisa
* Fin del mientras
Se lee si hay coincidencia plena o hubo un fallo

En atención a quienes no tienen interés por el código en Basic, lo situamos al final.

2) Identificar un número como primo

Aprovechamos este tema para introducir una mejora en el algoritmo de averiguar si un número es primo o no, sugerida por nuestro amigo Goyo Lekuona. En este blog, por simplicidad, buscábamos los divisores de un número entre los pares y los impares, pero una vez descartado el 2, se puede seguir con los impares. Con ello el tiempo se reduce casi a la mitad. Gracias, Goyo.

El nuevo código puede ser (hay alguna otra variante posible):

Public Function esprimo(a) As Boolean
Dim n, r
Dim es As Boolean
'Devuelve true si es primo. No analiza el que sea entero, por lo que en un decimal puede dar respuesta ilógica
If a = 1 Then es = False ‘El 1 no es primo
If a = 2 Then es = True ‘El 2 sí lo es
If a > 2 Then
If a / 2 = Int(a / 2) Then
es = False  ‘Si el número es par lo descartamos
Else
    n = 3: es = True: r = Sqr(a)
    While n <= r And es = True
    If a / n = Int(a / n) Then es = False ‘Probamos con todo los impares hasta la raíz cuadrada
    n = n + 2
    Wend
End If
End If
esprimo = es
End Function

Una pequeña cuestión: ¿funciona para N=3? ¿Por qué?

3) Buscar el próximo primo

Es muy simple y no necesita explicación:

Function primprox(a) As Long
Dim p, prim As Long
Dim sale As Boolean
'Encuentra el menor número primo mayor o igual al dado
p = a + 1: sale = False: prim = 0
While Not sale
If esprimo(p) Then prim = p: sale = True
p = p + 1
Wend
primprox = prim
End Function

Con estas herramientas hemos reproducido fácilmente los primeros pares de Ormiston, y te invitamos a intentarlo


 Para probar las funciones y aunque bastaba con una inspección visual, hemos pedido a la hoja un listado de pares de Ormiston en los que no haya cifras repetidas. Aquí tienes los primeros:



Anexo

Código de la función cifras_identicas

Public Function cifras_identicas(m, n) As Boolean
Dim i
Dim vale, esta As Boolean
Dim nn$, mm$, c$


nn$ = haztexto(n) ‘Convierte los números en textos
mm$ = haztexto(m)
vale = True
While Len(mm$) > 0 And vale
c$ = Mid$(mm$, 1, 1) ‘toma la primera cifra
esta = False
i = 1
  While i <= Len(nn$) And Not esta
    If c$ = Mid$(nn$, i, 1) Then
    esta = True
    mm$ = borracar(mm$, 1) ‘si ha coincidencia, borra la cifra
    nn$ = borracar(nn$, i)
    End If
    i = i + 1
Wend
If Not esta Then vale = False ‘si no hay coincidencia, sale del bucle con el valor “false”
Wend
cifras_identicas = vale
End Function

miércoles, 4 de abril de 2012

Damos vueltas a primos y al 18

Hace unos días Honorio, un seguidor de este blog, nos envió la siguiente conjetura: “Entre dos números primos consecutivos cuyos dígitos sumen lo mismo, como mínimo hay una diferencia de 18 entre ambos”.

Me causó sorpresa y aunque el tema de primos y cifras no es de los que más me entusiasman me puse a pensar en ella. Pronto descubrí que esta propiedad no la tienen por ser primos, sino por ser impares (el 2 no entra en la conjetura porque no coincide su suma con el consecutivo). Lo podemos demostrar:

La diferencia entre dos números impares distintos que presenten la misma suma de cifras es siempre un múltiplo (no nulo) de 18.

En efecto, si tienen la misma suma de cifras ambos presentan el mismo resto módulo 9 (recuerda el criterio de divisibilidad entre 9), luego su diferencia es múltiplo de 9. Pero como ambos son impares, su diferencia es par, luego también es múltiplo de 18, no nulo, porque ambos números son distintos.
Luego el valor mínimo de la diferencia es 18, y todas las demás, múltiplos de dicho número.

Esta propiedad abre un abanico de posibilidades: los primos pueden ser consecutivos o no. La diferencia suele ser 18 pero puede ser mayor.  Podíamos dar algunas vueltecitas al tema:

V1) Primos consecutivos con la misma suma de cifras y diferencia 18

Si disponemos de las funciones PRIMPROX (próximo primo), ESPRIMO  y SUMACIFRAS, ya tenemos las condiciones de búsqueda. Lo hemos realizado con el resultado de

523, 1069, 1259, 1759, 1913, 2503, 3803, 4159, 4373, 4423, 4463, 4603, 4703, 4733, 5059, 5209. 6229. 6529, 6619, 7159, 7433, 7459, 8191, 9109, 9749, 9949, 10691, 10753, 12619, 12763, 12923, 13763, 14033, 14303, 14369, 15859, 15973...  (Sólo se escribe el primer número primo de cada par)

Con nuestro Buscador de naturales puedes reproducirla planteando las condiciones

ES PRIMO(N)
ES SUMACIF(N)=SUMACIF(PRIMPROX(N))
ES PRIMPROX(N)=18+N

Se exige que N sea primo, que tenga la misma suma de cifras que el siguiente primo y que su diferencia sea 18. Si deseas ver el par completo añade EVALUAR PRIMPROX(N)




Siempre que encontramos una secuencia la comprobamos en OEIS para ver si está publicada, y en este caso no lo está, por lo que la hemos propuesto con el número A209875 (http://oeis.org/A209875) La nombraré como V1

V2) Primos con la misma suma de cifras que se diferencian en 18

Parece la misma cuestión, pero es que no exigimos que sean consecutivos. Por ejemplo, el 2 y el 11 presentan la misma suma y se diferencian en 9. Para buscarlos bastará ver que p sea primo y p+18 también, y que tengan la misma suma de cifras. Como las condiciones son menos restrictivas, es normal que aparezcan muchos más.

El resultado es este:

5, 13, 19, 23, 29, 43, 53, 79, 109, 113, 139, 149, 163, 173, 179, 223, 233, 239, 263, 313, 349, 379, 439, 443, 449, 491, 503, 523, 569, 613, 643, 659,…


Se puede reproducir con el Buscador usando las siguientes condiciones:

PRIMO
ES PRIMO(N+18)
ES SUMACIF(N)=SUMACIF(N+18)

En la imagen tienes el resultado.



También aquí puedes ver el par completo con EVALUAR N+18


Esta sucesión incluye a la V1. No estaba publicada en OEIS, por lo que la hemos incluido con el número A209663 (https://oeis.org/A209663)

Si la llamamos V2,tendremos que V1 es una subsucesión de V2.


V3) Primos consecutivos con la misma suma de cifras

En este caso las diferencias entre ellos serán múltiplos de 18.

El resultado es muy parecido al de V1 y está publicado en OEIS hace tiempo

523, 1069, 1259, 1759, 1913, 2503, 3803, 4159, 4373, 4423, 4463, 4603, 4703, 4733, 5059, 5209, 6229, 6529, 6619, 7159, 7433, 7459, 8191, 9109, 9749, 9949, 10691, 10753, 12619, 12763, 12923, 13763, 14033, 14107, 14303,… https://oeis.org/A066540

Puedes reproducirla en el Buscador de Naturales con

PRIMO 
ES SUMACIF(N)=SUMACIF(PRIMPROX(N))

El primer par con diferencia 36 es (14107,14143). El primero con diferencia 54 es (35617, 35671) y el primero con 72 (31397, 31469)

Es claro que V1 es un subconjunto de V3, porque 14107 o 35617 pertenecen a V3 y no a V1

Estos pares de consecutivos se pueden ampliar a tripletes: tres números primos consecutivos con la misma suma de dígitos

Los primeros que hemos encontrado son:

22193 22229 22247
25373 25391 25409
69539 69557 69593
107509 107563 107581
111373 111409 111427
167917 167953 167971
200807 200843 200861

Estos tripletes como tales tampoco figuraban en OEIS. Ya es de prever que los hemos incorporado (ver A209396)

Me he puesto a buscar conjuntos de primos consecutivos con la misma suma de cifras. Después de encontrar estos cuatro me he cansado. Si alguien quiere seguir…

1442173, 1442191, 1442209, 1442227

(Claudio Meller, en la entrada que enlazamos al final, presenta estos otros, aunque referidos a igual promedio: 8508473, 8508491, 8508509, 8508527. También nos ha indicado dónde se pueden consultar los primeros elementos de los pares, tripletes y demás conjuntos de primos consecutivos con la misma suma. Los puedes encontrar en  https://oeis.org/A071613. Gracias, Claudio)

V4) Otra vuelta más. 

Si dos números presentan la misma suma de cifras también coinciden en el valor de su raíz digital, que es el número entre  0 y 8 que resulta si sumamos sus cifras, y después volvemos a sumar las cifras de esa suma y reiteramos hasta obtener un número menor que 9. Es fácil razonar que ese número es el resto de dividir el número primitivo entre 9.

El inverso no es cierto: si se da la misma raíz digital las sumas de cifras no han de ser iguales, sino congruentes módulo 9.

Pues bien, si sólo exigimos que dos números primos consecutivos tengan la misma raíz digital nos resulta otra sucesión más amplia que la V1 y la V3, que también se ha publicado en OEIS

523, 1069, 1259, 1381, 1759, 1913, 2161, 2503, 2861, 3803, 3889, 4159, 4373, 4423, 4463, 4603, 4703, 4733, 5059, 5209, 5483, 6011, 6229, 6451, 6529, 6581, 6619, 7159, 7351, 7393, 7433, 7459, 7621, 7883, 8191, 8761, 9109, 9293, 9551, 9749, 9949,… (https://oeis.org/A117838)

Aquí se puede razonar también que las diferencias han de ser múltiplos de 18. Inténtalo.

V5) Aún quedan vueltas que dar, pero lejos de mí producir mareos irreversibles. Las presento con breves referencias:

V51) Tener la misma suma de dígitos es una condición fuerte, pero es más exigente pedir que sean los mismos dígitos, aunque en distinto orden, los que tengan dos primos consecutivos. Puedes verlos en  https://oeis.org/A069567 y se llaman pares de Ormiston. Los tienes completos en https://oeis.org/A072274 También existen tripletes de Ormiston.

V52) Y otra vuelta: Claudio Meller, de forma casi simultánea a nosotros ha tratado el tema, pero con promedios (ver http://simplementenumeros.blogspot.com/2012/03/889-primos-consecutivos-con-igual.html)

Bueno, bueno, ya vale de dar vueltas. Si encontráis temas similares los incorporo como extensión.