Esta entrada constituye nuestra participación en la Edición4.1231056256 del Carnaval de Matemáticas.
Iniciamos ahora un repaso de sucesiones definidas mediante una recurrencia lineal de segundo orden
(ver definición y propiedades en una entrada anterior
http://hojaynumeros.blogspot.com.es/2014/01/recurrencias-lineales-de-segundo-orden.html
Es muy aconsejable su lectura previa a la de la actual. Si no, puede que no entiendas algunos comceptos).
Unas son muy populares, como la de Fibonacci, otras menos, y podrán constituir un descubrimiento y, por último, algunas serán inéditas o poco estudiadas. Cuando una requiera más estudio le dedicaremos una entrada completa. Hay que destacar que el estudio de una sucesión puede tener el aliciente añadido del repaso de cuestiones diversas que no tienen nada que ver con la recurrencia. Esto último es nuestro principal objetivo.
Sucesión de Jacobsthal
Probemos con algunos valores de los coeficientes y valores iniciales de la recurrencia de segundo orden. Imagina que hacemos A=1, B=2, X0=0, X1=1 (Horadam(0,1,2,1). Acudimos a nuestra herramienta en hoja de cálculo
(http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#recurre2)
y obtenemos:
Esta sucesión, llamada de Jacobsthal, la tienes en http://oeis.org/A001045
0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691,…
Si visitas la página indicada te abrumará la cantidad de propiedades e interpretaciones que presenta esta sucesión.
Con la resolución de la ecuación característica, e interpretándola correctamente, obtendrás la expresión del término general
Por ejemplo, el término décimo será (2^10-1)/3=1023/3=341, como puedes observar en la tabla. A partir de esta expresión es fácil entender que el cociente X(n+1)/X(n) tiende a 2 al crecer n.
En binario puedes representarte mejor esta relación. El numerador tendrá la expresión 10000….001 para n par y 111…111 para n impar (sería un repunit). Al dividir entre 3, las expresiones que resultan para los términos de la sucesión estarán formadas por unos alternados con ceros, salvo si acaso el primero. Por tanto, todos equivaldrán a sumas de potencias alternas de 2 terminando al final en 1. Por ejemplo, 85=26+24+22+1.
Puedes sumar mentalmente en binario dos términos consecutivos y observarás que te van saliendo ceros hasta llegar a un último 1 a la izquierda. Más claro:
La suma de dos términos consecutivos X(n)+X(n+1) equivale a 2n
Basta estudiar un poco esta expresión para darnos cuenta de que cada término se aproxima al doble del anterior, una vez por la izquierda y la siguiente por la derecha, acercándose al límite del doble exacto. Lo puedes comprobar en esta tabla de cocientes:
Podemos concretar más:
Cada término se diferencia en una unidad con el doble del anterior.
X(n+1)=2X(n)+(-1)n
En efecto:
X(n+1)-2X(n)= (2^(n+1)-(-1)^(n+1))/3 - (2^(n+1)-2*(-1)^n)/3 = (2*(-1)^n-(-1)^(n+1))/3 =(2*(-1)^n+(-1)^n)/3 = (-1)^n, luego la diferencia es 1 en valor absoluto.
Esta es otra forma de demostrar que el cociente X(n+1)/X(n) tiende a 2 al crecer n.
Algunas propiedades
-El que la diferencia entre 3X(n) y 2n sea sólo la unidad, nos vale para descomponer una fila del triángulo de Pascal en tres sumandos, dos de ellos X(n) y el otro una unidad mayor o menor. Por ejemplo, la fila 1, 7, 21, 35, 35, 21, 7, 1 se puede descomponer usando x(7)=43:
1+7+21+35+35+21+7+1=(1+7+35)+(35+7+1)+(21+21)=43+43+42
- El producto de dos términos consecutivos es un número triangular:
Si X(n+1)=2X(n)+(-1)n,el producto X(n)*X(n+1)=2X(n)*(2X(n)+(-1)^n)/2 tendrá la forma de la mitad del producto de dos números consecutivos, que es la definición de un número triangular.
Quizás lo entiendas mejor con un ejemplo: 43691*87381 es un producto de ese tipo y lo podemos escribir como 87381*87382/2
- El término X(n) con n>1 equivale al número de teselaciones de un rectángulo de 3 por n-1 con baldosas de 1 por 1 y 2 por 2.
Lo podemos demostrar por inducción.
Para n=2 X(2)=1 y coincide con la única forma de teselar así un rectángulo de 3 por 1, ya que sólo se podrían emplear teselas 1 por 1 y no hay otra posibilidad.
Para n=3, X(3)=3, que cuenta las posibles teselaciones de un rectángulo de 2 por 3. Efectivamente, serían 3 las posibilidades con baldosas de 1 por 1 y de 2 por 2:
Procedamos a la inducción. Imaginemos que X(n-1) representa las teselaciones de este tipo en un rectángulo de 3 por n-2. Al añadirle una columna más al rectángulo sólo hay tres posibilidades:
En la primera los tres cuadrados no pueden completar una baldosa de 2 por 2, luego no añaden ni quitan posibilidades, es decir, que el número de teselaciones de este tipo coincidirá con X(n-1).
En las otras dos posiciones es obligado completar a 2 por 2, y de una forma única, luego el número total será X(n-2). Como hay dos posiciones, el número total será X(n)=X(n-1)+2X(n-2), que es precisamente l definición de la sucesión. La propiedad es cierta.
Dejamos como ejercicio demostrar una variante: X(n) es el número de teselaciones del rectángulo de 2 por n-1 mediante fichas de dominó de 1 por 2 y cuadrados de 2 por 2.
- Suma de la sucesión
La suma de los n primeros términos de la sucesión equivale al valor de X(n+1) si n es par y a X(n+1)-1 si es impar, es decir S(n)=X(n+1)+(-1)n mod 2. Observando la tabla se comprueba esta propiedad para los primeros términos:
Sólo nos quedaría completar la inducción:
Si S(n)=X(n+1)+(-1)n mod 2, al sumarle un nuevo término X(n+1) nos daría S(n+1)=2*X(n+1)+(-1)n mod 2= X(n+2)+(-1)n+1 mod 2.
Omitimos los detalles del encaje exacto de la paridad de n en la demostración.
- La función generatriz de esta sucesión es x/(1-x-2*x^2), como puedes comprobar con este desarrollo en PARI
write("sucesion.txt",taylor(x/(1-x-2*x^2),x,20))
x + x^2 + 3*x^3 + 5*x^4 + 11*x^5 + 21*x^6 + 43*x^7 + 85*x^8 + 171*x^9 + 341*x^10 + 683*x^11 + 1365*x^12 + 2731*x^13 + 5461*x^14 + 10923*x^15 + 21845*x^16 + 43691*x^17 + 87381*x^18 + 174763*x^19 + O(x^20)
Según la teoría explicada en la entrada citada, basta aplicar la fórmula general:
Y sigue sorprendiéndonos
La imagen que adjuntamos contiene una propiedad nueva de esta sucesión: Hemos tomado el término 3 y en la tercera columna lo hemos ido multiplicando por las distintas potencias de 2, con lo que obtenemos la suma de un término más avanzado con el correspondiente a la potencia. Se ha destacado que 3*2^3=24=21+3=X(7)+X(4).
Sigue bajando por la tabla y descubrirás nuevas sumas de este tipo. Ahora, haz lo mismo con el 5 o con el 11 y resultarán relaciones nuevas. Todas ellas se resumen en esta:
X(n)+X(n+2k+1)=X(2k+2)*2^(n-1)
(Se supone que al primer término lo consideramos X(1) y no X(0))
Por ejemplo, en la de la figura: X(4)+X(7)=X(4)*2^3=3+21=24. Otra: X(5)+X(10)=X(6)*2^4=5+171=176=11*16
Esta propiedad, expresada con otros índices, ha sido propuesta por Paul Curtz en http://oeis.org/A001045
Este blog es un complemento natural de mi página http://www.hojamat.es. Por ello, se dedicará a los temas numéricos tratados con Hoja de Cálculo y a la estructura y prestaciones de esta. Su nivel será elemental o medio, y su orientación lúdica e investigadora.
lunes, 27 de enero de 2014
miércoles, 22 de enero de 2014
Identidad de cifras con una parte de un número
Estudiamos en la entrada anterior (http://hojaynumeros.blogspot.com.es/2014/01/identidad-de-cifras-con-el-mayor.html) la coincidencia en la suma de cifras de un número par con su mayor divisor impar. Probemos ahora con otras funciones
Con la parte libre
Si no recuerdas qué son la parte cuadrada y la parte libre de un número natural puedes consultar http://hojaynumeros.blogspot.com.es/2011/05/parte-cuadrada-y-parte-libre.html
Si tomamos números no libres de cuadrados, su parte libre será distinta de ellos, y podemos plantear también la igualdad de suma de cifras. Son estos:
12, 24, 60, 100, 120, 132, 150, 156, 200, 204, 228, 240, 264, 276, 300, 320, 348, 372, 420, 500, 516, 552, 600, 624, 636, 660, 700, 708, 732, 744, 780, 912, 1000, 1014, 1050, 1056, 1068, 1092, 1100, 1128, 1164, 1200, 1212, 1216, 1236, 1248, 1272, 1300, 1308, 1320, 1356, 1380, 1392, 1400, 1416, 1425, 1428, 1464, 1500…
Todos ellos contienen un cuadrado mayor que 1, por lo que su parte libre será menor que ellos. Por ejemplo, la parte libre de 1200 es 3, porque 1200=3*202. Se cumple que la suma de cifras de 1200 es también 3.
N será igual a N=PL(N)*k2, con lo que la condición ahora será PL(N)(k2-1) es múltiplo de 9 (representamos la parte libre mediante el símbolo PL).
Aquí hay una novedad respecto a la anterior entrada, y es que PL(N) no puede ser múltiplo de 9, pues contendría un cuadrado, luego sólo lo podría ser de 3 y (k2-1) aportaría el otro 3, o bien PL(N) no es múltiplo de 3, con lo que (k2-1) debería serlo de 9. Analizamos:
(A) PL(N) es múltiplo de 3 y (k2-1) también
Para que se cumpla la segunda condición basta con que k no sea múltiplo de 3, como puedes razonar fácilmente. Esto ocurre, por ejemplo en el 156=4*39, en el que el cuadrado 4 no es múltiplo de 3 y la parte libre 39 sí lo es.
(B) Si PL(N) no es múltiplo de 3, (k2-1) lo será de 9
En ese caso k2 será congruente con 1 módulo 9
Ocurre en los términos 100, 200, 320, 500, 700, 1000, 1100, 1216, 1300, 1400, 1700, 1900, 2023, 2200, 2240, 2300, 2432, 2600…
En ellos el valor de k puede ser 8, 10, 17, 19, 26… que son los números cuyo cuadrado es congruente con 1 módulo 9 (http://oeis.org/A056020).
Hemos publicado esta sucesión en http://oeis.org/A230355
El código para obtenerlos en PARI es muy parecido al de la anterior entrada:
digsum(n)={local (d, p); d=0; p=n; while(p, d+=p%10; p=floor(p/10)); return(d)}
{for (n=2, 10^3,m=core(n);if(digsum(n)==digsum(m)&&m<>n,print(n)));}
Con la parte cuadrada
De forma simétrica, si tomamos números no cuadrados, que son distintos de su parte cuadrada, podremos plantear también la identidad de la suma de cifras. Resultan ser estos:
10, 18, 27, 40, 45, 54, 63, 72, 90, 108, 117, 126, 135, 153, 160, 162, 171, 180, 207, 216, 220, 234, 243, 250, 252, 261, 270, 304, 306, 315, 333, 342, 351, 360, 405, 414, 423, 432, 450, 490, 504, 513, 522, 531, 540, 603, 612, 621, 630, 640, 702, 711, 720, 801, 810, 931…
Si tomamos, por ejemplo, 270, su parte cuadrada es 9 y la suma de cifras es también 9. Entre ellos están los de la forma N*10 con N cuadrado, en los que la igualdad de sumas de cifras es trivial.
Siguiendo el mismo razonamiento de casos anteriores, si denominamos PC(N) a la parte cuadrada de N, tendremos que la diferencia entre ambos ha de ser múltiplo de 9:
N-PC(N)=PC(N)*(PL(N)-1), siendo PL(N) la parte libre, ha de ser múltiplo de 9. Al analizarlo, las consideraciones son inversas a las del caso anterior:
PC(N) múltiplo de 3
En ese caso también lo será de 9, y la parte libre puede ser cualquiera. En la sucesión figurarán múltiplos de 9 que no sean cuadrados, pero no todos, porque la condición no es suficiente: 99 es múltiplo de 9, no es cuadrado, pero sus cifras suman 18 y las de su parte cuadrada 9. Son congruentes módulo 9, pero no iguales.
PC(N) no múltiplo de 3
En ese caso, PL(N) -1 será congruente con 9, y eso sólo ocurre en los números del tipo 9k+1 que sean libres de cuadrados: 1, 10, 19, 37, 46, 55, 73, 82, 91, 109, 118,…
En esta tabla tienes analizados los primeros ejemplos: si en la segunda columna no figura un múltiplo de 9, entonces en la tercera aparecerán 10, 19,…55,…
Con el lenguaje PARI se buscan estos números de forma similar a la del anterior caso, sustituyendo m=core(n) por m=n/core(n), Los tenemos publicados en http://oeis.org/A230356
Último ejemplo
Números compuestos que coinciden en su suma de cifras con su función SOPF (suma de factores primos tomados sin repetición)
22, 94, 105, 114, 136, 140, 160, 166, 202, 222, 234, 250, 265, 274, 346, 355, 361, 382, 424, 438, 445, 454, 516, 517, 526, 532, 562, 634, 702, 706, 712, 732, 812, 913, 915, 922, 1036, 1071, 1086, 1111…
Lo habrás adivinado ya. La hemos publicado en http://oeis.org/A230357
Código PARI
sopf(n)= { local(f, s=0); f=factor(n); for(i=1, matsize(f)[1], s+=f[i, 1]); return(s) }
digsum(n)={local (d, p); d=0; p=n; while(p, d+=p%10; p=floor(p/10)); return(d)}
{for (n=4, 2*10^3,m=sopf(n);if(digsum(n)==digsum(m)&&m<>n,write1("final.txt",n,", ")));}
Otros ejemplos ya publicados
Números de Smith
En ellos la suma de sus cifras coincide con las de sus factores primos tomados con repetición, como el 666, cuyas cifras suman 18 y las de su desarrollo en factores primos 2*3*3*37 también: 2+3+3+3+7=18. Los tienes en http://oeis.org/A006753
Números “hoax” (o engañosos)
Poseen la misma propiedad pero tomando los primos sin repetir. 424=2^3*53 y las sumas de cifras son: 4+2+4=10. 2+5+3=10, tomando el 2 una sola vez. También están publicados en http://oeis.org/A019506
Si te pones a ello podrás descubrir más ejemplos.
Con la parte libre
Si no recuerdas qué son la parte cuadrada y la parte libre de un número natural puedes consultar http://hojaynumeros.blogspot.com.es/2011/05/parte-cuadrada-y-parte-libre.html
Si tomamos números no libres de cuadrados, su parte libre será distinta de ellos, y podemos plantear también la igualdad de suma de cifras. Son estos:
12, 24, 60, 100, 120, 132, 150, 156, 200, 204, 228, 240, 264, 276, 300, 320, 348, 372, 420, 500, 516, 552, 600, 624, 636, 660, 700, 708, 732, 744, 780, 912, 1000, 1014, 1050, 1056, 1068, 1092, 1100, 1128, 1164, 1200, 1212, 1216, 1236, 1248, 1272, 1300, 1308, 1320, 1356, 1380, 1392, 1400, 1416, 1425, 1428, 1464, 1500…
Todos ellos contienen un cuadrado mayor que 1, por lo que su parte libre será menor que ellos. Por ejemplo, la parte libre de 1200 es 3, porque 1200=3*202. Se cumple que la suma de cifras de 1200 es también 3.
N será igual a N=PL(N)*k2, con lo que la condición ahora será PL(N)(k2-1) es múltiplo de 9 (representamos la parte libre mediante el símbolo PL).
Aquí hay una novedad respecto a la anterior entrada, y es que PL(N) no puede ser múltiplo de 9, pues contendría un cuadrado, luego sólo lo podría ser de 3 y (k2-1) aportaría el otro 3, o bien PL(N) no es múltiplo de 3, con lo que (k2-1) debería serlo de 9. Analizamos:
(A) PL(N) es múltiplo de 3 y (k2-1) también
Para que se cumpla la segunda condición basta con que k no sea múltiplo de 3, como puedes razonar fácilmente. Esto ocurre, por ejemplo en el 156=4*39, en el que el cuadrado 4 no es múltiplo de 3 y la parte libre 39 sí lo es.
(B) Si PL(N) no es múltiplo de 3, (k2-1) lo será de 9
En ese caso k2 será congruente con 1 módulo 9
Ocurre en los términos 100, 200, 320, 500, 700, 1000, 1100, 1216, 1300, 1400, 1700, 1900, 2023, 2200, 2240, 2300, 2432, 2600…
En ellos el valor de k puede ser 8, 10, 17, 19, 26… que son los números cuyo cuadrado es congruente con 1 módulo 9 (http://oeis.org/A056020).
Hemos publicado esta sucesión en http://oeis.org/A230355
El código para obtenerlos en PARI es muy parecido al de la anterior entrada:
digsum(n)={local (d, p); d=0; p=n; while(p, d+=p%10; p=floor(p/10)); return(d)}
{for (n=2, 10^3,m=core(n);if(digsum(n)==digsum(m)&&m<>n,print(n)));}
Con la parte cuadrada
De forma simétrica, si tomamos números no cuadrados, que son distintos de su parte cuadrada, podremos plantear también la identidad de la suma de cifras. Resultan ser estos:
10, 18, 27, 40, 45, 54, 63, 72, 90, 108, 117, 126, 135, 153, 160, 162, 171, 180, 207, 216, 220, 234, 243, 250, 252, 261, 270, 304, 306, 315, 333, 342, 351, 360, 405, 414, 423, 432, 450, 490, 504, 513, 522, 531, 540, 603, 612, 621, 630, 640, 702, 711, 720, 801, 810, 931…
Si tomamos, por ejemplo, 270, su parte cuadrada es 9 y la suma de cifras es también 9. Entre ellos están los de la forma N*10 con N cuadrado, en los que la igualdad de sumas de cifras es trivial.
Siguiendo el mismo razonamiento de casos anteriores, si denominamos PC(N) a la parte cuadrada de N, tendremos que la diferencia entre ambos ha de ser múltiplo de 9:
N-PC(N)=PC(N)*(PL(N)-1), siendo PL(N) la parte libre, ha de ser múltiplo de 9. Al analizarlo, las consideraciones son inversas a las del caso anterior:
PC(N) múltiplo de 3
En ese caso también lo será de 9, y la parte libre puede ser cualquiera. En la sucesión figurarán múltiplos de 9 que no sean cuadrados, pero no todos, porque la condición no es suficiente: 99 es múltiplo de 9, no es cuadrado, pero sus cifras suman 18 y las de su parte cuadrada 9. Son congruentes módulo 9, pero no iguales.
PC(N) no múltiplo de 3
En ese caso, PL(N) -1 será congruente con 9, y eso sólo ocurre en los números del tipo 9k+1 que sean libres de cuadrados: 1, 10, 19, 37, 46, 55, 73, 82, 91, 109, 118,…
En esta tabla tienes analizados los primeros ejemplos: si en la segunda columna no figura un múltiplo de 9, entonces en la tercera aparecerán 10, 19,…55,…
Con el lenguaje PARI se buscan estos números de forma similar a la del anterior caso, sustituyendo m=core(n) por m=n/core(n), Los tenemos publicados en http://oeis.org/A230356
Último ejemplo
Números compuestos que coinciden en su suma de cifras con su función SOPF (suma de factores primos tomados sin repetición)
22, 94, 105, 114, 136, 140, 160, 166, 202, 222, 234, 250, 265, 274, 346, 355, 361, 382, 424, 438, 445, 454, 516, 517, 526, 532, 562, 634, 702, 706, 712, 732, 812, 913, 915, 922, 1036, 1071, 1086, 1111…
Lo habrás adivinado ya. La hemos publicado en http://oeis.org/A230357
Código PARI
sopf(n)= { local(f, s=0); f=factor(n); for(i=1, matsize(f)[1], s+=f[i, 1]); return(s) }
digsum(n)={local (d, p); d=0; p=n; while(p, d+=p%10; p=floor(p/10)); return(d)}
{for (n=4, 2*10^3,m=sopf(n);if(digsum(n)==digsum(m)&&m<>n,write1("final.txt",n,", ")));}
Otros ejemplos ya publicados
Números de Smith
En ellos la suma de sus cifras coincide con las de sus factores primos tomados con repetición, como el 666, cuyas cifras suman 18 y las de su desarrollo en factores primos 2*3*3*37 también: 2+3+3+3+7=18. Los tienes en http://oeis.org/A006753
Números “hoax” (o engañosos)
Poseen la misma propiedad pero tomando los primos sin repetir. 424=2^3*53 y las sumas de cifras son: 4+2+4=10. 2+5+3=10, tomando el 2 una sola vez. También están publicados en http://oeis.org/A019506
Si te pones a ello podrás descubrir más ejemplos.
miércoles, 15 de enero de 2014
Identidad de cifras con el mayor divisor impar
Observa esta sucesión de números
12, 18, 36, 54, 60, 72, 90, 108, 126, 132, 144, 156, 162, 180, 198, 204, 216, 228, 234, 240, 252, 270, 276, 306, 320, 324, 342, 348, 360, 372, 378, 396, 414, 420, 432, 450, 504, 516, 522, 540, 558, 594, 612, 624, 630, 636, 660,…
Si los divides entre 2 todas las veces posibles, el cociente (que es su mayor divisor impar) presenta la misma suma de cifras que el número original. Por ejemplo, las cifras de 660 suman 12. Lo voy dividiendo entre 2: 660, 330, 165, y el cociente 165 también tiene unas cifras que suman 12.
Al igual que hicimos en la entrada http://hojaynumeros.blogspot.com.es/2012/12/mayor-divisor-propio-con-la-misma-suma.html, aprovecharemos esta cuestión para repasar algunas cuestiones teóricas.
El mayor divisor impar (MDI(N)) de un número par N es siempre divisor propio, y la relación entre ambos es la de N=MDI(N)*2k, siendo k el mayor exponente posible tal que 2k divide a N y recibe el nombre de valuación de N respecto a 2 (ver http://hojaynumeros.blogspot.com.es/2012/12/volvemos-visitar-al-mayor-divisor-impar.html)
Si B es el mayor divisor impar de A se cumple A=B*2k siendo k la valuación de A respecto a 2. En el caso que nos ocupa A sería par y k>0
Condición necesaria de igualdad de sumas
Busquemos números pares que presenten la misma suma de cifras que su mayor divisor impar (MDI)
Si dos números presentan la misma suma de cifras es que son congruentes módulo 9, según vimos en la entrada referida más arriba.
Por tanto tendremos, NºMDI(N) (mod 9, o lo que es igual, N-MDI(N) ha de ser múltiplo de 9. Sustituimos N por MDI(N)*2k y obtenemos: MDI(N)*2k-MDI(N)=MDI(N)(2k-1) ha de ser múltiplo de 9.
Pueden ocurrir tres hechos para que esto se cumpla:
(a) Si MDI(N) es múltiplo de 9, se cumple seguro, y como N es par, habrá en la sucesión múltiplos de 18. Compruébalo: 18, 36, 54, 72, 90, 108, 126, 144, 162…
Unos términos de la sucesión serán múltiplos de 18
(b) Si MDI(N) es múltiplo de 3 pero no de 9, (2k-1) ha de ser múltiplo de 3, lo que ocurre para k=0, 2, 4, 6, y los pares, porque 22n-1=M(22-1)=M*3. Otra forma de verlo consiste en tener en cuenta que en este caso 2kº1 (mod 3, es decir, que 1 ha de ser resto de 2k respecto a 3, y eso sólo ocurre en los pares: 20º1, 21º2, 22º1, 23º2, 24º1,…Luego si MDI(N) es múltiplo de 3 pero no de 9, k ha de ser par.
Otros se compondrán de un múltiplo de 3 que no lo es de 9 multiplicado por una potencia par del número 2
Entre los primeros están 12, 60, 132, 156,…
Hay que recordar que estas condiciones son necesarias pero no suficientes. El número 48 se descompone como 48=3*24, y sin embargo no cumple la igualdad de suma de cifras: las del 48 suman 12 y las de su mayor divisor impar, 3.
(c) Si MDI(N) no es múltiplo de 3, entonces 2k-1 lo ha de ser de 9, y esto sólo ocurre si k es múltiplo de 6, ya que, recorriendo los restos potenciales del 2 módulo 9 obtenemos:
Esta imagen procede de nuestra herramienta
http://hojamat.es/sindecimales/congruencias/herramientas/hoja/potenciales.xls o su correspondiente para OpenOffice potenciales.ods.
En ella puedes observar que sólo los exponentes múltiplos de 6 producen un resto potencial igual a 1.
En la sucesión aparecerán números cuyo MDI no sea múltiplo de 3 y cuya valuación respecto al 2 sea múltiplo de 6.
Es el caso de 320, 1216, 1600, 2240…
Una cuestión de hoja de cálculo
Hemos clasificado los términos de la sucesión que estamos estudiando en tres tipos distintos. Creemos que nuestro razonamiento es correcto, pero ¿y si hubiera un error?¿y si apareciera un número que no obedeciera a estos tipos?. Podríamos obtener cuatro listas distintas, una, la general que hemos presentado arriba, y otras tres que corresponderían a los tipos presentados. Serían estas (sólo escribimos los primeros términos y se supone que incluimos sólo los que cumplen la condición de igualdad de suma de cifras):
General: 12, 18, 36, 54, 60, 72, 90, 108, 126, 132, 144, 156, 162, 180, 198, 204, 216, 228, 234,,…
Tipo A (MDI múltiplo de 9): 18, 36, 54, 72, 90, 108, 126, 144, 162, 180, 198, 216, 234, 252…
Tipo B (MDI múltiplo de 3 pero no de 9): 12, 60, 132, 156, 204, 228, 240, 276, 348, 372, 420,…
Tipo C(MDI no múltiplo de 3): 320, 1216, 1600, 2240,… (de estos hay menos)
En la imagen están los cuatro tipos en columna, para valores inferiores a 3000. Ahora unificamos las tres últimas y las ordenamos de menor a mayor. Así obtenemos dos listas idénticas, que constituyen nuestra comprobación para elementos menores que 3000.
Esto no prueba nada, pero aprovecha el manejo de la hoja de cálculo en una cuestión teórica.
Si te has iniciado al lenguaje PARI, muy útil en las cuestiones que estudiamos, puedes comprobar la lista anterior con estas líneas:
mdi(n)= n / 2^valuation(n, 2)
digsum(n)={local (d, p); d=0; p=n; while(p, d+=p%10; p=floor(p/10)); return(d)}
{for (n=2, 10^3,m=mdi(n);if(digsum(n)==digsum(m)&&m<>n,print(n)));}
Hemos usado este código para publicar nuestra sucesión, que estaba inédita, en http://oeis.org/A230354
miércoles, 8 de enero de 2014
Recurrencias lineales de segundo orden
En este blog no hemos tratado mucho las relaciones de recurrencia. Iniciamos ahora el estudio de un caso particular de las mismas, más por los casos curiosos que presenta que por su estudio teórico, que se puede desarrollar mejor en otras publicaciones, como
(http://mathworld.wolfram.com/LinearRecurrenceEquation.html)
Llamaremos relación de recurrencia lineal de segundo orden a la que existe entre los términos de una sucesión si reviste esta forma:
Interpretamos que cada término a partir uno de ellos equivale al anterior multiplicado por un número más el anterior del anterior por otro y sumado un tercer número. Como hemos indicado que nuestras pretensiones no son teóricas, nos dedicaremos tan sólo al caso en el que a3=0, es decir, a relaciones lineales de segundo orden homogéneas, pues en ellas encontraremos bastantes hechos curiosos.
Lo normal es definir directamente los primeros términos, llamados valores iniciales, y después dar los coeficientes de la recurrencia, que supondremos constantes.
Por ejemplo, en la sucesión de Fibonacci, definimos directamente x0=1, x1=1 y usamos los coeficientes a1=1 y a2=1, con lo que la relación de recurrencia vendrá dada por xn=xn-1+xn-2, constituyendo una recurrencia lineal de segundo orden homogénea, y entrando así en nuestro estudio.
Una sucesión definida por recurrencia vendrá dada así por el conjunto de valores iniciales y el de coeficientes, siendo conveniente fijar también el número de términos. Así se concreta, por ejemplo, en Mathematica, la función LinearRecurrence, y así lo trataremos más adelante.
Estas sucesiones reciben el nombre de “sucesiones de Horadam” y se caracterizan por estar determinadas por esos cuatro parámetros dentro de una recurrencia de segundo orden homogénea. Así, la sucesión de Fibonacci es Horadam(0,1,1,1), porque los parámetros se escriben en orden inverso a como lo hacemos aquí. Sólo estudiaremos algunos casos, pues el tema es muy amplio y con muchas sucesiones interesantes.
Generación con hoja de cálculo
Aprovechando la recursividad del Basic de las hojas de cálculo se pueden definir funciones que devuelvan el valor de x(n). El problema que tienen es que funcionan mientras no se llene la pila de datos (ver http://hojaynumeros.blogspot.com.es/2012/03/funciones-recursivas-en-las-hojas-de.html). En este caso podrían tener esta estructura:
Public Function recurre(c1, c2, d1, d2, n)
Dim r
If n = 0 Then
r = d1
ElseIf n = 1 Then
r = d2
Else
r = c1 * recurre(c1, c2, d1, d2, n - 1) + c2 * recurre(c1, c2, d1, d2, n - 2)
End If
recurre = r
End Function
La tienes implementada en la hoja recurre_lineal, que ofrecemos en
http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#recurre2
Para evitar el problema del llenado de la pila de recursividad, hemos preparado un generador muy simple de estas sucesiones, en la hoja mencionada, con el que practicaremos algunos conceptos y que no usa la recursividad para evitar ese problema:
Basta estudiar la imagen para entender que hay que escribir el número de términos, los coeficientes, aquí llamados A y B y los valores iniciales. Para fijar ideas, generaremos los números de Pell, dados por la ecuación xn=2xn-1+xn-2 con las condiciones iniciales x0=0 y x1=1. Todos ellos se pueden identificar en la imagen:
Con el botón Ver sucesión generamos los 20 primeros términos, que están ya publicados en http://oeis.org/A000129 y se nos indica que son los denominadores del desarrollo de los convergentes a raíz de 2 mediante fracciones continuas. Les dedicaremos una entrada próximamente.
Tenemos así una herramienta muy simple para inventarnos sucesiones, independientemente de su importancia matemática. Por ejemplo, llamaremos sucesión “sorpresa” a la engendrada mediante A=2, B=-1, X0=0, X1=1. Te dejamos que averigües su desarrollo y en qué consiste la sorpresa.
Ecuación característica
Existe un procedimiento simple para intentar expresar X(n) en función de n en sucesiones definidas por recurrencias de segundo orden: la ecuación característica. Puedes estudiarla en cualquier manual o página web específica, como
http://people.uncw.edu/tompkinsj/133/recursion/homogeneous.htm
En esencia este método consiste en:
(1) Dada la relación
planteamos la ecuación de segundo grado
o bien una combinación lineal de ambas:
Las soluciones pueden ser reales o complejas.
(3) Si las soluciones de esa ecuación son dobles e iguales a x1 la expresión buscada será
o bien una combinación lineal de ambas
(4) En ambos casos, los coeficientes C1 y C2 se calcularán a partir de los valores iniciales.
La herramienta que ofrecemos plantea y resuelve la ecuación característica de la sucesión que definamos. En el desarrollo de la fórmula general de x(n) no se ha desarrollado el caso de raíces complejas, ya que no compensaba el trabajo en una programación complicada, dado que nuestras pretensiones son meramente divulgativas.
Se comienza calculando el discriminante para ver si es el caso de raíz doble o no. Después se encuentran las soluciones de la ecuación característica y en el caso real se escribe la expresión general de x(n). En la imagen se observa la solución para la sucesión que llamamos “sorpresa”, que resulta representar la sucesión de números naturales. Si simplificas la expresión de abajo resulta ser x(n)=n.
Valores según la expresión general
Por último, en el caso de raíces reales, se ofrece una calculadora de los valores de x(n) dado el valor de n. En la imagen puedes ver el cálculo del término 21 de la sucesión de Fibonacci, que resulta tener el valor de 17711.
Hasta aquí las definiciones y la presentación de la herramienta implementada en hoja de cálculo. Recordaremos ahora cómo es su función generatriz antes de pasar al estudio de sucesiones particulares.
Función generatriz
No es difícil encontrar la función generatriz en este caso
(http://hojaynumeros.blogspot.com.es/2013/03/funciones-generatrices-en-combinatoria.html
y
http://eliatron.blogspot.com.es/2009/01/sucesiones-recurrentes-funciones.html).
Siguiendo el procedimiento explicado en el blog de Tito Eliatron, bastará aplicar lo siguiente:
Si representamos la sucesión por x0, x1, x2, x3, x4, …, su F.G. se construirá tomándolos como coeficientes de un polinomio:
Sumando miembro a miembro
Todos los paréntesis son nulos por la definición de la congruencia. Despejando F(x) tendremos:
Por ejemplo, en la sucesión de Fibonacci, si la hacemos comenzar por 0, tendríamos x0=0, x1=1, a1=1, a2=1 y nos daría
Usaremos esta expresión en las siguientes sucesiones que estudiemos. Hasta aquí la primera entrada sobre este tema. Más adelante, alternando con entradas de otras temáticas, iremos presentando casos particulares interesantes.
Suscribirse a:
Entradas (Atom)