jueves, 25 de febrero de 2010

Función cifras_distintas

En la entrada del 24 de Febrero de su blog “Números” , Claudio nos planteaba esta propuesta:

¿Cuál es el mayor número que entre él y su doble, no tienen dígitos repetidos?

Cuando quise emprender la búsqueda me di cuenta de que tenía que comenzar con el 49000 y después ir descendiendo en los ensayos hasta dar con el número pedido. Era una tarea para encargársela al ordenador y que él trabajara por mí.

Cuando planifiqué esta búsqueda vi que sería muy útil disponer de una función que me devolviera un 1 si su argumento no tuviese cifras repetidas o un 0 en caso contrario (preferí  1 y 0 porque es más cómodo que VERDADERO o FALSO). Pues bien, el estudio de esta función es el objetivo de esta entrada.

Función cifras_distintas


Para construir esta función sobre un argumento N son necesarios tres cálculos al menos:

  • Encontrar el número de cifras de N
  • Saber encontrar la cifra de N que ocupe el lugar K
  • Comprobar si las cifras son distintas o existe alguna repetición.
Número de cifras

Un número entero tiene K cifras si está comprendido entre 10K-1 y 10K por lo que tomando logaritmos decimales, K-1 <= log (N) < K

Public function numero_cifras(n)
numero_cifras=int(log(n)/log(10))+1
end function

En esta entrada del presente blog se explica el modo de implementarlas en OpenOffice.org Calc

Se declara Public para que se pueda usar como una función más de Excel o Calc y el dividir entre log(10) se justifica porque LOG se corresponde con el logaritmo natural.

Selección de cifras

Para extraer una cifra de un número entero podemos acudir a calcular su cociente entero respecto a 10K-1, y nos resultará el mismo número pero escrito sólo hasta la cifra K. Así INT(23543/100) se nos convierte en 235. Si ahora lo dividimos entre 10, desaparecerá la cifra K: INT(235/10)=23. Con algún pequeño detalle más llegamos a la función deseada. Si el número no posee tantas cifras nos devolverá un cero.

Public function cifra(m,n)
dim v

v=int(m/10^(n-1))
v=v-10*int(v/10)
cifra=v
end function

Función cifras_distintas

Ya sabemos contar las cifras de un número y separarlas unas de otras. Ahora hay que recorrerlas y detectar si alguna se repite.

Para ello crearemos diez memorias C, que se rellenarán con un 1 si la cifra existe en el número, y con un 0 si no existe. Así, cuando se recorre el número, se va marcando con un 1 cada cifra encontrada, pero si posteriormente nos encontramos con un 1 al marcar, es que existe una repetición. En la imagen vemos cómo se rellenarían las memorias con el número 27653:

Con esto ya tenemos preparado todo para la función. Se transcribe a continuación un posible listado en Basic con comentarios en cursiva:

Public function cifras_distintas(n)
dim nc,i,d
dim c(10)
dim vale

nc=numero_cifras(n)          Se cuentan las cifras y se almacenan en la memoria nc
for i=0 to 9:c(i)=0:next i    Ponemos todas a cero
vale=1                                  Provisionalmente damos el número como con cifras distintas
i=1                                        Iniciamos el recorrido
while vale=1 and i<=nc      Mantenemos el recorrido mientras no haya repetición
d=cifra(n,i)                          Leemos la cifra
if c(d)=0 then                      Si no está ya marcada, la marcamos
c(d)=1
else
vale=0                                  Si está marcada hay repetición y hacemos vale=0
end if
i=i+1
wend                                    Fin del recorrido
cifras_distintas=vale
end function

domingo, 21 de febrero de 2010

Ecuación de Pell

Se llama ecuación de Pell (por error, porque Pell no la estudió) a la ecuación diofántica cuadrática X2 - DY2 = 1, con X e Y variables enteras y D número entero positivo no cuadrado perfecto.

Existe una variante con el segundo miembro -1 que se resuelve de forma similar, con algunas restricciones, y también se consideran los casos en los que se trate de cualquier número entero.

En su resolución hay que distinguir dos problemas:

Primera solución

Una primera solución no es difícil de encontrar en general.

(a) Puedes acudir a un simple tanteo entre cuadrados perfectos. Por ejemplo, una solución de X2 - 6Y2 = 1 es X0=5 Y0=2. Con una hoja de cálculo no es tarea muy complicada.

(b) Las fracciones continuas también son útiles en la resolución de esta ecuación. Basta para ello desarrollar la raíz cuadrada de D mediante ellas y, según vimos en una entrada anterior, aprovechar la periodicidad del desarrollo. En el caso de la ecuación de Pell basta tomar las reducidas anteriores a la finalización del primer periodo.



En la imagen observarás que la solución X0=5,Y0=2 aparece antes del final del primer periodo [2,4] en el desarrollo por fracciones continuas. Después siguen otras: X=49, Y=20, X=485, Y=198, etc.

En nuestro modelo de hoja de cálculo que recomendamos más abajo basta escribir el valor de D y el segundo miembro +1 ó -1 y la hoja se encarga de desarrollar la raíz cuadrada de D mediante fracciones continuas:


