Derivada aritmética

Este original concepto fue presentado por el matemático español José Mingot Shelly en 1911 con el título "Una cuestión de la teoría de los números", trabajo presentado en el Tercer Congreso Nacional para el Progreso de las Ciencias, Granada. Es interesante su biografía, condicionada totalmente por la Guerra Civil española.

Como su nombre indica, esta derivada se basa en una operación similar a la de la derivada de un producto, y aplicada a números naturales. Podemos concretarla de esta forma:

D(0)=D(1)=0 (para completar la definición)
D(p)=1 si p es primo
D(ab)=aD(b)+bD(a) a>1, b>1 (Regla del producto)

Por ejemplo, D(10)=D(2*5)=2D(5)+5D(2)=2*1+5*1=7

Como la definición formal es similar a la de la derivada de una función, podemos extenderla a más factores, a potencias y a todos los números en general.

Así, en un número esfénico N=p*q*r, se tendrá D(N)=p*q+q*r+r*p.

Por ejemplo, D(30)=D(2*3*5)=2*3+3*5+5*2=31

Se generaliza fácilmente a las potencias de primos: D(p^k)=k*p^k-1

D(8)=D(2³)=3*2²=12
D(16)=D(2⁴)=4*2³=32

Veremos que nos conviene expresar la potencia de otra forma:

D(N)=D(p^k)=N*k/p

Caso general

Cualquier número se descompone en productos de potencias de primos. Con lo visto hasta ahora, se puede construir una forma de calcular la derivada aritmética en el caso general. Deberemos ir derivando cada potencia para multiplicarla por el resto de potencias de primos. Según el apartado anterior, cada potencia quedará multiplicada por su exponente y dividida entre su base. Extendemos a todas las potencias y queda:

Lo vemos mejor con un ejemplo:

D(360)=D(2³*3²*5)=360(3/2+2/3+1/5)=852

Estos resultados se pueden comprobar en https://oeis.org/A003415

Es fácil traducir todo esto a una función. En su primera parte es copia de nuestra rutina sacaprimos. Su salida es el conjunto de primos p() y el conjunto de exponentes ex(). A partir de ellos se construye la derivada.

Function derivada(n)
Dim f, a, e, nume, d, s
Dim p(20), ex(20)

‘Extrae primos y sus exponentes

a = n
f = 2
While f * f <= a
e = 0
While a / f = Int(a / f)
e = e + 1
a = a / f
Wend
If e > 0 Then
nume = nume + 1
p(nume) = f
ex(nume) = e
End If
If f = 2 Then f = 3 Else f = f + 2
Wend
If a > 1 Then
nume = nume + 1
p(nume) = a
ex(nume) = 1
End If

‘Fin de la extracción de primos

 s = 0 ‘Factor que multiplica a n
For f = 1 To nume
s = s + n*ex(f) / p(f) ‘Se suman los cocientes n*e/p
Next f
derivada = s
End Function

Hemos dimensionado los primos a 20 distintos, pues la gran mayoría de los números que tratamos tienen menos primos en su descomposición factorial. La misma idea usa la programación en PARI en la página enlazada. Aquí se puede comprobar la diferente potencia entre PARI y VBASIC:

(PARI) A003415(n) = {local(fac); if(n<1, 0, fac=factor(n); sum(i=1, matsize(fac)[1], n*fac[i, 2]/fac[i, 1]))} /* Michael B. Porter, Nov 25 2009 */

Dejamos su análisis como ejercicio lúdico.

Con cualquiera de estas dos herramientas podemos construir una tabla de derivadas aritméticas:

Observamos que todos los números primos tienen derivada 1 por definición, y las potencias de primos siguen la suya propia, como D(8)=D(2³)=3*2²=12

Naturaleza de la derivada aritmética

Siguiendo una costumbre en este blog, destacaremos algunas derivadas aritméticas según su tipo como números, primos, cuadrados, triangulares,…Publicamos a continuación una muestra:

Derivadas primas

Si añadimos a la búsqueda la condición de que la derivada sea prima, obtenemos este listado:

En la primera columna figuran los valores de N, y en la segunda las derivadas primas. Si siguiéramos buscando, observaríamos que muchos valores, como 191, se repiten bastante. Hemos añadido una columna más para comprobar que N es libre de cuadrados. En la página https://oeis.org/A157037 figuran los valores de N, y en ella se razona el porqué de que N no contenga divisores cuadrados.

Derivadas cuadradas

Deberemos en este caso excluir los casos en los que N es primo, pues nos llenarían las tablas con el valor cuadrado 1. Así que buscaremos derivadas cuadradas sólo para valores compuestos de N. El resultado es:

También están publicadas, en concreto en https://oeis.org/A256706

Por ejemplo, D(291)=D(3*97)=1*97+3*1=100=10²

Derivadas triangulares

Si exigimos que la derivada sea un número triangular, se encuentran muchos ejemplos. Estos son los primeros:

Esta sucesión parece estar inédita. El autor del blog no la va a publicar, y autoriza aquí su publicación por parte de otra persona.

Derivada que es potencia no trivial

Entre los valores de las derivadas aritméticas figuran, además de los cuadrados, otras potencias con exponentes mayores. Estos son los primeros valores:

Por ejemplo, D(108)=D(2²*3³)=108(2/2+3/3)=216=6³

También está inédita, aparentemente

Derivada de N igual a N

En la tabla anterior figura que la derivada de 27 es también 27. Buscaremos a continuación si existen más casos similares:

Basta observar la tabla para comprobar cuándo ocurre esto, y qué demostración sencilla es posible. Lo dejamos abierto a nuestros lectores.

Derivada múltiplo del número

