Hoy os traigo un tipo de números curiosos tanto por su definición como por la historia de su denominación: los números de Smith.
Vamos con la definición de este tipo de números:
Un número de Smith es un número natural compuesto que cumple que la suma de sus dígitos es igual a la suma de los dígitos de todos sus factores primos (si tenemos algún factor primo repetido lo sumamos tantas veces como aparezca).
Con esta definición es sencillo ver que el primer número de Smith es el
:

Y el siguiente es el
:

Pero hay muchos más, de hecho hay infinitos números de Smith. Otro ejemplo, esta vez con un número más grande,
:

Los números de Smith fueron presentados por el matemático Albert Wilanski en 1982. Pero, ¿por qué no llevan su nombre? Muy sencillo. Al parecer el número de teléfono de teléfono del cuñado de Wilanski era 493-7775 y Albert se dio cuenta de que el número
es un número de este tipo:

El nombre de este tipo de números se debe a que el cuñado de Wilanski (que no tenía nada que ver con las matemáticas) se llamaba Harold Smith. Se vuelve a cumplir la sentencia de Klein.
En el momento en el que aparecieron los números de Smith éste era el mayor número de este tipo conocido. Pero a partir de aquí comenzaron a aparecer artículos dando propiedades y ejemplos mayores que el citado
. Por ejemplo, en 1983 Oltikar y Wayland descubrieron que si
es un número primo repuit (es decir, con todos sus dígitos iguales a uno), entonces el número
es un número de Smith. Pero no es el único caso. Descubrieron muchos más números tales que multiplicados por un repunit primo dan siempre un número de Smith. Por ejemplo los números $1540, 1720, 2170, 2440, 5590$ y
también tienen esa propiedad. En la sucesión-pedia tenéis la lista de los mismos.
En 1984 Pat Costello encontró 75 nuevos números de Smith de la forma
, siendo
un primo pequeño y
un primo de Mersenne. El mayor de ellos (con 65319 dígitos) fue el siguiente:

En 1986 se presentó otro método distinto para generar números de Smith con el que se encontró, por ejemplo, el siguiente número de Smith:

Pero no fue el único Se encontraron números realmente colosales, por ejemplo un número de Smith con 2592699 dígitos.
Pero fue en 1987 cuando se produjo el descubrimiento más importante sobre este tipo de número. Wayne Mc Daniel descubrió que hay infinitos números de Smith. De hecho descubrió más cosas. Introdujo los k-números de Smith, que son los que cumplen que la suma de los dígitos de los factores primos es el producto de
por la suma de los dígitos del número y demostró que los k-números de Smith son infinitos, para todo
.
En este mismo año también se definieron los números de Smith palindrómicos (es decir, capicúas), como el
, o los hermanos de Smith, que son parejas de números de Smith consecutivos, como el
y el
o el
y el
. A partir de esto se han descubierto tripletes de Smith (por ejemplo,
y
), conjuntos de cuatro consecutivos (el más pequeño de este tipo es el formado por los números
y
), y así sucesivamente.
Para terminar os dejo la lista de números de Smith de la sucesión-pedia y el mayor número de Smith conocido hasta la fecha:

donde
es el primo repunit compuesto por 1031 unos.
Fuentes:
- La maravilla de los números, de Clifford A. Pickover.
- Fascinating Smith Numbers: Sección de la web de Shyam Sunder Gupta con mucha información sobre los números de Smith.
Autor: ^DiAmOnD^ | Publicado el 19 de October de 2009 | Comments Off
Categorías: Curiosidades, Números enteros
Este artículo es una colaboración enviada por fede a gaussianos (arroba) gmail (punto) com.
Este post sobre una curiosa propiedad de determinadas particiones en dos conjuntos de algunos conjuntos finitos de números me recordó una curiosa propiedad de cualquier partición en dos conjuntos infinitos del conjunto de todos los números naturales que leí en algún libro de Honsberger.
Sea
una secuencia cualquiera no decreciente,esto es,
, de enteros no negativos.
La función
que da el número de términos de la secuencia
que son menores o iguales que
, define una nueva secuencia no decreciente de enteros no negativos que para la secuencia anterior
resulta ser 
A esta segunda secuencia, cuyos términos cuentan los términos de la primera menores o iguales que
, la llamamos secuencia contadora de la primera secuencia.
Como la secuencia contadora es una secuencia no decreciente de no negativos, podemos obtener a su vez la secuencia contadora de esta secuencia contadora y así sucesivamente.
Pero sucede que:
Dada cualquier secuencia no decreciente de enteros no negativos, la secuencia contadora de la secuencia contadora es la secuencia inicial.
La curiosa conexión con las particiones de números está en:
Si tomamos dos secuencias de forma que una sea la secuencia contadora de la otra, y sumamos vectorialmente a cada una de ellas la secuencia de todos los naturales
, resulta una partición
de los números naturales.
En el caso de las secuencias anteriores
y
resulta la partición:


Recíprocamente, si partimos en dos subconjuntos infinitos el conjunto de todos los naturales y restamos la secuencia
de los naturales de las dos secuencias resultantes de la partición, obtenemos dos secuencias no decrecientes de enteros no negativos que son cada una contadora de la otra.

Los resultados anteriores tienen una demostración visual sin palabras, debida a Dijkstra.
Si busca, el lector encontrará representadas en la figura adjunta las 4 secuencias que hemos usado como ejemplo:




y la secuencia
, de los números naturales.
Y, tras unos momentos de reflexión, verá que la posibilidad de construir una figura análoga para cualquier partición en dos de los naturales da una demostración de los hechos anteriormente expuestos.
Autor: ^DiAmOnD^ | Publicado el 8 de October de 2009 | Comments Off
Categorías: Curiosidades, Números enteros
Introducción
El lunes pasado, en el post donde se desarrollaba un método para resolver ecuaciones diofánticas lineales, comentábamos la existencia de un método para el cálculo del máximo común divisor que no desarrollamos. Dicho método se atribuye a Euclides y este post va a servir para presentarlo.
El algoritmo de Euclides
El problema inicial es el siguiente:
Encontrar el máximo común divisor entre dos números enteros positivos
y
.
Todos conocemos el método que se nos enseña en el colegio para ello:
- Descomponemos en factores primos los dos números y tomamos los factores comunes a ambos con el menor exponente con el que aparezcan.
Aunque es un método bastante útil y sencillo para conseguirlo que queremos tiene un evidente problema: si los números son muy grandes, o si sus factores primos lo son, la cosa se complica ya que el cálculo de la descomposición se torna bastante tedioso.
Por ello es interesante tener a mano otro método para casos en los que el procedimiento inicial se complique. El llamado algoritmo de Euclides nos servirá.
El algoritmo de Euclides nos dice lo siguiente:
Para calcular el máximo común divisor entre dos números enteros positivos
y
dividimos el más grande, digamos
, entre el más pequeño, digamos
. Esta división nos proporcionará un cociente,
, y un resto,
. Si
, entonces
. Si no es cero dividimos el divisor,
, entre el resto,
, obteniendo otro cociente,
, y otro resto,
. Si
, entonces
. Si no es cero volvemos a dividir divisor entre resto. Y así sucesivamente.
Esto es, el máximo común divisor entre
y
es el último resto distinto de cero que obtengamos con el procedimiento anterior.
Si analizamos el algoritmo de Euclides se ve claramente que necesitamos demostrar que el máximo común divisor entre
y
es igual al máximo común divisor entre
y
. Así esa igualdad se mantendrá durante todo el proceso y llegaremos a que el último resto distinto de cero es el máximo común divisor de los dos enteros positivos iniciales. Vamos a demostrar este hecho para después ilustrar el algoritmo con un ejemplo:
Teorema:
- El máximo común divisor de dos números enteros positivos
y
, con
, coincide con el máximo común divisor de
y
, siendo
el resto que se obtiene al dividir
entre
.
Demostración:
Sean
y
. Vamos a demostrar que
.
Por definición de máximo común divisor, se tiene que
es un divisor tanto de
como de
. Por tanto
y
.
Por otro lado, por el algoritmo de la división se tiene que
, con
(1)
de donde llegamos a

Por tanto
es un divisor de
. Como ya teníamos que también es un divisor de
entonces debe dividir a su máximo común divisor, esto es,
es un divisor de
.
Por otro lado,
es un divisor tanto de
como de
. Por ello se tiene que
y
. Sustituyendo estas dos igualdades en (1) obtenemos lo siguiente:

