Cribas y barridos 2. Otros ejemplos

Debemos insistir en esta segunda entrega del tema de barridos en que nuestro objetivo es la forma de presentar hechos y conceptos, y en ningún momento demostrar o comprobar.

Desarrollamos otros dos ejemplos:

Primos que se descomponen en suma de dos cuadrados

Sabemos que si un primo es de la forma 4k+1 se podrá descomponer en suma no trivial de dos cuadrados, siendo esto imposible si es de la forma 4k+3. Podríamos comprobar este hecho mediante un barrido.

Obtenemos una lista de primos y los acompañamos con un símbolo, y al lado su resto módulo 4.

Después engendramos todas las sumas de dos cuadrados en un rango adecuado, que puede ser la raíz cuadrada del último primo de la lista, o algo mayor por precaución ante redondeos. Para cada suma buscamos en la lista de primos si coincide con ella. En caso positivo borramos el símbolo, y quedarán como resultados negativos los que posean resto 3 respecto a 4.

Por si deseas profundizar, copiamos el código empleado en OpenOffice Calc, que puedes adaptar a tu caso cambiando la hoja, filas y columnas y también a Excel.

sub primos2cuad
dim i,j,k, rango
rango=15
for i=1 to rango
for j=1  to i
a=i^2+j^2
for k=1 to 50
if StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(3,k).value=a then
StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(4,k).string=" "
end if
next k
next j
next i
end sub

Conjetura de Goldbach

Cuando se conoce por primera vez la conjetura de Goldbach la idea inicial es la de ir seleccionando números pares para buscarles su descomposición de suma de dos primos. Podríamos cambiar la perspectiva: engendrar todas las sumas de dos primos en un rango y cotejar con una lista de números pares para ver si alguno de ellos es resultado de esa suma. En ese caso, como venimos haciendo, le borraríamos el símbolo que le acompañe.

Así que comenzamos con una lista de pares que comience en 4:

Después engendramos todas las sumas de dos primos impares con rango 200.  Para ello creamos la macro Goldbach, cuyo código se ofrece más abajo, y al ejecutarla, ¡zas!, todas las caritas desaparecen y queda comprobada la conjetura.

Código de la macro goldbach

sub goldbach
dim i,j,k, rango,p,q


rango=200
for i=3 to rango
if esprimo(i)=1 then
for j=1  to i
if esprimo(j)=1 then
a=i+j
p=int(a/40)
q=a-p*40
StarDesktop.CurrentComponent.sheets(2).GetCellByPosition(3+2*p,2+q/2).string=" "
end if
next j
end if
next i
end sub

Cribas y barridos 1. Números intocables

Dos características de la hoja de cálculo apreciamos mucho en este blog. Una es que permite estudios de nivel elemental y medio sin gran preparación previa en los trabajos y la otra su facilidad de presentación de estructuras y procesos matemáticos. Evidentemente, no  la recomendamos para estudios universitarios, aunque también podría dar juego, pero su uso del formato en coma flotante la imposibilita para el tratamiento exacto de grandes números.

Una posibilidad muy atractiva es la de presentar en pantalla resultados de cribas de números y barridos exhaustivos. Lo explicaremos con un ejemplo, el de los números intocables.

Se llaman así a aquellos números que no pueden ser el resultado de la suma de las partes alícuotas de otro número, es decir, de la suma de sus divisores propios. Por ejemplo, el 88 no coincide con ningún resultado de sumar los divisores propios de ningún otro número natural. Si efectuamos un barrido de los N primeros números y anotamos el resultado de esa suma, nunca resultará 88.

Los primeros números intocables son

2, 5, 52, 88, 96, 120, 124, 146, 162, 188, 206, 210, 216, 238, 246, 248, 262, 268, 276, 288, …

http://oeis.org/A005114

Puedes aprender algo sobre estos números en la Red. Por ejemplo en http://mathworld.wolfram.com/UntouchableNumber.html, pero tampoco dan mucho de sí. Se aprenden sus propiedades en pocos minutos. Aquí nos va a interesar su generación y presentación atractiva con hoja de cálculo. Lo haremos con estos pasos:

(1) Presentemos los primeros números naturales en una pantalla de hoja de cálculo, y junto a cada uno escribamos cualquier símbolo, por ejemplo una carita sonriente:

La idea es que cuando encontremos un número que coincida con una suma de partes alícuotas de otro se borre la carita, y al final sólo la conserven los números intocables.

(2) Implementamos la función alícuota(n)

public function alicuota(n)
dim i,s
s=0
for i=1 to n/2
if n/i=n\i then s=s+i
next i
alicuota=s
End function

Esta función recorre los posibles divisores propios, con la prueba n/i=n\i, que equivale a afirmar que el cociente n/i es entero  que por tanto i divide a n. El resto se entiende fácilmente.

(3) Efectuamos un barrido de todos los posibles resultados de la función alícuota(n). Aquí hay un punto delicado y es el rango de cálculo que debemos elegir. Si deseamos encontrar los intocables menores que 100 deberemos buscar resultados hasta casi el 10000. El problema radica en que si un número es del tipo p+1 con p primo, será el resultado de la suma de divisores propios de p², como puedes razonar si te paras a pensar en ello. Como el máximo primo del 1 al 100 es 97, habrá que llegar más allá de 97²=9409.

La idea es que cada vez que salga una suma que equivalga a un número de nuestra tabla le borramos la carita sonriente, simplemente escribiendo sobre ella un espacio en blanco. Esto es muy dinámico, y si lo presentas a unos alumnos se darán cuenta de que sólo los números intocables se libran de que le borren la carita. Es una forma activa de comprender que estamos cribando números.

Para que todo funcione hay que encajar cada número en su fila y columna correspondiente para que localice la carita. Si cada columna contiene 20 números, hallaremos el cociente entero del resultado entre 20 y nos dará la columna y el resto resultante, la fila.

Lo puedes ver en este código (comentarios en cursiva):

sub intocables
dim i,f,c,p


for i=1 to 10000
p=alicuota(i) ‘ p es un resultado posible
if p<=100 then ‘restringimos p a la tabla que hayamos planteado
c=p\20  ‘se calcula la columna
f=p-20*c  ‘se calcula la fila
StarDesktop.CurrentComponent.sheets(3).GetCellByPosition(3+2*c,2+f).string=" "
‘se escribe un espacio en blanco en la celda. En el ejemplo se supone que trabajamos en la hoja 4 y que la tabla comienza en C3. Esta línea de código está adaptada a Calc. En Excel sería
ActiveWorkbook.Sheets(4).Cells(3+f,4+2*c).Value = " "
end if
next i
end sub

Al principio desaparecen las caras a gran velocidad, para ralentizarse después bastante. Las últimas en desaparecer son las de 80, 84 y 98 (¿por qué?). Al final queda así:

Quedan como supervivientes los números intocables.

¿Qué ocurriría si exigiéramos que no coincidieran con la suma de divisores propios, sino con la suma de todos (función SIGMA)? Nos daría una lista (más numerosa) de números intocables de otro tipo. Te dejamos el encargo.