Scripts de fuerza bruta = eficacia límite

Personalmente me encanta la programación y aunque nunca he estado en una cátedra de programación desde que conocí los computadores me he inquietado por hacer que mi pc ejecute mi ideas creativas, con la colaboración de una persona (Jorge Ardila) conocí la programación y con la ayuda de mucha creatividad y un poco de lectura he conseguido hacer cosas bien interesantes, dentro de esas cosas mi tesis de pregrado (un aplicativo de Matlab para el estudio de las cónicas), además me apunté al proyecto Euler que es un muy interesante reto para quienes pensamos en algoritmo. El hecho es que después de años programando a mi modo (sentado frente al pc sin más que una idea un lenguaje y un par de libros) el proyecto Euler me ha enseñado que es mejor ponerse a pensar en la idea y explotar la creatividad no solo con el algoritmo sino generando otras ideas, en particular, anoche al enfrentarme al problema 25 del proyecto Euler me encontré una sorpresa. El problema 25 resa (en resumen):

El décimo segundo término de la série de Fibonacci, es el primero en tener tres dígitos, y la pregunta es cual es el primer término de la serie que tiene 1000 dígitos.

Como de costumbre, teniendo claro el objetivo me senté frete a mi súper pc y empecé a pensar en como conseguir la meta, mi primer pensamiento estuvo en determinar uno a uno cada término de la serie de Fibonacci y contar cada término cuantos dígitos tiene de tal forma que el programa terminaría cuando encuentre el primer término de 1000 dígitos, así lo hice, unas cuantas líneas de código, un par de pruebas y estaba todo listo, empecé a hacerlo andar, vi que se demoraba mucho pero no lo detuve porque sabía que otros de mis algoritmos se han tardado hasta más de dos horas para encontrar la respuesta, sin embargo llegó un punto en el que mi intuición más que mi impaciencia me llevó a detener el proceso, apagar e irme a descansar.

Hoy al levantarme lo primero que hice fue sentarme nuevamente junto a mi súper amigo y empezar desglosar qué es lo que estaba pasando, empecé a poner a prueba mi algoritmo aumentando poco a poco el número de dígitos 100, 200, 300, 400 y empezó a tardarse, lo detuve ya que tenía claro que el inicio de la demora estaba entre 300 y 400, nueva prueba en 350 y nada (demora...), empecé entonces aumentando dígito a dígito desde 300, 301, 302, ... 309 y todo bien pero... en 310, demora. Bien, decidí hacer al cálculo del término con 310 dígitos a pedal, entonces tome la forma general de la serie de Fibonacci y busqué calcular el primer término con 310 dígitos, respuesta INF, es decir que después del término con 309 dígitos, la suma es muy grande para que sea calculada, ups eso significa pensar en otra forma de abordar el problema.

Empecé entonces haciendo una lista de los elementos a partir del número de dígitos y me encontré con la característica que me permitió determinar mi modelo. La cosa es que determinando el número de dígitos que debe tener un término específico de la serie de Fibonnacci se puede determinar que el primer término en tener un dígito más que el anterior esta 5 posiciones más adelante por ejemplo el término con 9 dígitos esta en la posición 40 y el término en con 10 dígitos esta en la posición 45, sin embargo cada 5 dígitos aumenta solo cuatro posiciones, es decir el término 14 esta en la posición 64, después de ese término vuelve a sumar 5 posiciones por cada dígito, pero la curiosidad se puede ver más fácilmente en la siguiente tabla

# Dígitos	Posición	# Dígitos	Posición
9	40	29	136
10	45	30	141
11	50	31	146
12	55	32	151
13	60	33	155
14	64	34	160
15	69	35	165
16	74	36	170
17	79	37	174
18	84	+5=42	+24=198
19	88	+5=47	+24=222
20	93	+4=51	+19=241
21	98	+10=61	+48=289
22	103	+4=65	+19=308
23	107	+14=79	+67=375
24	112	+28=107	+134=509
25	117	+28=135	+134=643
26	122
27	127
28	131

Encontré entonces ciertos patrones que permiten modelar en comportamiento de la série de Fibonacci con respecto, por lo menos al número de dígitos de cada término, el modelo es: el primer término con cinco dígitos más que el anterior se encuentra veinticuatro posiciones adelante, pero cada catorce dígitos más, aumenta solo cuatro posiciones lo que nos lleva que crear un modelo en el que cada 28 dígitos aumenta 134 posiciones.

Con esto fue muy fácil hacer un script con el que pudiera encontrar el primer término en tener más de 1000 dígitos (1003) y el primer estar más próximo a tener mil dígitos pero por debajo de mil (975), con esto y la aplicación lógica del modelo encontrado se llegó fácil y rápido a la respuesta.