Por tanto
es un divisor de
. Como también lo era de
debe ser un divisor de su máximo común divisor, es decir,
es un divisor de
.
Como
es un divisor de
y
es un divisor de
no queda otra opción más que
. Por tanto el algoritmo de Euclides funciona. 
Ejemplos de aplicación del algoritmo
En esta sección del artículo vamos a ver un par de ejemplos de aplicación del algoritmo de Euclides. Vamos con ellos:
Cálculo de 
Como hemos explicado antes dividimos el número mayor entre el menor; si el resto no es cero dividimos el divisor entre el resto; y así sucesivamente hasta que llegamos a un punto en el que el resto es cero. Los resultado de las divisiones (expresados como dividendo=divisor · cociente + resto) son:
Como marca el *, se tiene que
, el último divisor que no es nulo.
Cálculo de 
Vamos con el segundo ejemplo, con números más grandes en este caso. Expresamos los resultados parciales de la misma forma que en el ejemplo anterior:
Vemos que aunque los números son bastante mayores que los anteriores el número de operaciones necesarias para el cálculo es el mismo. Concluyendo, tenemos que, como marca el *,
.
Autor: ^DiAmOnD^ | Publicado el 5 de October de 2009 | Comments Off
Categorías: Aprenda como, Matemáticas discreta, Números enteros
Introducción
El pasado lunes presentábamos un método de resolución de ecuaciones diofánticas lineales. También vimos que no sólo existen este tipo de ecuaciones diofánticas: dependen de los exponentes de sus variables. Por desgracia cuando los exponentes no son 1 (es decir, cuando no son lineales) no tenemos un procedimiento general para resolverlas. Esto lo sabemos desde 1970, cuando Yuri Matiyasévich consiguió demostrar (después de 20 años de trabajo) que no es posible encontrar un algoritmo que nos diga si una ecuación diofántica tiene soluciones o no las tiene. Este fue uno de los 23 problemas, concretamente el décimo, que David Hilbert propuso en el año 1900.
Después de este mazazo vamos a alegrar un poco el asunto: aunque no tengamos un procedimiento para todas las ecuaciones diofánticas sí que sabemos resolver algunos casos particulares de ellas. El artículo de hoy trata sobre uno de estos casos: la ecuación de Pell.
(Leer el resto del post)
Autor: ^DiAmOnD^ | Publicado el 1 de October de 2009 | Comments Off
Categorías: Historia, Números enteros
Este artículo ha sido promovido en Menéame. Si te ha gustado y quieres votarlo entra aquí y menéalo.
Motivación
Supongamos que nos encontramos el siguiente problema:
Un hombre va a una tienda de ropa y compra 12 trajes, unos negros y otros grises, por 1200 €. Si los trajes negros valen 30 € más que los grises y ha comprado el mínimo posible de estos últimos, ¿cuántos trajes ha comprado de cada color?
Vamos a plantearlo:
La ecuación queda:

Haciendo cuentas nos queda lo siguiente:

Si estabais pensando que nos iba a quedar un sistema de ecuaciones sencillo de resolver estáis equivocados. Nos ha quedado una única ecuación con dos incógnitas. ¿Nos faltan datos? No. Podemos resolverla. Bienvenidos al maravilloso mundo de las ecuaciones diofánticas.
(Leer el resto del post)
Autor: ^DiAmOnD^ | Publicado el 28 de September de 2009 | Comments Off
Categorías: Aprenda como, Matemáticas discreta, Números enteros
La aventura de buscar qué números enteros positivos son primos es tan antigua como las propias matemáticas. Desde siempre los números primos han fascinado a los matemáticos. Los números primos, los átomos a partir de los cuales se pueden obtener todos los números naturales. Para no fascinar al personal.
Esto conlleva que desde siempre se hayan intentado desarrollar métodos para la búsqueda de los números primos. Quizás el más antiguo de los que se conocen sea la Criba de Eratóstenes, que consiste en lo siguiente:
Escribimos todos los números naturales desde el 2 hasta un cierto
, por ejemplo hasta 120 (como aparece en la figura, tomada de la Wikipedia en español). Nos quedamos con el 2, que es primo, y tachamos todos los múltiplos de 2. Nos quedamos con el siguiente número no tachado, que en este caso es el 3, y lo declaramos como primo, tachando después todos los múltiplos de 3. Seguimos de esta forma, quedándonos con el primer número no tachado como primo y tachando sus múltiplos. Conseguimos así descartar todos los compuestos y localizar todos los primos.
Interesante método, pero con un gran inconveniente: el proceso es larguísimo si
es muy grande. Por ello no serviría para localizar primos grandes, ya que costaría demasiado aplicar el método hasta el final. Imaginaos que quisiéramos determinar si un número de ocho cifras es primo…las dimensiones del cuadro y el tiempo que tardaríamos en terminar no son ni mucho menos asumibles.
(Leer el resto del post)
Autor: ^DiAmOnD^ | Publicado el 31 de August de 2009 | Comments Off
Categorías: Números enteros, Números primos
Introducción
Mucho se ha hablado en Gaussianos de Fermat y su último teorema. Pero que yo recuerde todavía no se ha mostrado ninguna demostración relacionada con él. En este artículo vamos a ver la de un caso, concretamente
, que a la postre resulta determinante para la demostración global del teorema.
Primer paso: demostrar el teorema para n=4

