Pandigitales, cromos y un poco de Benford (1)

Esta es la primera parte de nuestra participación en el  Carnaval de Matemáticas, Edición 3.1415926535, cuyo anfitrión es La Aventura de la Ciencia. El proximo día 27 publicaremos la segunda parte. 

Hace unas semanas conocí esta conjetura:

El número 168 es el mayor N que cumple que la potencia 2^N no contiene todas las cifras del 0 al 9

http://www.johndcook.com/blog/2012/11/23/digits-in-powers-of-2/comment-page-1/#comment-316640

Es decir, a partir de 2^169 todas las potencias de 2 son pandigitales en sentido amplio, pues contienen todas las cifras, pero repetidas (usualmente se exige que los pandigitales presenten cada cifra una sola vez).

2^168 = 374144419156711147060143317175368453031918731001856
(le falta la cifra 2)

2^169 = 748288838313422294120286634350736906063837462003712
2^170 = 1496577676626844588240573268701473812127674924007424
2^171 = 2993155353253689176481146537402947624255349848014848
2^172 = 5986310706507378352962293074805895248510699696029696
2^173 = 11972621413014756705924586149611790497021399392059392
(todos contienen las cifras 0 al 9)

Esta conjetura también está publicada en http://oeis.org/A130696

Comienzo de los pandigitales

Nos podíamos preguntar qué ocurre con las demás bases y sus potencias. Hemos trabajado un poco con la hoja de cálculo y llegado a esta tabla, en la que figuran las siguientes bases (no múltiplos de 10, que serían casi triviales) y los exponentes hasta donde llega la carencia de alguna de las cifras en sus potencias

Esta tabla “huele” a inverso de un logaritmo. En efecto, si en lugar del tope en el que se acaban las potencias no pandigitales (con repetición) nos fijamos en las cifras de esas potencias llegamos a una cierta uniformidad, especialmente en las primeras:

Para que una potencia alcance un número de cifras se deberá cumplir de forma aproximada esta igualdad:

B es la base dada, T el tope no pandigital y C el número de cifras a partir del cual están representadas todas las posibles. Si tomamos este número de cifras en un promedio de 50, por ejemplo, nos daría una aproximación del tope:

El logaritmo es decimal, evidentemente. Si aplicáramos esta fórmula obtendríamos:

Resulta coherente con los cálculos, luego lo importante es el número de cifras. El tope es una consecuencia de ellas.

Esto no funciona como algo aleatorio

Este problema, si tuviera una base aleatoria se parecería al de completar una colección de cromos. Aquí la colección completa sería el conjunto {0,1,2,3,4,5,6,7,8,9} y los “cromos” se incorporarían uno a uno a la colección. Cuando aparezcan todos la colección estará completa, pero se habrán producido repeticiones.

En este blog estudiamos dichas colecciones de sobre en sobre, lo que no es este caso.

http://hojaynumeros.blogspot.com.es/2012/05/este-cromo-lo-tengo-repe-1.html
http://hojaynumeros.blogspot.com.es/2012/05/este-cromo-lo-tengo-repe-2.html

En otras direcciones puedes consultar una fórmula sencilla para cuando se incorporan a la colección los cromos de uno en uno, caso más parecido al que nos ocupa.

http://www.cienciaonline.com/2012/07/25/%C2%BFpor-que-nunca-complete-mi-coleccion-de-cromos/
http://www-eio.upc.es/~delicado/docencia/Daniel_Alcaide/Documento/PFC.pdf

En ellas puedes estudiar una fórmula que te da el total de cromos T que has de comprar para completar una colección de N

En el caso de diez cifras T=29,29

En nuestro ejemplo hemos necesitado más, unos 50. Es claro. Estamos comparando como mera diversión dos conceptos diferentes:

•  Los cromos aparecen de forma aleatoria y las cifras de las potencias constituyen un cálculo exacto, determinista.
•  En los cromos cada  vez que sale uno ya lo tenemos definitivo y aquí en cada potencia hay que volver a empezar. Esto, en parte, justifica la discrepancia entre 29 y 50.
•  Aquí existe una relación clara de causalidad entre las cifras de 2^N y las de 2^N+1

Acabamos de afirmar que estudiamos un fenómeno determinista, pero si la distribución de cifras fuera muy uniforme, sus resultados se acercarían a los aleatorios. Cuidado: no confundas aleatorio con uniforme. Sólo afirmamos que los resultados serían más parecidos.

