lunes, 21 de febrero de 2022

Números de Zumkeller(1) – Definición y búsqueda

Quienes visitamos a menudo la La Enciclopedia On-Line de las Secuencias de Números Enteros (OEIS) http://oeis.org conocemos muy bien a Reinhard Zumkeller, uno de los autores que más ha aportado conocimientos a esta página. En 2010 publicó los números que estudiaremos a continuación, y T. D. Noe, otro colaborador muy distinguido les asignó su nombre, y así son ya conocidos, como “los números de Zumkeller”.

A pesar de su reciente publicación, ya existen reseñadas muchas propiedades. Basta buscar en OEIS “Zumkeller numbers”. Aquí, en nuestra modestia, nos limitaremos a lo que sea fácil de implementar en hoja de cálculo. En este caso usaremos Excel.

La definición es muy sencilla de entender: Son números de Zumkeller aquellos en los que sus divisores se pueden repartir en dos conjuntos que tengan la misma suma. No han de contener divisores consecutivos en el orden natural,  ni tener el mismo número de elementos. Un ejemplo:

El número 25122 posee los siguientes divisores:

1+2+3+6+53+79+106+158+159+237+318+474+4187+8374+12561+25122 = 51840

Esta suma de 51840 se puede repartir entre dos particiones de los divisores, de forma que sus sumas sean iguales. Serían estas:

1+2+3+53+79+106+158+159+237+4187+8374+12561 = 25920

6+318+474+25122 = 25920

Le daremos a 25122 el título de número de Zumkeller. No es una condición difícil de cumplir, y la prueba es que estos números aparecen entre los naturales con frecuencias altas. Estos son los primeros:

6, 12, 20, 24, 28, 30, 40, 42, 48, 54, 56, 60, 66, 70, 78, 80, 84, 88, 90, 96, 102, 104, 108,…

(Puedes consultar la página dedicada a estos números en OEIS: http://oeis.org/A083207)

Búsqueda de números de Zumkeller

En la página citada se incluyen códigos en distintos lenguajes de programación para decidir si un número es de Zumkeller o no. Con ellos hemos sabido que 25122 era de ese tipo. Todos se basan en la idea de las particiones de un conjunto, y por la orientación de la página, no se incluyen las dos particiones de igual suma. Eso es lo que se va a estudiar en esta entrada.

Últimamente acudimos a funciones para organizar búsquedas, pero como esa operación ya está bien estudiada, con lenguajes más potentes que Excel, nos ha parecido conveniente regresar a los esquemas de cálculo con botones y macros, de los que está lleno este blog.

La idea que se usará para buscar las dos particiones se basa en que el número de subconjuntos de un conjunto de N elementos es 2N. Cada partición se puede caracterizar por un número binario de N dígitos, en el que 1 puede significar que ese elemento entra en el conjunto y 0 que no entra. De esa forma, buscar particiones equivale a recorrer, en binario, todos los números entre 1 y 2N-1. No consideramos el 0, que devolvería el conjunto vacío. Lo vemos aplicado al ejemplo anterior

Hemos implementado esta idea en la hoja de cálculo zumkeller.xlsm, alojada en nuestra web Hojamat.es

http://www.hojamat.es/blog/zumkeller.xlsm

Su funcionamiento sigue varios pasos:

1) Dado un número entero positivo en la celda correspondiente, la hoja calcula la suma de sus divisores, y si no es par o esa suma no sobrepasa el doble del número, lo rechaza, porque no se puede repartir en dos particiones.

2) Si SIGMA es par se buscan todos los divisores del número, y simultáneamente se van también sumando, para obtener SIGMA de nuevo y contando, para conocer TAU. Este último valor es muy importante, porque determinará en número de subconjuntos a buscar, que será 2TAU-1, según se explicó más arriba. Si descargas la hoja y pides Programador-Visual Basic podrás estudiar el código de las macros. Si no tienes esa barra Programador puedes activarla en las Opciones.

La macro ordenará los divisores en columna, y junto a ellos irá desplegando todos los números en binario desde 2TAU-1 hasta 1. Después multiplicará los divisores por estos unos y ceros para construir una partición. Lo puedes ver en esta imagen:


Se está analizando el número 42. Su SIGMA es par, por lo que se inicia el proceso. El valor de TAU es 8 (no aparece en la imagen)

En la primera columna observamos los divisores de 42, que son ocho. La segunda es auxiliar, y sirve para construir los dígitos binarios. Multiplicando esos dígitos por los divisores se obtiene la cuarta columna, los sumandos de cada partición.