CONCLUSIÓN:
Algunas veces vale más pensar en la pregunta que en como darle respuesta.

Matlab con problemas para resolver productos grandes

Resolver problemas del proyecto Euler se ha vuelto un hábito diario y más al descubrir que la ir avanzando en la lista los problemas se ponen cada vez más interesantes, sin embargo hay algunos de solución realmente simple, la cuestión esta en darle la mejor mirada para evitar un algoritmo de fuerza bruta que consuma demasiado tiempo de procesamiento cuando no sea estrictamente necesario (aunque este tipo de algoritmos es bueno crearlos porque dejan abierto el código a variaciones interesantes).

Sin embargo, y aunque continúo resolviendo problemas, hoy quiero comentar algo muy curioso que encontré ayer al procurar resolver el problema 20 que propone determinar la suma de todos los dígitos del valor 100!, algo realmente fácil de trabajar ya que utilizando la función num2str y su inversa str2num se puede construir un vector con la cadena de vectores y sumar todas las entradas de este vector, el error apareció al obtener el resultado final ya que no coincide con el calculado en mi calculadora (Texas Instruments Voyage 200).

Después de un tratamiento riguroso de la cuestión encontré lo siguiente:

Texas Instruments Voyage 300
Resultado de la operación
50*49*48*47*46*45*44*43*42*41*40*39
Es
58150627116341760000
Matlab R2008b (GNU/Linux Debian Squeeze)
Resultado de la misma operación
58150627116341755904

y a partir del 39, el factorial de 100 cambia con respecto a los resultados obtenidos tanto en calculadora como a pedal (comprobación manual realizada).

Explicación???
Ojalá hubieran respuestas.

Dos horas de procesamiento para un número, Proyecto Euler problema 14

El problema o conjetura de Collatz, problema propuesto por el matemático Lothar Collatz en 1937 y que aún no se ha demostrado, genera una serie de número enteros que se presume siempre termina en uno, el planteamiento dice que si n es par el nuevo término es n/2, si es impar será 3n+1, así por ejemplo con el primer término el entero 13, la serie será

13 - 40 - 20 - 10 - 5 - 16 - 8 - 4 - 2 -1

El problema propuesto en el Proyecto Euler indica encontrar el entero menor a un millón que produzca la cadena de Collatz más larga, esto implica en el script que yo desarrollé, calcular la cadena de Collatz con todos los enteros menores que 1000000 y determinar cada una de ese millón de cadenas, cuantos elementos tiene, así después de algo más de dos horas de proceso me arrojó la respuesta, la cadena más larga que se genera con un entero menor a un millón contiene 525 elementos, la pregunta inquieta por cuál es el entero inicial que genera esa cadena, la respuesta la pueden encontrar corriendo el siguiente script en matlab ;-)


clc;
clear all;
i=2;j=1;
k=input('Indique el valor máximo inicial k= ');
while k~=1
    n=k;
    c(1)=n;
    while n~=1
        if rem(n,2)~=0
            n=3*n+1;
        elseif rem(n,2)==0
            n=n/2;
        end
        c(i)=n; %vector que contiene la cadena completa incluido el término inicial
        if n~=1
            i=i+1; %Indisador de los términos de la cadena
        elseif n==1
            i=2;
        end
    end
    m1(j,1)=c(1); %Vector de los valores iniciales de la cadena
    m2(j,1)=length(c); %Vector de la cantidad de términos de cada cadena
    M=[m1 m2];
    clear c;
    j=j+1;
    k=k-1;
end
disp(m1(find(m2==max(m2)),1));


PDTA: Este algoritmo hace equivale a un ataque de fuerza bruta ya que determina cada una de las cadenas de Collatz, la manera más práctica de resolverlo reduce el tiempo ejecutando la función collatz integrada en Matlab.

PROYECTO EULER - Problemas interesantes!?!?!

Hasta ahora, pasar el tiempo y los momentos en compañía de la codificación para solucionar las cuestiones planteada por el Proyecto Euler ha sido una tarea de inmensa satisfacción sobre todo porque plantea retos sobresalientes que inquietan por nuevos conceptos y conocimientos, sin embargo algunas de estas cuestiones tienen cierto sin sabor cuando parecen planteadas por salir del paso, es más es incluso ofensivo que se planteen problemas tan sin sentido, ejemplo de ello es el problema 13 que para su desarrollo más tiempo se toma el introducir los escuálidos 100 números de 50 dígitos cada uno, que lo que implica sumarlos todos para saber cuales son los diez primero dígitos de este resultado.