¿Cómo se comportan las potencias respecto a la frecuencia de las distintas cifras? ¿Qué grado de uniformidad presentan? Lo vemos en la siguiente entrada.

Números altamente compuestos (3)

Encontrar sin ver

La hoja de cálculo tiene una precisión limitada en el cálculo con enteros, pero para encontrar números altamente compuestos no es necesario ver su desarrollo en el sistema de numeración decimal, pues basta poder dar los exponentes correspondientes de 2, 3, 5, 7, 11, 13,…(ver entradas anteriores) Así podemos estar seguros de haber encontrado un NAC aunque no lo veamos escrito, sólo leyendo los exponentes.

Hemos preparado una herramienta siguiendo las ideas contenidas en el documento http://wwwhomes.uni-bielefeld.de/achim/julianmanuscript3.pdf de D. B. Siano and J. D. Siano - Oct. 7, 1994

La idea consiste en manejar tan sólo las potencias del tipo

Para cada juego de exponentes tendremos en cuenta los siguientes hechos:

(a) El número 2N tiene más divisores que N, luego si tenemos un N altamente compuesto, para encontrar el siguiente partiremos de ese valor 2N hacia abajo, números cada vez más pequeños hasta llegar a N. Uno de ellos será el mínimo que cumpla el tener más divisores que N.

(b) Ramanujan descubrió una desigualdad doble para los exponentes de 2, 3, 5, 7,…en un NAC, que nos da el mínimo y máximo valor que han de tener estos en el desarrollo. Si llamamos aq al exponente con el que figura el número primo q en ese desarrollo, se cumple que

En la desigualdad p representa el último número primo del desarrollo y p+ el siguiente primo después de él.

Podemos recorrer todas las combinaciones posibles  entre estas cotas para descubrir el próximo NAC a partir de un juego de exponentes dado. Necesitaremos efectuar cuatro comparaciones:

•  Con 2N y exigir que el número encontrado sea menor o igual
•  Con N y exigir que sea mayor
•  Con el anterior candidato  para ver si es menor 
•  Sus divisores han de compararse con los de N y presentar mayor número

No daremos excesivos detalles, pero la idea es la de comparar los exponentes de cada candidato con los de N y llamar exceso al número formado por aquellas potencias en las que el primero sobrepasa al segundo y defecto a aquellos en los que ocurre lo contrario. Es la única forma de comparar si tener que escribir los números en el sistema decimal.

Si el exceso es mayor que el doble del defecto, se desecha el candidato, porque sobrepasaría a 2N. Si el defecto es mayor que el exceso también, porque sería menor que N. Entre los que quedan analizaremos sus divisores calculados mediante. Además, deberán presentar más divisores que N

(c) Lo anterior presenta un problema, y es que dado un juego de exponentes para N, el siguiente puede tener el mismo número de ellos, uno más e incluso uno menos. Puedes verlo en estos ejemplos de la lista de NAC:

Los mismos primos:

20160 2* 2* 2* 2* 2* 2* 3* 3* 5* 7
25200 2* 2* 2* 2* 3* 3* 5* 5* 7

Un primo más

50400 2* 2* 2* 2* 2* 3* 3* 5* 5* 7
55440 2* 2* 2* 2* 3* 3* 5* 7* 11

Un primo menos

27720 2* 2* 2* 3* 3* 5* 7* 11
45360 2* 2* 2* 2* 3* 3* 3* 3* 5* 7

Así que el algoritmo que intentemos deberá ser triple, uno para cada caso. Como dijimos, no damos más detalles, que podrían ser largos y pesados.

Herramienta

Hemos preparado una herramienta que sacrifica la velocidad para que se vean bien los cambios de exponentes, el exceso y defecto y el resultado final

En la fila 6 escribimos los exponentes de un NAC conocido, en este caso 21621600, cuyo juego es 5, 3, 2, 1, 1 y 1 (en el resto, para que estén en blanco, usa la tecla Supr). En la 9 se irán formado todas las combinaciones posibles dentro de las cotas de Ramanujan (algo ampliadas) y en las 12 y 13 se calculan los excesos y defectos, para garantizar que se mueven entre 2N y N.

También se calcula el número de divisores del inicial y el candidato, así como sus valores, aunque estos no son representativos y pueden presentar desbordamiento.

Si usas el botón “Buscar el próximo NAC” verás que van cambiando los valores de las filas 9 a 19, pero que en esta última se puede ir estabilizando el mejor candidato, hasta que termina el proceso y se convierte en el definitivo. En nuestro ejemplo se obtiene el siguiente  32432400.

