Por @Alvy — 19 de Julio de 2005

Piensa un número cualquiera, que sea entero y mayor que cero. Haz lo siguiente: Si es par, divídelo por dos. Si es impar, multiplícalo por tres y súmale uno. Repite esta misma operación una y otra vez. Al final siempre obtendrás el mismo resultado: 1.

Compartir en Flipboard  Compartir en Facebook  Tuitear

22 comentarios

#1 — Carlos / Artik

Jaja, muy buena, Eneko. Queda más limpio que con mi código :-)

También me gusta mucho el de Pontfx. Venga, alguien que se anime a hacer un one-liner en Perl ;-)

#2 — phreak4

show con siete si que funciona:

7, 21, 22, 11, 33, 34, 17, 51, 52, 26, 13, 39, 40, 20, 10, 5, 15, 16, 8, 4, 2, 1

;)

#3 — show

He quedado mal delante de todos los lecots... :S

Yo hacía con los impares nx3-1, (nota mental: tengo que fijarme más en los detalles)

#4 — Alvy

Bueno, antes de que alguien se vuelva tarumba con esta «Curiosidad» desvelaré el misterio.

(Aunque si estás muy interesado, sigue investigándola.)

.

.

.

.

.

.

.

.

.

Esta curiosidad matemática se llama la La Conjetura de Collatz también conocida como 3n+1, conjetura de Ulam, el problema de Siracusa, la secuencia hailstone, los números hailstone y muchos más nombres. Hay más info en MathWorld: Collatz Problem.

Hasta donde he podido investigar nadie ha resuelto todavía esta conjetura (es decir: no ha demostrado que sea verdadera ni que sea falsa).

Se ha comprobado que para todos los valores entre 1 y 27.021.597.764.222.976 es cierta: siempre se acaba volviendo tarde o temprano al 1. Pero no está demostrado que así sea siempre.

Hay varias razones para pensar que es cierta, y la intuición así lo dice, pero no hay todavía una demostración matemática.

Hay premios (al menos uno de 500 dólares y otro de 1.000 libras) y sin duda grandes honores para quien la resuelva.

Un dato que es fácil de observar es que si en algún momento de la secuencia se llega a un número de forma 2^n entonces se termina en una rápida espiral de divisiones por dos acabando en 1. Cabría pensar que siempre se va a terminar aterrizando en uno de esos números, pero a medida que aumenta n esos números son menos frecuentes.

El problema en cierto modo también es similar al problema de la detención de Turing.

Otro dato es que fijándose únicamente en los números impares de las secuencias, como promedio el siguiente número es unos 3/4 del anterior, así que se podría decir que la secuencia tiende a disminuir.

Pero nada de lo anterior es concluyente.

.

.

.

Por alguna extraña razón cuando encontré esta «Curiosidad» ayer y la publiqué estaba convencido de que realmente se había demostrado ya como cierta, pero mirando un poco he confirmado que no.

Hubiera sido divertido que alguien hubiera dado realmente con la solución: sueño de todo matemático, como la anécdota aquella del estudiante que llega tarde a clase, ve el problema en la pizarra, lo resuelve y el profesor luego le dice que era un ejemplo de problema sin resolver durante siglos.

En fin, ha estado divertido de todos modos, creo.

La próxima prometo que no será algo como «Curiosidad: Mmmm… Parece que cualquier mapa puede colorearse con cuatro colores… ¿Puedes dibujar uno que no se pueda colorear con cuatro colores?» ;-)

#5 — Eneko

Voy a responder a esto último pq me parece estar seguro de haberlo oido.

Bueno, en un mapa ficticio bastaría con que un país hiciese frontera con más de 4 para que al menos dos países colindantes tuvieran que ser pintados del mismo color.

Sin embargo, creo que con el mapa del mundo, es decir, nuestro mundo real, si que basta con sólo 4 colores para pintar todos los países.

No estoy seguro. :)

PD: Muy buena la curiosidad del uno. Ha dado que pensar. Al principio parecía mucho más simple, pero no lo es, como hemos visto.

#6 — tywok

