miércoles, 19 de diciembre de 2012

Volvemos a visitar al mayor divisor impar


Participamos con esta entrada en el Carnaval de Matemáticas 3.131592653 cuyo anfitrión es el blog Que no te aburran las M@tes.

En una entrada ya algo antigua

 (http://hojaynumeros.blogspot.com.es/2009/03/la-hoja-de-calculo-ayuda-razonar.html)

resolvimos una cuestión muy elegante sobre el mayor divisor impar de un número (le llamaremos MDI).

Al revisar ahora esta cuestión nos hemos encontrado con que desde entonces se han desarrollado en este blog muchos estudios que nos podrían ayudar a estudiar con más profundidad esta función. Algunos de los temas que trataremos los hemos encontrado en http://oeis.org/A000265, pero sin desarrollar.

Definición y cálculo

Llamaremos mayor divisor impar (MDI) de un número natural N al mayor número impar (eventualmente igual a 1) que es divisor de N

Es evidente que si N es impar, MDI(N)=N y que si es potencia de 2, MDI(N)=1

Esto nos da una idea muy simple para calcularlo en un caso concreto: dividimos entre 2 todas las veces posibles y al final llegaremos al MDI:

144/2=72; 72/2=36; 36/2=18; 18/2=9, que será el MDI(144)

Visto de otra forma, hemos eliminado la mayor potencia de 2 posible. El exponente correspondiente, en este caso 4, recibe el nombre de valuación de N respecto a 2, V2(N) (definición tomada de los números p-ádicos).

Podemos descomponer N como N=MDI(N)* V2(N)

Esto nos lleva a códigos muy sintéticos para calcularlo:

En el Basic de las hojas:

Public Function mdi(n)  'mayor divisor impar
Dim s
s = n
While s/2=int(s/2): s = s / 2: Wend ‘ Divide entre 2 mientras se pueda.
mdi = s
End Function

No requiere explicación. Basta leerlo.

En PARI, como ya tiene implementada la función VALUATION, el código es aún más simple:

mdi(n)= {m=n / 2^valuation(n, 2);return(m)}

Existen otras formas elegantes de cálculo, pero más lentas:


Aquí hay un exceso: no es necesario llegar a 2N. Es claro que el denominador es la valuación de N respecto a 2.Intenta razonarlo.

La sucesión de los mayores divisores impares la tienes en http://oeis.org/A000265:

1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 11, 3, 13, 7, 15, 1, 17, 9, 19, 5,21, 11, 23, 3, 25, 13, 27, 7, 29, 15, 31, 1, 33, 17, 35, 9, 37, 19, 39,…

Razona una propiedad muy sencilla y compruébala en la lista:

MDI(N)=MDI(2N)

Basándonos en esta propiedad podemos calcular MDI mediante recursividad, pues definiremos MDI(N) como el mismo N si es impar y MDI(N/2) si es par.

Es una solución muy elegante. Podemos usar la recursividad en las hojas de cálculo, ya explicada en http://hojaynumeros.blogspot.com.es/2012/03/funciones-recursivas-en-las-hojas-de.html:

Public Function mdirecu(n)
Dim d
If n = 2 * Int(n / 2) Then d = mdirecu(n / 2) Else d = n
mdirecu = d
End Function

Propiedades

(1) Es multiplicativa

En efecto, si m y n son coprimos, se cumple que MDI(m*n)=MDI(m)*MDI(n)

Casi podríamos dejarlo como ejercicio: Si m y n son coprimos tendrán diferentes factores primos. Es más, si m es par, n será impar. Hallarles el MDI equivale a eliminarle todas las potencias de 2 al que sea par, pero los demás factores no cambiarán y serán distintos en ambos números, luego al multiplicarlos se multiplicarán también sus MDI.

Como todas las multiplicativas (ver http://hojamat.es/publicaciones/multifun.pdf) para definir MDI basta hacerlo en el caso N=pk, siendo p un factor primo de N. En este caso es trivial: si p=2, MDI(2k)=1 y en caso contrario, MDI(pk)= pk

(2) El MDI representa la pauta de unos en su representación binaria

Ya nos referimos a esta propiedad en la anterior entrada: si N=MDI(N)* V2(N), el paso de MDI(N) a N consistirá en añadir ceros a la derecha, luego la pauta de unos se conserva. Lo vemos con un ejemplo:

N=2664=101001101000(2  y MDI(2664)=333=101001101(2

Coinciden las pautas de unos

(3) Los conjuntos {MDI(N+1), MDI(N+2),…MDI(2N)} y {1,3, 5, 7…(n elementos)…} son idénticos.

También nos referimos a ella en su momento.

1.- Los elementos del primer conjunto son todos distintos, pues si dos fueran iguales, MDI(K)=MDI(J), uno de los números, por ejemplo K debería cumplir K=J*2r y entonces, si J pertenece al rango N+1,…2N, K sería mayor que 2N y no pertenecería a ese rango.

2.- Todos los N primeros números impares deben pertenecer al segundo conjunto. Lo que es seguro es que pertenecen al intervalo 1..2N. Si pertenecen al intervalo N+1..2N ya está demostrado. Si no, M£N, y entonces existe un múltiplo suyo del tipo M*2h que pertenece al rango N+1..2N. Supongamos que no, que existen dos exponentes consecutivos tales que M*2£ N < 2N < M*2h+1 (h eventualmente igual a la unidad). Dividiendo resultaría M*2h+1/ M*2h > 2N/N, es decir 2>2, luego esta situación es imposible. Debe existir un exponente tal que M*2r pertenezca a N+1..2N y por tanto su MDI estará en el segundo conjunto.

(3.1) Consecuencia: MDI(N+1)+MDI(N+2)+,…+MDI(2N) = N2, por ser suma de los primeros impares.

(3.2) Otra consecuencia: Si llamamos U(n) a la suma de los MDI de los n primeros números naturales, se obtendrá que

U(2n) = n2+U(n)

(lo tienes en http://arxiv.org/pdf/1103.2295v1.pdf)

(4) La suma de los 2N primeros términos de la sucesión de MDI equivale a (4N+2)/3

Es consecuencia de la propiedad anterior. Lo vemos por inducción (recorre la sucesión presentada más arriba) 1+1=(41+2)/3=2;  1+1+3+1 = (42+2)/3 = 6, 1+1+3+1+5+3+7+1 = (43+2)/3=22,… luego podemos suponer cierta la igualdad para N. Sea

MDI(1)+MDI(2)+…+MDI(2N) = (4N+2)/3

Para 2N+1, según la propiedad anterior, la suma sería: MDI(1)+MDI(2)+…+MDI(2N+1) = (4N+2)/3)+4N = (4*4N+2)/3 = (4N+1+2)/3 y queda demostrado.

Y dejamos para el final la propiedad más elegante:

(5) Si sumamos los valores que toma la función j(N) (indicatriz de Euler) para todos los divisores impares de N, el resultado es el mayor divisor impar.

Es sabido que esa suma extendida a todos los divisores de N da como resultado N
(ver http://es.wikipedia.org/wiki/Funci%C3%B3n_%CF%86_de_Euler)



Por ejemplo, para el número 576, en la siguiente tabla tienes la comprobación de esta propiedad, los valores de la indicatriz también suman 576.



Como la función j es multiplicativa, la suma de la parte derecha se puede dividir en dos factores, uno para todos los divisores que son potencia de 2 y otro con los impares. Así, los 21 sumandos se pueden expresar así:
S = (j(1)+ j(3)+ j(9))*(j(1)+ j(2)+ j(4)+ j(8)+ j(16)+ j(32)+ j(64)) = 9*64 = 576

Vemos que la suma de la primera parte es 9, el MDI(576), como habíamos afirmado.

Esta descomposición se puede efectuar en cualquier número: por una parte incluimos las potencias de 2 y por la otra los coprimos con dos. La segunda suma dará la máxima potencia de 2 que divide a N y la primera tendrá como resultado MDI(N).

Extensión

Al igual que hemos definido el mayor divisor impar podíamos haberlo hecho con el mayor divisor no múltiplo de 5 (lo podemos representar como MD_5) que está estudiado en http://oeis.org/A132739, o no múltiplo de 10 (http://oeis.org/A132740) Puedes trasladar todo lo que se ha expuesto al caso en el que en lugar de 2 se use otro número.

También puedes pensar si siempre se cumplirá que MD_K(MD_L(N)) = MD_L(MD_K(N))

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.