A la derecha tienes la posibilidad de obtener varios NAC consecutivos a partir del escrito en la fila 6. No abuses de números grandes, que lo que obtendrás será un gran bloqueo en los cálculos. Si te metes en ese terreno, intenta salir con la tecla ESC.

En este caso aparecen los valores, pero si avanzáramos más llegaría un momento en el que sólo podríamos leer los exponentes. Por eso usábamos la expresión “encontrar sin ver”

En la anterior entrada ya dimos la dirección para que descargues la herramienta. Sólo la hemos implementado en Excel, pues su complejidad nos ha llevado bastante tiempo.

http://hojamat.es/blog/nac.xlsm

Puedes intentar exprimirla y comparar con la lista publicada en http://wwwhomes.uni-bielefeld.de/achim/highly.txt. Y también puedes mejorar el algoritmo…con paciencia.

Números altamente compuestos (2)

Generación ordenada de los NAC (ver entrada anterior)

Ya hemos visto una forma de generar los NAC a base de columnas en una hoja de cálculo, pero este procedimiento tiene el inconveniente de que para números grandes los intervalos de aparición son tan amplios que no se pueden presentar en una columna. Lo ideal sería poderlos tener en filas consecutivas, como vemos en la imagen:

Pero esto no es fácil, porque el orden natural de los números no coincide con el del número de divisores, por lo que deberemos avanzar uno a uno y quedarnos con el máximo.

Veamos qué necesitamos:

Una función POTE(a;p) que nos indique el exponente con el que figura un número p en la descomposición en factores primos de a. Si no figura, el valor de la función será cero.

Otra función ESPRENAC(n) que indique si un número puede ser altamente compuesto o no, dependiendo de si presenta el esquema exigido con exponentes decrecientes.

Deberemos usar la función POTE y con ella verificar que los exponentes son los adecuados.

Un truco muy útil es el siguiente:

Si el número no obedece el esquema previo, la función ESPRENAC devuelve un cero, pero si lo obedece, la salida será el número de divisores. De esta forma podremos comparar este número con los de los anteriores y descubrir cuándo se ha llegado a un NAC.

Función POTE

Dado un número natural a y un primo p (en el algoritmo no se necesita que sea primo), para calcular el exponente con el que figura p en la descomposición de a bastará ir dividiendo a entre p todas las veces posibles siempre que p siga siendo divisor de a. Algo así:

•  Pongo un contador a cero
•  MIENTRAS p sea divisor de a
•  Divido a entre p y vuelvo a probar
•  Aumento el contador por cada división exacta
•  FIN del MIENTRAS

 El contador será el exponente

Su funcionamiento se entiende bien: al principio no sabemos si p es divisor de a, por lo que le asignamos exponente cero (el contador). Después intentamos una división exacta de a entre p. Cada vez que lo logremos aumenta el contador del exponente.

Código en Basic de hoja de cálculo

Public Function pote(a, b)
Dim p, c, d

p = 0: c = a
d = c / b (división con decimales)
While d = c \ b (división entera)
p = p + 1
c = c / b
d = c / b
Wend
pote = p
End Function

Dejamos a nuestros lectores la interpretación de este código.

Función ESPRENAC

Su objetivo es descubrir si un número tiene la estructura adecuada para ser NAC, es decir, que en su descomposición en factores primos sólo figuren los primeros con exponentes no crecientes.

Esta función recorre los primeros números primos 2, 3, 5, 7, … (representados en el código por la variable pr(i)) y va calculando la función POTE para cada uno de ellos. Analiza si ninguno es cero y si forman una sucesión no creciente. De paso, almacena (1+POTE) para al final calcular el número de divisores.

El esquena sería:

•  Inicio una variable SIGUE a uno
•  MIENTRAS el número N sea mayor que 1 y SIGUE>0
•  Recorro los primeros números primos
•  Para cada uno de ellos evalúo la función POTE, con lo N disminuirá
•  Si POTE es nula o mayor que la anterior, hago SIGUE=0
•  En caso contrario multiplico SIGUE por (1+POTE), con lo que preparo el cálculo del número de divisores
•  FIN del mientras

 Por último, ESPRENAC toma el valor de SIGUE. Si es cero, es que el número no puede ser altamente compuesto y si no lo es, devolverá el número de divisores.

Su código puede ser:

Public Function esprenac(n)
Dim p(20)
Dim c, i
Dim sigue

