lunes, 7 de julio de 2014

Distancia de Hamming entre números de igual tipo

(Con esta entrada despedimos el curso 2013-14. En septiembre volovemos)

Hamming definió su distancia para palabra binarias como el número total de bit en los que ambas se diferencian, comparando, como es de esperar cada uno con el que ocupa el mismo lugar en la otra palabra. Así, la distancia de Hamming entre 11001011 y 11100011 es de 2, porque son diferentes entre sí los dígitos resaltados en negrita.

Es fácil extender esta definición a cadenas de caracteres o a las cifras de un número. Así, la distancia entre estos números de móvil 656232110 y 636182170 es de 4, que son las cifras en las que difieren. Con esta definición nos podíamos preguntar cómo se relacionan entre sí números del mismo tipo: primos con primos o cuadrados con cuadrados. La idea viene a cuento porque esperamos que en los primos abunden las cifras impares, o que en los cuadrados aparezcan 1, 4, 9, 6 o 5, o que en los triangulares o de Fibonacci se distribuyan uniformemente. Como siempre advertimos, hay que decir que esto sólo es una curiosidad sin valor matemático.

Para ello hemos construido la función hamming(a,b) (para el Basic de las hojas de cálculo), que cuenta las cifras diferentes existentes entre dos números. Hemos previsto el valor -1 como valor de error. Para aquellos que no tengan el mismo número de cifras, las de uno que no están en el otro se cuentan como diferencias. Su listado es el siguiente, aunque no lo explicaremos, ya que contiene varias funciones predefinidas:

Public Function hamming(a, b) 'devuelve -1 si algo va mal. Cuenta las diferencias entre cifras. Si uno es más largo que el otro cuenta los huecos también

Dim h, i, n, m

h = -1
If esentero(a) And esentero(b) Then
n = numcifras(a)
m = numcifras(b)
h = 0
If n > m Then h = n - m: n = m
For i = 1 To m
If cifra(a, i) <> cifra(b, i) Then h = h + 1
Next i
End If
hamming = h
End Function

Con esta función analizaremos qué números presentan más o menos diferencias con sus compañeros de tipo. Para no complicar la tarea, que al fin y al cabo es lúdica, nos limitaremos a comparar aquellos que tengan el mismo número de cifras. Comenzamos:

Distancias entre primos

Comenzamos con los de dos cifras. El valor de la función sólo podrá ser 1 o 2, porque el 0 indicaría igualdad. Comparamos cada primo de dos cifras con todos los demás, tomando nota de la distancia existente entre ellos. Nos ha resultado esta tabla:


En ella hemos reflejado las distancias de cada uno de los 21 primos de 2 cifras respecto a sus compañeros. En la segunda columna contamos las distancias de Hamming que valen 1 y en la siguiente las de 2. En la última columna se ha calculado la media ponderada de las distancias. Viendo las columnas se destaca que son mucho más abundantes las diferencias h=2.

Es fácil ver que el 97 es el primo que más diferencias presenta, el que está más alejado en cifras de los demás. En total 36 diferencias (4+2*16). Por el contrario, para el 13 hay 32, (8+2*12). Para comparar este colectivo con otros, hemos sumado todas las diferencias, con un resultado de 716 y una media de 34,095.

Primos de tres cifras

Como aquí aparecerán más resultados, usaremos un filtro para presentarlos. Los primeros valores de los 143 totales son:



Mediante ordenaciones y filtros en la hoja de cálculo descubrimos lo siguiente:

El primo más cercano a sus compañeros es el 157. Ha sido una sorpresa, pues no pensamos en él. Es curioso que los seis siguientes en la lista terminen en 7. Estos son los que tienen las cifras menos destacadas.




En el extremo opuesto, de los que presentan más diferencias han resultado números terminados en 9. A ver quién aclara esto (¿pura casualidad o hay algo detrás?)



Hay un triple empate entre 719, 919 y 929. Los tres se encuentran a una distancia media de los demás igual a 61,5, o una suma de diferencias de 369.

La suma de todas las diferencias es 51842, con un promedio de 362,5

Primos de cuatro cifras

Los más afines en cifras son



Y los más alejados



Con esta idea nos quedamos. El total de diferencias es de 3870022 con una media de 3647,5

Resumiendo, el resultado global es



En la última columna dividimos de nuevo ente los elementos, ya que su número influye en las distancias medias (hay más con los que comparar)

Estas medidas nos servirán para comparar la homogeneidad de las cifras ordenadas respecto a otros colectivos. Veremos ahora los cuadrados, triangulares y cualquier otro colectivo que nos llame la atención.

Distancias entre cuadrados

Los cuadrados son menos abundantes. En concreto, para dos cifras solo existen 6. Llama la atención en la tabla resumen que sólo un par (16 y 36) presenta una distancia de 1, mientras el resto se diferencia totalmente de los demás.



Las diferencias son muy uniformes. Los más afines son los ya destacados 16 y 36

Cuadrados de tres cifras

Aparecen 22 cuadrados. Los que tienen cifras más parecidas a sus compañeros son estos:



También es una sorpresa que el 121 comparta más dígitos que ningún otro. La clave está en los 13 con los que se diferencia en dos cifras.

Los que más se alejan:



Se ve que el 6 no es una terminación tan popular como creíamos.

Con cuatro cifras

Resultan 68 cuadrados. Los ordenamos como en los casos anteriores. Vemos los que presentan menos diferencias con los demás tienen todos una cifra 0


También es sorprendente que el mínimo caiga precisamente en 1024, el elemento más pequeño del conjunto.

Los que más se alejan terminan todos en 6. Otra casualidad.



Resumen




Distancias entre triangulares

Sólo damos los resultados más llamativos

Triangulares más afines: De dos cifras, el 15, de tres el 120 y de cuatro hay dos, el 1275 y el 1770
Triangulares más diferentes: Hay cinco de dos cifras: 10, 36, 66, 78 y 91. De tres cifras 378 y 528. De cuatro el 6903

No seguimos. No parece que el tipo de número influya mucho en los resultados si corregimos los totales según el número de elementos. Puede más la falsa aleatoriedad que produce la repetición que las diferencias del tipo de cifras.