Menor múltiplo oblongo

Para su uso en los cálculos diarios que publico en Twitter, visito casi a diario la página The On-Line Encyclopedia of Integer Sequences!, (OEIS), http://oeis.org, fundada por N. J. A. Sloane. En la primavera de 2022 me llevé la sorpresa de ver una sucesión suya, del año 2021, referente a divisores de números oblongos. El tema de estos números no es muy popular en OEIS, y por eso me sorprendió verlos tratados por el mismo fundador de la página. Esto me ha llevado a tratar el tema con la mayor amplitud posible, según las sucesiones A345988 y A344005.

Lo que plantea N. J. A. Sloane en sus sucesiones es encontrar el oblongo más pequeño que es divisible entre un número dado. Si llamamos n a ese número, es claro que tiene dos múltiplos oblongos con seguridad, n(n+1) y (n-1)n. Por eso, se puede plantear una búsqueda infinita, como figura en OEIS, con la certeza  de que se detendrá:

(PARI) a(n) = for(m=1, oo, if((m*(m+1))%n==0, return(m))) \\ Felix Fröhlich, Jun 04 2021

Lo planteamos para hoja de cálculo en VBASIC. Como no podemos usar el símbolo de infinito, nos serviremos de un bucle WHILE sin fin:

Function menoroblongo(n)

Dim m, o

m = 1 ‘Comenzamos la búsqueda con 1

o = m * (m + 1) ‘Creamos el oblongo

While o Mod n <> 0 ‘Mientras no sea divisible, avanzamos el WHILE

m = m + 1

o = m * (m + 1)

Wend

menoroblongo = o

End Function

Se podía plantear con más eficiencia, pero funciona con rapidez y la hemos dejado así. Con esta función podemos encontrar las mismas soluciones de Sloane:

Uso del Buscador de Naturales

Nuestra herramienta de búsqueda de números naturales permite encontrar el menor oblongo múltiplo de un número dado. Lo que no puede construir es un listado como el de la tabla anterior, pero para explicar el concepto, a nivel elemental, nos vale.