c = n
i = 0
sigue = 1
While c > 1 And sigue > 0
If i < 20 Then
i = i + 1
p(i) = pote(c, pr(i))
If p(i) = 0 Then sigue = 0
c = c / pr(i) ^ p(i)
sigue = sigue * (p(i) + 1)
If i > 1 Then
If p(i) > p(i - 1) Then sigue = 0
End If
Else
sigue = 0
End If
Wend
esprenac = sigue
End Function

Búsqueda ordenada

Con estas dos funciones podemos generar fácilmente la lista de NAC. Es un algoritmo “ingenuo” porque recorre todos los números entre cada dos posibles NAC, con el consiguiente gasto de trabajo y tiempo, pero para números no muy grandes va bastante bien.

Consistiría en

•  Iniciamos la lista con el 1. Llamamos ANTERIOR al mismo y DANTERIOR  a su número de divisores (también 1)
•  DESDE el valor 2 hasta el tope que marquemos
•  Analizamos cada número consecutivo para ver si puede ser NAC. Le calculamos su número de divisores y lo comparamos con DANTERIOR. 
•  Si el resultado de la comparación es que es mayor, ya hemos encontrado el siguiente NAC. Lo almacenamos en ANTERIOR y su número de divisores en DANTERIOR
•  FIN del DESDE
• De esta forma iremos comparando los divisores de los candidatos y cuando encontremos un NAC lo consideramos como ANTERIOR y vuelta a empezar.

El código de esta búsqueda contiene elementos propios cada hoja de cálculo concreta, por lo que es preferible que los descargues desde

http://hojamat.es/blog/nac.xlsm

¿Y qué ocurre si llegamos a números tan grandes que las hojas de cálculo no pueden ya representar sus cifras? Pues o bien nos pasamos a programas más potentes o intentamos buscar NAC sin verlos. Eso es lo que haremos en la siguiente entrada.

Números altamente compuestos (1)

Estos números fueron estudiados por Ramanujan, que ya tenía ideas sobre ellos antes de su colaboración con Hardy. Su definición es muy sencilla:

Un número altamente compuesto es un entero positivo con más divisores que cualquier número entero positivo menor que él mismo.

Así, el 12 tiene 6 divisores, mientras que todos los números menores que él tienen (del 1 al 11) 1, 2, 2, 3, 2, 4, 2, 4, 3, 4 y 2 respectivamente, luego 12 es altamente compuesto (lo expresaremos como NAC)

Los primeros son:

1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, ... 