Hemos observado derivadas que son iguales o el doble que el número dado. También existen casos en los que es un múltiplo mayor. Estos son los primeros casos:

Según lo explicado hasta ahora, esto ocurre cuando la suma de los cocientes entre los exponentes de los factores primos y ellos mismos es un número entero. Nos fijamos, por ejemplo en el número 6912=2⁸*3³, en el que esa suma es 8/2+3/3=5, y esa es la causa de que su derivada sea un múltiplo con cociente 5.

Esto traslada la cuestión a saber qué números cumplen la propiedad. Es fácil ver que no sólo la suma de esos cocientes ha de ser entera, sino que han de serlo cada uno por separado, pues al ser primos los denominadores no se podrán agrupar en sumas enteras esos cocientes si ellos no lo son.

Divisor propio mayor que la raíz cuadrada

 

Explorando por OEIS, encontré un tipo de números en https://oeis.org/A332269 y me ha apetecido desarrollar el tema mediante nuestras funciones en hoja de cálculo.

La idea es que en muchos números naturales N, un solo divisor propio de N es mayor que su raíz cuadrada, siendo todos los demás menores. Al ser propio, se descarta N, por lo que ese divisor ha de cumplir Sqr(N)<d<N, siendo Sqr la función raíz. Su valor máximo posible será N/2.

Por ejemplo, el número 27 posee como divisores propios 1, 3 y 9, siendo 9 el único divisor propio de 27 que es mayor que la raíz cuadrada de 27=5,19. Con este ejemplo ya tenemos un resultado, y es que los cubos de los números primos presentan esta propiedad.

Su búsqueda con Vbasic de Excel y Calc es bastante sencilla. Se puede desarrollar con esta función:

Function undivisor(n)
Dim k, m, d As Long
Dim r

r = Sqr(n) ’Cálculo de la raíz cuadrada
m = 0 ‘Contador de divisores
k = Int(n / 2) ‘Máximo divisor propio posible
While k > r ‘Contamos divisores mayores que la raíz
If n / k = n \ k Then d = k: m = m + 1
k = k - 1
Wend
‘Si el contador marca m=1 es de ese tipo
If m = 1 Then undivisor = d Else undivisor = 0
End Function

Devuelve un cero si no presenta la propiedad, y el mayor divisor si se cumple. Los primeros números con ella son:

6, 8, 10, 14, 15, 16, 21, 22, 26, 27, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 81, 82, 85, 86, 87, 91, 93, 94, 95, 106, 111, 115, 118, 119, 122, 123, 125, 129, 133, 134, 141, 142, 143, 145, 146, 155, 158, 159, 161, 166, 177, 178, 183, 185, 187, 194

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

En esta tabla observamos el cumplimiento de la condición:

 

En la página enlazada figuran algunos tipos de números con la propiedad pedida:

Semiprimos libres de cuadrados: Si N=pq, con p y q primos y p<q, es lógico que q sea el divisor único pedido. En el listado figuran muchos, como el 14=2*7, y 7 es mayor que la raíz cuadrada de 14.

Cubos y cuartas potencias de primos: En ambos casos se cumple, y el divisor es p² en el primer caso y p³ en el segundo. Así, en 16 el mayor divisor, 8, es el único mayor que la raíz cuadrada de 16, que es 4.

Simplificación

En la referida página de OEIS se incluye un comentario que nos permite simplificar la búsqueda, y es que si Sqr(N)<d<N, y d es único, también lo será N/d, que será divisor, pero que ahora se cumplirá N/d<Sqr(N), lo que nos permite buscar el divisor único entre 2 y Sqr(N).

El desarrollo de la función sería similar al presentado:

Function undivisor2(n)
Dim k, m, d As Long
Dim r

r = Sqr(n)
m = 0
k = 2 ‘Ahora se comienza en el 2, hasta la raíz cuadrada
While k < r ‘El resto se desarrolla igual
If n / k = n \ k Then d = k: m = m + 1
k = k + 1
Wend
If m = 1 Then undivisor2 = d Else undivisor2 = 0
End Function

Como era de esperar, resultan los mismos números:

Profundización

El número de divisores propios mayores que la raíz cuadrada coincide con el de los divisores menores, como vimos más arriba, ya que si D divide a N, también lo divide N/D. Esto nos permite cambiar la condición impuesta por la de que x*y=N tenga una sola solución si x es distinto de y y ambos mayores que la unidad. En ese caso, si x es menor que la raíz cuadrada de N, la otra variable y presentará un valor mayor que ella, con lo que se cumple la condición.

Si analizamos el valor de TAU(N) (número de divisores de N) observaremos que el número de pares x, y es igual a TAU(N)/2 si N es libre de cuadrados, y si (N,1) es un par, sólo deberá existir otro par (D,N/D), por lo que si TAU(N) vale cuatro, como ocurre en  los semiprimos libres de cuadrados p*q, con divisores (1, p, q, pq) y en los cubos de primos (1, p, p², p³), algo que ya se afirmó más arriba.

Si TAU(N) es mayor que 4, sólo se encuentran como ejemplos válidos las potencias cuartas de los números primos.

Ejemplos consecutivos

En la tabla figuran términos consecutivos. En la página de OEIS enlazada figuran varios tipos de números que forman pares de consecutivos. Es una curiosidad digna de leerse.

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+n²+n³+n⁴+n⁵+…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+5².

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+k², como, por ejemplo, el 73, que equivale a 1+8+8².

El 31 presenta dos soluciones: 31=1+2+2²+2³+2⁴=1+5+5², 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=(2⁵-1)/(2-1)=(32-1)/1=31

También 31=(5³-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,…

 

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.

 

 

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.