Se puede descargar desde (http://www.hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#buscador)

En la captura de pantalla siguiente figura la búsqueda en el caso de 80. Hemos buscado entre 80 y 6480=80*81, con las condiciones de ser oblongo y múltiplo de 80. Vemos que la solución es 240 como mínimo oblongo:

Casos particulares

Potencia de un primo

Si n es una potencia de un primo p, es claro que cualquier oblongo m(m+1) múltiplo de n ha de contener el factor primo p, luego lo contendrá m o m+1, porque no se puede repartir entre ellos, luego el mínimo será (n-1)n

El mínimo oblongo múltiplo de p^k (p primo) es (p^k-1)p^k

Así, el número 243=3^5 poseerá como menor oblongo múltiplo el 242*243=58806.

Es fácil comprobarlo con el Buscador:

Los dos únicos oblongos de la solución son 242*243 y 243*244. En las factorizaciones destaca el número 3 repetido cinco veces, luego son múltiplos de 243.

Números que solo poseen dos factores primos

Si un número presenta la factorización N=p^a * q^b con p y q primos, es claro que en un oblongo m(m+1) m será múltiplo de uno de los primos, y m+1 lo será del otro. Esto nos lleva a una ecuación diofántica: p^ax - q^by = ±1

Esta ecuación siempre tendrá solución, al ser los coeficientes primos entre sí, y la duda será si el segundo miembro deberá valer 1 o -1 y si las soluciones serán positivas.

Por ejemplo, el número N=3²*5³=1125 poseerá un oblongo múltiplo si 3²x - 5³y = ±1

Si tomamos el valor 1, será x=(1+125y)/9, con lo que habrá que buscar múltiplos de 125 que al sumarles 1 sean múltiplos de 9

Creamos una tabla con esos cocientes:

Observamos que (1, 14) es una solución y, en efecto, 14*9=126 y 1*125=125, luego m=125 y m+1=126, con lo que su producto será un oblongo múltiplo de 1125, 15750. Pero la cuestión es que no sabemos si es el mínimo, porque más abajo hay otra solución, 10, 139, en la que 139*9=1251 y 10*125=1250, con lo que el oblongo sería 1250*1251, claramente mayor que 15750.

A esto hay que añadir que habrá que repetir todo con el caso -1.

En nuestro ejemplo aparecería la solución 8, 111, es decir 8*125=1000 y 111*9=999, que también sería válida.

Vemos que la resolución es posible, pero que no nos garantiza el carácter de mínimo múltiplo.

Estudio diofántico

Podemos plantear

125x-9y=1 o bien 12x-9y=-1

Usamos WolframAlpha:

Caso +1

Paramétricas:

Caso -1

Paramétricas:

Se observa que en las dos paramétricas el mínimo valor positivo se alcanza si n=0.

En la primera tendríamos x=8, y=111, con lo que m=999 y m+1=1000, resultando el oblongo 999000.

En la segunda, x=1 y=14, m=125, m+1=126 y el oblongo el ya conocido

En la práctica es más rápido usar el Buscador ya que sabemos que existen soluciones.

En la siguiente captura de pantalla observamos que se ha buscado un oblongo múltiplo menor que 15750 y no se ha encontrado, luego este es el mínimo:

Caso general

Para un número con más de dos factores primos, bastará agruparlos en dos productos cuyos factores sean primos entre sí, y aplicar la misma técnica de ecuación diofántica, además de las técnicas de búsqueda ya estudiadas. Para encontrar el mínimo deberemos recorrer todos los pares de factores unitarios. Puedes leer la propuesta de Sloane en la sucesión A344005.

Múltiplos anagramáticos

Llegamos hoy a otra entrada de este blog que se basa en un “twitt” publicado en nuestra cuenta de Twitter (@connumeros) el 11/6/19.

El número de fecha de hoy, 11619, presenta dos múltiplos sencillos anagramáticos (mismas cifras en distinto orden):

11619*13 = 151047

11619*9 = 104571

Se puede sospechar que todo número puede cumplir el tener dos múltiplos anagramáticos para factores convenientemente grandes, pero como no tenemos herramientas para este tipo de búsquedas nos limitaremos a múltiplos que usan factores no mayores que un número determinado. Después nos podemos plantear una extensión del estudio.

Para investigar esta cuestión necesitamos una función que nos indique si dos números poseen las mismas cifras y con la misma frecuencia pero en distinto orden. Contamos con dos versiones de esta función. La primera, de hace años, se basa en la conversión de cada número en cadena de texto, para después investigar si cada carácter de uno se encuentra en el otro. Las frecuencias las tiene en cuenta borrando cada carácter encontrado en ambas cadenas. La puedes consultar en una entrada de 2012 de este blog:

http://hojaynumeros.blogspot.com/2012/04/proposito-de-ormiston.html

Aquí usaremos otra versión, que no necesita funciones de texto, pero sí varias memorias que almacenen las cifras de cada uno de los números.

Public Function cifras_identicas(m, n) As Boolean

Dim i, h, s

Dim ci As Boolean

Dim ca(10), cb(10)

For i = 1 To 10: ca(i) = 0: cb(i) = 0: Next i ‘Prepara memorias para recibir frecuencias de cifras

h = m ‘Extracción de cifras del primer número

While h > 0

i = Int(h / 10)

s = h - i * 10

h = i

ca(s + 1) = ca(s + 1) + 1 ‘Almacenamiento de las frecuencia de una cifra

Wend

h = n ‘El mismo proceso para el otro número

While h > 0

i = Int(h / 10)

s = h - i * 10

h = i

cb(s + 1) = cb(s + 1) + 1

Wend

ci = True

For i = 1 To 10

If ca(i) <> cb(i) Then ci = False ‘Si una de las frecuencias no coincide, las cifras no son idénticas

Next i

cifras_identicas = ci

End Function

Con esta función podemos encontrar dos múltiplos de un número que presenten las mismas cifras.

En PARI es mucho más simple, pues permite la ordenación de los dígitos de un número en forma de vector:

anagram(a,b)=vecsort(digits(a))==vecsort(digits(b))

Listado de soluciones

Podemos investigar si un número dado posee dos múltiplos anagramáticos al menos. Tal como explicamos más arriba, solo buscaremos múltiplos hasta un factor dado, para no alargar ni bloquear el proceso. Hemos creado la función multianagram, que busca los múltiplos anagramáticos hasta una cota k.

Como lo que nos interesa es saber si existe solución o no, está construida de forma que detiene el proceso cuando encuentra la primera solución. Sus parámetros son n, el número dado, y k, la cota para los factores que formarán los múltiplos pedidos.

Public Function multianagram(n, k) As String

Dim s$

Dim i, j, a, b, l

s$ = "" ‘Si no hay solución, devuelve un string vacío.

i = 2

While i <= k And s$ = ""   ‘Recorre los factores hasta una cota k

j = 1

While j < i And s$ = ""  ’Busca el segundo múltiplo

If i <> j Then

a = n * i: b = n * j

If cifras_identicas(a, b) Then s$ = s$ + Str$(i) + Str$(j) + Str$(a) + Str$(b)

‘Si las cifras son idénticas, devuelve los dos factores y los múltiplos resultantes

End If

j = j + 1

Wend

i = i + 1

Wend

multianagram = s$

End Function

Hemos preparado varias búsquedas con la cota 1000 para los factores que producirán los múltiplos anagramáticos. Parece que todos los primeros números presentan la propiedad.

Por ejemplo, entre 30 y 45, todos poseen un par al menos de múltiplos anagramáticos. En el listado figura cada número, después el par de factores necesarios y al final los dos múltiplos pedidos, que presentan las mismas cifras:

Modificando ligeramente la función multianagram podemos tener una idea del máximo factor necesario para lograr el par de múltiplos anagramáticos. Para los número del 1 al 100, el máximo es 137, necesario para el número 95 y sus múltiplos 95*137=13015 y 95*119=11305.

Hasta el 500 el número que necesita un factor mayor es el 425, que forma los múltiplos 12750 y 70125 con un factor máximo de 165. De este orden de magnitud suelen ser los factores. Por eso, para cota 1000 todos los primeros números poseen múltiplos anagramáticos.

Con PARI podemos investigar qué factor presenta cada número de los dados (que por ahora son todos). Con este listado se logra:

anagram(a,b)=vecsort(digits(a))==vecsort(digits(b))

for(n=200,500,k=2;e=0;while(k<=200&&e==0,h=1;while(h<=k-1&&e==0,a=n*k;b=n*h;e=anagram(a,b);if(e<>0,print(n,", ",k));h+=1);k+=1))

En primer lugar definimos anagram(a,b), que devuelve 1 si los números son anagramáticos y 0 si no lo son. Después construimos los múltiplos posibles e investigamos si existen anagramáticos y cuál es el factor máximo. En el ejemplo buscamos entre 2 y 200 con un factor máximo de 200 (Observa k<=200) Después se pueden cambiar los parámetros. Estos serían los resultados desde 420 a 430:

420, 22

421, 65

422, 74

423, 4

424, 84

425, 165

426, 58

427, 45

428, 147

429, 47

430, 41

Comprobamos que 425 es el que necesita un factor mayor (dentro de la cota 200)

Problema contrario

Podemos plantear el problema contrario, y es la búsqueda de números que no posean múltiplos anagramáticos para una cota razonable, como puede ser 1000. Si encontramos alguno, subimos la cota.

Podemos usar nuestro buscador en Excel o el código anterior de PARI ligeramente modificado.

anagram(a,b)=vecsort(digits(a))==vecsort(digits(b))

for(n=2,5000,k=2;e=0;while(k<=1000&&e==0,h=1;while(h<=k-1&&e==0,a=n*k;b=n*h;e=anagram(a,b);h+=1);k+=1);if(e==0,print(n)))

En este caso solo imprimimos resultados si después de recorrer los múltiplos no se encuentra ningún par anagramático. Usamos cota 1000, a ver qué ocurre. Hasta 5000 no hemos encontrado ninguno. Vamos aumentando el rango de búsqueda, aunque se va lentificando el proceso. Hasta una cota de 100000, con un factor máximo de 1000, no ha aparecido ningún caso. Es arriesgado conjeturar nada, porque si aumenta el factor, también lo hace el número de cifras del múltiplo, lo que dificulta la coincidencia. Lo dejamos aquí.