…el número 11111…11111 (109297 unos seguidos) es un número primo casi seguro? En realidad es un número primo probable.
Los números formados sólo por unos se denominan repunit, abreviatura de repeated unit. Para escribirlos se utiliza la expresión R(x), siendo x el número de unos que forman el número. Se sabe que R(2)=11, R(19)=1111111111111111111 y R(23)=11111111111111111111111 son primos. También lo son R(317) y R(1031) y se cree que los enooormes R(49081) y R(86453) pueden serlo.
Recientemente Haervey Dubner ha descubierto que R(109297) es el primer repunit primo probable con más de cien mil dígitos. Tal y como dice su descubridor: «hoy en día es imposible de comprobar, en la práctica, si ese número es realmente primo».
Vía Microsiervos.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Se me antoja curioso ver que 2,19,23,317,1031 tambien son primos.
¿Existe algun repunit que siendo primo el resultado no lo sea el factor de repetición?
Tranquilos, cuando se construya un ordenador cuántico y podamos implementar en el el algoritmo de Shor se podrá saber si esos números tan grandes son realmente primos o no, el problema es que no sé si viviremos para verlo xD, un saludo.
Mmmm… hay algo que no entiendo muy bien. ¿Por qué no se puede en la práctica comprobar si ese número es primo? Estaba pensando lo siguiente…. Si actualmente existe algún computador capaz de procesar ese número y operar con él entonces sí debería poder descubrir si es primo o no. ¿Cómo? Pues teniendo varios (unos cientos o miles) de esos súper computadores trabajando simultáneamente intentando dividir por TANTEO a ese número, cada computador trabajando en un distinto rango determinado de números naturales desde 1 hasta R(x). De poderse hacer eso, tal vez en cuestión de unos pocos años, o quizás… Lee más »
Precisamente Samy, esa es la gracia de los problemas NP-Completos (los problemas con tiempo polinómico en un modelo de computación no determinista), que al implementarlos en nuestro modelo de computación actual, que es determinista, el tiempo se vuelve exponencial, y con todos los ordenadores del mundo trabajando en paralelo se podrían tardar siglos en comprobarlo ^^, un saludo desde Sevilla, España.
Al decir exponencial me refiero a lo siguiente, si N es el numero a factorizar, puede tardar 2^N segundos en factorizarse, si N es del tamaño del numero anterior, 2^N es un numero que escapa a nuestra imaginación, he ahí el problema.
>>jacityc. No.
Sea N un numero natural no primo, y sea a algun divisor de N, Como a divide a N, supongamos que N=a*c.
Se hace evidente que R(N)= 11111..1( con n unos) = 11111..1000…0( con a unos y n-a ceros) + 11111..1000…0( con a unos y n-2a ceros) + … + 11111..1000…0( con a unos y n – (c-1)a ceros) + 11111..1( con a unos). Obviamente R(a) divide a ese número.
Es decir:
R(N) = R(a)*(10^(n-a) + 10^(n-2a)
… 10^(n – (c-1)a) + 10^0)
De otra forma, que en realidad viene a ser la misma: R(n) = (10^n – 1)/9 Si n = a*c, ambos mayores que 1, tenemos que R(n) = (10^(a*c) – 1)/9 Llamando x = 10^a, tenemos que el paréntesis es x^c – 1. Este polinomio, sea cual se c, tiene el factor (x – 1): x^c – 1 = (x – 1)P(x) Por tanto R(n) = (10^a – 1)P(10^c)/9 = R(a)P(10^c) Igualmente, R(n9 será divisible por R(c). En definitiva, a | n ====> R(a) | R(n) Otro tanto ocurre con los números de Fibonacci F(n) y los de Mersenne, M(n)… Lee más »
Gracias Xidane