Espero no recordar o que el que me lo contó no fuese muy fantasma, pero al parecer, este problema se discutió mucho durante la guerra fria entre los matematicos estadounidenses. El desarrollo de las matematicas bajo tanto en los Estados Unidos que se prohibió el estudiarlo durante un tiempo. Se creia que eran los rusos los que querian sabotear la capacidad matematica americana proponiendo ese problema. (ATENCION: Esta leyenda urbana puede tener de cierto lo que ET de normal, así que no la hagais mucho caso. Además, no estoy seguro si eran los americanas los que se estacaron o los rusos)

Todavía sigue siendo un problema abierto y podeis probar vuestros programas en el archivo de problemas de la universiadad de valladolid (http://acm.uva.es/p/v1/100.html)

#7 — pepevi

Al dividir por dos la mitad de las veces da un número par pero al multiplicar un impar por 3 y sumar uno da par siempre.

Es decir, aproximadamente:

1/2 de las veces se multiplica por 3 y se suma 1 => da par SIEMPRE

1/2 de las veces se divide entre 2:

- 1/4 de las veces => da par

- 1/4 de las veces => da impar

Es decir, sólo 1/4 de las veces estamos tratando con un número impar. Sólo se multiplica por 3 cada 4 números.

(((n/2)/2)/2)*3 512 par

2: 512 -> 256 par

3: 256 -> 128 par

4: 128 -> 64 par

5: 64 -> 32 par

6: 32 -> 16 par

7: 16 -> 8 par

8: 8 -> 4 par

9: 4 -> 2 par

10: 2 -> 1 par

Y bueno, se tiene que llegar a una potencia de dos en algún momento ya que hacia infinito no tiende y es imposible (lo digo a bote pronto) entrar en un bucle infinito.

Por ejemplo para 101 hay 17 pares y 7 impares, está claro que no tiende a infinito.

¿Alguna pega?

#8 — pepevi

Argh no ha salido el <

Quise decir

(((n/2)/2)/2)*3 < n

(por no dar a previsualizar :S)

#9 — Luis

Al #14: No es necesario usar el principio de inducción para demostrar esas fórmulas, basta con recordar (o calcularse) cuánto vale la suma de n términos de una progresión aritmética (matemáticas de primero de bup).

En cuanto al tema principal, es fascinante para un friki de los números como yo, muchas gracias por llamarnos la atención sobre ese tema.

Hace algún tiempo, cuando estaba aburrido y tenía una calculadora cerca, se me ocurrió un juego parecido. Supongamos un número natural positivo, y veamos qué cifra debemos añadirle al final para que sea divisible entre 11 (o, lo que es equivalente, veamos cuál es el resto resultante de dividirlo entre 11). Si el número es múltiplo de 11, directamente se efectúa la división. Si el resto está entre 1 y 9, se añade el valor del resto al final del número y se efectúa la división (esto es, se multiplica el número por 10 y se suma el resto, de 1 a 9). Si el resto es 10, se añade "01" al número y se divide (o sea, se multiplica por 100 y se suma 1).

Parece claro que al final se llegará a uno de los primeros nueve números naturales, pero encontré un bucle cerrado en el que se caía bastantes veces cuyo valor mínimo era el 32. Hasta me hice un programita fortran, y testando hasta 10^10 no encontraba más bucles cerrados.

Hasta me hice estadísticas viendo en que número era más probable que acabara la serie, y me parece recordar que era el 1. Al final se me pasó el aburrimiento...

#10 — ggarfield

#30 sí es necesario utilizar algun método matemático cómo la inducción o la reducción al absudro para demostrar esas fórmulas, ya que se tienen que demostrar para TODOS los números naturales (infinitos). No hace falta aplicar la inducción para hacer el cálculo pero sí para demostrarlo : -)

#11 — Guille

A ver si conoceis este:

Si multiplicas cualquier numero por 9, y sumas unidades+decenas+..., siempre te dara como resultado 9.

Ejemplo:

2*9= 81 -> 8+1=9

47*9=423 -> 4+2+3=9

Curioso eh?

#12 — Luis

#31: De acuerdo, quizá me despistó que en tu post no decías explícitamente que valía para todos los números naturales, fallo mío.

#32: En realidad te ha de salir un múltiplo de 9, y si repites la operación con ese número que será la suma de las cifras hasta quedarte con un número de una sola cifra te quedará 9. De pequeños estudiábamos los criterios de divisibilidad...

#13 — Scila

Yo estoy con #28, es tan facil como que estadísticamente vas a hacer más veces la división que la multiplicación. No puedes multiplicar más veces que divides porque detrás de una multiplicación siempre va a haber una división, sin embargo después de dividir tienes un teórico 50% de posibilidades de volver a dividir.

Ahara, demostrarlo matematicamente ya es otra cosa!

#14 — Alvy

Guille (#32) – Bueno, dicho de otra forma cualquier 9n módulo 9 = 9. No es tan sorprendente sabiendo que precisamente 9n por definición siempre es 9.

#15 — Pablo Martínez-Almeida

No soy un experto, pero creo que este programilla en Excel debería simular el experimento. Se agradecen revisiones y consejos sobre el código:

Sub Uno()

Dim i As Single

Dim j As Integer

Do Until i > 0 And i = Int(i)

i = InputBox("Introduce un número entero positivo")

Loop

Do Until i = 1

If i Mod 2 = 0 Then i = i / 2 Else i = i * 3 + 1

j = j + 1

Loop

MsgBox "Se llega al uno tras " & j & " iteraciones"

End Sub

#16 — Carles

Muy curioso.

¿Habéis probado a representar en un grafico los resultados? (Solo por curiosidad, yo no lo he hecho)

Soy lector asiduo desde hace meses a vuestro blog y aprendo muchas cosas, me gusta la ciéncia y las mates en general, pero no llego a este nivel de hacer el programa en php y recordar tantas teorias...

Siempre que leo cosas interesantes creo que puedo hacer un comentario o elogio, pero me da palo por el nivel que hay aqui, este es el primero que posteo.

Felicidades Microsiervos ;)

#17 — tywok

#37 En mathworld, el link que dio Alvi en el #25 puedes ver un par de gráficos;)

#18 — Dem

28. Pero serviría si el dividir o multiplicar fuese algo aleatorio, pero dado el número inicial, la secuencia no es aleatoria.

#19 — pepevi

No es aleatoria pero es independiente. Tiene que serlo, ya que no se encuentra ningún número que no funcione.

#20 — MateO

Es la primera vez que escrivo aqui, soy licenciado en matematicas y estudio meteorologia y estoy llegando a mi tesis relacionando esta conjetura con la variable de Wellingtong que trata de la caida del granizo, estoy elavorando un algoritmo estadistico para para determinar un porcentage de margen de herror en la prediccion de ciertas tormentas frias, si alguien tiene una idea por mas tonta que le parezca sobre la demostracion u otra cosa asi como referencias a sitios y a libros que por favor me escriva a syracuse_problema@hotmail.com para compartir informacion gracias.

#21 — antonio

Acabo de terminar la licenciatura de matemáticas. Desde que tuve noción de este problema 3n+1 hace ya unos cuantos años, me ha venido a la memoria recurrentemente, confieso que a veces hasta me ha obsesionado. He tenido algunos progresos, pero nunca sabes si tienen valor, dado que otro/s pueden haber llegado a lo mismo que t mucho antes. Uno no sabe si en alguna/s de la infinidad de páginas de internet en que se cita la conjetura hay resultados que tiran por tierra el valor de tus propios avances.

Por otra parte, podría enviar mis resultados parciales a alguna revista para su posible publicación. Si no les parece interesante y te lo devuelven, ¿puedo estar seguro de que en un futuro no lo publique otro matemático, amigo del de la revista, en otra publicación? ¿cómo funciona el tema de la propiedad intelectual?

#22 — Matematica insolita

En matematicainsolita.8m.com se encuentra una demostracion general y muy sencilla de la Conjetura de Collatz.
demostracion apta para principiantes y aficionados a las matematicas.
Igual se encuentran demostraciones de otras famosas conjeturas.

Felicidades para todos.