jueves, 22 de febrero de 2024

Números generados por sumas alternas

El contenido de esta entrada no tendrá valor teórico destacable. Su objetivo es analizar el procedimiento para encontrar sumas de números alternados que generen uno dado N. Por alternados entenderemos consecutivos de cierto tipo en los que se suprime uno de cada dos. También podríamos afirmar que “se salta” un elemento y se elige el siguiente.

Por ejemplo, 84=1+9+25+49, y esa suma es alternada de cuadrados, porque hemos elegido una suma de consecutivos y le hemos ido suprimiendo un término de cada dos. Los representamos entre paréntesis:

84=1+(4)+9+(16)+25+(36)+49

Otro ejemplo es el publicado en https://oeis.org/A300395, que contiene todos los números que se forman con una suma de nueve primos alternados. Por ejemplo:

521 = 23+31+41+47+59+67+73+83+97

En este conjunto se han ido suprimiendo los primos 29, 37, 43, 53,…

Queda claro, pues, lo que entenderemos por alternados.

Un número N puede ser equivalente a varias sumas de este tipo. Por eso, los algoritmos que busquen dichas sumas necesitarán dos bucles, pues primero hay que analizar el inicio de la suma y luego su longitud. Para cada inicio existirán varias posibles sumas, lo que exige los dos bucles. En este blog hemos usado la función PROXIMO en la entrada “En el punto medio de dispares” (https://hojaynumeros.blogspot.com/2023/06/en-el-punto-medio-de-dispares.html) para ir encontrando sumandos del tipo dado si conocemos el primero.

El siguiente listado es el usado para encontrar el próximo primo, ya que usa la función ESPRIMO, pero se adapta fácilmente al la búsqueda de otros tipos de números, usando las funciones ESTRIANGULAR, ESCUBO, ESOBLONGO,…todas usadas en este blog y accesibles con el comando Buscar.

Function proximo(a) As Long

Dim p, prim As Long
Dim sale As Boolean

p = a + 1: sale = False: prim = 0
While Not sale ‘Reitera hasta que aparezca el próximo
If escuad(p) Then prim = p: sale = True
p = p + 1
Wend
proximo = prim
End Function

La función PROXIMO puede resultar lenta, por lo que si buscamos una suma alternada para un número N, es muy conveniente guardar en un vector todos los números comprendidos entre 1 y N y que sean del tipo dado. También tiene el peligro de no parar nunca, pero en los casos habituales esto no sucede.

Estructura de un algoritmo

Según las consideraciones anteriores, para encontrar las sumas deseadas deberemos recorrer tres etapas:

1) Hay que encontrar todos los posibles sumandos del tipo dado entre 1 y N. Lo explicamos con un ejemplo, el de encontrar una suma de triangulares consecutivos alternados cuyo resultado sea 200.

En primer lugar, usando la función PROXIMO, creamos un vector que contenga todos los triangulares comprendidos entre 1 y 200. Si llamamos s al vector, tendríamos que s(1)=1, s(2)=3, s(3)=6, …s(18)=171 y s(19)=190. Tomamos nota de que existen 19 triangulares que pueden ser sumandos.

El uso de un vector nos facilita el “saltar” un elemento, pues se pasará de s(k) a s(k+2) en cada paso.

2) Se establece un bucle de búsqueda del primer sumando, que comenzará en el 1 y se avanzará hasta 190. En el ejemplo tendríamos que llegar, como veremos, hasta un inicio de 10.

3) Para cada posible inicio de la suma se construirá un segundo bucle que vaya añadiendo un sumando alternado en cada paso. Para ello se irá incrementado el índice en dos unidades cada vez. Si en uno de ellos se alcanza el resultado de N, se habrá conseguido el objetivo. Para el número 200 la solución sería

10+21+36+55+78=200. Habríamos saltado los triangulares 15, 28, 45, y 66.

Estas fases se pueden implementar en una subrutina para VBasic con objeto de usarla en Excel o Calc.

Rutina en VBasic

El listado que sigue ha sido diseñado para Excel, pero con un pequeño cambio se adapta a LibreOffice Calc.

fila = 14 ‘O cualquier otro valor
‘Se lee el valor de N y el tipo de sumando
n = ActiveWorkbook.Sheets(1).Cells(9, 4).Value
tipo = ActiveWorkbook.Sheets(1).Cells(29, 8).Value

‘Con el uso de la función PROXIMO se carga un vector con candidatos a sumandos, para acelerar el proceso

i = 0
k = 0
While a <= n
a = proximo(a, tipo)
If a <= n Then i = i + 1: s(i) = a: k = i
Wend

‘Se ha construido el vector s

For i = 1 To k ‘Bucle para elegir el inicio de la suma
j = i
a = s(i)
suma = a
st$ = Str$(a)
While suma <= n And j <= k – 2 ‘Bucle para construir una suma
j = j + 2 ‘Es importante añadir un 2, para alternar
a = s(j)

