miércoles, 12 de diciembre de 2012

Mayor divisor propio con la misma suma de cifras



A partir de una cuestión simple (que no sencilla) desarrollaremos varias técnicas y conceptos, ejercicio que nos agrada mucho en este blog.

¿Qué números poseen la misma suma de cifras que su mayor divisor propio?

Uno de ellos es el 12673 que se descompone como 12673=19*23*29, luego su mayor divisor propio es 23*29=667 y, en efecto la suma de las cifras de 12673 es 19 y la de 667 también es 19.

No hay que irse tan lejos: el mayor divisor de 18 es 9 y también se cumple esta propiedad. Puede que hayas pensado que la cumplen todos los múltiplos de 9 y no es así, porque 45 tiene como mayor divisor 15 y ahí no coinciden las sumas, y tampoco en 63. Sin embargo sí se cumple en 18, 27, 36, 54,…

Esto se complica, porque tienen la propiedad números no múltiplos de 9 y entre los que sí lo son, unos la cumplen y otros no. Reflexionemos:

Relación entre un número y su mayor divisor propio

Si B es el mayor divisor propio de A se tendrá que A/B será el menor divisor de A (mayor que 1 pues si no B no sería propio), pero por uno de los más elegantes teoremas sobre divisores, ese cociente A/B ha de ser primo. Por tanto

Si B es el mayor divisor propio de A se cumple A=Bp siendo p primo (igual o menor que B)

Condición de igualdad de sumas

Si dos números presentan la misma suma de cifras es que son congruentes módulo 9, como bien se sabe en Aritmética Modular (recuerda el criterio de divisibilidad por 9).

Por tanto tendremos, con la notación anterior, que AºB (mod 9, es decir BºBp (mod 9 y por tanto Bp-B=B(p-1) deberá ser múltiplo de 9. Ten cuidado, que esta condición es necesaria pero no suficiente.

Esto nos lleva a tres posibilidades: (a) B es múltiplo de 9 (b) B es múltiplo de 3 pero no de 9 (c) B no es múltiplo de 3

(a) Si B es múltiplo de 9, el número primo p sólo puede ser 2 o 3. Si fuera mayor no se cumpliría, porque entonces B no sería el mayor divisor, ya que el menor sería 3 y por tanto el mayor sería A/3. Esto divide a los múltiplos de 9 en dos clases:

(a1) Los números en los que un múltiplo de 9 está multiplicado por 2 o 3 (y por otros), sí pueden cumplir la igualdad de sumas. De hecho son estos:

18, 27, 36, 54, 72, 81, 90, 108, 126, 135, 144, 162, 180, 198, 216, 234, 243,…

No sé si echas de menos alguno. No estará el 288, a pesar de cumplir el contener el factor 2, pero es que sus cifras suman 18 y las de su mayor divisor 144 sólo 9.

Aquí tienes la trampa: dijimos que la condición era necesaria pero no suficiente. Por eso hemos usado la palabra “pueden ser”. Lo que sí ocurrirá es que las sumas sean congruentes módulo 9 (razónalo)

(a2) Aquellos que tienen la forma 9p con p producto de primos mayores que 3. Estos no tienen que cumplir la igualdad de sumas. Por ejemplo 873=9*97. Sus cifras suman 18. Su mayor divisor es 873/3=291 y sus cifras suman 12.

(b) Para que B(p-1) sea múltiplo de  9 también puede ocurrir que B sea múltiplo de 3 pero no de 9, luego el otro factor 3 debe pertenecer a p-1, de donde se deduce que p tiene la forma de 3k+1 con k>0, luego p será un primo mayor que 3 y entonces B no será el mayor divisor de A sino A/3. No se puede dar este caso.

(c) Si B no es múltiplo de 9, lo será p-1. Así que si A no es múltiplo de 9, tampoco lo será B y  si se cumple la igualdad de suma de cifras, ha de ser divisible entre un número primo del tipo 9k+1 con k>0. Más exigente aún: como p-1 es par, p será del tipo 18k+1

Efectivamente, a continuación presentamos los números que cumplen la propiedad que estamos exigiendo y que no son múltiplos de 9. En todos ellos figura un factor primo del tipo 18k+1. En la factorización el primer número de cada corchete es el factor primo y el segundo su exponente.

361    [19,2]
551    [19,1][29,1]
703    [19,1][37,1]
1007  [19,1][53,1]
1273  [19,1][67,1]
1691  [19,1][89,1]
1843  [19,1][97,1]
2033  [19,1][107,1]
2071  [19,1][109,1]
2183  [37,1][59,1]
2413  [19,1][127,1]
2603  [19,1][137,1]
2641  [19,1][139,1]
2701  [37,1][73,1]
2831  [19,1][149,1]
2923  [37,1][79,1]
3071  [37,1][83,1]
3173  [19,1][167,1]
3293  [37,1][89,1]
3743  [19,1][197,1]
3781  [19,1][199,1]

No creas que todos son semiprimos. Hay otros que no lo son: 18791 está en la lista y se descompone como 19*23*43.

Recuerda también que la condición no es suficiente aquí tampoco.

Hemos publicado esta lista en OEIS con la referencia https://oeis.org/A219340

El código PARI que engendra esta secuencia lo tienes a continuación, aunque en este blog la primera búsqueda se efectúa con hoja de cálculo y después se comprueba con PARI, Wmaxima o Wiris cuando es posible.

digsum(n)={local (d,p); d=0; p=n; while(p,d+=p%10;p=floor(p/10)); return(d)}
largdiv(n)=if(n==1, 1, n/factor(n)[1, 1]) \\ Charles R Greathouse IV, Jun 15 2011
{ k=0; for (n=2, 10^5,  if(digsum(n)==digsum(largdiv(n))&&n%9>0, k=k+1;write("B219340.txt",k,", ",n))); } 

Sí, esta era una cuestión menor, pero nos ha divertido estudiarla. Se puede aprender mucho con este tipo de planteamientos.