Personalmente prefiero los problemas que implican el generar script's para encontrar resultados con características especiales como el problema 12 en el que piden descubrir el primer número triangular que tiene más de quinientos divisores.

Pero bueno, los problemas ya están escritos así que no hay modo, dejo script que generé para resolver el problema 12, este script debe mejorarse para que sea más precisa su ejecución pero así como esta consigue el objetivo.

%Encuentra números triangulares, en particular el número triangular que (en
%este caso) tenga más de 501 divisores, por mejorar que cuando encuentre el
%primero que cumpla la condición se detenga.
d=(1:1000000);
for n=1:1000000
    T=n*(n+1)/2;
    p=find(rem(T,d)==0);
    if length(d(p))>=501
        disp(T);
        disp(length(d(p)));
    end
end


Así hasta ahora están resueltos 12 de los 13 problemas en los que he trabajado porque el problema 11 pide enseñarle al computador a resolver sopas de letras con una matriz 20X20, resolver ese problema sera sublime jejeje.

Soluciones (Proyecto Euler y otros)

Después de una larga ausencia Mauripides vuelve a estar activo, primero problemas con la conexión a internet (gracias a Dios ya solucionados) y segundo una dificultad para interpretar correctamente que es lo que el séptimo problema del Proyecto Euler propone, aquí la pregunta original

Encuentre el mayor producto de cinco dígitos consecutivos en el número de 1000 dígitos

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Lo que para mucho puede ser evidente a mi me llevó varios días comprender, esta la interpretación correcta

En el número de 1000 dígitos, seleccione quintublas de dígitos adyacentes y de esas quintuplas encontrar el mayor producto de sus cinco dígitos.

Pues después de lograr esta interpretación (ayuda incluida), desarrollar el algoritmo que lo resolviera fue algo de apenas unos segundos


n=[7 3 1 6 7 1 7 6 5 3 1 3 3 0 6 2 4 9 1 9 2 2 5 1 1 9...0]; %Vector con los 1000 dígitos
i=1;j=5;
while j<=1000 
    r(j)=prod(n(i:j)); %Crea un vector en el cual guarda todos los productos de quintublas de dígitos consecutivos 
    i=i+1; j=j+1; 
end 
disp(max(r)); %imprime el máximo de las quintublas de dígitos consecutivos

Por otro lado, después de resolver problemas de conexión, siguen adelante Universo Cultura y Alcuerno por RadioGNU así como los otros proyecto de Mauripides, por demás se esta preparando el libro Apuntes de Trigonometría y Geometría Analítica que será liberado bajo licencia creative commons.

Otros problemas ya solucionados - Proyecto Euler

Después de encontrar la solución al problema de los palíndromos, (algo que dio que pensar) el quinto problema también fue muy interesante de resolver aunque más cómodo, lo más interesante de este problema es que así como el de los palíndromos, el script generado permite poner a prueba la capacidad de procesamiento de la máquina, el quinto problema, mi laptop tardó 28 minutos en arrojar la respuesta mientras que mi desktop solamente tardó 8 minutos en conseguirlo dedicando solamente uno de sus cuatro núcleos.

El problema consiste en encontrar el número positivo más pequeño que es divisible por toda la serie de naturales del 1 al 20, la respuesta correcta es 232792560.

El script generado para conseguirlo fue el siguiente

%Encuentra el número más pequeño que es divisible por toda la serie de y
%hasta n
n=input('Escriba el número de divisores '); %dividendo inicial
d=(1:n); %vector de los divisores
r=rem(n,d); %vector de los remanentes
while any(r)==1 %si alguno de los remanentes no es cero
    n=n+1; %nuevo dividiendo
    r=rem(n,d);
end
if r==0 %cuando todos los remanentes son cero
    disp(n);
    disp(r);
end


Después de este problema apareció uno que es muy fácil de solucionar. Encontrar la diferencia entre la suma de los cuadrados de los 100 primeros naturales y el cuadrado de la suma de los 100 primeros naturales. Respuesta 25164150. Para este problema no es necesario generar ningún script, simplemente generar un vector de naturales del uno (1) al veinte (20) y utilizar la función suma.

N=(1:20) %genera un vector de naturales del uno al veinte
d=sum(N.^2)-(sum(N))^2

y eso es todo. El siguiente problema también es algo muy simple de resolver. Piden encontrar el número primo 10001, que utilizando la función primes se encuentra en un par de segundos.

Sigo abordando los problemas del proyecto Euler, voy apara el octavo problema.