suma = suma + a ‘Se construye la suma
st$ = st$ + ", " + Str$(a) ‘Modo texto para la suma
If suma = n Then
st = st + " # " + Str$((j - i) / 2 + 1)

‘Se presenta la solución en modo texto

ActiveWorkbook.Sheets(1).Cells(fila, 10).Value = st$
ActiveWorkbook.Sheets(1).Cells(fila, 12).Value = rotulo(tipo)
End If
Wend
Next i
End Sub

En la imagen vemos la forma en la que aparecería la solución en Excel:

Se leerían los sumandos, el número de ellos, 5 en este caso, y el tipo, “Triangulares”. Lo del este último rótulo no lo hemos explicado aquí.

Este algoritmo se podría haber construido como una función, pero esta vez hemos optado por una rutina, pues usamos una similar en una de nuestras herramientas.

Uno de los últimos usos, por si deseas reproducirlo, es comprobar que el número 5623 equivale a la suma de nueve números primos alternados y que, por tanto, pertenece a la sucesión https://oeis.org/A300395

5623=577+593+601+613+619+641+647+659+673

Si se dispone de varios tipos de números (en mis trabajos uso 17), se podría construir una gran rutina que recorriera varios tipos para buscar sumas. En la siguiente imagen lo hemos aplicado al número 200 con un resultado sorprendente por el número de soluciones:


Entre ellos figura el que hemos usado de ejemplo con triangulares.

Con esta idea finalizamos la entrada, ya que el objetivo era diseñar y explicar un algoritmo.

martes, 13 de febrero de 2024

Divisores y sumas palindrómicas

El día 4/03/2023 publiqué en Twitter (@connumeros) que los divisores propios del número 4323 son todos palindrómicos (consideramos de este tipo también los de una cifra):

1441 393 131 33 11 3 1

Estudiando este hecho llegué a una sucesión de mi amigo Claudio Meller en la que figuran aquellos números cuya suma de divisores propios coincide con la de sus simétricos o reversos  https://oeis.org/A163122).

A primera vista parecía que coincidirían los términos, pero mi sentido matemático lo negaba, y, en efecto, la sucesión de Claudio contiene términos, como el 840, cuyos divisores no son todos capicúas (o palindrómicos).

En ambos casos es evidente que solo tratamos con números compuestos. La búsqueda de estos números no es difícil. Basta recorrer sus divisores propios y abandonar el proceso si aparece un divisor no capicúa. Puede ser así:

 Function esdivcapi(n) As Boolean

Dim i
Dim es As Boolean
If esprimo(n) Then esdivcapi = False: Exit Function ‘No puede ser primo
es = True ‘Suponemos que es cierta la hipótesis
i = 2 ‘Primer divisor
While i <= n / 2 And es
If n / i = n \ i And Not escapicua(i) Then es = False ‘Si un divisor no es capicúa, cortamos el proceso
i = i + 1 ‘Siguiente posible divisor
Wend
esdivcapi = es
End Function

Resultado:

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 21, 22, 25, 27, 33, 35, 44, 49, 55, 66, 77, 88, 99, 121, 202, 242, 262, 302, 303, 362, 363, 382, 393, 404, 453, 484, 505, 524, 543, 573, 605, 606, 626, 655, 706, 707, 726, 746, 755, 766, 786, 808, 847, 905, 909, 917, 939, 955, 968,…

 

Por ejemplo, los divisores propios de 524 son 262 131 4 2 1, todos palindrómicos.

 

Es fácil, pero algo oscura, la traducción de esta función a PARI. Hemos usado esta, que da los mismos resultados de forma casi instantánea:

 