(http://oeis.org/A002182)

La sucesión contiene infinitos términos, porque si N es NAC, el número 2N tiene los mismos factores que N y uno más, luego al menos existe un número con más divisores que N y recorriendo N+1, N+2, N+3,…N+N=2N bastará quedarse con el primer número que presente un máximo de divisores respecto a los anteriores (puede ser el mismo 2N).

Podemos expresarlo mediante la función divisor o sigma0, que cuenta los divisores de un número. En los NAC esta función presenta un valor superior al de cualquier otro número entero menor que él.
Pero si recordamos que la expresión de la función divisor es

siendo  a_i los exponentes en su descomposición en factores primos

comprenderemos  que lo que debemos estudiar son los máximos de esta expresión, que sólo dependen de la signatura prima de N (esto es, el conjunto de los exponentes en la factorización. Esto es importante: si sustituimos uno de los números primos de la factorización por otro, el valor de la función divisor no se altera. Esta idea tan simple nos lleva a la primera propiedad de los NAC:

Todo número altamente compuesto tiene como factores primos los primeros de la lista, de forma consecutiva: 2, 3, 5, 7, 11, …

Es sencillo demostrarlo. Imagina que en su desarrollo no figuraran todos los primeros números primos. Por ejemplo, que figurara el 11 y no el 7. Entonces, si sustituyéramos el 11 por un 7, el valor de N disminuiría, pero el de su función divisor, tal como vimos en el párrafo anterior, se mantendría igual, lo que contradice lo afirmado de que N presenta más divisores que cualquier otro número menor.

Esto recuerda a los primoriales. Puedes repasarlos, que los usaremos más adelante. Los tienes en http://hojaynumeros.blogspot.com.es/2012/02/el-primorial.html

No sólo han de figurar los primeros primos, sino que sus exponentes deberán ser no crecientes si ordenamos las potencias mediante bases crecientes: e1 ³ e2 ³ e3 ³ e4 ³ e5 ³…

También es fácil demostrarlo: si un par de exponentes se presentaran en orden inverso, intercambiando sus bases obtendríamos un número menor que N con sus mismos divisores, luego N no es NAC.

Por último, salvo en los casos de N=4=22 y N=36=22*32, el último de los exponentes debe ser 1. No he encontrado demostración de este hecho.

Obtención con hoja de cálculo

Debes disponer de la función divisor. Puedes definirla con esta versión muy simple

Public Function divisor(n)
Dim i, s

s = 1
For i = 1 To n / 2
If n / i = n \ i Then s = s + 1
Next i
divisor = s
End Function

Para implementarla en la hoja de cálculo puedes seguir las instrucciones contenidas en http://hojamat.es/guias/descubrir/htm/macros.htm

Comprueba que funciona bien y escribe en columna los primeros números naturales y junto a ellos el valor de divisor(n)

Una tercera columna la rellenaremos con los máximos consecutivos que se produzcan en la segunda. En la siguiente imagen te damos una idea del método para conseguirlo. Lee la fórmula en la línea de entrada.

Por último, en los saltos que se produzcan en ese máximo, allí estarán los NAC. Te dejamos en la imagen la fórmula usada

Con estas cuatro columnas te irán apareciendo los números altamente compuestos, para lo que basta que rellenes las fórmulas hacia abajo hasta donde quieras.

Más adelante volveremos a la generación ordenada de los NAC.

Relación con los primoriales

Si has visitado http://hojaynumeros.blogspot.com.es/2012/02/el-primorial.html sabrás ya que un número primorial el que equivale al producto de los primeros números primos sin saltar ninguno, es decir, son primoriales 1, 2, 6, 30, 210, 2310, 30030, 510510

Pues bien, es fácil demostrar que todo número altamente compuesto es un producto de primoriales.
La clave está en que los exponentes son no crecientes. De esa forma extraemos del NAC un primer primorial con todos los factores primos usados. Al cociente que nos resulte le hacemos lo mismo, dividirlo entre los primos que hayan quedado, y así sucesivamente. Al ser los exponentes no crecientes, siempre quedarán primos consecutivos que comenzarán en 2. Es mejor verlo con un ejemplo:

2520 es un NAC y se descompone como 2520=2⁵*3³*5*7= (2*3*5*7)*(2*3)*(2*3)*2*2 = P(5)*P(3)*P(3)*P(2)*P(2), si representamos por P(k) el k-ésimo primorial.

Se ve que se pueden repetir primoriales  y que no tienen que estar todos lo posibles. El recíproco no es cierto: no todo producto de primoriales es un NAC. Por ejemplo, en el caso de P(2)*P(2)*P(2)*P(3)*P(4)=2*2*2*6*30=1440 no resulta un NAC.

Otra propiedad: A partir del 6, todos los elementos de la sucesión son múltiplo de 6 y abundantes.

En la siguiente entrada generaremos todos los NAC de forma ordenada en filas consecutivas de una hoja de cálculo.

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, V₂(N) (definición tomada de los números p-ádicos).

Podemos descomponer N como N=MDI(N)* V₂(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 2^N. 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=p^k, siendo p un factor primo de N. En este caso es trivial: si p=2, MDI(2^k)=1 y en caso contrario, MDI(p^k)= p^k

(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)* V₂(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*2^r 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*2^h que pertenece al rango N+1..2N. Supongamos que no, que existen dos exponentes consecutivos tales que M*2^h £ N < 2N < M*2^h+1 (h eventualmente igual a la unidad). Dividiendo resultaría M*2^h+1/ M*2^h > 2N/N, es decir 2>2, luego esta situación es imposible. Debe existir un exponente tal que M*2^r 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) = N², 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) = n²+U(n)

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

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

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

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

Para 2^N+1, según la propiedad anterior, la suma sería: MDI(1)+MDI(2)+…+MDI(2^N+1) = (4^N+2)/3)+4^N = (4*4^N+2)/3 = (4^N+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))

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.

Descomposición de un número según una lista