Por si alguien no sabe todavía de qué va este último teorema vamos a enunciarlo otra vez:
No existen enteros positivos
y
tales que
para n > 2.
En esta parte del artículo vamos a demostrar que este resultado es cierto para
, es decir:
Teorema: No existen enteros positivos
y
tales que
.
Demostración:
Vamos a utilizar el método de reducción al absurdo. Supongamos que existen
y
tales que
. Podemos suponer que cada par de ellos son primos relativos (ya que si dos de ellos tuvieran un divisor común el otro también debería tenerlo y por tanto podríamos simplificarlo). Esto implica que
y
son una terna pitagórica (es decir, terna de números cuyas longitudes son los lados de un triángulo rectángulo), por lo que, intercambiando los papeles de
e
si fuera necesario, tenemos lo siguiente (echad un ojo al artículo sobre ternas pitagóricas enlazado en esta misma frase si no sabéis por qué):



donde
y
tienen distinta paridad y cumplen que
.
Pero la segunda ecuación se puede escribir como
y, como
y
son primos relativos, se sigue que
y
forman una terna pitagórica primitiva. Por lo tanto
es impar y, como
y
tienen distinta paridad,
es par.
De aquí:



donde
y
son primos relativos de paridad opuesta y
. Así:

Esto demuestra que
es un cuadrado (exactamente el cuadrado de
). Pero
y
son primos relativos, ya que si un primo
divide a
debería dividir también a
o a
, pero no a ambos, ya que
y
son primos relativos. Por tanto no puede dividir a
.
En consecuencia
y
deben ser ambos cuadrados. Pero si
es un cuadrado deben ser
y
los dos cuadrados (al ser primos relativos). Digamos entonces que
y
. Por tanto
es un cuadrado. Pero esto es suficiente para aplicar el método del descenso infinito, ya que la única suposición que se hizo al principio es que
era un cuadrado, no una cuarta potencia. En otras palabras, si
e
son enteros positivos tal que
es un cuadrado la demostración anterior nos permite encontrar otros dos enteros positivos,
e
, tales que
es un cuadrado. Además:

.
Por tanto tenemos una sucesión decreciente infinita de enteros positivos, lo cual es imposible. Es decir, este razonamiento prueba que el último teorema de Fermat se cumple para
.
¿Qué tiene de especial el caso
?
Partiendo de lo que acabamos de demostrar se tiene que
no se puede dar para
y
enteros positivos cuando
es un entero positivo, ya que
,
y
serían solución de
, pudiendo aplicarles entonces la demostración anterior. Por tanto el último teorema de Fermat es cierto para todo
múltiplo de 4.
Ahora, un entero positivo
que no es múltiplo de 4 no es una potencia de 2. Entonces debe ser divisible por algún primo
, digamos
. Por tanto es obvio que para demostrar que
es imposible será suficiente demostrar que
es imposible. Esto es:
Una vez que el último teorema de Fermat ha sido probado en el caso
la demostración del caso general se reduce a probarlo en el caso en el que
es primo.
Esta es la importancia del caso
: demostrando el teorema sólo en este caso permite tenerlo demostrado para todos los no primos.
Ahora sólo faltaría demostrarlo para los exponentes números primos.
Autor: ^DiAmOnD^ | Publicado el 20 de August de 2009 | Comments Off
Categorías: Demostraciones, Números enteros, Números primos, Teoremas
En este artículo os traigo otra de esas paradojas para la intuición que en realidad están perfectamente demostradas matemáticamente (tipo la de Banach-Tarski). Me refiero, como podéis ver en el título, a la sucesión de Goodstein.
Introducción
Tomamos un número natural cualquiera, por ejemplo el
(que ya apareció por aquí hace un tiempo). Vamos a expresarlo en base 2:
Expresemos ahora cada uno de los exponentes también en base 2:
Esto que hemos hecho se denomina expresar un número natural en su forma normal de Cantor en base
.
Ahora aplicamos lo que podríamos llamar un salto de base, que en una situación así es básicamente sustituir todas las ocurrencias de
por
, y después restamos 1 al resultado. Por tanto, en este caso sustituimos todas las apariciones del número 2 por el 3 y restamos 1:
Utilizando que
(ver 1 al final del artículo) obtenemos:
El resultado es un número de 15 cifras, concretamente el
. La cosa ha crecido bastante.
Volvemos a realizar la misma operación: ahora sustituimos todas las apariciones del número 3 por el 4 (los números menores que 3 quedan igual) y restamos 1:
Obtenemos el número
que tiene 156 cifras. La cosa sigue subiendo.
Otra paso más: ahora saltamos a base 5 y restamos 1:
Llegamos al número
que tiene la friolera de 2189 cifras. Vamos a realizar la misma operación una vez más (sustituimos cada 5 por un 6 y restamos 1):
Como
obtenemos el número:
que alcanza la nada despreciable cantidad de 36311 cifras.
Si continuamos realizando la misma operación los números resultantes son cada vez más grandes. ¿Dónde terminará la cosa? Pues…
El teorema de Goodstein
…veamos dónde termina:
Teorema: (de Goodstein)
Toda sucesión de Goodstein creada con el procedimiento anterior termina en cero.
¿Cómo? ¿Que toda sucesión de Goodstein, comience en el número que comience, termina en el número cero? Pues sí, todas terminan en cero. De hecho la demostración no es excesivamente complicada. En la Wikipedia inglesa podéis verla.
Para imaginar por qué ocurre esto podéis coger un número pequeño, por ejemplo el 3, y crear su correspondiente sucesión de Goodstein. Quedaría algo así:

Sustituimos cada 2 por un 3 y restamos 1:

Sustituimos cada 3 por un 4 y restamos 1:

Sustituimos cada 4 por un 5 y restamos 1:

Sustituimos cada 5 por un 6 y restamos 1:

Sustituimos cada 6 por un 7 y restamos 1:
Si escogemos para comenzar el número 4 la cosa se alarga bastante más. La secuencia comenzaría con los resultados
y llegaría hasta un número de ¡121210695 cifras! desde donde comenzaría a decrecer hasta terminar irremediablemente en el cero.
Como curiosidad comentar que se sabe que el teorema de Goodstein no puede probarse con la aritmética de Peano, hecho que probaron Kirby y Paris en 1982. Ellos interpretaron el teorema de Goodstein como una hidra, creando el juego llamado hydra game, que parte de una hidra (un árbol, hablando en término de grafos) y consiste en ir cortándole cabezas. Las reglas del juego nos dicen que con ciertos cortes la hidra hará que le crezcan cierto número de cabezas y con otros la hidra se mantendrá tal cual quede después del corte. En esta web podéis ver tanto la explicación del juego como el enlace a un applet de java donde podéis jugar al hydra game. La analogía con el teorema de Goodstein es bien sencilla: por muy largo que sea el proceso (que lo será por muy pequeño que sea el número inicial de cabezas) siempre se llega a cortar todas las cabezas de la hidra.
Fuentes:
1: En ese paso se usa la siguiente propiedad:
Es sencillo comprobar que este hecho es cierto simplemente operando la parte derecha de la igualdad.
Autor: ^DiAmOnD^ | Publicado el 18 de May de 2009 | Comments Off
Categorías: Curiosidades, Números enteros, Teoremas
Introducción
El teorema de Wilson es un resultado de teoría de números relacionado con la primalidad de un número entero positivo. Fue atribuido a John Wilson por su profesor Edward Waring. Éste último comentó que Wilson había dejado anotado este resultado en un cuaderno pero que no lo había demostrado (os suena esta historia, ¿verdad?). El propio Waring tampoco pudo hacerlo y tuvo que ser Lagrange en 1771 quien dio la primera prueba.
En esta entrada vamos a dar una sencilla demostración que utiliza propiedades más o menos elementales de teoría de números.
El teorema de Wilson
Teorema: Sea
un número entero mayor que 1. Entonces
es primo si y sólo si

