lunes, 1 de febrero de 2016

Los interprimos (2)

En la anterior entrada estudiamos los números interprimos, que son media de dos primos consecutivos. Entre ellos había cuadrados y triangulares. Veremos ahora otros tipos.

Otros interprimos

Oblongos

Un oblongo puede ser también interprimo. Los primeros son estos:

6, 12, 30, 42, 56, 72, 240, 342, 420, 462, 506, 552, 600, 650, 870, 1056, 1190, 1482, 1722, 1806, 2550, 2652, 2970, 3540, 4422, 6320, 7140, 8010, 10302, 12656, 13572, 14042, 17292, 18360, 19182, 19460, 20022, 22952,…

Esta sucesión estaba inédita y la hemos publicado en https://oeis.org/A263676

Por su propia definición, todos son pares. Si estudiamos sus restos respecto al 6, veremos que sólo pueden ser 0 y 2, es decir, todos los oblongos de esta sucesión han de tener la forma 6k o bien 6k+2. La razón es que los primos son todos del tipo 6k+1 o 6k+5. Intenta encontrar sus medias y verás que nunca pueden ser del tipo 6k+4.

Potencias de primo no triviales

Las potencias de un primo aparecen en muchas cuestiones sobre números. Tampoco faltan entre los interprimos. Los primeros son estos:

4, 9, 64, 81, 625, 1681, 4096, 822649, 1324801, 2411809, 2588881, 2778889, 3243601, 3636649, 3736489, 5527201, 6115729, 6405961, 8720209, 9006001, 12752041, 16056049, 16589329, 18088009, 21743569, 25230529, 29343889, 34586161, 37736449, …

Los más abundantes son los cuadrados de primos, como puedes comprobar en la lista.

Se pueden engendrar en PARI (nosotros los hemos comprobado con hoja de cálculo) mediante este código:

{for(i=1,10^10,if(isprimepower(i)>1&&i==(precprime(i-1)+nextprime(i+1))/2,write1("final.txt",i,", ");print(i)))}

Hemos publicado esta sucesión en https://oeis.org/A263675

La función isprimepower es muy útil, pues da el posible exponente de la potencia de primo que buscamos. Como deseamos que dicha potencia no sea trivial, exigimos que el valor de la función sea mayor que 1. Es muy curiosa la lista de potencias en base pequeña que son interprimas. Las más destacadas son:

Potencias de 2

4, 64, 4096, 75557863725914323419136, 3064991081731777716716694054300618367237478244367204352,…

Por ejemplo, 75557863725914323419136=2^76 es interprimo entre 75557863725914323419121 y 75557863725914323419151. Es una simple curiosidad, pero impresiona que hayamos podido llegar a encontrar estos ejemplos.

Potencias de 3

9, 81, 387420489, 3486784401, 7509466514979724803946715958257547, 147808829414345923316083210206383297601, 11433811272836884826665874049685357613602127080237382571153151471568389249023393608050222706416077770721, 448892491307036257313398359006707643432387469456810160991926368303464199896097475113561830407152947942076292623881529083368591747123618100530770752056321305926194706763551153705251146130442138394723337920866081218864301061606664140464321,

Potencias de 5

5, 625, 32311742677852643549664402033982923967414535582065582275390625, 161558713389263217748322010169914619837072677910327911376953125,

Una buena cuestión, que daríamos por verdadera, es si existen infinitas potencias de este tipo.

Dobles interprimos

A los interprimos, que son media entre dos primos consecutivos, les podíamos exigir que también lo fueran respecto al anterior y al siguiente primo de ese par. Es decir, que dados cuatro primos consecutivos p, q, r y s, exista un número N tal que N=(p+s)/2 y N=(q+r)/2. Esto se cumplirá cuando q-p = s-r, lo cual no quiere decir que los cuatro estén en progresión aritmética.

Un ejemplo: 600 es doble interprimo, porque está en el centro de los cuatro primos consecutivos 593, 599, 601 y 607, cumpliéndose que 600 = (599+601)/2 = (593+607)/2.

No es difícil encontrarlos, y no son escasos. Los primeros que aparecen son:
9, 12, 15, 18, 30, 42, 60, 81, 102, 105, 108, 120, 144, 165, 186, 195, 228, 260, 270, 312, 363, 381, 399, 420, 426, 441, 462, 489, 495, 552, 570, 582, 600, 696, 705, 714, 765, 816, 825, 858,…