Hoy presentamos una herramienta de hoja de cálculo que nos permitirá descomponer un número en sumandos extraidos de una lista. Ya la anunciamos en anteriores entradas y tratamos el tema en
 (http://hojaynumeros.blogspot.com.es/2010/02/frobenius-y-los-mcnuggets.html)

El concepto es el siguiente: dado un conjunto de números enteros positivos a₁, a₂, a₃,…a_n, diremos que otro entero positivo N es representable según ese conjunto si existen coeficientes enteros no negativos x₁, x₂, x₃,…x_n tales que

 N= a₁*x₁+a₂*x₂+…a_n*x_n

Si exigimos que los coeficientes sólo puedan valer 0 o 1, obtendremos la descomposición en elementos distintos. Si los dejamos libres pasaremos al caso general del problema, también llamado “de las monedas”.

Herramienta

Hemos preparado una herramienta de hoja de cálculo. La tienes en

(http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#reprenum)

 y resuelve este problema para números no demasiado grandes. Tiene dos variantes, que explicaremos por separado.

(1) Descomposición de un sólo número

Para descomponer un número según una lista, es evidente que esos son los datos necesarios que habrá que aportar a la herramienta: el número, la lista y si deseamos o no repeticiones de sumandos. Es importante que se entienda esto bien, pues si por ejemplo deseamos expresar un número como suma de primos, será responsabilidad nuestra escribir la lista de números primos correctamente y tener una idea clara de hasta dónde debe llegar, dentro de las limitaciones de la hoja que estamos usando.

Por ejemplo, deseamos expresar el número 30 de todas las formas posibles como suma de cuadrados con repetición.

Para ello habrá que decidir el número a descomponer (30), la lista de cuadrados (1,4,9,16,25). En la imagen puedes ver el planteamiento

Además hay que indicar con un SI que deseamos repetición en los sumandos, es decir, que los coeficientes puedan ser números enteros positivos, no necesariamente 0 y 1. Hay que escribir en mayúsculas y sin tilde SI o NO.

Con el botón Iniciar se comienza la búsqueda de coeficientes. A cada sumando se le asigna un tope, que es el cociente entero por exceso entre 30 y él, para evitar cálculos inútiles. A la derecha de los topes verás de forma muy animada la búsqueda de coeficientes. El hecho de que aparezcan ralentiza el proceso, pero le da más vida y aquí nos interesa más la comprensión que la velocidad.

Los resultados se expresan como combinaciones lineales, que son más compactos que la lista de sumandos. En nuestro ejemplo han aparecido 27 formas distintas de expresar el número 30 como combinación lineal del tipo

30 = 1*x₁+4*x₂+9*x₃+16*x₄+25*x₅

Estas combinaciones las puedes interpretar como sumas con elementos repetidos:

2*1+7*4 = 1+1+4+4+4+4+4+4+4 = 30

27 sumas son muchas. Si el número fuera mayor la lista también tenía que crecer. Por eso no debe extrañar que los tiempos de cálculo se acerquen a 10 o 20 minutos en números pequeños, o más si se le exige mucho. Si te cansas del cálculo, pulsa ESC si usas Excel o Ctrl+Maúscula+Q si estás con OpenOffice o LibreOffice.

La variante sin repetición, al sólo admitir 0 y 1 como coeficientes es mucho más rápida y con menos resultados. Aquí tienes todas las descomposiciones del número 50 en sumas de números primos no repetidos. Al ser extensa la lista de primos, a un ordenador, si no es muy rápido, puede costarle más de diez o quince minutos encontrarlos.

Resultan 23 formas de expresar 50 como suma de primos no repetidos. Puedes comprobarlo en la lista contenida en http://oeis.org/A000586. Intenta reproducir algún resultado más de la misma, pero si el número es mayor, deja al ordenador trabajando solo y al cabo de media hora vuelves.

(2) Elaboración de una lista

Hemos señalado que la página http://oeis.org/A000586 contiene las descomposiciones de los números enteros en sumas de primos distintos. Sus primeros valores son 1, 0, 1, 1, 0, 2, 0, 2, 1, 1, 2, 1, 2, 2, 2, 2. Eliminamos el primer 1, que corresponde al cero y no tiene sentido en nuestra tarea. Intentaremos reproducirla.

Para obtener una lista pasamos a la parte derecha de la hoja sin borrar la lista de sumandos, pero sí eliminando los primos que no vayamos a usar. Por ejemplo, se podían preparar los 20 primeros números con la lista {2, 3, 5, 7, 11, 13, 17, 19}. En esa parte derecha concretamos el inicio, final y salto de la lista. Aquí serían 1, 20 y 1 respectivamente.

Al pulsar en el botón Lista observaremos que las búsquedas no presentan a la izquierda ni los coeficiente ni los resultados parciales, para aumentar la velocidad, y sólo aparecerán los números y sus resultados.

Reproduce la búsqueda en tu equipo y compara estos resultados con los de  http://oeis.org/A000586 para comprobar su exactitud. Puedes realizar más comprobaciones, pero lo dejamos para otro día