is(n)=my(i=1,v=divisors(n),a=#v);if(a>2,for(i=1,a-1,if(!(digits(v[i])==Vecrev(digits(v[i]))),return(0))),return(0));1

for(i=4,1000,if(is(i),print1(i,", ")))

 

Este es el resultado en la página oficial de PARI



Puedes comprobar este otro código por si te sirve de aprendizaje del lenguaje:

 

is(n)=my(s);if(!isprime(n)&&n>1,s=sumdiv(n,d,digits(d)==Vecrev(digits(d))&&d<n),return(0));s+1==#divisors(n)

for(i=1,1000,if(is(i),print1(i,", ")))

 

Soluciones palindrómicas

 

En la lista de resultados se observan capicúas, como 303 o 484. El proceso de encontrarlos se hace más sencillo. Bastará llegar en el primer código hasta a en lugar de a-1. Seguiremos tratando con compuestos, pues el caso de primos nos llevaría a los “palprimos”, que ya hemos estudiado en otra ocasión

(https://hojaynumeros.blogspot.com/2016/05/palprimos-primos-palindromicos.html)

 

La previsible nueva lista es

 

4, 6, 8, 9, 22, 33, 44, 55, 66, 77, 88, 99, 121, 202, 242, 262, 303, 363, 393, 404, 484, 505, 606, 626, 707, 808, 909, 939, 1111, 1331, 1441, 1661, 1991, 2222, 2662, 2882, 3333, 3443, 3883, 3993, 4444, 5555, 6666, 6886, 7777, 7997, 8888, 9999,…

 

La podemos crear con este código PARI:

is(n)=my(i,v=divisors(n),a=#v);if(a>2,for(i=1,a,if(!(digits(v[i])==Vecrev(digits(v[i]))),return(0))),return(0));1
for(i=4,10000,if(is(i),print1(i,", ")))

 


En nuestro caso, la hemos comprobado en hoja de cálculo añadiendo la condición de que N sea palindrómico.

 

Sucesión de Claudio Meller

 

Al haber acudido a esta sucesión, bueno será adjuntar el modo de construirla con nuestros métodos habituales.

 

Function igualsumconrever(n) As Boolean

Dim i, s1, s2

 

If esprimo(n) Or n = 1 Then igualsumconrever = False: Exit Function

s1 = 0: s2 = 0

For i = 2 To n / 2

If n / i = n \ i Then

s1 = s1 + i: s2 = s2 + cifrainver(i)

End If

Next i

If s1 = s2 Then igualsumconrever = True Else igualsumconrever = False

End Function

 

Resultado

 

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 21, 22, 25, 27, 33, 35, 44, 49, 55, 66, 77, 88, 99, 121, 202, 242, 262, 302, 303, 362, 363, 382, 393, 403, 404, 453, 484, 505, 524, 543, 573, 605, 606, 626, 655, 689, 706, 707, 726, 746, 755, 766, 783, 786, 808, 840, 847, 905, 909, 917, 920, 939, 955, 968, 989,…( https://oeis.org/A163122)

         

 

Con PARI

 

is(n)=my(i=1,v=divisors(n),a=#v,s1=0,s2=0);if(!isprime(n),for(i=1,a-1,s1=s1+v[i];s2=s2+eval(concat(Vecrev(Str(v[i]))))));s1==s2&&s1>0

for(i=2,1000,if(is(i),print1(i,", ")))

 

 

Resultado

 



 Suma palindrómica

Por último, a la condición de que todos los divisores propios sean palindrómicos, podríamos añadir que su suma (las partes alícuotas) también lo sea. Hemos usado  en hoja de cálculo esdivcapi junto con escapicua(sigma(i)-i), con este resultado:


Llama la atención la ausencia de números de tres o cuatro cifras.


viernes, 2 de febrero de 2024

Sumas de términos en progresión

En esta entrada nos preguntaremos, dado un número natural N, qué progresiones aritméticas de números, también naturales, tienen como suma el número dado N.

Esta cuestión maneja tres variables distintas, como son el término inicial de la progresión, a1, el número de términos k, y la diferencia de la progresión, sea d. Para una gestión cómoda del problema, es conveniente fijar una de ellas y dejar como variables las otras dos. Su relación algebraica es sencilla, si se recuerdan las fórmulas de las progresiones aritméticas:

Término general:

Suma de la progresión


Si combinamos las dos fórmulas, y  llamamos N a la suma (que es nuestro objetivo), obtendremos, después de simplificar:

Multiplicando por 2:

Esta es nuestra igualdad básica, que nos informa de algo fundamental, y es que el número de términos k ha de ser divisor de 2N.

Por otra parte, el máximo valor de k sería el resultante de sumar una progresión aritmética formada por los primeros números naturales (d=1). Cualquier otra progresión requiere menos sumandos. Esa suma de los primeros naturales constituye un número triangular, luego la cota de k se desprendería de la desigualdad

En otras entradas de este blog hemos despejado el equivalente a k respecto a N, y nos ha resultado, después de manipulaciones algebraicas:

En lenguaje de VBASIC y similares, k<=Int((Sqr(8 * n + 1) - 1) / 2)

Además de ser divisor de 2N y presentar esta acotación, al despejar a1 o d en la fórmula básica, deberá resultar un entero positivo. Según planteemos la búsqueda, exigiremos que uno u otro sean de ese tipo.

Por otra parte, si llamamos q al cociente (que será entero) 2N/k, es fácil ver que la diferencia d tiene como cota q/(k-1) (que sería cuando  a1=0).

Por ejemplo, la siguiente función depende de N y k, y en ella exigimos que a1 sea entero positivo:

Function sumaprogre$(n, k) ‘Es un texto, para abarcar todas las soluciones

Dim a, d, b, c, q
Dim s$

s$ = "" ‘Contenedor para el texto
q = 2 * n / k ‘Cociente para ver si k es divisor de 2N
If q = Int(q) Then ‘Es divisor
For d = 2 To q / (k - 1) ‘Usa la cota q/(k-1) para d
a = (q - d * (k - 1)) / 2 ‘Cálculo de a1
If a > 0 And a = Int(a) Then ‘Si a1 es entero positivo, seguimos
b = a + d * (k - 1) ‘Último término
s = s + " ## a(1)=" + Str$(a) + " a(k)=" + Str$(b) + " d=" + Str$(d)
‘Se presenta el resultado como texto, con inicio, fin y diferencia
End If
Next d
End If
If s = "" Then s = "NO" ‘No hay solución
sumaprogre = s
End Function

Por ejemplo, el número 142 es igual a 2*71, con lo que los divisores de 284 (2N) son  284, 142, 71, 4, 2, 1, y constituyen los valores posibles de k. Si probamos k=71, la función nos devuelve un “NO”, porque no existen sumas con k=71. Por el contrario, si elegimos k=4, nos resulta un número excesivo de soluciones:

Sumaprogre(142;4)= ## a(1)= 31 a(k)= 40 d= 3 ## a(1)= 28 a(k)= 43 d= 5 ## a(1)= 25 a(k)= 46 d= 7 ## a(1)= 22 a(k)= 49 d= 9 ## a(1)= 19 a(k)= 52 d= 11 ## a(1)= 16 a(k)= 55 d= 13 ## a(1)= 13 a(k)= 58 d= 15 ## a(1)= 10 a(k)= 61 d= 17 ## a(1)= 7 a(k)= 64 d= 19 ## a(1)= 4 a(k)= 67 d= 21 ## a(1)= 1 a(k)= 70 d= 23

Observamos que varían entre d=3: 31+34+37+40=142 hasta d=23, 1+24+47+70=142.

Los valores posibles de las diferencias cumplen la acotación 2N/k/(k-1), que en este caso sería 284/4/3=23,666…

Llama la atención que probando varios números, suelen aparecer muchas soluciones, o ninguna. En algunos casos, la solución es única. Por ejemplo, el número 2024 sólo admite una solución con 44 sumandos:

Sumaprogre(2024;44)= ## a(1)= 3 a(k)= 89 d= 2

Es una suma de impares desde 3 hasta 89. Con otra herramienta, usando diferencias de cuadrados,  se llega al mismo resultado:

Aquí se ha expresado 2024 como 452-12, de donde resulta la misma suma de impares.

Estudio para un número dado

La anterior función se puede aplicar a todos los divisores de un número, con lo que obtendríamos un panorama general de todas las posibilidades que tiene de ser suma de una progresión aritmética. El problema es de visualización, pues, tal como comentamos anteriormente, pueden obtenerse muchas soluciones, con lo que se perdería la visión de conjunto. En el siguiente recorte (incompleto) podemos observar los resultados para 2024:


La primera columna indica el número de sumandos, y la segunda, en forma de texto, todas las posibilidades, descritas mediante a(1), a(k) y d.

Uso de la diferencia como parámetro

Podemos estar interesados en cuántas sumas, con una diferencia dada, se pueden encontrar para N. Por ejemplo, en el recorte anterior del caso del 2024, se descubren varios ejemplos con d=4.

La siguiente función, muy similar a la anterior, nos devuelve todas las sumas con una diferencia dada. No se añaden comentarios porque la metodología es la misma.

Function sumaprogre2$(n, d)

Dim a, k, b, c, q, l
Dim s$

s$ = ""
l = Int((Sqr(8 * n + 1) - 1) / 2)
For k = 2 To l
q = 2 * n / k
If q = Int(q) Then
a = (q - d * (k - 1)) / 2
b = a + d * (k - 1)
If a > 0 And a = Int(a) Then s = s + " ## a(1)=" + Str$(a) + " a(k)=" + Str$(b) + " k=" + Str$(k)
End If
Next k
If s = "" Then s = "NO"
sumaprogre2 = s
End Function

Aplicada al año 2024 y a la diferencia d=4 nos ha devuelto estas soluciones, que coinciden con las del esquema general:

## a(1)= 1010 a(k)= 1014 k= 2 ## a(1)= 500 a(k)= 512 k= 4 ## a(1)= 239 a(k)= 267 k= 8 ## a(1)= 164 a(k)= 204 k= 11 ## a(1)= 50 a(k)= 134 k= 22 ## a(1)= 44 a(k)= 132 k= 23

En ellas se nos ofrecen el primer término a(1), el último a(k) y el número de sumandos k.

Por ejemplo, a(1)= 164 a(k)= 204 k= 11 se refiere a esta suma con 11 sumandos que se diferencian en 4 unidades:

2024=164+168+172+176+180+184+188+192+196+200+204

Podríamos repetir las búsquedas fijando un valor para a1, pero no parece resultar interesante.