Regresos 3: Números intocables

Hoy regresamos a la fecha del 10 de junio de 2011, en la que publicamos la entrada “Cribas y barridos 1. Números intocables”. La primera parte trata del uso de las hojas de cálculo para cribar números según sus propiedades. Ahora nos interesa más un ejemplo concreto que se usó en ese estudio, el de los números intocables.

Se llaman así a aquellos números que no pueden ser el resultado de la suma de las partes alícuotas de otro número, es decir, de la suma de sus divisores propios. Por ejemplo, el 88 no coincide con el resultado de sumar los divisores propios de ningún número natural. Si efectuamos un barrido de los N primeros números y anotamos el resultado de esa suma, ningún resultado coincidirá con 88.

Los primeros números intocables son 2, 5, 52, 88, 96, 120, 124, 146, 162, 188, 206, 210, 216, 238, 246, 248, 262, 268, 276, 288, … http://oeis.org/A005114

Puedes aprender algo sobre estos números en la Red. Por ejemplo en

 http://mathworld.wolfram.com/UntouchableNumber.html,

No dan mucho de sí. Se aprenden sus propiedades en pocos minutos.

Para saber si un número es intocable o no, necesitaremos evaluar la suma de divisores propios de cualquier número (o partes alícuotas). Con una búsqueda exhaustiva podemos construir la función alícuota:

public function alicuota(n)

dim i,s

s=0

 

for i=1 to n/2 ‘El divisor propio máximo posible es n/2

if n/i=n\i then s=s+i ‘Si encuentro un divisor propio, lo sumo

next i

alicuota=s

End function

Esta función recorre los posibles divisores propios, con la prueba n/i=n\i, que equivale a afirmar que el cociente n/i es entero y que por tanto i divide a n. El resto se entiende fácilmente.

Si se dispone de la función SIGMA, es claro que es más sencillo el uso de ALICUOTA(N)=SIGMA(N)-N

Es lo que ocurre en el lenguaje PARI, que podemos usar sigma(n)-n. En este blog también puedes encontrar la función SIGMA para Excel o Calc.

Función de búsqueda

Si deseamos saber si un número es intocable o no, deberemos recorrer “muchos” números consecutivos y comparar su función ALICUOTA o SIGMA(N)-N con el número dado, pero el problema radica en cuántos son “muchos”. En OEIS usan la cota (n-1)^2, basándose en la desigualdad s(n)-n >= sqrt(n)+1 para números compuestos. Así lo haremos aquí. Al final de la entrada esbozamos una demostración de esta desigualdad.

Con esta cota, es fácil encontrar (pero puede que muy lento) si un número es intocable o no:

Esta puede ser la función:

 

Function intocable(n) As Boolean

Dim i

Dim m As Boolean

 

m = True ‘Suponemos que sí es intocable

i = 1

While i <= (n - 1) ^ 2 And m ‘Recorremos casos hasta (n-1)^2

If fsigma(i, 1) - i = n Then m = False ‘Si n es sigma, no es intocable

i = i + 1

Wend

intocable = m

End Function

Con esta función es fácil organizar un bucle de búsqueda en Excel, con el mismo resultado que el publicado en OEIS:

Este proceso tiene fácil traducción al lenguaje PARI:

intocable(n)={my(m=1,i=1);while(i<=(n-1)^2&&m==1,if(sigma(i)-i==n,m=0);i+=1);m}

for(m=2,1000,if(intocable(m),print1(m,", ")))

Con este código obtenemos los intocables inferiores a 1000

Se conjetura que el único intocable impar es el 5. Se ha demostrado que sería cierta si también lo es la de Goldbach, por lo que es, por ahora, un problema abierto. Si fuera cierto, los únicos primos intocables serían 2 y 5.

Ya afirmábamos en este blog hace 12 años que estos números no presentan muchas propiedades. Además de en  http://oeis.org/A005114 puedes buscar “untouchable numbers” en la Red.

Algunos tipos de intocables

Nosotros ahora nos dedicaremos a tipos especiales de intocables. Ya sabemos que primos solo están 2 y 5, y que impar solo el 5, y se puede demostrar que no habrá números perfectos, amigos o iguales a un primo más la unidad, pero, por ejemplo, ¿habrá cuadrados o triangulares? Adjuntamos a continuación algún resultado:

Triangulares: Si añadimos en PARI la condición issquare(8*m+1), que es la que detecta triangulares, encontramos que sí existen de ese tipo. Estos son los primeros triangulares intocables:

120, 210, 276, 406

Como el proceso es lento, nos basta con saber que existen esos cuatro.

Oblongos: Con la condición issquare(4*m+1) descubriremos oblongos:

También existen, y los primeros son:

2, 210, 306, 342, 552, 756

Cuadrados: Existen al menos tres: 324, 576 y 784

Otra posible definición

Ya planteábamos esta pregunta en la anterior entrada sobre estos números:

¿Qué ocurriría si exigiéramos que no coincidieran con la suma de divisores propios, sino con la suma de todos (función SIGMA)? Nos daría una lista (más numerosa) de números intocables de otro tipo.

Si adaptamos lo anterior eliminando el restar el número de su sigma, efectivamente, resultan tantos números que la cuestión pierde interés:

2, 5, 9, 10, 11, 16, 17, 19, 21, 22, 23, 25, 26, 27, 29, 33, 34, 35, 37, 41, 43, 45, 46, 47, 49, 50,…

Los tienes estudiados en http://oeis.org/A007369

 

ANEXO

Demostración de s(n)-n >= sqrt(n)+1 para números compuestos

Nos basamos en cualquiera de estas dos fórmulas equivalentes para s(n)

En ambas, p representa a los factores primos y e a sus exponentes.

Lo efectuaremos por fases. Por comodidad tipográfica, representaremos la raíz cuadrada como sqrt

(1) En los semiprimos:

(1a) Si n es un cuadrado, n=p², con p primo, s(n)=1+p+p²,(ver las fórmulas de s(n)) luego s(n)-n=1+p=1+sqrt(n). Se cumple con igualdad.

(1b) Si n no es cuadrado, n=ab, con a distinto de b, y s(n)=(1+a)(1+b)=1+a+b+ab, luego

s(n)-n=1+a+b=1+2(a+b)/2>1+2sqrt(ab)>1+sqrt(n)

Nos hemos basado en que la media aritmética (a+b)/2 es mayor que la geométrica sqrt(ab)

(2) Por inducción:

Si la propiedad es verdadera para dos factores, bastará estudiar qué ocurre cuando se agrega un nuevo factor primo.

Sea n1=n*a, con n compuesto. Consideremos dos casos, que a sea ya un factor de n o que sea nuevo.

(2a) Si a no es factor de n, s(n1)=s(n)*(1+a), por ser una función multiplicativa. Ahora, si se cumple la desigualdad para n, tendremos;

s(n1)=s(n)*(1+a)>(1+sqrt(n))*sqrt(a)sqrt(a)>1+sqrt(n*a)

(3b) Si a es factor de n, quedaría, siendo e su exponente en n,

s(n1)=s(n)(a^e+1-1)/(a^e-1) (cambia un numerador por otro en la primera fórmula)

(a^e+1-1)=(a*a^e-a+a-1)=a(a^e-1)+a-1,

s(n1)=s(n)(a(a^e-1)+a-1)/(a^e-1)= s(n)*a+s(n)*(a-1)/(a^e-1)= s(n)*a+M*(a-1),siendo M un número natural (porque (a^e-1) divide a s(n). Así llegamos como en el caso 3a, que

s(n1)>1+sqrt(n)*sqrt(a)sqrt(a)>1+sqrt(n*a)