Tema
A falta de mejor nombre. De HAKMEM, folletín clásico.
ITEM 33 (Schroeppel):
Numbers whose right digit can be repeatedly removed and they are still prime: CONJECTURE: There are a finite number of them in any radix. In decimal there are 51, the longest being 1,979,339,333 and 1,979,339,339.
De dónde viene esa conjetura? Alguien sabe si es probable?
Para cualquier base dada parece fácilmente probable a lo bruto armando un árbol con pruning, pero no me imagino la prueba para toda base.
Saludos!
No entiendo. Si a 1,979,339,333 le saco el digito menos significativo nueve veces, me queda 1 que no es primo.
Ademas, en decimal encontre 83 (sin contar los que empiezan con 1).
podes poner los primeros...
Quimey
Puedo poner todos:
2
3
5
7
23
29
31
37
53
59
71
73
79
233
239
293
311
313
317
373
379
593
599
719
733
739
797
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393
23333
23339
23399
23993
29399
31193
31379
37337
37339
37397
59393
59399
71933
73331
73939
233993
239933
293999
373379
373393
593933
593993
719333
739391
739393
739397
739399
2339933
2399333
2939999
3733799
5939333
7393913
7393931
7393933
23399339
29399999
37337999
59393339
73939133
Aca hay mas informacion:
http://www.research.att.com/~njas/sequences/A024770
http://mathworld.wolfram.com/TruncatablePrime.html
http://en.wikipedia.org/wiki/Truncatable_prime
Por supuesto muy cierto lo del 1.
Tiene sentido la conjetura para cualquiera de las dos versiones?
Al incluir el cero y desde la izquierda hay infinitos:
Sigo sin entender por que dice que hay 51 en decimal, incluso aceptando los numeros que empiezan con 1. Deberia haber mas de 83 en esa version.
Intuitivamente tiene sentido la conjetura, pero no pude demostrarla. El problema de la demostracion por fuerza bruta es que obviamente no se puede generalizar para toda base. Por eso trate de encontrar otro argumento para demostrar que en decimal hay una cantidad finita, para potencialmente generalizarlo a otras bases. Pero no llegue a nada usable. Usando la regla de division del 3, podes limitar bastante las opciones: estos numeros pueden tener a lo sumo dos digitos 1 o 7. El resto, despues del digito mas significativo, tiene que ser siempre 3 o 9. Otro detalle es que nunca podes repetir los mismos digitos dentro del numero, porque de esa forma llegas a un compuesto. Por ejemplo, \(3737 = 101 \times 37\), \(373373 = 1001 \times 373\), etc.
Todo muy lindo, pero este tipo de argumentos no sirve para descartar "extensiones" en las que los divisores son numeros grandes y no tienen divisores del tipo \(10^k + 1\). Por ejemplo:
\(73939133\) es right-truncatable, pero si lo extendemos agregandole un \(9\) nos queda \(739391339 = 9521 \times 77659\).
Lo que podria llegar a andar seria una demostracion por el absurdo, pero no se suficientes propiedades de numeros primos como para encontrar una contradiccion como consecuencia de suponer que hay una cantidad infinita de right-truncable primes decimales.