(Los publicamos en https://oeis.org/A263674)

A primera vista todos parecen ser múltiplos de 2 o 3, pero, como nos ocurrió con una propiedad similar, esa afirmación es falsa. El primer contraejemplo es 2405, doble interprimo entre 2393, 2399, 2411 y 2417.

viernes, 22 de enero de 2016

Los interprimos (1)

Los interprimos

Se llaman “interprimos” a los números naturales que son media de dos primos consecutivos. El conjunto de estos números es amplísimo, y se puede descomponer en diversos subconjuntos interesantes, la mayoría ya publicados.

Los primeros interprimos son

4, 6, 9, 12, 15, 18, 21, 26, 30, 34, 39, 42, 45, 50, 56, 60, 64, 69, 72, 76, 81, 86, 93, 99, 102, 105, 108, 111, 120, 129, 134, 138, 144,…y están publicados en https://oeis.org/A024675.

Basta estudiar la lista para darse cuenta de que hay entre ellos cuadrados (A075190), como 81 y 144, pares (A072568) e impares (A072569), triangulares (A130178), como el 6 y el 15, semiprimos (A078443), como el 21, y muchos más tipos. Sólo los que son potencias ocupan muchas páginas de OEIS (A075190, A075191, A075192, A075228, A075229,…)

Visita la página http://oeis.org/wiki/Interprimes y te abrumará la cantidad de variantes que presentan los interprimos.

Quedan pocas posibilidades para explorar, pero alguna habrá por ahí.

Evidentemente, un interprimo no puede ser primo, pues entonces los dos primos no serían consecutivos.

Casi todos los interprimos son múltiplos de 2 o de 3, pero no todos (que es lo que afirma Wikipedia), ya que hemos encontrado este contraejemplo: 803 es interprimo entre 797 y 809, y no es múltiplo ni de 2 ni de 3, ya que 803=11*73.

De hecho, están publicados los interprimos que no lo cumplen:

205, 217, 473, 515, 625, 667, 803, 1003, 1207, 1243, 1313, 1465, 1505, 1517, 1537, 1681, 1715, 1795, 1817,… https://oeis.org/A072573

Interprimos entre primos gemelos

Entre ellos son interesantes los que son media de dos primos gemelos:

4, 6, 12, 18, 30, 42, 60, 72, 102, 108, 138, 150, 180, 192, 198, 228, 240, 270, 282, 312, 348,… https://oeis.org/A014574

Salvo el primero, todos son múltiplos de 6, ya que los primos gemelos han de tener la forma 6k-1 y 6k+1 (salvo 3 y 5), con lo que la media será 6k. Este mismo hecho demuestra también que el interprimo es la raíz cuadrada del producto de los dos primos más una unidad:

(6k-1)(6k+1)+1=36k2=(6k)2

Según esto, (6k)2-1 es un semiprimo, pues sólo tiene como factores 6k-1 y 6k+1. Esta puede ser una definición alternativa para estos interprimos. Lo puedes comprobar con PARI

{for(i=1,10^3,m=i*i-1;if(!issquare(m)&&bigomega(m)==2,print1(i,", ")))}

Te devuelve la misma sucesión, pero con la definición de números tales que n2-1 es un semiprimo.

Interprimos entre primos “cousin” y “sexy”

Los primos “cousin” son los que se diferencian en 4 unidades. Sus promedios son estos:

5, 9, 15, 21, 39, 45, 69, 81, 99, 105, 111, 129, 165, 195, 225, 231, 279, 309, 315, 351, 381, 399, 441,… https://oeis.org/A087679

Si los anteriores eran todos múltiplos de 6, salvo los primeros, estos lo serán de 3 y no de 6. La razón es que los primos que se diferencian en 4 unidades han de tener la forma 6k+1 y 6k+5, con lo que el promedio será (12k+6)/2=6k+3.

Si el par de primos es “sexy”, es decir, que se diferencian en 6 unidades, sus interprimos son:

26, 34, 50, 56, 64, 76, 86, 134, 154, 160, 170, 176, 236, 254, 260, 266, 274, 334, 356, 370, 376, 386,… https://oeis.org/A072571

En este caso, para que diferencien en 6, los primos han de ser 6k+1 y 6(k+1)+1 o bien 6k+5 y 6(k+1)+5. Y los promedios 6k+4 o 6(k+1)+2, luego estos interprimos son todos pares, pero no múltiplos de 3.

Algunos tipos curiosos de interprimos

Ya hemos destacado que existen interprimos cuadrados (A075190). También los hay triangulares (A130178)

Interprimos cuadrados

Son los siguientes:

4, 9, 64, 81, 144, 225, 324, 441, 625, 1089, 1681, 2601, 3600, 4096, 5184, 6084, 8464, 12544, 13689, 16641, 19044, 19600, 25281, 27225, 28224, 29584, 36864, 38025, 39204, 45369,…( http://oeis.org/A069495)

Salvo el primero, asociado a los primos gemelos 3 y 5, ningún otro será media de este tipo de primos, pues estos tendrían la expresión n2-1 y n2+1, y el primero no es primo para n>3, por ser igual a (n+1)(n-1). El mismo razonamiento nos vale para afirmar que la diferencia entre el cuadrado dado y sus primos próximos no puede ser un cuadrado k2, pues el anterior sería n2-k2=(n+k)(n-k), no primo. De hecho, estas son las primeras diferencias entre el interprimo cuadrado y el primo más próximo:


Vemos que ninguna es un cuadrado. En ocasiones similares nos hemos preguntado si se recorrerán todas las diferencias posibles, en este caso no cuadradas. Vemos 2, 3, 5, 6, 7, 8, 12,…¿Estarán todas? Hemos creado una función para averiguarlo. Si no te interesa la programación, ignora el código que se inserta a continuación:

Public Function difcuad(d) ‘Busca el primer cuadrado interprimo con diferencia d
Dim i, n, d1, d2, n0
Dim novale As Boolean

i = 1 ‘Contador de búsqueda
n0 = 0 ‘En el inicio damos el valor 0 a la función por si fracasa la búsqueda
novale = True ‘Variable para controlar el fin de la búsqueda
While i < 10 ^ 5 And novale ‘El tope de 10^5 es arbitrario. Si salen ceros habrá que aumentarlo
n = i * i ‘Se construye un cuadrado
d1 = n - primant(n) ‘Se analizan sus diferencias con los primos próximos
d2 = primprox(n) - n
If d1 = d And d2 = d Then n0 = n: novale = False ‘Si es interprimo, se toma nota y paramos
i = i + 1
Wend
difcuad = n0 ‘La función devuelve el primer cuadrado con la diferencia pedida.
End Function

Con esta función hemos creado una tabla, en la que a cada diferencia (no cuadrada) se le asigna el primer cuadrado n2 tal que sea interprimo y su diferencia con los primos próximos sea la dada:



Observamos que hasta el 37 todas las diferencias se corresponden con un cuadrado. A partir de ahí, el cálculo se ralentiza, aunque es de esperar que todas las diferencias no cuadradas tengan una imagen en esta función. Si quieres experimentar por tu cuenta, usa este programa en PARI

difcuad(n)= { local(i=2,m,v=0,p,q);
while(v==0&&i<10^6,m=i*i; p=m-precprime(m-1);q=nextprime(m+1)-m;if(p==n&&q==n,v=m);i+=1)
;return(v) }
{x=difcuad(50);print(x);print(sqrt(x))}

Sustituye el 50 por otro número cualquiera, y si el resultado es 0, cambia 10^6 por una potencia mayor. Aunque PARI es rápido, puedes tener que esperar un poco. Si nuestra conjetura es cierta, al final obtendrás un cuadrado.

Interprimos triangulares

Existen también números triangulares que son interprimos. Los primeros son estos:

6, 15, 21, 45, 105, 120, 231, 300, 351, 465, 741, 780, 861, 1176, 1431, 1485, 3081, 3240, 3321, 3828, 4005, 4278, 5460, 6786, 6903, 7140, 7381, 7503, 7875, 8001, 10731, 11175, 11325, 11781, 12246, 12561,…( http://oeis.org/A130178)

Casi todos ellos son múltiplos de 2, 3 o ambos, pero no todos. Una excepción es 7381=11*11*61, interprimo entre 7369 y 7393.

No hemos encontrado interprimos triangulares cuya diferencia con sus primos próximos sea también triangular, salvo el caso trivial de 6 con 5 y 7.

lunes, 11 de enero de 2016

Volvemos a los números AROLMAR (2) Diferencias


En una entrada anterior, cuya lectura previa recomendamos,

(http://hojaynumeros.blogspot.com.es/2015/12/volvemos-los-numeros-arolmar-1-historia.html

se desarrollaron algunas técnicas para la búsqueda e identificación  de los números arolmar (aquellos números compuestos que tienen todos sus factores primos distintos (son números libres de cuadrados) y el promedio de esos factores es un número primo). En esta buscaremos propiedades y curiosidades sobre ellos.

Todos son impares

No puede haber números pares en esta sucesión arolmar, porque en ese caso uno de los factores primos sería 2 (elevado a la unidad por ser libres de cuadrados) lo que daría lugar a lo siguiente:

Si el 2 está acompañado de un número impar de primos impares, su suma con el 2 sería impar, y al hallar el promedio deberíamos dividir entre un número par, lo que produciría un promedio no entero. Si el número de factores primos que acompañan al 2 es par, la suma de todos sería par, pero habría que dividir entre un impar, con lo que, en el caso de media entera, esta sería par y no prima.

No obstante este razonamiento, hemos generado términos hasta altas potencias de 10 sin encontrar ningún par, como era de esperar.

Estudio de las diferencias

Podemos encontrar números arolmar que se diferencien en un número par dado 2K. Así podemos encontrar, por ejemplo números arolmar gemelos (que se diferencien en 2 unidades). Usaremos esta función para ver si N y N+2K son ambos del tipo arolmar:

Public Function aroldif(n, k) As Boolean
If esarolmar(n) And esarolmar(n + 2 * k) Then aroldif = True Else aroldif = False
End Function

(Tienes la descripción de la función esarolmar en la anterior entrada citada)

Si formamos un bucle con todos los números naturales hasta un tope y una diferencia dada, se nos devolverán aquellos números N del tipo arolmar tales que N+2k también lo sea.

Números arolmar gemelos

Si hacemos k=1 y pasamos la función anterior a un conjunto de números, obtendremos la lista de los números arolmar gemelos. Son estos:


En las dos primeras columnas tenemos los pares de números arolmar gemelos, en las siguientes su descomposición en factores primos, y en las últimas, los promedios primos de sus factores. Los hemos incluido para que se destaque que aparecen valores promedio bastante alejados, especialmente si el número de primos en la descomposición es diferente en ellos.

También se observa que ambos gemelos han de tener factores primos diferentes. Si hubiera uno igual en ambos, al sacarlo factor común veríamos que la diferencia debería ser mayor que 2. Destacamos en la tabla el par (5883,5885), que produce primos promedio muy cercanos, 31 y 41.

Como estas entradas van de curiosidades en gran parte, incluimos ahora conjuntos de cuatro impares consecutivos, en los que los dos primeros son del tipo arolmar y los últimos primos gemelos:

Arol,    Arol,   Primo, Primo
3367,   3369,   3371,   3373
5017,   5019,   5021,   5023
15637, 15639, 15641, 15643
16645, 16647, 16649, 16651
23737, 23739, 23741, 23743
42277, 42279, 42281, 42283
48307, 48309, 48311, 48313
52285, 52287, 52289, 52291
52357, 52359, 52361, 52363
91093, 91095, 91097, 91099

Por su magnitud vemos que no parece ser un caso infrecuente, y que surgirán más en números mayores.

También existen conjuntos similares, pero con los dos primos gemelos anteriores a los gemelos arolmar:

Primo,   Primo,   Arol,      Arol
5879,     5881,     5883,     5885
59357,   59359,   59361,   59363
82529,   82531,   82533,   82535
116189, 116191, 116193, 116195
121439, 121441, 121443, 121445
122609, 122611, 122613, 122615
152039, 152041, 152043, 152045
192629, 192631, 192633, 192635
206909, 206911, 206913, 206915
223829, 223831, 223833, 223835

Y ya, por terminar, situaremos a los arolmar en el centro y los primos en los extremos:

Primo, Arol,    Arol,    Primo
7681,   7683,   7685,   7687
10831, 10833, 10835, 10837
23167, 23169, 23171, 23173
27067, 27069, 27071, 27073
28387, 28389, 28391, 28393
30631, 30633, 30635, 30637
33311, 33313, 33315, 33317
33931, 33933, 33935, 33937
37561, 37563, 37565, 37567

Os invitamos a encontrar otras posibilidades.

Números arolmar cousin (se diferencian en 4)

Usando la misma técnica que con los gemelos, podemos encontrar pares (N, N+4) entre los arolmar. Los primeros son:




Al igual que los anteriores, estos tampoco pueden tener factores primos comunes, pues en ese caso la diferencia no podría ser 4. Predominan los pares en los que uno de los términos es múltiplo de 3, con pocas excepciones, como 19561=31*631 y 19565=5*7*13*43. Como ambos son impares, si el primero es múltiplo de 3 se cumplirá que el segundo es del tipo 6k+1. Basta desarrollar 3*(2m+1)+4=6m+7=6k+1. Si el múltiplo de 3 es el segundo, el primero será 3*(2m+1)-4=6m-1

Los arolmar sexy

En los pares (N,N+6) sí puede existir el factor común 3, y es un caso que se presenta frecuentemente:



Como en casos similares, nos podemos preguntar si existirán pares con cualquier diferencia par que imaginemos. En la tabla siguiente hemos reflejado la primera aparición de dos números arolmar con diferencia 2k igual al doble de la dada k.



Podemos confiar en que sea verdadera la conjetura de que para una diferencia dada 2k siempre existirá un par de números arolmar con esa diferencia.

Hemos proseguido con PARI y para las primeras 1000 diferencias pares nos resultan números arolmar no excesivamente grandes.

913, 129, 231, 85, 195, 21, 217, 69, 177, 85, 195, 33, 205, 57, 597, 145, 231, 21, 445, 93, 195, 85, 889, 21, 145, 33, 177, 253, 195, 33, 133, 21, 129, 145, 195, 21, 553, 57, 231, 133, 483, 21, 145, 57, 105, 85, 1239, 33, 133, 33, 93, 133, 1239, 21, 85, 21, 195, 133, 663, 57, 505, 21, 69, 85, 663, 85, 493, 69, 57, 253, 793, 33, 85, 57, 483, 85, 627, 21, 469, 57, 33, 85, 627, 69, 493, 33, 21, …

Ello puede ser debido a la tendencia prácticamente lineal de los números arolmar.

Ternas de números arolmar gemelos

Ya hemos adivinado que los números que estudiamos son más asequibles que los primos para ciertas propiedades. Por ejemplo, podemos encontrar muchas ternas de números arolmar con diferencia igual a 2:

4713,   4715,   4717
12813, 12815, 12817
26941, 26943, 26945
27861, 27863, 27865
46293, 46295, 46297
56013, 56015, 56017
57757, 57759, 57761
63969, 63971, 63973
66009, 66011, 66013…

Dejamos a los lectores su búsqueda, así como otras estructuras similares. Sólo daremos algún otro ejemplo destacado.

663243, 663245, 663247, 663249, es una cuaterna de números arolmar gemelos. Aquí tienes el desarrollo:



979145, 979147, 979149, 979151 es la siguiente.

Con cinco pares consecutivos hemos encontrado estos: 10075387, 10075389, 10075391, 10075393, 10075395. La comprobación es esta:



Os dejamos el resto de búsquedas de este tipo.

lunes, 21 de diciembre de 2015

Números belgas


Estos números han sido introducidos por Eric Angelini y publicados en el año 2005 en http://oeis.org/A106039. Hay varios tipos, por lo que comenzaremos con los 0-Belgas. Estos números tienen la propiedad de que si a partir del número 0 vamos sumando reiteradamente las cifras (por orden) del número dado, se forma una sucesión que contiene a ese número. Por ejemplo, el 18 es 0-belga, porque a partir del 0 vamos a ir sumando sucesivamente 1, 8, 1, 8,…hasta llegar o sobrepasar el 18: 0, 1, 9, 10, 18, resultando que el mismo 18 es término de la sucesión. Sin embargo, el 19 no lo es, porque se forma la sucesión 0, 1, 10, 11, 20, 21, 30,…al ir sumando sucesivamente 1, 9, 1, 9,… y el mismo 19 es sobrepasado sin pertenecer a la sucesión. Se llaman 0-belgas porque la sucesión la comenzamos en 0, y los primeros son estos:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 17, 18, 20, 21, 22, 24, 26, 27, 30, 31, 33, 35, 36, 39, … http://oeis.org/A106039

Si un número posee 3, 4 o más cifras, estas se irán también sumando de forma sucesiva y ordenada.

Llamaremos n-belgas a aquellos números que pertenecen a la sucesión formada al sumar cifras, pero comenzando en el número n, siendo n menor que el número dado. Así, estos son los 1-belgas:

1, 10, 11, 13, 16, 17, 21, 23, 41, 43, 56, 58, 74, 81, 91, 97, 100, 101, 106, 110,… http://oeis.org/A106439

Por ejemplo, el 23, comenzando en 1, genera con las cifras 2 y 3 la sucesión 1, 3, 6, 8, 11, 13, 16, 18, 21, 23,…a la que él mismo pertenece.
Se han publicado también los 2-belgas (A106518), los 3-belgas (A106596) y otros.

Función ESBELGA

Dado un número cualquiera, es posible saber si es 0-belga, 1-belga o de rango superior. Podemos idear una función con dos parámetros, uno, el número dado, y otro, el tipo. Como el objetivo de esta entrada es experimentar y descubrir curiosidades, daremos dos versiones de esta función, una un poco larga, antes de reflexionar sobre la cuestión, y otra simplificada.

En primer lugar pensamos en lo obvio:
* Deberemos extraer las cifras del número
* Después las iremos sumando ordenadamente a partir del número tipo
* Proseguimos hasta llegar o sobrepasar el presunto número belga
* Si un término de la sucesión coincide con el número dado, es que sí es belga.

Algo así, en el Basic VBA:

Function esbelga(n, t) ‘Los parámetros son el número y el tipo
Dim c(10) ‘Se reserva un vector para almacenar hasta diez cifras (se puede ampliar)
Dim i, nu, a, b, m, p
Dim es As Boolean

‘En primer lugar se extraen las cifras y se almacenan

i = 0: m = n
While m > 0
p = m - 10 * Int(m / 10)
i = i + 1
c(i) = p ‘memorias que guardan las cifras
m = Int(m / 10)
Wend
nu = i

‘Iniciamos la prueba para ver si es belga

es = False
i = 1: a = t ‘La variable a se inicia en el tipo
While a < n ‘Creamos una sucesión hasta n
m = i Mod nu: If m = 0 Then m = nu
a = a + c(nu - m + 1) ‘Se van sumando las cifras a la variable a
i = i + 1
If a = n Then es = True ‘Si la sucesión coincide con n, es belga
Wend
esbelga = es
End Function

Esta función resulta lenta para valores grandes de n, ya que contiene demasiados ciclos de suma de cifras. Sería más práctico eliminar todo esos ciclos dividiendo de forma entera n-t (siendo t el tipo de belga) entre la suma de sus cifras. Para números pequeños no se advierte diferencia en la rapidez del algoritmo, pero siempre debemos intentar simplificar. También se puede usar la función MOD para acelerar la extracción de cifras. Quedaría así:

Function esbelga(n, t) As Boolean
Dim c(10)
Dim i, nu, a, m, p, s
Dim es As Boolean

i = 0: m = n: s = 0
While m > 0
p = m Mod 10
i = i + 1
c(i) = p: s = s + p ‘Extracción de cifras en orden inverso
m = Int(m / 10)
Wend
nu = i

a = (n - t) Mod s ‘Se eliminan los ciclos de suma de cifras
i = 1
If a = 0 Then ‘Si el número es múltiplo de la suma de cifras, es belga
es = True
Else
es = False
For i = 1 To un ‘Se eliminan cifras de la suma para ir probando
If Abs(a - s) < 1 Then es = True ‘Debería escribirse a=s, pero así eliminamos problemas de coma flotante
If Not es Then s = s - c(i)

Next i
End If
esbelga = es
End Function

Por si deseas experimentar, esta es la versión de la función para PARI:

esbelga(n,p)={s=0;k=0;x=n;while(x>0,s+=x%10;x=(x-x%10)/10;k++);
r=(n-p)%s;t=s;x=n;e=0;for(j=0,k,if(r==t,e=1);t-=x%10;x=(x-x%10)/10;);
return(e);}

En la imagen se han generado con esta función los belgas de tipo 0, 1 y 2:



Algunas propiedades

Esta idea de eliminar previamente todos los ciclos de suma de cifras permite afirmar algo más:

Si un número es divisible entre la suma de sus cifras, será 0-belga.

En efecto, al sumar n ciclos de suma de cifras llegamos a n sin tener que recorrer la sucesión. Estos números son los llamados Números Harshad o de Niven:

 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 18, 20, 21, 24, 27, 30, 36, 40, 42, 45, 48, 50, 54, 60, 63, 70,… http://oeis.org/A005349

Aplícale a cualquiera de ellos la función ESBELGA con parámetro 0 y deberá devolverte siempre VERDADERO.

El número de k-belgas, para cualquier valor de k, es infinito.

Bastará sumar a k todos los múltiplos de la suma de cifras de cualquier otro número.

Todo número es k-belga para algún valor de k.

Porque k puede ser el resto de dividir n entre la suma de sus cifras.

Números autobelgas

Puede darse la casualidad de que un número que comienza por la cifra k, sea también k_belga. Por ejemplo, el 25 tiene como primera cifra el 2, y 2-belga.
Esto no pasa de ser un divertimento, como todo el tema, pero nos permite crear una función:

Function autobelga(n)
Dim c, l

l = Len(Str$(n)) – 1 ‘Extrae el número de cifras
If l = 1 Then c = n Else c = Int(n / 10 ^ (l - 1)) ’Extrae la oprimera cifra
If esbelga(n, c) Then autobelga = True Else autobelga = False ‘Comprueba si es belga
End Function

Con ella es fácil crear listados de autobelgas. En la imagen se han listado los comprendidos entre 10 y 30:



Están publicados en http://oeis.org/A107062

Estos números se llaman autobelgas de primer tipo. Hay otros de segundo, en los que además de coincidir la primera cifra con el tipo, también lo hace la segunda con la primera cifra del segundo término. No merece el tema tanta complicación. Te dejamos que busques información y experimentes.

miércoles, 9 de diciembre de 2015

Volvemos a los números "arolmar" (1) Historia y generación


Esta entrada y otras siguientes que aparecerán sobre el mismo tema suponen un regreso a una sucesión que ideamos en 2011, cuya originalidad atrajo a nuestro colaborador Rafael Parra, que fue quien le dio el nombre de “números arolmar”. Tanto él como el autor publicaron sobre el tema en OEIS (The On-line Encyclopedia of integer sequences). Ahora, transcurridos cuatro años, hemos querido desarrollar con tranquilidad la generación de esos números, así como sus propiedades, curiosidades y otras sucesiones afines.

No busque el lector profundidad en esta serie. Se trata tan sólo de exprimir a nivel descriptivo las posibilidades que nos ofrece esta sucesión, sin plantearnos otros objetivos.

Es posible que la publicación no se efectúe de forma consecutiva, a fin de no bloquear el blog si surgen cuestiones de actualidad. Pueden aparecer siete o más entradas distintas.

Historia

Con fecha 23/2/2011 se publicó en este blog una pequeña entrada titulada “Primos por todas partes” (http://hojaynumeros.blogspot.com.es/2011/02/primos-por-todas-partes.html) En ella se presentaba la sucesión

21, 33, 57, 69, 85, 93, 105, 129, 133, 145, 177, 195,…

Son números compuestos que tienen todos sus factores primos distintos (son números libres de cuadrados) y el promedio de esos factores es un número primo.

Por ejemplo 145=5*29, y el promedio de ambos es (5+29)/2= 17, que es primo.
195=3*5*13, y el promedio es (3+5+13)/3 = 21/3 = 7, también primo.

Posteriormente se publicó esta sucesión en OEIS (https://oeis.org/A187073), y Rafael Parra Machío les dio el nombre de números arolmar, dedicándoles un estudio publicado en http://hojamat.es/parra/arolmar.pdf

Dado el interés del tema, ampliaremos la búsqueda de esos números y estudiaremos algunos detalles más sobre esta sucesión y otras afines. Nos moveremos en un nivel de profundidad de tipo medio, que es el que domina el autor, sin pasar a cuestiones de criptosistemas, muy bien explicados en el documento de Rafael Parra. Nuestro objetivo será el de ampliar las formas de generarlos, estudiar alguna subsucesión y buscar números con propiedades similares.

En esta primera entrada reflexionaremos sobre su generación con varias herramientas.

Generación de la sucesión

Con el Buscador de Naturales

En el documento http://www.hojamat.es/publicaciones/Hojanum3.pdf publicamos la forma de encontrar estos números con nuestro Buscador de números naturales (http://www.hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#global)

Basta leer las cuatro líneas de condiciones necesarias para entender la gran potencia de este buscador:



Si lo descargas y escribes las cuatro condiciones en la zona dedicada a ellas obtendrás los primeros términos de la sucesión:



En la primera columna figuran los términos y en la segunda el número primo promedio de los factores primos de los mismos.

La primera condición exige que el promedio de factores primos sea también primo. La segunda lo presenta. La tercera exige que esté libre de cuadrados, y la cuarta que no sea primo.

Con el Basic de las hojas

Al ser el Buscador una herramienta no contrastada, puede ser bueno comprobar los resultados con otros instrumentos. En este blog solemos usar el Basic de las hojas de cálculo. Si tenemos definidas las funciones pertinentes, la búsqueda se reduce a un simple bucle FOR-NEXT

Necesitamos las funciones

PARTECUAD

Te devuelve la parte cuadrada de un número natural. Si esa parte vale 1, es que el número es libre de cuadrados. La tienes en

http://hojaynumeros.blogspot.com.es/2011/05/parte-cuadrada-y-parte-libre-solucion.html

Se puede encontrar escribiendo PARTECUAD en Google.

ESPRIMO

La hemos usado mucho en este blog. La puedes encontrar en nuestra hoja sobre conjeturas

http://www.hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#global

SOPF y F_OMEGA

(o SOPFR Y BIGOMEGA, que en libres de cuadrados son equivalentes)

La primera suma los factores y la segunda los cuenta. Su cociente dará el promedio.
En la entrada http://hojaynumeros.blogspot.com.es/2013/11/de-donde-vengo-3-sumamos-y-contamos.html damos algunas ideas sobre ellas.

Bucle

Con esas funciones y alguna otra podemos ya construir nuestro bucle de búsqueda:

For i = 2 to 1000
If Not esprimo(i) And partecuad(i) = 1 Then
b = sopf(i) / f_omega(i)
If esentero(b) And esprimo(b) Then msgbox(i)
End If
Next i

Implementando un programa similar en una hoja en la que los resultados aparecen bien ordenados, obtenemos los mismos resultados que con el Buscador:



En la primera columna figuran los números arolmar y en la segunda el promedio (primo) de sus factores primos.

Existen infinitos números arolmar, según veremos en la próxima entrada, siempre que se admita la conjetura de Goldbach. En el gráfico de los primeros de ellos (hasta una cota de 2000) se percibe una clara tendencia lineal, que en este intervalo presenta una pendiente aproximada de 17 con un ajuste de nivel 0,9971. Podemos esperar un número arolmar en cada incremento de 17.



Más incidencias presenta la distribución de los números primos que son promedio de sus factores:



En el gráfico distinguimos fácilmente varias líneas de tendencia ¿Adivinas la causa? Pues sí, depende del número de factores que intervengan en el promedio. La línea superior corresponden a los números arolmar que son semiprimos, la siguiente a los que tienen tres factores, y las de más abajo, que llegan a hacerse indistinguibles, a los números que poseen más factores aún. Como también veremos en utra entrada, este gráfico recorre todos los primeros números primos.

Código PARI

En la sucesión A187073 figura un código generador debido a Charles R Greathouse IV

 isA187073(n)=my(f=factor(n)); #f[, 1]>1&vecmax(f[, 2])==1&denominator(f=sum(i=1, #f[, 1], f[i, 1])/#f[, 1])==1&isprime(f) 

Como puede resultar incomprensible, por compacto, lo sustituiremos por otro más sencillo (y largo), pero que nos permitirá ir explicando las funciones que necesitamos:

freesqrcomp(n)=issquarefree(n)&&!isprime(n)
sopf(n)= { local(f, s=0); f=factor(n); for(i=1, matsize(f)[1], s+=f[i, 1]); return(s) }
averg(n)={local(s); s=sopf(n)/omega(n); return(s)}
{  for (n=4, 10^3,  if(freesqrcomp(n), m=averg(n);if(m==truncate(m),if(isprime(m), print1(n, ", ")))))}

En él se van implementando las condiciones exigidas a los números buscados.

Carácter de número compuesto libre de cuadrados:

Basta definir esta función.

freesqrcomp(n)=issquarefree(n)&&!isprime(n)

En ella exigimos que sea libre de cuadrados (issquarefree) y que no sea primo (!isprime(n)). El signo “!” representa la conectiva NO y && la conjunción Y. Si escribes a continuación “{print(freesqrcomp(30))}” la respuesta será 1, que significa VERDADERO, pues 30=2*3*5 es compuesto y libre de cuadrados. Ya tenemos el primer paso: identificar los números de este tipo.

Función SOPF

sopf(n)= { local(f, s=0); f=factor(n); for(i=1, matsize(f)[1], s+=f[i, 1]); return(s) }

Esta parte es más difícil de entender. Esta función suma los factores primos de un número sin contar las repeticiones. En PARI la matriz (o vector) factor(n) contiene los factores primos en la primera columna y sus exponentes en la segunda. La variable s suma sólo los factores primos, pero no sus exponentes. Por eso se escribe s+=f[i, 1])

Promedio de los factores primos

averg(n)={local(s); s=sopf(n)/omega(n); return(s)}

Se basa en la función anterior SOPF y en OMEGA, que cuenta los factores primos sin repetición. Por tanto, su cociente es el promedio de los factores primos.

Bucle de búsqueda

{  for (n=4, 10^3,  if(freesqrcomp(n), m=averg(n);if(m==truncate(m),if(isprime(m), print1(n, ", ")))))}

Lo que queda es ya recorrer los números (en el ejemplo desde 4 hasta 1000) e imprimir aquellos cuyo promedio de factores primos es entero (m==truncate(m)) y primo (isprime(m))

Aquí tienes la pantalla con el resultado:


Hemos querido detenernos en esta generación en PARI porque usaremos más adelante códigos similares.

Por último, incluimos la función ESAROLMAR, que nos devuelve VERDADERO si su argumento es un número arolmar. Con ella se pueden emprender otras búsquedas y encontrar curiosidades.

Función ESAROLMAR

Con el Basic de las hojas de cálculo podría tener esta estructura:

Public Function esarolmar(n)
Dim es As Boolean
Dim b

es = False
If Not esprimo(n) And partecuad(n) = 1 Then
b = sopf(n) / f_omega(n)
If esentero(b) And esprimo(b) Then es = True
End If
esarolmar = es

End Function

La segunda línea exige que el número no sea primo (Not esprimo(n))y que sí sea libre de cuadrados, o bien que su parte cuadrada sea igual a 1 (partecuad(n) = 1), que son las dos condiciones iniciales de la definición de número arolmar.

En la siguiente se calcula la media de los factores primos, dividiendo su suma (sopf(n)) entre su número (f_omega(n)) y, por último, se exige que el resultado sea entero y primo.

La versión con PARI necesita la definición progresiva de varias funciones:

freesqrcomp(n)=issquarefree(n)&&!isprime(n)
sopf(n)= { local(f, s=0); f=factor(n); for(i=1, matsize(f)[1], s+=f[i, 1]); return(s) }
averg(n)={local(s); s=sopf(n)/omega(n); return(s)}
esarolmar(n)={local(a=averg(n),s);s=freesqrcomp(n)&&a==truncate(a)&&isprime(a); return(s)}
{for(i=2,1000,if(esarolmar(i),print(i)))}

La última línea presenta todos los números arolmar hasta el 1000.

En la siguiente entrada sobre este tema estudiaremos el carácter impar de estos números y cómo aparecen sus diferencias (arolmar gemelos, cousin, sexy,...)

Recuerda que esta serie no se publicará de forma consecutiva. Intercalaremos otros temas y para el verano resumiremos todo en una publicación,

lunes, 30 de noviembre de 2015

Primos de Fibonacci


Hoy estudiaremos otra conjetura bastante popular:

Existen infinitos números de Fibonacci que son primos.

Así que si construimos la sucesión de Fibonacci y elegimos los términos que sean primos, encontraremos uno de ellos que sea mayor que cualquier otro entero que imaginemos. Aprovecharemos esta conjetura para repasar conceptos, construir algoritmos y explicar algunas propiedades de los números de Fibonacci.

Los primeros primos de Fibonacci son estos:

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497,…

(http://oeis.org/A005478)

Según la conjetura, esta sucesión debería tener infinitos términos. No es intuitivo, porque en cada aumento de índice resulta más improbable que el término correspondiente sea primo, pero así son las conjeturas, que se encuentran a veces en el término de separación entre lo imposible e improbable.

Comprobación de la conjetura

En la hoja Conjeturas
(http://www.hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#conjeturas)

dispones de las funciones necesarias para comprobar la conjetura, se entiende que en unos pocos ejemplos. La primera, ESPRIMO, ya ha sido presentada muchas veces en este blog (escribe ESPRIMO HOJA en un navegador de Internet), pero necesitamos otra,  ESFIBO, que nos indica si un número pertenece o no a la sucesión de Fibonacci. Esta función se basa en un popular criterio para saber si un número es de Fibonacci o no: Un número N pertenece a la sucesión de Fibonacci si y sólo si 5N2+4 o 5N2-4 es un cuadrado perfecto.

(Ver http://gaussianos.com/algunas-curiosidades-sobre-los-numeros-de-fibonacci/)

Según eso, ésta puede ser la función que devuelva VERDADERO si un número es del tipo Fibonacci y FALSO en el caso opuesto:

Public Function esfibo(n) As Boolean 'devuelve verdadero si N es de Fibonacci
Dim f As Boolean
Dim a

f = False
a = 5 * n * n + 4
If escuad(a) Then f = True
a = 5 * n * n - 4
If escuad(a) Then f = True
esfibo = f
End Function

Disponiendo de esta función y de la ESPRIMO, podemos construir otra, a la que llamaremos FIBOPRIMPROX, que, dado un entero positivo, devuelva el menor primo Fibonacci que es mayor que él, es decir, el “próximo primo Fibonacci”. Su código sería:

Function fiboprimprox(a) As Long
Dim p, prim As Long
Dim sale As Boolean

'Encuentra el menor primo de Fibonacci mayor que el dado
p = a + 1: sale = False: prim = 0
While Not sale
If esprimo(p) And esfibo(p) Then prim = p: sale = True
p = p + 1
Wend
fiboprimprox = prim
End Function

Se entiende fácilmente. El problema, como ocurre frecuentemente en este blog, es que la hoja de cálculo tiene una capacidad limitada de cálculo con enteros. Por ello, con la hoja CONJETURAS sólo hemos podido llegar al próximo a 100000.



Observa que los números de la segunda columna pertenecen a la sucesión de primos Fibonacci. El siguiente, 433494437, sería difícil de obtener con este procedimiento.

Si la conjetura es cierta, la función FIBOPRIMPROX(N) debe devolver un resultado por muy grande que sea N.

Como procedemos a menudo en este blog, traducimos el proceso a PARI para ver si podemos reproducir más elementos de la sucesión. Hemos optado por este código:

{for(i=1,10^4,f=fibonacci(i);if(isprime(f),print(f)))}

El resultado ha sido impresionante, porque en pocos segundos nos ha devuelto los primos contenidos en los 10000 primeros términos de la sucesión de Fibonacci:



Si en el código PARI hubiéramos pedido el valor del índice en lugar del término de Fibonacci nos hubiera resultado la sucesión:

3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433, 449, 509, 569, 571, 2971, 4723, 5387, 9311, 9677,…

Como se ve, salvo el caso del 4, todos los índices de números de Fibonacci primos son también primos. Esto se deriva de que si p divide a q, Fp también divide a Fq para p,q>=3. Así que si el número de orden no es primo, tampoco lo será el número Fibonacci correspondiente. La propiedad recíproca no es cierta. Por ejemplo, el término de índice 19, primo, es 4181=37*113, compuesto.

Divisibilidad en los números Fibonacci

La cuestión anterior da pie a que revisemos algunas propiedades interesantes que presentan los factores primos de los términos de esta sucesión.

El máximo común divisor

Los términos de la sucesión  de Fibonacci cumplen la siguiente curiosa propiedad:


Por ejemplo, si elegimos los términos 24 y 36 de la sucesión,

 F(24) = 46368 =25*32*7*23 y F(36) = 14930352 = 24*33*17*19*107, tendremos

MCD(46368, 14930352) = 144, MCD(24, 36) = 12 y F(12)=144

Por tanto, si el índice de un número de Fibonacci es primo, éste será coprimo con el anterior y el siguiente. Obviamente, esto lo cumplirán los primos Fibonacci, pero también el contraejemplo que vimos más arriba, F(19) = 4181. En la tabla verás la falta de elementos comunes con el anterior y el siguiente elemento Fibonacci.




Teorema de Carmichael

Relacionado con este tema de divisores de los números Fibonacci disponemos de este interesante teorema:

Todo término de la sucesión de Fibonacci distinto de 1, 8 y 144, posee un factor primo que no divide al anterior término.

Lo puedes comprobar en esta tabla de divisores de los términos 10 a 20:



Todo término posee un factor primo que no divide al anterior (recuerda que el segundo número de cada corchete es el exponente del factor primo).

Puede ocurrir que un factor dado no divida a ningún otro término anterior. Por ejemplo, el factor 41 de F(20) no divide a ningún término anterior. En este caso le llamaremos factor característico o primitivo. Los tienes en https://oeis.org/A001578.


jueves, 19 de noviembre de 2015

Sucesión de Golomb

Ya estudiamos en 2010 conjuntos relacionados con este matemático

http://hojaynumeros.blogspot.com.es/2010/03/jugamos-con-sidon-y-golomb.html

Hoy lo hacemos con una de sus sucesiones. Se trata de esta:

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12,…

http://oeis.org/A001462

También se la conoce como sucesión de Silverman. Como ves, es no-decreciente.

Tiene una definición muy curiosa, y es que a(n) representa el número de veces que aparece n en la sucesión, si además definimos a(1)=1 e implícitamente aceptamos que cada valor  de n ocupa el mínimo número de orden posible.
Lo verás mejor si acompañamos cada valor con su índice:



La imagen de 1 es 1 por definición. La de 2 es 2 porque en la sucesión figura ese valor dos veces. También el 3 aparece repetido, por lo que a(3)=2. A(4)=3 debido a que aparecen tres cuatros, y así con todos.

Este es un ejemplo muy elegante de autorreferencia, pues se define un objeto como si ya estuviera construido, pero sólo lo podemos formar si seguimos la definición.

Si aceptamos la condición de que cada valor ocupe el primer número de orden que esté libre, y que cada nueva imagen es la menor que cumple a(n)>=a(n-1), esta sucesión es única. En efecto, nos ponemos a razonar:

A(1)=1 por definición, luego sólo existirá un 1 en la sucesión, por lo que la imagen de 2 no podrá ser 1. Según las condiciones, ha de ser 2, luego en la sucesión deberá haber un par de 2. Como hemos quedado en que se ocupan los menores números de orden, deberá quedar:


Esto significa que a(3)=2, luego también repetiremos el 3 dos veces:


Obligamos así a que el 4 y el 5 figuren tres veces:


Ya podrás seguir tú el razonamiento y completar la sucesión, que con las condiciones impuestas será única.

¿Lo podría conseguir una hoja de cálculo? La respuesta es afirmativa, y el algoritmo no es muy complejo. Necesitamos dos punteros, indi1, que recorrerá los valores de n, e indi2 que llevará la cuenta de los lugares que van quedando libres en la sucesión. Con indi1 se leen los valores, y con indi2 se escriben. Para evitar celdas vacías en los primeros valores, se rellenan el 1 y el 2. Quedará así con el Basic de las hojas:


Sub golomb()
Dim indi1, indi2, i, j, v


indi1 = 2 ‘El primer valor que se lee es el 2, en la celda (2,2)
indi2 = 2 ‘El primero que se escribe también es el 2
Cells(1, 2).Value = 1 ‘Rellenamos los dos primeros valores en las celdas (1,2) y (2,2)
Cells(2, 2).Value = 2
For i = 1 To 12 ‘Tomamos 12 valores, pero podían ser muchos más
v = Cells(indi1, 2).Value ‘Leemos el valor indicado por indi1 (que también es fila en la hoja)
For j = 1 To v ‘Escribimos tantos valores nuevos como indique v
Cells(indi2, 2).Value = indi1 ‘Todos los valores serán iguales a indi1
indi2 = indi2 + 1 ‘Avanza la escritura
Next j
indi1 = indi1 + 1 ‘Avanza la lectura
Next i
End Sub

Con esta subrutina se generará la sucesión de Golomb en la columna 2 de una hoja de cálculo:



Para mayor claridad hemos copiado los resultados en varias columnas, manualmente. Observarás que se reproducen fielmente los valores deseados.



La forma de generación de esta sucesión garantiza que a(n)<=n, ya que los valores de los números naturales aparecen “con retraso”, y cuando aparece el valor, el índice ha crecido más que él. El retraso se puede medir con la diferencia n-a(n):



Vemos que los retrasos a partir de 3 son todos positivos y crecientes.

Una propiedad elemental, pero que hay que pensar en ella un poco, es que las sumas parciales de esta sucesión coinciden con el índice de la última aparición en la sucesión del número de sumandos. Más claro: si sumo tres términos, 1+2+2=5, obtengo que la última aparición del 3 ocurrirá en el término 5. Esto es por la propia definición: el 1 aparece una vez, el 2 dos y el 3 otras dos, luego el último 3 aparecerá en el lugar 5.

La sucesión de sumas parciales es

1, 3, 5, 8, 11, 15, 19, 23, 28, 33, 38, 44, 50, 56, 62, 69, 76, 83, 90, 98, 106, 114, 122, 131, 140, 149, 158, 167, 177, 187,… (http://oeis.org/A001463) y coincide con el lugar de la última aparición de su número de orden. Así, si el quinto término es 11, ahí ocurrirá la última aparición del 5.

Según esto, si llamamos F(n) a los términos de la sucesión de Golomb y G(n) a sus sumas parciales, se cumplirá (estúdialo bien) que

F(G(n)) = n


Fórmula recurrente

Colin Mallows ha ideado una recurrencia muy atractiva para evaluar F(n):

F(1) = 1; F(n+1) = 1 + F(n+1-F(F(n)))

En hoja de cálculo las recurrencias son posibles, pero si se agota la pila de datos se puede bloquear el cálculo. Lo hemos intentado y funciona bien para los primeros términos, pero no va mucho más allá. En Basic sería

Public Function a(n)
If n = 1 Then
a = 1
Else
a = 1 + a(n - a(a(n - 1)))
End If
End Function

Con ella hemos formado esta tabla



En PARI también funciona la recurrencia, pero no merece la pena porque se va ralentizando para números grandes:

a(n)=if(n==1,1,1+a(n-a(a(n-1))))
{for(i=1,30,print1(a(i),", "))}



Aproximación asintótica

Por lo que hemos leído, no ha sido muy fácil llegar a esta expresión:


La comprobamos gráficamente



Se ve que son prácticamente indistinguibles.