Demostración:
De forma sencilla puede comprobarse que este resultado es cierto para
y para
. Supongamos entonces que
.
Para demostrar la implicación de derecha a izquierda (si
entonces
es primo) vamos a demostrar su contrarrecíproco, es decir, vamos a demostrar que si
es compuesto entonces no se cumple esa igualdad:

Supongamos que

es compuesto. Entonces sus divisores positivos se encuentran entre los enteros

. Por tanto es claro que

>1$. En particular

tiene algún divisor

.
Supongamos ahora que el resultado es cierto, es decir, que
. Como
divide a
entonces
también divide a
y, por la congruencia,
divide a
. Por tanto
divide a 1, hecho que nos lleva a una contradicción con la condición
. En consecuencia la implicación de derecha a izquierda es cierta.
Supongamos ahora que
es primo. Por tanto todos los enteros
son primos relativos con
. Por otra parte ese conjunto de números forma un grupo con la multiplicación, en concreto el grupo
de los enteros módulo
(en realidad, al ser
primo ese conjunto es un cuerpo, pero ahora sólo nos interesa su condición de grupo con esa operación). Entre otras cosas eso significa que para todo
existe un único
tal que
. También por ser
primo se tiene que
si y sólo si
ó
, es decir,
y
son inversos el uno del otro. Por tanto para cualquier otro elemento del grupo distinto de éstos se tiene que su inverso también es distinto de éstos. En consecuencia podemos agrupar el resto de elementos por parejas (cada uno junto a su inverso) para que se cumpla lo siguiente:
Esto es,
. Multiplicando ahora a ambos lados por
y utilizando que
obtenemos el resultado buscado.
Utilidad del teorema
El teorema tiene principalmente valor teórico ya que en la práctica es relativamente complicado calcular
para valores grandes de
. Por eso generalmente antes que este teorema suelen usarse otros tests de primalidad, como el pequeño teorema de Fermat.
De todas formas es útil para generar a partir de él fórmulas de primos, es decir, fórmulas que generar números primos (en Gaussianos ya vimos algo así con los números primos pseudogemelos). Aunque, como en el caso anterior, suelen ser fórmulas poco prácticas por lo costoso que es calcular
para
muy grande.
De todas formas, como dije antes, la belleza del resultado reside en su valor teórico. Y algunas, en ocasiones, tenemos suficiente con ello.
Fuentes:
Autor: ^DiAmOnD^ | Publicado el 20 de October de 2008 | Comments Off
Categorías: Demostraciones, Números enteros, Números primos, Teoremas
Sive, en este comentario, ha dado una demostración informática de que un número de Mersenne con exponente compuesto es también compuesto. En este post voy a dar yo una más matemática.
Definición
Un número de Mersenne es un número
de la forma
, con
.
Teorema
Todo número de Mersenne
con
compuesto es también compuesto.
Demostración
Si
es compuesto se puede descomponer como producto de al menos dos factores mayores que
. Supongamos entonces
, con
.
Sabemos que
. Además
. Tomando
y
en la igualdad anterior se tiene el resultado:
Es decir,
tiene al menos dos factores mayores que
y, por tanto, es compuesto.
¿Qué pasa si
es primo? Pues que sus únicos divisores son
y el propio
. Por tanto, utilizando la igualdad anterior obtendríamos:
número éste que podría ser primo o no. Por eso
sólo puede ser primo si
lo es.
Autor: ^DiAmOnD^ | Publicado el 29 de August de 2008 | Comments Off
Categorías: Demostraciones, Números enteros, Números primos