(c) En el documento recomendado al final de esta entrada puedes estudiar estos y otros métodos muy útiles.

Siguientes soluciones

Según la teoría del anillo  Q(R), siendo R la raíz cuadrada de D (no lo desarrollaremos aquí), las primeras soluciones, escritas como 

constituyen una unidad del anillo, y también lo serán todas sus potencias, por lo que las siguientes soluciones provendrán de los desarrollos de las expresiones


agrupando después los términos que no contienen el radical como valor de Y y los que sí lo contienen como valor de X. Este método puede ser fatigoso, por lo que es mejor ir obteniendo las distintas soluciones por recurrencia. En efecto, de la anterior consideración se deduce que

O bien, separando términos:

Estas son las fórmulas que hemos usado en la hoja de cálculo.

Puedes consultar la búsqueda de la primera solución por fracciones continuas y la recurrencia para las siguientes en las hojas de cálculo

http://www.hojamat.es/sindecimales/aritmetica/herramientas/hoja/pell.ods para Calc
http://www.hojamat.es/sindecimales/aritmetica/herramientas/hoja/pell.xls para Excel

Por ejemplo, intenta resolver esta cuestión: ¿Qué cuadrado perfecto de diez cifras, al quitarle una unidad se puede descomponer en cinco cuadrados perfectos idénticos?

Nuestro colaborador Rafael Parra Machío nos ha facilitado un documento muy interesante sobre la ecuación de Pell, en el que podrás consultar otros métodos de resolución, como el que usa aritmética modular, y también algunos detalles históricos y teóricos que no hemos incluido aquí.

Lo puedes descargar desde la dirección http://www.hojamat.es/parra/pell.pdf

martes, 16 de febrero de 2010

Aproximación diofántica (2)

Cualquier número expresado en forma decimal puede representarse mediante una fracción continua. Si el número es racional, ésta será finita, pero si es irracional no podrá serlo, y tendríamos que prolongar el desarrollo de la fracción continua hasta el infinito. En los siguientes párrafos veremos cómo.

Un caso muy interesante es el de los irracionales cuadráticos, que, como demostró Lagrange, presentan desarrollos periódicos.

¿Cómo desarrollar un decimal cualquiera en fracción continua exacta (caso racional) o aproximada (si es irracional)?

La idea es: separamos la parte entera y la parte decimal del número N=e+d, y la decimal la expresamos así: N=e+1/(1/d). Volvemos a separar parte entera y decimal de 1/d y reiteramos, con lo que irán apareciendo los cocientes enteros de una fracción continua. Además de esta idea, existen otros procedimientos con más contenido teórico que no desarrollaremos aquí.

Probamos con la raíz cuadrada de 3. Los cálculos serían:

1,73205080757 = 1+ (1/(1/1,73205080757) =
1+ 1/1,36602540378 = 1+ 1/(1+1/2,73205080760) =
1+1/(1+1/(2+1/1,36602540378) = ….

Al salir este último número se descubre la periodicidad, luego 1,73205080757 equivale a la fracción continua

[1,1,2,1,2,1,2,….] que es periódica por tratarse de un irracional cuadrático.

A continuación destacamos algunos desarrollos importantes:


Números metálicos

Número de oro



Número de plata

Número de bronce



Las hojas de cálculo

http://www.hojamat.es/sindecimales/aritmetica/herramientas/hoja/fraccont.xls

http://www.hojamat.es/sindecimales/aritmetica/herramientas/hoja/fraccont.ods

automatizan el proceso. Si las descargas recuerda que están compuestas de dos hojas, una para números fraccionarios y otra para racionales. Si en la primera escribes =RAIZ(3) (En Calc con tilde: RAÍZ) obtendrás las aproximaciones (leyendo las reducidas) a la raíz cuadrada de 3.

El carácter aproximado de los cálculos produce que se rompan las posibles periodicidades después de muchos pasos.

domingo, 14 de febrero de 2010

Aproximación diofántica

¿Sabías que la fracción 3650401/2107560 es una muy buena aproximación de la raíz cuadrada de 3 (coinciden en los trece primeros decimales)?

¿Cómo se ha obtenido?

lunes, 8 de febrero de 2010

Frobenius y los Mcnuggets

(Con esta entrada participamos en el Primer Carnaval de Matemáticas)

Un número entero positivo “McNugget”, es aquel que es expresable como combinación lineal, con coeficientes enteros no negativos, de los números 6, 9 y 20. Se llama así porque 6, 9 y 20 eran los contenidos de las cajas de McDonald's® Chicken McNuggetsTM.

Hay números que son “McNugget”, como el 30 = 2*9+2*6, que abarcan un número entero de cajas (un pedido normal), y otros que no pueden serlo, como el 11, que no se puede descomponer en sumandos 6, 9 y 20.

Este es un simpático ejemplo de descomposición de un entero N en sumandos extraídos de un conjunto (lista) L. Por ejemplo, el número 10, según la lista (5,3,1) se puede descomponer en 10= 5+5 = 5+3+1+1 = 5+1+1+1+1+1 = 3+3+3+1 = 3+3+1+1+1+1 = 3+1+1+1+1+1+1+1 = 1+1+1…

Las sumas las podemos expresar como combinaciones lineales:

10 = 2*5+0*3+0*1 = 1*5+1*3+2*1 = 1*5+5*1 = …

En el caso de los “McNugget”, los coeficientes serían, evidentemente, el número de cajas que deberíamos pedir.

Generalizando, dado un conjunto de números enteros positivos a1, a2, a3,…an, diremos que otro entero positivo N es representable según ese conjunto si existen coeficientes enteros no negativos x1, x2, x3,…xn tales que N= a1*x1+a2*x2+…an*xn

Según sea el conjunto a1, a2, a3,…an será distinta la discusión de si todos los enteros positivos N son representables en ese conjunto. Nos referiremos a partir de ahora a aquellos en los que que MCD(a1, a2, a3,…an)=1, es decir, que sean coprimos, aunque no necesariamente dos a dos.

Este problema es llamado también de las monedas, porque equivale a discutir si una cantidad de dinero se puede expresar sólo con dos o tres tipos de monedas (o de billetes, o de sellos).

Se puede demostrar que para números N grandes es posible siempre esta expresión de un número como combinación lineal de este tipo (uno de los teoremas de Schur). Existirá, por tanto, un número que sea el mayor para el que no se cumpla, que no sea representable en ese conjunto. Este es el llamado número de Frobenius. Por ejemplo, en los McNugget, el número de Frobenius es 43, porque es el mayor de los números no representables con 6, 9 y 20. Todos los mayores que él lo son.

Encontrar el número de Frobenius para un conjunto de varios números primos entre sí es un problema muy complejo (tipo NP-hard) que sobrepasa los objetivos de este blog, dedicado a las cuestiones de nivel medio.

No obstante, podemos hacer alguna propuesta sobre él.

(a) El que un número N suficientemente grande sea representable siempre lo podemos razonar para el caso de dos coeficientes. Sean A y B enteros positivos primos entre sí. Sabemos que entonces la ecuación Ax+By=N siempre tiene solución: X0=pN-Bt Y0=qN+At, siendo p y q una solución de Ax+By = 1 y t un parámetro. Lo que tienes que investigar es si para N suficientemente grande, X0 e Y0 pueden ser ambos no negativos. Pues a por ello.

Con la ayuda de la hoja de cálculo también se puede investigar algún aspecto de este problema:

(b) Nuestro Buscador de Números Naturales permite encontrar aquellos que sean suma de múltiplos de otros. Así, los números McNugett serán suma de múltiplos de 6, 9 y 20. De esta forma puedes comprobar que el número de Frobenius para ellos es 43.

Sigue estos pasos:

Abre el Buscador de Naturales para Calc en

http://www.hojamat.es/sindecimales/divisibilidad/herramientas/hojas/buscador.ods

o para Excel en

http://www.hojamat.es/sindecimales/divisibilidad/herramientas/hojas/buscador.xls

Borra las condiciones con el botón correspondiente y diseña una búsqueda como suma de múltiplos en “Suma Especial” guiándote por la siguiente imagen (escribe SI, M6, M9…)



Concreta en la parte superior que buscaremos desde 1 hasta 200. Pulsa sobre el botón “Buscar números” y obtendrás una lista en la que a partir del número 44 todos aparecen consecutivos, por lo que se comprueba que 43 es el máximo que no es representable.



Silvester demostró que para dos números a y b coprimos, su número de Frobenius equivale a
g(a,b)=ab-a-b.

Puedes comprobarlo con el Buscador de Naturales. Borra condiciones y diseña una búsqueda sólo con dos múltiplos, y podrás observar que su número de Frobenius cumple la fórmula de Silvester. En la imagen puedes ver el caso de que a=11 y b=8, con lo que g(11,8)=11*8-11-8=69, y a partir del 70 todos son consecutivos.



(c) Hemos preparado un modelo de hoja de cálculo que encuentra todas las posibilidades de representación de un número respecto a otros varios. Por tratarse de un algoritmo voraz, puede tener algún fallo, pero parece funcionar bien.


Puedes descargártelo (dos versiones: Excel y Calc) desde

http://www.hojamat.es/blog/mcnugget.zip

En la segunda hoja dispones de unas breves instrucciones

viernes, 5 de febrero de 2010

Sumas con simetría

En un libro sobre calculadoras de Elie Vannier se presentaban estas operaciones

como ejemplo de sumas que forman con su resultado una matriz simétrica

¿Cuántas de esas sumas de tres cifras existen?

Si eliminamos la cifra 0, que produce demasiados casos triviales, resultan 252 sumas, salvo algún error que se haya cometido. La de cifras más pequeñas es 112+112=224 y la última en aparecer 819+179=998

¿Podrías implementar un algoritmo exhaustivo que las hiciera aparecer en una hoja de cálculo?