La macro no se detiene hasta que encuentra el valor correcto de suma, que en este caso es 6+42=48. La imagen de arriba se ha podido capturar porque se ha llegado a la detención de la macro. En caso contrario, si no hay solución, se recorren todas las posibilidades sin detención previa.

En caso de llegar a una solución, se reflejarán en la parte derecha las dos particiones con igual suma:


Esta hoja presenta una rapidez aceptable para valores de TAU inferiores a 12 o 15. En el resto de valores deberemos usar la paciencia y dejar a Excel que trabaje solo.

Un número de Zumkeller, como este 42 del ejemplo, será un sumando en una de las particiones, luego la otra tendrá como suma un número igual o superior a él, pero eso significará que el número será perfecto o abundante, porque la suma de su divisores propios será igual o mayor que él. En el caso del 42, sus divisores propios suman 54.

Casos particulares

(1) Se ha demostrado que todos los primoriales (ver en este blog https://hojaynumeros.blogspot.com/2012/02/el-primorial.html), a partir del 6 son de Zumkeller. Vemos un ejemplo, el 210=2*3*5*7:

En estos números TAU es siempre una potencia de 2 (Ver en este blog https://hojaynumeros.blogspot.com/search?q=multiplicativas y siguientes) y sigma es par, como en este caso, que es (1+2)(1+3)(1+5)(1+7)=576

Esto es consecuencia de lo que sigue.

(2) Los números del tipo 3*2k son de Zumkeller. El mismo autor lo explica, y lo adaptamos aquí. Todo se basa en que las funciones SIGMA Y TAU son multiplicativas (ver en este blog la entrada

https://hojaynumeros.blogspot.com/2011/10/funciones-multiplicativas-1.html

para factores coprimos. En este caso, SIGMA(3*2k)=SIGMA(3)*SIGMA(2k) y desarrollando:

Sigma=(1+3)(1+2+4+8+16+…2k)=4*(2k+1-1)

Por ejemplo, en el caso de 96=3*25 será SIGMA(96)=4*(26-1)=4*63=252

La mitad de esa expresión general será 2*(2k+1-1), que coincide con la suma de divisores 3*2k+3*2k-2+…y esa será una de las particiones pedidas. En el caso de 96 equivale a

96+24+6=3*25+3*23+3*21=3*(2*(43-1)(4-1))=2*(26-1)=126

Así que siempre tendremos una partición formada por una serie de divisores con potencias de 2 alternas. Lo vemos con nuestra hoja:

Total divisores: 1+2+3+4+6+8+12+16+24+32+48+96=252

Primera partición: 1+2+3+4+8+12+16+32+48=126

Segunda partición: 6+24+96=126

(3) Si a estos números del tipo 3*2k los multiplico por un número coprimo con 2 y 3, el resultado sigue siendo del tipo Zumkeller.

Es evidente que si multiplico por un coprimo, todas las sumas quedarán multiplicadas y, según R. Gerbicz (ver http://oeis.org/A179527), el producto seguirá siendo de Zumkeller.

Eso ocurre, por ejemplo en 3*11*4=132

Total divisores: 1+2+3+4+6+11+12+22+33+44+66+132=336    

Primera partición: 1+2+4+6+11+12+22+44+66=168

Segunda partición: 3+33+132=168         

Observamos, como era de esperar, que SIGMA contiene todos los divisores de 12 y otros que son sus productos por 11.               

Esto demuestra la primera afirmación de que los primoriales son todos de Zumkeller.

(4) Los números admirables, de reciente publicación en este blog (ver entrada anterior a esta) también son de Zumkeller, porque ellos coinciden con la suma de sus divisores propios cambiando a un divisor de signo, o, lo que es igual restando a SIGMA dos veces este divisor. En este caso, basta sumar ese divisor para obtener las dos particiones. Lo vemos con un ejemplo:

812 es admirable y el divisor que cambia de signo es el 28:

812 =406+203+116+58+29-28+14+7+4+2+1

Si ahora sumamos 812+28=840, esa será la partición “corta”. Lo comprobamos con nuestro esquema:

Total divisores: 1+2+4+7+14+28+29+58+116+203+406+812=1680   

Primera partición: 1+2+4+7+14+29+58+116+203+406=840                 

Segunda partición: 28+812=840             

Estamos llegando al límite de extensión que le doy a mis entradas, por lo que dejo materia para la siguiente.

                   

jueves, 10 de febrero de 2022

Números admirables

 Pedro D. Pajares (@Pedrodanielpg) twitteó el día 31/12/21

En Matemáticas decimos que un número es ADMIRABLE si al SUMAR sus divisores propios (todos los divisores salvo él mismo) CAMBIANDO EL SIGNO de uno de ellos, obtenemos el mismo número.

(https://twitter.com/Pedrodanielpg/status/1476932068827443203?t=uj-WEOnFugC2oAdYEfpnWw&s=03)

Como ya es tradicional en este blog, Twitter nos proporciona  detalles que se pueden extender en varias direcciones. Es lo que efectuaremos con los números admirables. Hay que agradecer a Pedro D. Pajares su información.

No sigo con atención los nombres algo curiosos que se suelen dar a números naturales, por lo que no conocía este término de “admirable”. Imagino que se lo merecen números que, como veremos, presentan una cercanía teórica con los números perfectos. En estos la coincidencia se da con la suma de todos los divisores propios (parte alícuota) y en los admirables a esa suma hay que restarle el doble de uno de los divisores, para que así cambie su signo en la suma.

Por ejemplo, es admirable 650, porque sus divisores propios suman de esta forma:

652=325+130+65+50+26+25+13+10+5+2+1

La diferencia entre 650 y la suma de los divisores propios es 2, luego bastará cambiar de signo al 1:

650=325+130+65+50+26+25+13+10+5+2-1

Este sencillo cálculo nos da una pista de cómo saber si un número es admirable:

  • Ha de ser abundante, es decir, que la suma de sus divisores propios sea mayor que él
  • La diferencia entre ambos ha de ser par, y su mitad, divisor del número.

Con estas condiciones es fácil saber si un número es abundante o no. Como es costumbre, comenzaremos con una búsqueda de “fuerza bruta” y después la mejoraremos.

En cualquier método que usemos, habrá que usar la función SIGMA, que está implementada en muchas herramientas. No lo está en hojas de cálculo, pero si buscas “Sigma”, o “función sigma” en este blog encontrarás nuestra versión. Por ejemplo, en https://hojaynumeros.blogspot.com/2019/10/la-funcion-sigma-y-sus-traslados.html

Con esta función es fácil construir que nos indique si un número es admirable:

Public Function esadmirable(a)

Dim s, i, d

'Es suma de sus divisores propios cambiando a uno de signo

s = sigma(a) - a 'Partes alicuotas

d = 0

i = 1

While i <= a / 2 And d = 0 ‘Recorre divisores

If a / i = a \ i Then

If s - 2 * i = a Then d = i ‘Si es divisor y construye la suma adecuada, es la solución

End If

i = i + 1

Wend

esadmirable = d ‘Devuelve un 0 si no encuentra el divisor adecuado.

End Function

Con esta función distinguimos los admirables de los que no lo son. En estos últimos devolvería un cero. En este intervalo elegido al azar, aparecen dos admirables:



Son el 102, con divisor 6 y 104 con el 1. En efecto:

102=51+34+17-6+3+2+1

104=52+26+13+8+4+2-1

Esta función es ineficiente. Con las ideas expresadas más arriba, es mejor esta:

Public Function esadmirable(a)

Dim s, i, d, es

'Es suma de sus divisores propios cambiando a uno de signo

s = fsigma(a, 1) - a 'partes alicuotas

d = s – a ‘Halla la diferencia entre la suma de divisores propios y el número

If d > 0 And d / 2 = d \ 2 Then ‘La diferencia ha de ser positiva y par

i = d / 2 ‘Si la mitad de la diferencia es un divisor, es un número admirable

If a / i = a \ i Then es = i Else es = 0

End If

esadmirable = es

End Function

Si volvemos al intervalo elegido en párrafos anteriores se puede comprobar la equivalencia entre ambas funciones:


Según las condiciones de este planteamiento, existirán infinitos números admirables, porque lo serán todos los múltiplos de 6 formados como 6p, con p primo mayor que 3. En efecto:

Si N=6p, con primo y mayor que 3 (para eliminar los casos 2 y 3), sus divisores serán 1, 2, 3, 6, p, 2p, 3p, 6p y la suma de los divisores propios (eliminando 6p) tendrá el valor de 12+6p, con lo que su diferencia con N será 12, que cumple la condición de ser par y doble de un divisor. Por tanto, en estos números el divisor que hay que cambiar de signo es el 6, como vemos en esta tabla de múltiplos de 6 de este tipo:

Son muy escasos los números consecutivos que son admirables ambos. Según https://www.numbersaplenty.com/ sólo existen dos pares menores que 10^12:

(29691198404, 29691198405) y (478012798575, 478012798576).

Sabemos que todos los admirables son abundantes, pero se puede concretar afirmando que su abundancia (cociente entre SIGMA(N) y N) está entre 2 y 3

 (https://hojaynumeros.blogspot.com/2011/05/como-crece-la-abundancia.html)

En efecto, por ser abundante, ha de ser mayor que 2, pero si fuera superior a 3, la diferencia con las partes alícuotas no podría ser el doble de un divisor. Lo vemos en los múltiplos de 6 que hemos estudiado:

 


Números compatibles

Al igual que los números perfectos dan lugar a los números amigos, como aquellos en los que cada uno de ellos coincide con la suma de divisores propios del otro (Números amigos - Wikipedia, la enciclopedia libre), los admirables dan lugar a los compatibles.

En un par de números compatibles, cada uno de ellos coincide con la suma de los divisores propios del otro si en esa suma se ha cambiado de signo un divisor.

Por ejemplo, 24 Y 28 son compatibles, según estas dos sumas:

28=12+8+6-4+3+2+1 (divisores propios de 24)

24 =14+7+4-2+1 (ídem de 28)

Los números menores de cada par están publicados en A109797 - OEIS:

24, 30, 40, 42, 48, 60, 80, 80, 96, 102, 126, 140, 140, 156, 156, 156, 174, 180, 180, 198,…

Los mayores de cada par se encuentran en http://oeis.org/A109798, y son:

28, 40, 42, 52, 60, 96, 102, 104, 124, 110, 182, 182, 188, 210, 230, 234, 184, 358, 362,…

Las repeticiones en ambas listas son una prueba de que esta relación no es biunívoca.

Hemos diseñado una función de dos variables para Excel, que nos devuelve el factor de cada una para que los números sean compatibles:

Public Function soncompatibles$(a, b)

Dim s, i, d

Dim s1$, s2$

s = fsigma(b, 1) - b 'partes alicuotas de b

d = 0

i = 1

ss$ = ""

While i <= b / 2 And d = 0

If b / i = b \ i Then

If s - 2 * i = a Then d = i: s1$ = "De b: " + Str$(d)

End If

i = i + 1

Wend

If s1 <> "" Then

s = fsigma(a, 1) - a 'partes alicuotas de a

d = 0

i = 1

While i <= a / 2 And d = 0

If a / i = a \ i Then

If s - 2 * i = b Then d = i: s2$ = " De a:" + Str$(d)

End If

i = i + 1

Wend

End If

If s1 <> "" And s2 <> "" Then ss = s1 + s2 Else ss = "NO"

soncompatibles = ss

End Function

No necesita explicación, porque es como una duplicación de la función para admirables. Si los números no son compatibles devuelve un NO. Con esta función y una búsqueda adecuada se pueden descubrir compatibles mayores que los publicados.

Por ejemplo, con esta función mayorcompatible es posible encontrar los mayores compatibles que figuran entre 1000 y 1100:

Public Function mayorcompatible(b)

Dim i

Dim a$, c$

i = 2

a = ""

While i < b And a = ""

c$ = soncompatibles(i, b)

If c$ <> "" Then a$ = c$ + " con " + Str$(i)

i = i + 1

Wend

If a$ = "" Then a$ = "NO"

mayorcompatible = a$

End Function

El resultado es:

1012   De b: 1 De a: 1 con  1002   

1016   De b: 4 De a: 64 con  896   

1022   De b: 2 De a: 50 con  750   

1026   De b: 342 De a: 6 con  690

1034   De b: 2 De a: 2 con  690     

1050   De b: 525 De a: 73 con  876

Hay que interpretar que, en primer lugar, figuran los divisores que hay que cambiar de signo, y en segundo lugar, el otro número del par de compatibles. Así el 1022 es compatible con 750 si cambiamos de signo el factor 2 de 1022 y el 50 de 750. Así:

750=511+146+73+14+7-2+1

1022 =375+250+150+125+75-50+30+25+15+10+6+5+3+2+1

El encontrar el menor compatible es más complejo, porque de entrada no se puede saber hasta dónde buscar. Se puede adaptar la anterior función a una cota, por ejemplo a tres veces el número, sabiendo que sólo es válido el resultado positivo, si completa el par, pero ante resultados negativos habría que subir esa cota.