Download Aliquot Sequences

Complex Systems
and
Number Theory
Teoría de números
Muchos problemas abiertos son fáciles de
formular, aunque las respuestas pueden ser
extremadamente difíciles de encontrar [Guy]:
(1) Conjetura de Golbach: todo número par es
expresable como la suma de dos primos (primos
de la forma p y p + 2) .
(2) Existen infinitos primos gemelos.
Fáciles de explorar mediante ordenador:
Búsqueda de contraejemplos, estudio de
distribuciones, récords, ...
Por su naturaleza, muchos de estos
problemas se prestan a exploración
numérica mediante ordenador. En muchos
casos, encontrar un solo contraejemplo
numérico permitiría determinar
inmediatamente la falsedad de una
conjetura. Eso ocurre incluso con la
conjetura más famosa de las matemáticas:
la hipótesis de Riemann. La existencia de
un solo cero no trivial fuera de la línea
crítica daría al traste con la hipótesis
[ZerosRiemann].
Tradicionalmente la teoría de números ha
sido territorio exclusivo de matemáticos, sin
embargo, recientemente los físicos han
comenzado ha mostrar interés en el área.
En especial, con herramientas propias de
la mecánica estadística y las ciencias de la
complejidad se están proponiendo nuevos
enfoques y alcanzando resultados
interesantes [Numbers and Physics].
Todo es número.
Pitágoras
Die ganzen Zahlen hat Gott gemacht, andere
ist Menschenwerk.
Leopold Kronecker
Siempre pensé que la teoría de números
es una ciencia experimental, y antaño, antes
de la existencia de los ordenadores, Gauss,
Ramanujan y muchos otros la consideraban así.
Richard Guy
Phase transition in a
stochastic prime number
generator.
Physical Review E 76, 010103
(R) (2007) Rapid
Communication.
Bartolo Luque, Lucas Lacasa,
and Octavio Miramontes.
Phase transition and
computational complexity
in a stochastic prime number
generator.
New Journal of Physics
10 (2008) 023009.
Lucas Lacasa, Bartolo Luque,
and Octavio Miramontes.
Number Theoretic Example of Scale-Free Topology Inducing
Self-Organized Criticality.
Physical Review Letters 101, 158702 (2008) .
Bartolo Luque, Octavio Miramontes, and Lucas Lacasa.
The first digit frequencies of prime numbers
and Riemann zeta zeros
Proceedings of the Royal Society A (2009) 465, 2197–2216.
Bartolo Luque and Lucas Lacasa.
Aliquot Sequences
Sucesiones alícuotas o alicuatorias
The function s(n)
s(n) is the sum of the proper
divisors of n [Yan] .
(1 is a proper divisor of n and n isn't)
Example:
s(10) = 1 + 2 + 5 = 7.
Abundant numbers:
s(n) > n, s(12) = 1+2+3+4+6 = 16.
Deficient numbers:
s(n) < n, s(22) = 1+2+11 = 14.
Deficient and abundant numbers first described
by Nichomachus (100 A. D.)
Perfect numbers:
s(n) = n,
s(6) = 1 + 2 + 3 = 6.
The smallest perfect numbers are:
6, 28, 496, 8.128, 33.550.336.
Today there are 43 perfect numbers known.
(Se desconoce si existen números perfectos impares).
Abundantes:
s(n) > n,
s(12) = 1+2+3+4+6 = 16.
Defectuosos:
s(n) < n,
s(22) = 1+2+11 = 14.
The smallest perfect numbers are:
6: known to the Greeks
28: known to the Greeks
496: known to the Greeks
8.128: known to the Greeks
33.550.336: recorded in medieval manuscript
8.589.869.056: Cataldi found in 1588
137.438.691.328: Cataldi found in 1588
Sequence A000396 in OEIS
Se desconoce si hay infinitos números
perfectos e, incluso, si existen
números perfectos impares,
probablemente el problema irresuelto
más antiguo de la Matemática.
Una fórmula para calcular s(n)
n  p11  ...  pk k

 

s n   1  p1  p  ...  p1  ...  1  pk  p ...  pk  n
2
1
1
2
k
pk k 1  1
p11 1  1
s ( n) 
 ... 
n
p1  1
pk  1
Ejemplo:
2 4  1 53  1 17 2  1
s (3400) 


 3400  4970
2
4
15
k
Números amigos
Parejas de números (n, m) tq.: s(n) = s(m)
Pythagoras said true friendship is comparable to the numbers
220 and 284 - this is the smallest amicable pair:
s(220) = 284 and s(284) = 220.
•220 & 284: known to the Greeks
•1184 & 1210: discovered by Paganini at age 16 in 1866
•17.163 & 18.416: discovered by Fermat in 1636
•9.363.584 & 9.437.056: discovered by Descartes in 1638
Fact: Over 1000 pairs of friendly numbers are now known!
Pedersen counted more than 10.410.218
(on December, 29th, 2005)
(Se desconoce si existen infinitos pares de amigos).
Ciclos o números pandilla
Some cycles are of higher order (so called sociable numbers).
Cycles with 4, 5, 6, 8, 9 and 28 members are known.
Other orders are possible, too.
Today (May 2006) we know 146 aliquot cycles
with higher order.
There are:
138 cycles of the order 4,
3 of the order 6,
2 of the order 8,
1 of the order 5, 9 and 28.
Números intocables de Erdös
n tales que n  s(m) para todo m.
Por ejemplo 2 y 5.
Equivalente a "jardines del edén".
En 1973 Erdös demostró que existen infinitos.
Aliquot Sequences
Sucesiones de sumas alícuotas o sucesiones alicuatorias.
An aliquot sequence is a sequence of integers,
built with the sigma function (n) .
(n) is the sum of divisors of an integer n
(include 1 and n).
Ejemplo:
(10) = 1 + 2 + 5 + 10 = 17.
s(n) is the sum of the proper divisors is:
s(n) = (n) - n
(s(n) es la suma de las partes alícuotas de n).
Ejemplo:
s(10) = 1 + 2 + 5 = 7.
Aliquot Sequences
Sucesiones alicuatorias
Iterate:
s(n), s(s(n)), s(s(s(n))) and so on.
Por ejemplo:
s(12) = 16, s(16) = 15, s(15) = 9, s(9) = 4, s(4) = 3, s(3) = 1,
s(1) = 1, s(1) = 1, ...
La sucesión alicuatoria que comienza en 12 es por tanto:
12, 16, 15, 9, 4, 3, 1, 1, 1, 1, 1, ...
s
k

( n)
kN

, s ( n)  s s
k
k 1

( n) , s ( n)  n
0
"Las sucesiones alícuotas siguen intrigando a los matemáticos
y apasionando a los amateurs después de 2000 años".
Les inattendus mathématiques
Jean-Paul Delahaye
log10 s(n)
To get a general idea a graphic
presentation of an aliquot
sequence is helpful using a
semi logarithm axis, i.e. a
linear x-axis beginning
with 0 for the index number of
the sequence and the y-axis on
a scale of decadic logarithm for
the sum of the proper divisors.
So there is a function
f: N(n) -> log10 s(n).
iteration
There are three types of aliquot sequences:
(1) Terminating sequence
Normally the end of an aliquot sequence is a prime and 1. Or
end in a perfect number.
log10 s(n)
iteration
(2) Aliquot cycle
Ending in an amicable pair (2620-2924)
Sociable numbers
(Ciclos o números pandilla)
Some cycles are of higher
order (so called sociable
numbers).
Ending in an aliquot 4-cycle
Cycles with 4, 5, 6, 8, 9 and
28 members are known.
Other orders are possible,
too. Today (May 2006) we
know 146 aliquot cycles
with higher order.
Ending in the aliquot 28-cycle
Catalan Conjecture
This was first published by the Belgian
mathematician Eugène Catalan in the year
1887-88. Leonard Eugene Dickson
extended in 1913 the so called
Catalan conjecture:
"Each aliquot sequence
ends in one, in a perfect
number or in an aliquot
cycle".
Up to now it is not possible to certify the
Catalan conjecture. Each confluence of
two sequences gives some more hope,
but it's no proof of the conjecture, it's only
some work on the way to possible solution.
Eugène Catalan
(3) open-end sequence
276
s (n)
n
Several sequences are not computed up to their end.
They are increasing and no one knows if they will end or not.
The smallest start-up number (or key-number, beginning
number) of such a so-called open-end sequence is 276.
Hay una conjetura opuesta a la de Catalan que
dice que toda sucesión alícuota que comienza en
un número par va al infinito, excepto un número
finito de casos excepcionales...
H. Lenstra demostró que para todo entero k puede
construirse una sucesión alícuota creciente de k
pasos.
There are 5 open-end sequences
in the interval [1, 1000]
with the key numbers
276, 552, 564, 660 and 966.
There are 80 open-end-sequences
in the interval [1, 104].
There are now 911 open-end
sequences in [1, 105] and
9472 open-end-sequences
in [1,106].
Any progress in calculation can
reduce these numbers.
OE-sequence with deep minimum
La primera secuencia para la que se tuvo dudas
sobre su finalización comenzaba con n = 138.
Fue el matemático D. H. Lehmer quien encontró que
s177(138) = 1. Para números n < 1000, Lehmer no fue
capaz de encontrar el final de las secuencias que
comenzaban por 276, 552, 564, 660, 840 y 966.
Más tarde A. Guy y R. K. Guy encontraron que
s747(840) = 1. La existencia de final para el resto de
los cinco números (the “Lehmer five”), a pesar del
gran esfuerzo computacional que se ha dedicado (se
han alcanzado valores mayores que 10132 a lo largo
de las sucesiones), es desconocida todavía.
En la literatura las secuencias para las que se
desconoce su final se denominan open-end
sequences y sus números iniciadores, key numbers.
Así, el key-number más pequeño que genera una
open-end sequence es 276.
De manera similar a las “Lehmer five”, las secuencias
dudosas que comienzan en el intervalo [1000, 2000]
se conocen como secuencias de Godwin y en este
momento son 12 (“Godwin twelve”). En la tabla 1 se
recogen las open-end sequences conocidas hasta el
momento, clasificadas por el intervalo al que
pertenecen sus key numbers y los límites de
computación de escrutinio que se han alcanzado
hasta el momento.
interval
number of OEsequences
limits of
computation
[1, 1000]
5
> 10^132
[1, 10000]
80
> 10^110
[1, 50000]
444
> 10^100
(50000, 10^5]
467
> 10^100
[1, 100000]
911
> 10^100
(100000, 200000]
974
> 10^80
(200000, 300000]
936
> 10^80 /
10^90
(300000, 400000]
877
> 10^80
(400000, 500000]
917
> 10^80
(500000, 600000]
971
> 10^80
(600000, 700000]
958
> 10^80
(700000, 800000]
961
> 10^80
(800000, 900000]
982
> 10^80
(900000, 10^6]
985
> 10^80
Si la conjetura de Catalan-Dickson es cierta,
computaciones posteriores irán reduciendo el
número de open-end-sequences al encontrar que
terminan en puntos fijos o ciclos.
El problema está en lo enorme que pueden llegar a
ser los números intermedios que se necesitan
factorizar para alcanzar el fin de la secuencia.
Por ejemplo, recientemente Benito et al. [Benito1]
establecieron un nuevo récord al demostrar que el
key number 3630 termina en 1, s2642(3630) = 1,
después de alcanzar un máximo s1263(3630) con
¡100 dígitos!
Normally an aliquot sequence ends in a prime.
Different sequences can come together and end in
the same prime. All these side sequences are called
a prime family.
New calculations occasionally lead to a confluence of two
former different aliquot sequences into one family.
About 1% of all integers are beginning numbers
(key numbers) of an open-end sequence.
This is an empirical result.
http://www.aliquot.de/aliquote.htm
http://www.aliquot.de/index.htm
Tipos de sucesiones
(1) La sucesión termina en 1
(siendo el número anterior un primo).
(2) La sucesión llega a un número perfecto
(y permanece constante).
(3) Llega a un par amigo o a un ciclo.
(4) No está acotada (¿?).
Algunos matemáticos no están de acuerdo con la
conjetura de Catalan-Dickson y piensan que
existen sucesiones alicuatoarias no acotadas.
Una conjetura alternativa se debe a Guy y
Selfridge [Guy-Self] y dice que existen muchas
secuencias que van al infinito, de hecho casi
todas las que empiezan por un número par.
Sequence = Aliquot chain
69
27
Podemos reinterpretar
las sucesiones alicuatorias
como cadenas dirigidas...
13
1
Aliquot network
69
93
27
35
Estudio de las propiedades
de la red:
13
Distribución de conectividad
Clustering
Distancia media dependiente
del tamaño
etc
1
Pero, ¿añade algo
nuevo ver la cuestión
en forma de red?
Aliquot network
Un voluntario para dibujar el
grafo de los 100 primeros
números
No puede haber cambio de paridad entre n y s(n)
excepto si n es un cuadrado (n = a2) o el doble de
un cuadrado (n = 2a2) (pero estos números se
"rarifican" a medida que n crece).
Jean-Luc Garambois conjecture (por argumentos
heurísticos) que la media de s(n)/n converge a
(π2 − 6) / 6 = 0.644934...
Resultado a favor de la conjetura de Catalan
porque en media es menor que 1.
Pero s(n)/n tiende a 1,055307 si lo hacemos para
los n pares hasta 10.000 y a 0,2337 para los n
impares hasta 10.000...
Jean-Luc Garambois ha demostrado que todos
los antecedentes m, s(m) = n, son inferiores a
n2 + 2.
Estadísticamente los antecedentes aumentan con
n si n es impar y son pequeños si n es par.