Complejidad de los números naturales

230 COMPLEJIDAD DE LOS N´ UMEROS NATURALES Complejidad de los n´umeros naturales por J. Arias de Reyna 1.INTRODUCCI ´ ON 1.COMPLEJIDAD DE UN N´ UMERO NATURAL Voy a hablar de un tema aparentemente menor, que puede comprender un estudiante con catorce a˜nos, pero que encierra dificultades muy profundas. Llevo alg´un tiempo interesado en uno de los problemas que considero m´as importantes de entre los que tienen planteados los matem´aticos: el problema P? =NP. En este caso, la primera dificultad es exponer el problema de forma asequible a un matem´atico tradicional, digamos que a un especialista en An´alisis Matem´atico. No es ´esta una cuesti´on banal, pues creo que debe poder plantearse como un problema de acotaci´on, y que entiendan el problema los analistas puede ser el paso principal hacia la soluci´on. La cuesti´on de la que quiero hablar aqu´ısurgi´oenunintentode conseguir esta explicaci´on. Empecemos con la pregunta principal: dado un n´umero natural n, ¿cu´antos unos son necesarios para escribir n? Por ejemplo, 19=1+(1+1)(1+1+1)(1+1+1), luego no se necesitan m´as de 9 unos para escribir el n´umero 19. Decimos entonces que la complejidad de 19 es menor o igual a 9, lo que escribiremos abreviadamente por 19≤9. Naturalmente la complejidad de 19 ser´ael n´umero de unos en la representaci´on de 19 que menos unos utilice. S´olo se admiten expresiones con las operaciones de suma y de producto. Los primeros valores de la funci´on complejidad pueden calcularse con no demasiado trabajo: 1,2,3,4,5,5,6,6,6,7,8,7,8,8,8,8,9,8,9,9,... Vemos que no forman una sucesi´on mon´otona: 8 = 11>12=7. Cuando en alg´un problema matem´atico surge una sucesi´on de n´ umeros naturales, hay algo que debemos hacer: consultar The Encyclopedia of Integer Sequences de Sloane y Plouffe [SP]. En ella encontramos la sucesi´on anterior y nos remite al art´ıculo de Guy [G], donde se la define y analiza. LAGACETA 231 2.COMPLEJIDAD DE UN N´ UMERO NATURAL Hemos definido la complejidad como una funci´on n→nde N→N tal que para todo par de n´umeros naturales mynse tiene 1=1,m+n≤m+n,m·n≤m+n. De hecho es la mayor funci´on que cumple estas condiciones. Para probar ´esta y otras afirmaciones es ´util introducir otro concepto: el de expresi´on. 2.DEFINICI ´ ON DE LAS EXPRESIONES Una expresi´on es una sucesi´on de s´ımbolos. Los s´ımbolos permitidos son los cuatro siguientes x, +, (, ). No toda sucesi´on de s´ımbolos es una expresi´on. Ejemplos de expresiones son: (x + x);(x+(xx));(x+((x+x)((x+(x+x))(x+(x+x))))). La definici´on formal es una definici´on inductiva: (a) xes una expresi´on. (b) Si AyBson expresiones, tambi´en lo son (A+B) y(AB). (c) S´olo son expresiones las sucesiones finitas de s´ımbolos que resulten de aplicar reiteradamente las reglas (a) y (b). Definimos el valor de una expresi´on Acomo el n´umero v(A)queresulta de sustituir xpor 1 y efectuar las operaciones indicadas. De nuevo usamos la inducci´on para definir el valor v:v(x)=1,ysiAyBson expresiones v((A+B))=v(A)+v(B)yv((AB))=v(A)v(B). Dada una expresi´on, podemos definir su complejidad como el n´umero de letras iguales a xque contiene, por ejemplo, (x+(xx))=3.Sea Eel conjunto de las expresiones. La definici´on de la complejidad puede expresarse ahora en la forma n=inf{A:A∈Eyv(A)=n}. Si queremos calcular el valor de ndebemos usar la proposici´on siguiente: Proposici´on 1 Para todo n´umero natural n∈N, n=min(d+n/d,j+n−j): 2≤d≤√n, d/n 1≤j≤n/2 Prueba. Supongamos que n>1. Sea Euna expresi´on ´optima de n,es decir una que d´e su complejidad, n=E. Ahora la expresi´on ser´ao 232 COMPLEJIDAD DE LOS N´ UMEROS NATURALES bien E=(A +B) ´obienE=(AB). Pongamos a=v(A), b=v(B). De este modo, ´obienn=a+byn=a+b,´obienn=ab yn=a+b. En el primer caso, si jel menor de los dos, ayb,setiene1≤j≤n/2, y en el segundo, si des el menor de los dos, des un divisor de ncon 2≤d≤√n. Naturalmente, para que el razonamiento anterior sea v´alido, debemos comprobar que, si Ees una expresi´on ´optima de n, entonces Ay Bdeben ser expresiones ´optimas de ayb. Dejamos dicha comprobaci´on al lector. Usando el esquema anterior hemos calculado, con el programa Mathematica, los valores de npara 1 ≤n≤200 000. 3.COTAS Proposici´on 2 Sea P:N→Runa aplicaci´on tal que P(1) = 1,P(n+m)≤P(n)+P(m),P(n·m)≤P(n)+P(m). Entonces, para todo n∈N,setieneP(n)≤n. Prueba. Vemos que, para toda expresi´on A,setienePv(A)≤A. Usamos inducci´on. Es cierto para A=x,y,siesciertoparaAyB,es tambi´en cierto para (A+B) y(AB). En efecto, para el producto: Pv((AB))=Pv(A)v(B)≤Pv(A)+Pv(B)≤A+B=(AB), yunargumentoan´alogo vale para la suma. (Observar que, por la definici´on de v,setienev((A+B))=v(A)+v(B)yv((AB))=v(A)v(B)). Basta ahora tomar ´ınfimo en Pv(A)≤Apara todas las expresiones Atales que n=v(A). Se obtiene entonces P(n)≤n. Corolario 3 Para todo n´umero natural n,log2(1 + n)≤n. Prueba. Basta comprobar las propiedades de P(n)=log 2(1 + n). M´as adelante en el corolario 9 mejoraremos esta desigualdad. 3.COTAS SUPERIORES A continuaci´on establecemos una cota superior. Con este objeto introducimos una funci´on L:N→N. Definici´on 4 Definimos la funci´on Linductivamente: (a) L(1) = 1. LAGACETA 233 (b) Si pes un n´umero primo, L(p)=1+L(p−1). (c) Si n=p1p2···pkes un producto de n´umeros primos iguales o diferentes, entonces L(p1p2···pk)=L(p1)+L(p2)+···L(pk). Con esta definici´on es claro que si n=ab, siendo aybmayores o iguales a 2, entonces se tiene L(n)=L(a)+L(b). Proposici´on 5 Para todo n∈N,setiene n≤L(n). Prueba. Podemos probarlo por inducci´on. Para n= 1, tenemos 1= L(1) = 1. Supongamos que se cumple k≤L(k), para todo k<n. Pueden darse dos posibilidades: Si n=pes un n´umero primo, p≤p−1+1=p−1+1≤L(p−1) + 1 = L(p). Si n=ab con ayb>2, n≤a+b≤L(a)+L(b)=L(ab)=L(n). Proposici´on 6 Para todo n≥2se tiene L(n)≤3 log 2(log n). Prueba. En primer lugar, puesto que L(2) = 2, el resultado es cierto para n=2. Supongamos ahora que n≥3, y que la desigualdad es v´alida para n´umeros naturales menores que n. Si n=pes primo, se tiene L(p)=1+L(p−1) = 1 + 2 + Lp−1 2≤3+ 3 log 2 logp−1 2.(1) Queremos que esto sea ≤3 log 2(log p). Es decir, basta comprobar que 3≤3 log 2 log2p p−1,(2) 234 COMPLEJIDAD DE LOS N´ UMEROS NATURALES lo cual se cumple para p≥3. Si n=ab,conayb≥2, se tiene L(ab)=L(a)+L(b)≤3 log 2(log a)+ 3 log 2(log b)= 3 log 2(log ab). Nota 1. No sabemos si la constante 3/log 2 en el teorema anterior es ´optima. Analizando la prueba, sospechamos que el cociente L(n)/log n es grande cuando n=pksea un primo tal que exista una sucesi´on de primos (pj)k j=1 de forma que pj=2pj+1 + 1. Por ejemplo, los n´umeros 89, 179, 359, 719, 1439, 2879 son todos primos, y el m´aximo valor del cociente L(n)/log nque conocemos es L(2879) log 2879 =3.766384578 ···<4.328085123 ···=3 log 2. La diferencia principal entre las dos funciones L(·)y·consiste en que L(·) es multiplicativa y ·no. Para cada pareja de n´umeros nym mayores que 1, la funci´on Lverifica L(nm)=L(n)+L(m). En cambio, existen nymmayores que 1 tales que nm<n+m.Diremosque n·mes una mala factorizaci´on. En la figura 1 situamos un punto en (n, m)cadavezquen×mes mala factorizaci´on. La figura cubre todos los factores n´o m≤60. Naturalmente 1 ·mes siempre mala factorizaci´on, pero en la figura aparecen otras regularidades sorprendentes. As´ı, saltan a la vista ciertas alineaciones de puntos, las m´as prominentes se situan en n= 23, 41 y 59, que merecen una explicaci´on. Estos n´umeros, dir´ıamos que malos factores, parecen tener una complejidad grande. Definimos la sucesi´on de n´umeros con complejidad grande nk: son aquellos tales que nkes la menor soluci´on de n=k. Los primeros valores de esta sucesi´on son 1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, 59, 89, 107, 167, 179, 263, 347, 467 , 683, 719, 1223, 1438, 1439, 2879, 3767, 4283, 6299, 10079, 11807, 15287, 21599, 33599, ... que aparece en [SP] con alguna errata. Encontramos as´ı la referencia a Rawsthorne [R]. LAGACETA 235 Figura 1. Malos factores 4.VALORES MEDIOS Existe otra prueba de que n≤3logn/ log 2. Consiste en observar que, si escribimos nen binario n=k−1 j=0 εj2j+2 k, tenemos una forma de expresar n: n=ε0+2(ε1+2(ε2+···+2(εk−2+2(εk−1+2))···)), donde podemos sustituir cada 2 por 1 + 1 y cada cifra εjes 0 ´o1.Deeste modo obtenemos una expresi´on de nusando a lo m´as 2k+kunos, donde kcumple 2k≤n<2k+1.Luegon≤3logn/ log 2. El razonamiento anterior prueba que la funci´on L2(n)=2k+ε0+ε1+ ···εk−1es otra cota superior de n.Lacomparaci´on de L2(n)ydeL(n) no es f´acil. Entre los primeros 1000 n´umeros, generalmente L(n)esmenor, pero esto tiene excepciones. La primera es L2(161) = 16 <17 = L(161). En este rango la diferencia es peque˜na. 236 COMPLEJIDAD DE LOS N´ UMEROS NATURALES La funci´on L2(n) puede usarse para obtener informaci´on sobre la funci´on ·. Consideremos el conjunto de los n´umeros nque se escriben en binario en la forma 1εk−1...ε 0, es decir, con k+1 cifras. Seg´un la expresi´on anterior, tenemos n≤2k+ε0+···+εk−1. Podemos pensar que εjson variables aleatorias independientes de media 1/2. La desigualdad de Chernoff (ver [C] y para una exposici´on sencilla [AS]) nos dice que Pεj−k/2<x √k≥1−2e−2x2. Se sigue que P(n≤2k+k/2+x√k)≥1−2e−2x2. Finalmente, con x=√log k, Pn>5k/2+klog k≤2k−2. Luego entre los 2kvalores de ncon 2k≤n<2k+1 alom´as (2/k2)2k verifican n>5k/2+√klog k.Losdem´as, la mayor parte, cumplen n≤5k 2+klog k=5 2 log n log 2 +O(log nlog log n). De alg´un modo podemos decir que para casi todos los valores grandes de nse tiene n≤5 2 log n log 2 +O(log nlog log n). La cota superior L(n) es extraordinariamente buena para valores peque˜nos de n. Por ejemplo, entre los primeros 220 valores de n,L(n)=n, salvo para los indicados en la tabla siguiente: n||n|| L(n) 46 12 13 47 13 14 55 12 13 82 13 14 83 14 15 92 14 15 94 15 16 110 14 15 n||n|| L(n) 115 15 16 118 15 16 121 15 16 138 15 16 139 16 17 141 16 17 145 15 16 161 16 17 n||n|| L(n) 164 15 16 165 15 16 166 16 17 167 17 18 184 16 17 188 17 18 217 16 17 220 16 17 En estos casos la cota L2(n) es igual o mayor que L(n), salvo para el valor 161. Las dos funciones L(n)yncoinciden en 771 valores de npara 1 ≤ n≤1000, siendo la diferencia igual a 1 en los otros 229 casos, salvo unas pocas excepciones. LAGACETA 237 4.VALORES PARTICULARES 5.N´ UMEROS CON COMPLEJIDAD PEQUE˜ NA Una cota inferior para la complejidad nresultaderesolverlacuesti´on de qu´en´umero Npodemos alcanzar con munos. Esto es, dado m, cu´al es el mayor n´umero natural Ntal que N=m. La respuesta, grosso modo, es que debemos agrupar los munos disponibles en grupos de 3 y multiplicarlos. Para ver esto definimos el concepto de expresi´on extremal. Sea Mmuna expresi´on con Mm=m, (es decir, Mmest´aformadaconm xsy las operaciones de suma y producto), y tal que su valor v(Mm)sea m´aximo entre las expresiones formadas con munos, esto es N=v(Mm)= sup A=m v(A). Diremos que Mmes extremal. Afirmamos entonces que N=m. En efecto, por ser N=v(Mm)y Mm=m,setieneN≤m. Supongamos, por contra, que fuese N< m.Existir´ıa entonces una expresi´on Btal que v(B)=NyB=N<m. Sea dtal que m=d+B. Podemos construir una expresi´on Cde la forma C=B+x+···+x,ytalqueC=B+d=myv(C)=v(B)+d>N. Esto contradice la definici´on de Mm. Es f´acil comprobar que las siguientes expresiones son extremales M1=x,M2=(x + x),M3=(x + (x+x)), M4=(x+x)(x+x),M5=(x+(x+x))(x+x),... Como vemos, dado m,laexpresi´on extremal Mmno es ´unica, por ejemplo M4=(x+(x+(x+x))) es otra posibilidad. Usaremos una notaci´on poco precisa, por ejemplo, escribiremos Ma 3M2 para denotar cualquier expresi´on que tenga esa forma sin precisar c´omo construimos el producto a partir de los factores. As´ıM4 3puede denotar cualquiera de las expresiones ((M3M3)(M3M3)),(M3(M3(M3M3))),ocualquier otra forma de agrupar los factores. Proposici´on 7 Sean M2=(x + x),M3=(x + (x+x)) yM4=(x+x)(x+x). Para n>1, las expresiones Mndefinidas por Mn= ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ Mk 3si n=3k, Mk−1 3M4si n=3k+1, Mk 3M2si n=3k+2, son extremales. 238 COMPLEJIDAD DE LOS N´ UMEROS NATURALES Prueba. Directamente podemos comprobar que el resultado es v´alido para n=2,3y4. Supongamos que es v´alida para todo s<ny tratemos de probarlo para n≥5. Ciertamente existe una expresi´on extremal Kcon K=n.Existen entonces dos expresiones AyBtales que K=(A+B) obienK=(AB).Tanto Acomo Bson extremales, en otro caso Kno lo ser´ıa. Podemos cambiar AyBpor expresiones extremales de la misma complejidad y la expresi´on resultante Kseguir´a siendo extremal. Por tanto sin restringir la generalidad podemos suponer, usando la hip´otesis de inducci´on, que AyBson de la forma dada en el enunciado, o bien A=xyBcomo en el enunciado El caso de ser K=(A+B) s´olo es posible si v(A)ov(B) = 1, (en otro caso la expresi´on (AB) contradice la extremalidad de K). Pero K=(x+Mk 3), K=(x+Mk−1 3M4),oK=(x+Mk 3M2)es imposible con n≥5. Pues estas expresiones claramente no son extremales. (Compararlas con Mk−1 3M4,Mk 3M2, oMk+1 3respectivamente). Llegamos pues a la conclusi´on de que K=(AB), siendo AyBde la forma dada en el enunciado. Algunas de las combinaciones no son posibles: por ejemplo, A=Mk 3M2yB=Mj−1 3M4no es posible pues Mk+j−1 3M4M2es mejorada por Mk+j−1 3yKno ser´ıa extremal. Un estudio caso por caso, demuestra que Kes de la forma dada en el enunciado. De lo anterior se sigue Corolario 8 Para a=0,1´o 2yb∈Nse tiene 2a3b=2a+3b, a =0,1,2. Todo n´umero natural n>1 se escribe de manera ´unica en la forma n=2a+3bsiendo a=0,1´o 2. En ese caso 2a3bes el mayor n´umero m tal que m=n.Portantom>2a3bimplica m>2a+3b. Definimos g:N→Nen la forma g(n)= ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ 3asi n∈3a,3a+3 a−1, 3a+1 sin∈3a+3 a−1,2·3a, 3a+2 sin∈2·3a,3a+1. Se tiene entonces que para todo n,g(n)≤n. Corolario 9 Para todo n≥1tenemos 3log n log 3 ≤n≤L(n)≤3log n log 2 . LAGACETA 245 sea entonces fa b(x12,...,x a−1,a) la funci´on que vale 1 si y s´olo si existen b v´ertices tales que est´en todos conectados en el grafo. Cabe pensar que fa b≥a b, ya que para conocer el valor de fa ben un grafo necesitamos comprobar cada conjunto de bv´ertices. Se puede probar que, si esto es as´ı, entonces P=NP.Deestemodoprobarfa b≥a b se convierte, a mi parecer, en el camino m´as prometedor de probar que P=NP. Volviendo a la complejidad de los naturales, un problema an´alogo al anterior es el siguiente, planteado por Guy [G]: Problema ¿Existe una sucesi´on de naturales (an)tales que lim n→∞ an log an >3 log 3 ?(1) Un candidato es la sucesi´on 2n. Todos los valores calculados hasta ahora cumplen 2n=2n. Selfridge pregunta (cfr. [G]) si existe ntal que 2n<2n. Si para alg´un valor de nexistiera ktal que 2n=3 k, (cosa imposible por otra parte), la segunda expresi´on dar´ıa un valor de 2n<2n. Naturalmente la ventaja ser´ıa mayor mientras mayor fuera n. Aunque lo anterior es imposible, no cabe descartar que se den otro tipo de casualidades que hagan posible 2n<2n. Por ejemplo, si el desarrollo en base 3 de 2ntuviera cifras con poco peso. De nuevo esto tiene pocas probabilidades de ocurrir; ahora bien, podr´ıa tratarse de otro tipo de expresi´on de 2n. La situaci´on aqu´ıesque,sitengounn´umero que ya puedo expresar en la forma (1 + 1)(1 + 1) ···(1 + 1), parece dificil encontrar otra expresi´on que con menos unos conduzca al mismo resultado. Tenemos un casi-ejemplo trivial 4 = (1 + 1)(1 + 1) = 1+1+1+1.Aqu´ı aparece el mismo n´umero de unos en ambos lados, por esto lo llamo casi-ejemplo. Pero pueden darse casi ejemplos no triviales, como el que sigue: 227 =1+(1+2·3)(1 + 23·32)(1 + 29·33(1 + 2 ·32)). Bastasustituir2por1+1y3por1+1+1paraobtenerunaexpresi´on alternativa de 227 con 57 unos, y en la que la estructura multiplicativa del n´umero 227 deja de usarse. La igualdad anterior prueba que 227 −1≤56. A pesar de una intensa b´usqueda no he conseguido encontrar n>2talque2n−1<2n−1, sin embargo creo que esto puede ocurrir. 246 COMPLEJIDAD DE LOS N´ UMEROS NATURALES La evidencia parece estar del lado de que existe la sucesi´on que cumpla (1). Basta observar el gr´afico en la figura 2. En ´el se ha situado un peque˜no disco con centro en cada punto (n, n)con1≤n≤2000 y tambi´en se han dibujado las gr´aficas de las curvas suaves que acotan a n, es decir 3(log t)/log 3 y 3(log t)/log 2, as´ıcomodelacurva5logt/2 log 2. Los puntos se unen y forman en la figura unas lineas paralelas al eje x.Vemosquela cota superior parece muy mala y que aparentemente n≤5logt/2 log 2, cuando s´olo hemos probado que aproximadamente esta desigualdad se cumple para casi todo n∈N. 500 1000 1500 2000 15 20 25 30 Figura 2 Pero esta figura nada dice sobre la existencia del l´ımite lim n/log n, queesdeloquesetrata.S´olo vemos que entre los 2000 primeros valores de nesta sucesi´on oscila entre unos l´ımites pr´oximos a 5/2log2 y 3/log 3. 6.CONJETURAS He calculado mediante la proposici´on 1 la complejidad de los primeros 200.000 n´umeros naturales. Observando estos n´umeros, saltan a la vista ciertas regularidades. Las llamar´e conjeturas sobre el comportamiento de la funci´on ·, aunque no tengo mucha confianza de que se mantengan para n´umeros mayores. LAGACETA 247 Los or´ıgenes de estas conjeturas son tablas como la que sigue: 36 9 12 15 18 21 24 10 100 1000 10000 100000 1000000 10000000 100000000 22 220 2200 22000 220000 2200000 22000000 21 210 2101 21010 210100 2101000 21010000 202 2100 21000 210000 2100000 21000000 201 2020 20200 202000 2020000 20200000 122 2010 20100 201000 2010000 20100000 2002 20020 200222 2002220 20022200 2001 20010 200200 2002000 20020000 1221 20002 200100 2001000 20010000 1220 20001 200020 2000200 20002000 1212 12221 200010 2000100 20001000 1211 12210 200002 2000020 20000200 1201 12200 200001 2000010 20000100 1122 12122 122210 2000002 20000020 1121 12120 122100 2000001 20000010 1112 12111 122000 1222100 20000002 12110 121220 1221000 20000001 12102 121200 1220000 12221000 12101 121121 1212200 12210000 12012 121110 1212000 12200000 12010 121100 1211210 12122000 12001 121022 1211100 12121201 11221 121020 1211000 12120000 En ella tenemos escritos en columna los n´umeros de complejidad 3n(n=1, 2, ... , 8), escritos en base 3 y ordenados de mayor a menor. La primera observaci´on: 3n=3+nes err´onea. 107=16y 321=1+2 65= 18. Las que s´ı parecen ciertas son las siguientes conjeturas: Conjetura 1 Para cada n´umero natural n, existe un entero a≥0tal que 3jn=3(j−a)+3an,paratodon´umero natural j≥a. Definimos el conjunto A={n∈N:3jn=3j+npara todo j}. Conjetura 2 Para todo par de n´umeros naturales pyq, existe a≥0tal que, para j≥a,setienep(q3j+1)=3j+1+p+q. Al observar la tabla anterior, vemos que los mayores n´umeros de complejidad 3nson los n´umeros naturales contenidos en la sucesi´on (3nan), 248 COMPLEJIDAD DE LOS N´ UMEROS NATURALES donde anviene dada por 1,2(3 + 1) 32,26 34,2·3+1 32,2(32+1) 33,2·32+1 33,29 36,2(33+1) 34,2·33+1 34,..., ...,2(3k+1) 3k+1 ,2·3k+1 3k+1 ,... Conjetura 3 Existen tres sucesiones transfinitas de n´umeros racionales (aα)α<ξ,(bα)α<ξ,(cα)α<ξ, tales que los (mayores) n´umeros de complejidad 3n(respectivamente 3n+1,3n+2) son los (primeros) n´umeros naturales contenidos en la sucesi´on (3naα),(resp.(3nbα),(3ncα)). ξes un ordinal numerable infinito tal que ωξ =ξ. Estas sucesiones comienzan del siguiente modo (aα),1,8 9,64 81 ,7 9,20 27 ,···→2 3 160 243 ,52 81 ,···→16 27 1280 2187 ,140 243 ,···→5 9... (bα),4 3,32 27 ,10 9,256 243 ,28 27 ,···→180 81 ,26 27 ,···→8 9 640 729 ,70 81 ,···→64 81 ... (cα),2,16 9,5 3,128 81 ,14 9,···→4 3 320 243 ,35 27 ,···→32 27 95 81 ,2560 2187 ,···→10 9... donde los puntos suspensivos indican sucesiones infinitas, y los l´ımites indicados no pertenecen a las sucesiones. Conjetura 4 Las tres sucesiones son decrecientes. Los denominadores de cada t´ermino aα,bαocαson potencias de 3. Conjetura 5 Los n´umeros de la sucesi´on (aα),sonlosn´umeros del conjunto n 3n/3:n≡0mod3,yn∈A, ordenados en orden decreciente. Conjetura 6 Los n´umeros de la sucesi´on (bα),sonlosn´umeros del conjunto n 3(n−1)/3:n≡1mod3,yn∈A, ordenados en orden decreciente. Conjetura 7 Los n´umeros de la sucesi´on (cα),sonlosn´umeros del conjunto n 3(n−2)/3:n≡2mod3,yn∈A, ordenados en orden decreciente. LAGACETA 249 Lo que sigue es m´as tentativo y s´olo est´a basado en unos pocos casos. Conjetura 8 Para todo ordinal β<ξ,setiene lim n→∞ aβω+n=cβ/3,lim n→∞ bβω+n=aβ,lim n→∞ cβω+n=bβ. Esta es la base para la afirmaci´on sobre el valor de ξ, que parece debe ser al menos ξ=ωω, ya que es la menor soluci´on de ωξ =ξ. Las siguientes afirmaciones, junto con la conjetura 8, permiten predecir hasta cierto punto los valores de las sucesiones transfinitas. Conjetura 9 Los n´umeros de la sucesi´on bβω+nque converge a aβ=b/3a (con b=3a)sonn´umeros de las sucesiones p(q3j+1) 3a+j,donde b=pq, y, p(q3j+1)=3a+3j+1, y aquellos t´erminos espor´adicos de la sucesi´on 23j+2/32j+1 que est´en contenidos entre supγ<β aγyaβ. Conjetura 10 Los n´umeros de la sucesi´on cβω+nque converge a bβ= b/3a(con b=3a+1)sonn´umeros de las sucesiones p(q3j+1) 3a+j,donde b=pq, y, p(q3j+1)=3a+3j+2, y aquellos t´erminos espor´adicos de la sucesi´on 23j+1/32jque est´en contenidos entre supγ<β aγyaβ. Conjetura 11 Los n´umeros de la sucesi´on aβω+nque converge a cβ/3= b/3a(con b=3a−1)sonn´umeros de las sucesiones p(q3j+1) 3a+j,donde b=pq, y, p(q3j+1)=3a+3j, y aquellos t´erminos espor´adicos de la sucesi´on 23j/32jque est´en contenidos entre supγ<β aγyaβ. En las conjeturas 9, 10 y 11 debe tenerse en cuenta que algunos t´erminos provienen de sucesiones posteriores. As´ı, el t´ermino cω= 320/243 es el t´ermino correspondiente a j= 0 de la sucesi´on 26(4·3j+1)/3j+5,que converge a b3= 256/243. Las anteriores conjeturas permiten predecir, por ejemplo, los 200 mayores n´umeros de complejidad 30. 250 COMPLEJIDAD DE LOS N´ UMEROS NATURALES Los n´umeros de complejidad 14 divididos por 81, son los n´umeros c0=162 81 ,c 1=144 81 ,c 2=135 81 ,c 3=128 81 , c4=126 81 ,c 5=120 81 ,c 6=117 81 ,c 7=114 81 , c9=112 81 ,c 10 =111 81 ,c 11 =110 81 ,c 13 =109 81 , cω+1 =105 81 ,c ω+2 =104 81 ,c ω+3 =102 81 ,c ω+6 =100 81 , cω+8 =99 81 ,c ω+10 =98 81 ,c ω+14 =97 81 ,c 2ω=95 81 , c2ω+3 =93 81 ,c 2ω+5 =92 81 ,c 2ω+8 =91 81 ,c 3ω+4 =88 81 , c3ω+7 =87 81 ,c 3ω+15 =86 81 ,c 4ω+2 =85 81 ,c 5ω+1 =83 81 , cω2+ω+2 =79 81 ,c ω2+2ω+3 =77 81 ,71 81 ,69 81 ,67 81 ,59 81 , A los cuatro ´ultimos no tengo suficientes datos para asignarles el ordinal correspondiente. Bibliograf´ıa [AS] ALON, N., SPENCER, J.H.: “The probabilistic method”, John Wiley and Sons, New York, (1992) [C] CHERNOFF, H.: “A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations”, Annals of Mathematical Statistics,23 (1952), 493—509 [GJ] GAREY, M.R., JOHNSON, D.S.: “Computers and Intractability, a guide to the theory of NP-completeness”, W. H. Freeman and Co., (1979) [G] GUY, R.K.: “What is the least number of ones needed to represent nusing only + and ×(and parentheses)?”, American Mathematical Monthly,93 (1986), 189—190 [H] HASTAD, J.The Shrinkage exponent of de Morgan formulas is 2,Siam J. Comput. 27, (1998), 48–64 [MP] MAHLER, K., POPKEN, P.: “On a maximum problem in arithmetic (Dutch)”, Nieuw. Arch. Wiskunde,(3)1(1953), 1—15 [R] RAWSTHO R N E , D.A.: “How many 1’s are needed?”, Fibonacci Quart.,27 (1989), 14—17 [SP] SLOANE, N.J.A., PLOUFFE, S.: “The Encyclopedia of Integer Sequences”, Academic Press, London, (1995) [Z] ZWICK, U.: “A 4nlower bound on the combinatorial complexity of certain symmetric boolean functions over the basis of unate dyadic boolean functions”, Siam J. Comput., 20 (1991), 499—505 J. Arias de Reyna. Facultad de Matem´aticas, Universidad de Sevilla. P.O. Box 1160, 41080 Sevilla. e-mail: [email protected]