lunes, 21 de octubre de 2024

Primos brasileños

En esta entrada nos plantearemos qué números primos se pueden formar con la suma de las primeras potencias de un número, es decir, cuándo una suma del tipo 1+n+n2+n3+n4+n5+…será un número primo. No consideraremos el caso en el que un primo p sea igual a 1+n, ya que esto lo cumplen todos los primos.

Esta cuestión equivale a la búsqueda de números primos que sean “repitunos” en una base de numeración dada. Por ejemplo, 31(10=111(5, ya que las tres cifras 1 provienen de la igualdad 31=1+5+52.

Función caracterizadora

En nuestras últimas entradas estamos usando funciones para Excel y Calc que devuelven una cadena de texto con los resultados. Es un formato que nos da mucha información y que es susceptible de cambios sencillos para la búsqueda de otros objetivos.

En este caso usamos la siguiente función:

Function primo_sumpot$(n)
Dim p, k, m, q
Dim s$

If Not esprimo(n) Then primo_sumpot = "NO": Exit Function
k = 2 ‘Base de las potencias
p = 1’Suma de potencias
m = 0’ Exponente
s = ""’Contenedor del resultado
q = 0’ Contador de soluciones
While k < n
p = 1 + k: m = 1’Primera suma de potencias
While p <= n
m = m + 1’ Siguiente suma de potencias
p = p + k ^ m
If p >= n Then
If p = n Then q = q + 1: s = s + " # " + Str$(k) + ", " + Str$(m) ‘Solución
End If
Wend
k = k + 1: p = 1 + k: m = 1 ‘Siguiente base de potencias
Wend
If s = "" Then s = "NO" Else s = ajusta(q) + "## " + s
primo_sumpot = s
End Function

Si buscamos con ella los primeros primos que cumplen lo exigido, obtenemos:

Observamos que la mayoría de las soluciones son del tipo 1+k+k2, como, por ejemplo, el 73, que equivale a 1+8+82.

El 31 presenta dos soluciones: 31=1+2+22+23+24=1+5+52, lo que lo convierte en “repituno” en dos bases de numeración:

31(10 = 11111(2 = 111(5

Según una conocida fórmula, estos números también se caracterizan porque para un valor adecuado de m se cumple

En efecto, 31=(25-1)/(2-1)=(32-1)/1=31

También 31=(53-1)/(5-1)=124/4=31

Para que el resultado sea primo, m ha de ser primo, pues en caso contrario el cociente presentaría más de un factor. Es un razonamiento similar al usado en los primos de Mersenne.

Estos primos están publicados en https://oeis.org/A085104

Con el afán de nombrar ciertas clases de números, a estos se les conoce como “brasileños”, porque se dieron a conocer en una olimpiada matemática celebrada en Brasil (ver https://oeis.org/A125134/a125134.pdf)

Números brasileños

Si eliminamos la condición de que N sea primo, nos resultan los números brasileños. En nuestra función suprimimos la condición de que sea primo y los obtendremos:



Están publicados en https://oeis.org/A053696

No son objeto de estudio en esta entrada, pero es aconsejable la lectura de https://oeis.org/A125134/a125134.pdf

Valores de K

La siguiente lista contiene los primeros valores de K que pueden producir un primo con la expresión que estamos estudiando, con un exponente final fijado de antemano, mayor que 2 y con tope 100:


Observamos que hay bases primas entre estos primeros pasos:



Los primos resultantes, ordenados, están publicados en https://oeis.org/A023195

3, 7, 13, 31, 127, 307, 1093, 1723, 2801, 3541, 5113, 8011, 8191, 10303, 17293, 19531, 28057, 30103, 30941,…

 

lunes, 7 de octubre de 2024

Números Bogotá

Estos números fueron llamados así por Tomás Uribe y Juan Pablo Fernández, por su similitud con los números colombianos o autonúmeros. Es un homenaje a Bernardo Recamán, matemático colombiano

(Ver mi entrada https://hojaynumeros.blogspot.com/2015/03/autonumeros-1.html)

Su definición es simple: se trata de números N que equivalen a uno de sus divisores multiplicado por el producto de sus cifras (su raíz digital). Un ejemplo es el número 520, que se puede expresar como 52*5*2, o bien 8991 = 333*(3*3*3).

Para encontrarlos podemos recorrer todos los divisores del número y verificar que el cociente entre ambos coincide con el producto de cifras de ese divisor.

Ya hemos usado la función PRODUCIFRAS, pero reproducimos aquí su versión en VBASIC:

Public Function producifras(n)
Dim h, i, s, m
if n<10 then producifras=n:exit function
h = n  ‘la variable h recoge el valor de n
s = 1 ,‘El producto comienza con un 1 en la variable s
While h > 0  ‘Mientras queden cifras…
i = Int(h / 10) ‘Se queda con todas las cifras menos la última
m = h - i * 10 ‘La variable m recoge la última cifra
h = i ‘La variable h tiene una cifra menos
s = s * m ‘La última cifra se incorpora al producto
Wend
producifras = s
End Function

(ver https://hojaynumeros.blogspot.com/2018/09/permutacion-de-cifras-al-sumar-su.html)

Si contamos con esta función u otra similar, es fácil construir un criterio para saber si un número es Bogotá o no. Últimamente hemos optado por funciones en modo texto, porque en sus valores podemos incluir el número de soluciones y la expresión de cada una mediante el producto pedido (en este caso). En su listado se usan funciones que han aparecido en algún momento en mis publicaciones:

Function esbogota$(n)
Dim k, m, j, c
Dim noes As Boolean
Dim s$, t$

If n = 1 Then esbogota = "1*1": Exit Function Caso especial
k = 2 ‘Primer divisor
noes = True ‘Suponemos que no existe solución
s = "" ‘Contenedor de la solución
c = 0 ‘Contador de soluciones
While k <= n  And noes ‘Recorremos divisores incluido n
If n / k = n \ k Then ‘Es divisor
If n = k * producifras(k) Then ‘Es número Bogotá
t = ""
c = c + 1 ’Una solución más, y se construye a continuación
For j = numcifras(k) To 1 Step -1: t = t + "*" + ajusta(cifra(k, j)): Next j
s = s + " # " + Str$(k) + t
End If
End If
K=k+1 ‘Siguiente divisor
Wend
If s = "" Then s = "NO" Else s = ajusta(c) + " : " + s
esbogota = s
End Function

Para estar escrita en VBasic, no es lenta. Esta tabla es un ejemplo de su utilidad:



Aquí todos presentan una sola solución, pero entre las soluciones menores ya aparecen con dos o tres soluciones:

Estos son los primeros ejemplos con dos soluciones:

Están publicados en https://oeis.org/A336944

El listado de los primeros números de Bogotá de cualquier número de soluciones es:

1, 4, 9, 11, 16, 24, 25, 36, 39, 42, 49, 56, 64, 75, 81, 88, 93, 96, 111, 119, 138, 144, 164, 171, 192, 224, 242, 250, 255, 297, 312, 336, 339, 366,…

Están publicados en https://oeis.org/A336826

En esta página se proponen algunas cuestiones, y aquí plantearemos alguna otra.

Se advierte que los números “repidígitos” son todos de Bogotá, como es fácil razonar: 1111=1111*1*1*1*1. Entre ellos figuran algunos primos, que son los únicos posibles (ver https://oeis.org/A004022).

Ningún número múltiplo de 10 será de este tipo, porque la cifra 0 final anulará el producto de las cifras.

Se puede usar el hecho de que el producto de las cifras ha de ser 7-liso, ya que los números del 2 al 9 sólo poseen como factores primos 2, 3, 5 y 7. No hemos encontrado ventajas en usar este hecho

 (ver https://es.wikipedia.org/wiki/N%C3%BAmero_liso)

 
Números de Bogotá consecutivos

Al usar cifras, la existencia de estos pares será algo casual. Como poseemos la función esbogota(), bastará exigir que tanto N como N+1 sean de este tipo. Con un buscador apropiado se pueden encontrar:


Puedes consultar
https://oeis.org/A336864

También podemos buscar el par (N, N+2):


Estos números no están publicados en OEIS.

Ya puestos, podemos buscar pares (N,2N):


Invitamos a los lectores a buscar más casos, que estarán inéditos muchos de ellos.

Números de Bogotá especiales

En los primeros números de este tipo figuran cuadrados, como 36 o 49. ¿Cuáles serán los siguientes? Para encontrarlos usaremos nuestra función ESCUAD junto a ESBOGOTA:


Esta sucesión también está inédita.

De igual forma se pueden buscar:

Triangulares


Oblongos N(N+1)



Potencias de exponente mayor que 2


Otras variantes

Con lo explicado, es fácil encontrar variantes de estos ejemplos. Si se busca en OEIS “Bogotá numbers”, se encuentran definiciones parecidas y algunas relaciones con los números de Recamán.

 

 

viernes, 20 de septiembre de 2024

Algoritmos codiciosos para sumas

 

Este tipo de algoritmo recibe muchos nombres distintos: voraz, goloso, devorador, codicioso, greedy,…Se basa en la estrategia de elegir en cada paso la solución óptima del problema, esperando que, al reiterar esta estrategia, se construya una solución óptima global. Para conseguirlo, no da marcha atrás en las decisiones si no se llega a un óptimo. Esto lo hace más rápido, pero más inseguro, porque no hay garantía de consecución de objetivos.

Ha de ser posible la elección óptima en cada paso, como en el caso de descomposición en suma de factoriales, que siempre se puede conocer el mayor factorial menor o igual que el número dado

Aquí estudiaremos varios ejemplos de descomposición de un número entero positivo en sumandos de un cierto tipo. Un ejemplo claro es el de encontrar una suma de factoriales cuyo resultado sea un número dado. Este algoritmo lo llevamos usando años en nuestras publicaciones, porque es rápido, aunque en ocasiones produce soluciones con un número alto de sumandos.

Lo vemos con un ejemplo elegido al azar, el número 1329, al que queremos convertir en una suma de factoriales lo menos extensa posible.

Es claro que si no deseamos muchos sumandos, vayamos eligiendo los factoriales mayores posibles para construir la suma. Podríamos efectuarlo así:

1329-720=609
609-120=489
489-120=369
369-120=249
249-120=129
129-120=9
9-6=3
3-2=1
1-1=0

Con ello, hemos descompuesto 1329 en suma de factoriales:

1329=720+120+120+120+120+120+6+2+1

Basta analizar la solución para darnos cuenta de que no podemos esperar demasiado de este algoritmo, pero al contar con el 1 entre los factoriales, siempre dará solución.

Un caso similar es el de descomponer una fracción en fracciones egipcias (del tipo 1/p). Bastará ir buscando en el numerador el mayor divisor posible del denominador (suponemos fracción irreducible). Por ejemplo, la fracción 17/24 se puede descomponer de esta forma, eligiendo en el numerador sucesivamente los mayores divisores de 24:

17/24=(12+4+1)/24=1/2+1/6+1/24

Los dos ejemplos los hemos desarrollado de forma manual, pero es claro que se podrá automatizar fácilmente.

Para planificar los algoritmos, distinguiremos dos variantes:

La primera requerirá que los sumandos pertenezcan a un mismo tipo, como los factoriales de más arriba, o, por ejemplo el problema de descomponer un número en sumandos triangulares.

La segunda, muy parecida a la primera, deberá elegir los sumandos dentro de una lista, como en el problema de las monedas, en el que una cantidad hay que traducirla a un conjunto de monedas con distintos valores.

En realidad, el ejemplo de los factoriales se puede considerar de este segundo tipo, por su escasez.

Sumandos del mismo tipo

Si el sumando óptimo lo debemos elegir dentro de un tipo, como primos, cuadrados o pentagonales, podremos usar un sencillo algoritmo que el autor usa con frecuencia. Tendría esta estructura, en la que, para un número n y un tipo dado, devuelve la suma más adecuada que un algoritmo codicioso puede dar.

Function codicioso$(n)
Dim c$
Dim i, r, s,suma
Dim vale As Boolean

suma = 0 'Irá sumando progresivamente
i = n ‘Recorrerá los posibles sumandos
r = n ‘Posible sumando válido
c = "" ’Recogerá soluciones
While i > 0 ‘Recorremos de mayor a menor, para optimizar
vale = False ‘Aún no hay solución
if CONDICION then vale=true ‘La CONDICIÓN dependerá del tipo de sumandos
If vale Then
c$ = c$ + Str$(i) + "  "
suma=suma+i
‘Si existe solución, se resta y se incorpora a la suma
r = r - i: i = r
Else
‘Si no existe solución, se sigue buscando el óptimo, descendiendo
i = i – 1
end if
Wend
If suma=n then codicioso = c else codicioso=”NO”
End Function

Por ejemplo, si la condición es la de ser primo, usaríamos la función ESPRIMO, fácilmente localizable en nuestro blog. En la tabla siguiente se recogen las sumas en números primos, si es que son posibles, para los primeros números de tres cifras:

Este ejemplo es muy interesante, porque ilustra las limitaciones de los algoritmos codiciosos. En primer lugar, sólo figuran los números en los que, al finalizar el algoritmo, la suma coincide con ellos, sin dejar ningún residuo no primo. Por ejemplo, el 15 daría como resultado 7+7, y sobraría 1, porque no es primo. En segundo lugar, al no explorar todas las posibilidades, ignora las sumas de Golbach para números pares, porque se detiene antes de llegar a los dos primos que predice la conjetura. Por ejemplo, el número 104, que no figura en la tabla, presenta varias descomposiciones en sumas de dos primos, y el algoritmo codicioso las ignora:

No obstante, en sumados de algunos tipos, el algoritmo funciona relativamente bien. Por ejemplo, cuando el 1 pertenece a ese tipo, como ocurriría en los cuadrados, triangulares, palindrómicos o de Fibonacci, la descomposición siempre será exitosa, aunque, quizás, algo larga. También suele funcionar bien con primos y cuadrados de primos, y con oblongos si el número es par. El siguiente ejemplo contiene resultados de cuadrados de primos entre 375 y 400:

En este caso están condicionados por el cuadrado de 19, 361. En general suelen aparecer los ejemplos con una cierta rapidez.

Un ejemplo clásico, y que publicamos a veces, es el de la representación de Zeckendorf, en la que todo número es suma de elementos de la sucesión de Fibonacci (ver, por ejemplo, nuestra entrada

https://hojaynumeros.blogspot.com/2020/09/representacion-de-zeckendorf.html).

En ella el algoritmo indicado es el codicioso. Hemos aplicado la función que presentamos más arriba a un conjunto de números consecutivos, y observamos que todos están representados así:

Puedes decubrir aspectos muy interesantes sobre esta descomposición en

https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem

Sumandos dentro de una lista

Este otro tipo de descomposición en sumandos que se adapta bien a los algoritmos codiciosos, es el de expresar un número como suma de números ya fijados en una lista. De este tipo es el problema de las monedas, en el que hay que encontrar la forma de pagar una cantidad si se dispone de un número suficiente de monedas de varias clases.

En este blog hemos tratado este tema y otros similares, como el de los números McNugget y la representación de un número respecto a una lista:

https://hojaynumeros.blogspot.com/2010/02/frobenius-y-los-mcnuggets.html

https://hojaynumeros.blogspot.com/2012/11/descomposicion-de-un-numero-segun-una.html

Por ejemplo, si nos piden representar el número 80 mediante los números de la lista 2, 4, 14, 32, procederíamos como en los problemas anteriores, restando de 80 el número mayor posible cada vez, y usando repeticiones:

48=80-32; 16=38-32; 16=14+2

Luego 80=32+32+14+2

No hemos necesitado el sumando 4.

El procedimiento usado para sumandos del mismo tipo es válido aquí, pero deberemos iniciar el algoritmo declarando los elementos de la lista según un vector.

Algo similar usa las herramientas que ofrecemos en hojamat.es:

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

http://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#mcnugget

Aquí seguiremos usando una función como en el primer caso, pero declarando los sumandos. Los introduciremos como componentes de un vector. Por ejemplo, en el siguiente listado se pretende encontrar qué monedas y billetes de euro podemos usar en una compra ordinaria, sin céntimos, y con un tope del billete de 50€:

Function codicioso3$(n)
Dim c$
Dim i, j, r, s, suma, tope
Dim v(20) ‘Usamos un vector de 20 componentes
v(1) = 1: v(2) = 2: v(3) = 5: v(4) = 10: v(5) = 20: v(6) = 50
tope = 6 ‘Determinamos seis monedas y billetes

‘El resto del listado es muy similar al del anterior tipo

suma = 0 'Irá sumando progresivamente
i = n 'Recorrerá los posibles sumandos
r = n 'Posible sumando válido
c = "" 'Recogerá soluciones
j = tope
While i > 0 And j > 0 'Recorremos de mayor a menor, para optimizar
If i >= v(j) Then
c$ = c$ + Str$(v(j)) + "  "’Aquí sumamos componentes del vector
suma = suma + v(j)
i = i - v(j)
Else

'Si no existe solución, se sigue buscando el óptimo, descendiendo

j = j - 1
End If
Wend
If suma = n Then codicioso3 = c Else codicioso3 = "NO"
End Function

Como ejemplo, insertamos una tabla con algunas cantidades en euros y su descomposición en monedas y billetes:

Hay que volver a advertir que estas soluciones no han de ser ni únicas ni óptimas.

miércoles, 4 de septiembre de 2024

Diferencias de cubos enteros positivos

Algunos números enteros positivos son diferencia de dos cubos, también enteros y positivos. Por ejemplo, 3367 lo es de tres formas diferentes: 3367=343-333=163-93=153-23. Otros números, como 8624, no coinciden con ninguna diferencia de  cubos. En esta entrada aprenderemos a descubrir ejemplos y estudiar algunos casos especiales.

Cuando se trata con diferencias, el estudio previo que se debe emprender es el de encontrar una cota para los números que se restan. En este caso, además de ello, podremos añadir una condición que deban cumplir minuendo y sustraendo. Es un tema algebraico sencillo en este caso. Llamemos a+k a la base del cubo mayor y a a la del menor, siendo además N el valor de la diferencia entre ambos cubos. Tendremos entonces:

(a+k)3- a3 = 3a2k+3ak2+k3 = k(3a2+3ak+k2) = N

Esta igualdad nos indica que N ha de ser múltiplo de k. Esto nos da una cota para la diferencia entre bases, junto con la condición de que sea un divisor de N. Por otra parte, no es difícil acotar las bases de los cubos:

3a2+3ak+k2 = N/k

3a2 < 3a(a+k) = N/k-k2 < N/k

De aquí deducimos que una cota de a es la raíz cuadrada de N/(3k)

Si recorremos los valores de los divisores de N, obtendremos valores posibles de k, y con esta cota podremos encontrar valores de a para comprobar si (a+k)3- a3 = N

Estas condiciones se usan en la siguiente función de VBasic, que nos devolverá las descomposiciones en diferencia de cubos que presente un número N:

Function difcubos$(n)

Dim k, a, t, m
Dim s$

s = "" ‘Contenedor de soluciones
m = 0 ’Número de soluciones
For k = 1 To n / 2
If n / k = n \ k Then k ha de ser divisor de N
t = Sqr(n / k / 3) ‘Cota para a
For a = 1 To t

If (a + k) ^ 3 - a ^ 3 = n Then m = m + 1: s = s + "a=" + Str$(a) + " k=" + Str$(a + k) ‘Si es una solución, se incorpora
Next a
End If
Next k
If s = "" Then difcubos = "NO" Else difcubos = ajusta(m) + " " + s ‘Si no hay solución devuelve un NO
End Function

Con esta función encontraremos los números enteros que son diferencia de cubos, con el dato del número de soluciones que presenten. Por ejemplo, en la siguiente tabla figuran los resultados desde 720 hasta 730:


Observamos que sólo dos números cumplen la condición, y, en este caso, con dos soluciones cada uno. Las diferencias son divisores de N. En el caso de 721, son 1 y 7, y, en el caso de 728, 2 y 8, divisores en ambos números.

Una idea nos viene al momento, y es que si N es primo, la única diferencia posible es 1:

Si un número primo es diferencia de dos cubos, ambos han de ser consecutivos.

Lo comprobamos con la función anterior añadiendo la condición de ser primo:


Se trata de los “primos cubanos”, que son objeto de estudio en otra entrada en nuestro blog

(ver https://hojaynumeros.blogspot.com/2024/03/primos-cubanos.html

Están publicados también en https://oeis.org/A002407

Los primeros números que son diferencia de cubos de una, dos o tres formas son estos:

7, 19, 26, 37, 56, 61, 63, 91, 98, 117, 124, 127, 152, 169, 189, 208, 215, 217, 218, 271, 279, 296, 316, 331, 335, 342, 386, 387, 397, 448, 469, 485, 488, 504, 511, 513, 547, 602, 604,

Están publicados en https://oeis.org/A038593, y parece ser que serán muy raros los que presenten más de tres soluciones. Como en nuestra función el primer carácter representa el número de soluciones, no es difícil separar esta tabla según este dato.

Una sola solución:

https://oeis.org/A014439

Dos diferencias de cubos:


https://oeis.org/A014440

Tres diferencias:

Observamos que van disminuyendo los casos.

Ver https://oeis.org/A014441

Segunda versión de búsqueda

En la función propuesta hemos usado un bucle de búsqueda para k y otro para a. Este último se puede evitar despejando a en 3a2+3ak+k2-N/k. Así lo hemos efectuado en PARI, y se consigue más velocidad de proceso, pero para números con tres soluciones sigue siendo lento. Lo copiamos aquí por si alguien desea experimentar:

difcubos(n)={my(m=0,k,a,q);for(k=1,n/2,if(n%k==0,q=9*k^2-12*(k^2-n/k);if(issquare(q),a=(-3*k+sqrt(q))/6;if(a==truncate(a)&&a>0,m+=1))));m}

for(i=1,10^6,if(difcubos(i)==3,print(i)))

Se exige en él que a sea entera y positiva. Cambiando el 3 de la última línea se puede intentar buscar números con cuatro soluciones, si se dispone de un equipo potente.

Casos particulares en la diferencia

En nuestras publicaciones en Twitter o X nos aparecen casos en los que un cuadrado y un cubo están relacionados por una identidad. En este apartado comenzaremos por estudiar el caso en el que una diferencia de cubos es cuadrada. Para ello cambiaremos un poco nuestra función básica, en el sentido de exigir al principio que N sea un cuadrado. El resultado, ya conocido, es


La segunda columna está publicada en
https://oeis.org/A038597

Hay un caso interesante en la tabla, y es 14^3-7^3=7^4, y esto nos anima a buscar otras diferencias entre cubos que sean potencia de cualquier exponente. Para ello disponemos de la función en Excel ESPOTENCIA, que devuelve el exponente mínimo de una potencia, o cero si no es de ese tipo. Con ella encontramos diferencias que son cuartas potencias:


Con esta búsqueda hemos descubierto una propiedad interesante: si N es diferencia entre dos cubos, su cuarta potencia también lo es:


La razón es sencilla: Si en una diferencia de cubos con resultado N multiplicamos ambos cubos por N
3, resultará otra diferencia de cubos con resultado N4. Ocurrirá igual con N7 o N10.

Podemos observar que los datos de la cuarta columna coinciden con los de la segunda multiplicados por N.

Otros tipos de diferencias de cubos

Esta última parte del estudio la desarrollaremos con brevedad salvo que surja alguna propiedad interesante.

Diferencias que son números primos

Ya advertimos que, en este caso, las bases de los cubos han de ser consecutivas y los primos son los llamados “cubanos”:


Diferencias de cubos triangulares

Los primeros son estos:


No descubrimos particularidades, luego pasamos a otro caso.

Diferencia de cubos igual a suma de cubos

Aprovechando una pequeña función disponible, SUMCUBOS, se puede exigir que la diferencia de cubos coincida con la suma de otros dos. Los primeros resultados son:

Están publicados en https://oeis.org/A225908

Como se señala en esta página, estos datos dan lugar a identidades en las que un cubo es suma de otros tres, pues basta pasar de miembro el cubo que aparece restando:

6^3-4^3=3^3+5^3 da lugar a 6^3=3^3+4^3+5^3.

Esto explica que en la segunda columna aparezcan repetidos tres veces algunos cubos mayores de cada caso, como el 6, el 9 o el 12, ya que la suma da lugar a tres diferencias.