230 COMPLEJIDAD DE LOS N´
UMEROS NATURALES
Complejidad de los n´ume os na u ales
po
J. A ias de Reyna
1.INTRODUCCI ´
ON
1.COMPLEJIDAD DE UN N´
UMERO NATURAL
Voy a habla de un ema apa en emen e meno , que puede comp ende
un es udian e con ca o ce a˜nos, pe o que encie a dificul ades muy p o un-
das. Lle o alg´un iempo in e esado en uno de los p oblemas que conside o
m´as impo an es de en e los que ienen plan eados los ma em´a icos: el
p oblema P?
=NP. En es e caso, la p ime a dificul ad es expone el p o-
blema de o ma asequible a un ma em´a ico adicional, digamos que a un
especialis a en An´alisis Ma em´a ico. No es ´es a una cues i´on banal, pues
c eo que debe pode plan ea se como un p oblema de aco aci´on, y que
en iendan el p oblema los analis as puede se el paso p incipal hacia la
soluci´on. La cues i´on de la que quie o habla aqu´ısu gi´oenunin en ode
consegui es a explicaci´on.
Empecemos con la p egun a p incipal: dado un n´ume o na u al n,
¿cu´an os unos son necesa ios pa a esc ibi n? Po ejemplo,
19=1+(1+1)(1+1+1)(1+1+1),
luego no se necesi an m´as de 9 unos pa a esc ibi el n´ume o 19. Decimos
en onces que la complejidad de 19 es meno o igual a 9, lo que esc ibi emos
ab e iadamen e po 19≤9. Na u almen e la complejidad de 19 se ´ael
n´ume o de unos en la ep esen aci´on de 19 que menos unos u ilice. S´olo se
admi en exp esiones con las ope aciones de suma y de p oduc o.
Los p ime os alo es de la unci´on complejidad pueden calcula se con
no demasiado abajo:
1,2,3,4,5,5,6,6,6,7,8,7,8,8,8,8,9,8,9,9,...
Vemos que no o man una sucesi´on mon´o ona: 8 = 11>12=7.
Cuando en alg´un p oblema ma em´a ico su ge una sucesi´on de n´
ume os
na u ales, hay algo que debemos hace : consul a The Encyclopedia o
In ege Sequences de Sloane y Plouffe [SP]. En ella encon amos la sucesi´on
an e io y nos emi e al a ´ı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 unci´on n→nde N→N
al que pa a odo pa de n´ume os na u ales mynse iene
1=1,m+n≤m+n,m·n≤m+n.
De hecho es la mayo unci´on que cumple es as condiciones. Pa a p oba
´es a y o as afi maciones es ´u il in oduci o o concep o: el de exp esi´on.
2.DEFINICI ´
ON DE LAS EXPRESIONES
Una exp esi´on es una sucesi´on de s´ımbolos. Los s´ımbolos pe mi idos
son los cua o siguien es x, +, (, ). No oda sucesi´on de s´ımbolos es una
exp esi´on. Ejemplos de exp esiones son:
(x + x);(x+(xx));(x+((x+x)((x+(x+x))(x+(x+x))))).
La definici´on o mal es una definici´on induc i a:
(a) xes una exp esi´on.
(b) Si AyBson exp esiones, ambi´en lo son (A+B) y(AB).
(c) S´olo son exp esiones las sucesiones fini as de s´ımbolos que esul en
de aplica ei e adamen e las eglas (a) y (b).
Definimos el alo de una exp esi´on Acomo el n´ume o (A)que esul a
de sus i ui xpo 1 y e ec ua las ope aciones indicadas. De nue o usamos
la inducci´on pa a defini el alo : (x)=1,ysiAyBson exp esiones
((A+B))= (A)+ (B)y ((AB))= (A) (B).
Dada una exp esi´on, podemos defini su complejidad como el n´ume o
de le as iguales a xque con iene, po ejemplo, (x+(xx))=3.Sea
Eel conjun o de las exp esiones. La definici´on de la complejidad puede
exp esa se aho a en la o ma
n=in {A:A∈Ey (A)=n}.
Si que emos calcula el alo de ndebemos usa la p oposici´on si-
guien e:
P oposici´on 1 Pa a odo n´ume o na u al n∈N,
n=min(d+n/d,j+n−j): 2≤d≤√n, d/n
1≤j≤n/2
P ueba. Supongamos que n>1. Sea Euna exp esi´on ´op ima de n,es
deci una que d´e su complejidad, n=E. Aho a la exp esi´on se ´ao
232 COMPLEJIDAD DE LOS N´
UMEROS NATURALES
bien E=(A +B) ´obienE=(AB). Pongamos a= (A), b= (B). De es e
modo, ´obienn=a+byn=a+b,´obienn=ab yn=a+b.
En el p ime caso, si jel meno de los dos, ayb,se iene1≤j≤n/2,
y en el segundo, si des el meno de los dos, des un di iso de ncon
2≤d≤√n. Na u almen e, pa a que el azonamien o an e io sea ´alido,
debemos comp oba que, si Ees una exp esi´on ´op ima de n, en onces Ay
Bdeben se exp esiones ´op imas de ayb. Dejamos dicha comp obaci´on al
lec o .
Usando el esquema an e io hemos calculado, con el p og ama Ma he-
ma ica, los alo es de npa a 1 ≤n≤200 000.
3.COTAS
P oposici´on 2 Sea P:N→Runa aplicaci´on al que
P(1) = 1,P(n+m)≤P(n)+P(m),P(n·m)≤P(n)+P(m).
En onces, pa a odo n∈N,se ieneP(n)≤n.
P ueba. Vemos que, pa a oda exp esi´on A,se ieneP (A)≤A.
Usamos inducci´on. Es cie o pa a A=x,y,siescie opa aAyB,es
ambi´en cie o pa a (A+B) y(AB). En e ec o, pa a el p oduc o:
P ((AB))=P (A) (B)≤P (A)+P (B)≤A+B=(AB),
yuna gumen oan´alogo ale pa a la suma. (Obse a que, po la definici´on
de ,se iene ((A+B))= (A)+ (B)y ((AB))= (A) (B)).
Bas a aho a oma ´ınfimo en P (A)≤Apa a odas las exp esiones
A ales que n= (A). Se ob iene en onces P(n)≤n.
Co ola io 3 Pa a odo n´ume o na u al n,log2(1 + n)≤n.
P ueba. Bas a comp oba las p opiedades de P(n)=log
2(1 + n).
M´as adelan e en el co ola io 9 mejo a emos es a desigualdad.
3.COTAS SUPERIORES
A con inuaci´on es ablecemos una co a supe io . Con es e obje o in o-
ducimos una unci´on L:N→N.
De inici´on 4 De inimos la unci´on Linduc i amen e:
(a) L(1) = 1.
LAGACETA 233
(b) Si pes un n´ume o p imo, L(p)=1+L(p−1).
(c) Si n=p1p2···pkes un p oduc o de n´ume os p imos iguales o
di e en es, en onces L(p1p2···pk)=L(p1)+L(p2)+···L(pk).
Con es a definici´on es cla o que si n=ab, siendo aybmayo es o
iguales a 2, en onces se iene L(n)=L(a)+L(b).
P oposici´on 5 Pa a odo n∈N,se iene
n≤L(n).
P ueba. Podemos p oba lo po inducci´on. Pa a n= 1, enemos 1=
L(1) = 1. Supongamos que se cumple k≤L(k), pa a odo k<n.
Pueden da se dos posibilidades: Si n=pes un n´ume o p imo,
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).
P oposici´on 6 Pa a odo n≥2se iene
L(n)≤3
log 2(log n).
P ueba. En p ime luga , pues o que L(2) = 2, el esul ado es cie o pa a
n=2.
Supongamos aho a que n≥3, y que la desigualdad es ´alida pa a
n´ume os na u ales meno es que n.
Si n=pes p imo, se iene
L(p)=1+L(p−1) = 1 + 2 + Lp−1
2≤3+ 3
log 2 logp−1
2.(1)
Que emos que es o sea
≤3
log 2(log p).
Es deci , bas a comp oba que
3≤3
log 2 log2p
p−1,(2)
234 COMPLEJIDAD DE LOS N´
UMEROS NATURALES
lo cual se cumple pa a p≥3.
Si n=ab,conayb≥2, se iene
L(ab)=L(a)+L(b)≤3
log 2(log a)+ 3
log 2(log b)= 3
log 2(log ab).
No a 1. No sabemos si la cons an e 3/log 2 en el eo ema an e io
es ´op ima. Analizando la p ueba, sospechamos que el cocien e L(n)/log n
es g ande cuando n=pksea un p imo al que exis a una sucesi´on de
p imos (pj)k
j=1 de o ma que pj=2pj+1 + 1. Po ejemplo, los n´ume os 89,
179, 359, 719, 1439, 2879 son odos p imos, y el m´aximo alo del cocien e
L(n)/log nque conocemos es
L(2879)
log 2879 =3.766384578 ···<4.328085123 ···=3
log 2.
La di e encia p incipal en e las dos unciones L(·)y·consis e en
que L(·) es mul iplica i a y ·no. Pa a cada pa eja de n´ume os nym
mayo es que 1, la unci´on L e ifica L(nm)=L(n)+L(m). En cambio,
exis en nymmayo es que 1 ales que nm<n+m.Di emosque
n·mes una mala ac o izaci´on.
En la figu a 1 si uamos un pun o en (n, m)cada ezquen×mes mala
ac o izaci´on. La figu a cub e odos los ac o es n´o m≤60.
Na u almen e 1 ·mes siemp e mala ac o izaci´on, pe o en la figu a
apa ecen o as egula idades so p enden es. As´ı, sal an a la is a cie as
alineaciones de pun os, las m´as p ominen es se si uan en n= 23, 41 y 59,
que me ecen una explicaci´on.
Es os n´ume os, di ´ıamos que malos ac o es, pa ecen ene una com-
plejidad g ande. Definimos la sucesi´on de n´ume os con complejidad g ande
nk: son aquellos ales que nkes la meno soluci´on de n=k. Los p ime os
alo es de es a 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 apa ece en [SP] con alguna e a a. Encon amos as´ı la e e encia a
Raws ho ne [R].

LAGACETA 235
Figu a 1. Malos ac o es
4.VALORES MEDIOS
Exis e o a p ueba de que n≤3logn/ log 2. Consis e en obse a
que, si esc ibimos nen bina io n=k−1
j=0 εj2j+2
k, enemos una o ma de
exp esa n:
n=ε0+2(ε1+2(ε2+···+2(εk−2+2(εk−1+2))···)),
donde podemos sus i ui cada 2 po 1 + 1 y cada ci a εjes 0 ´o1.Dees e
modo ob enemos una exp esi´on de nusando a lo m´as 2k+kunos, donde
kcumple 2k≤n<2k+1.Luegon≤3logn/ log 2.
El azonamien o an e io p ueba que la unci´on L2(n)=2k+ε0+ε1+
···εk−1es o a co a supe io de n.Lacompa aci´on de L2(n)ydeL(n)
no es ´acil. En e los p ime os 1000 n´ume os, gene almen e L(n)esmeno ,
pe o es o iene excepciones. La p ime a es L2(161) = 16 <17 = L(161).
En es e ango la di e encia es peque˜na.
236 COMPLEJIDAD DE LOS N´
UMEROS NATURALES
La unci´on L2(n) puede usa se pa a ob ene in o maci´on sob e la un-
ci´on ·. Conside emos el conjun o de los n´ume os nque se esc iben en
bina io en la o ma 1εk−1...ε
0, es deci , con k+1 ci as. Seg´un la exp esi´on
an e io , enemos
n≤2k+ε0+···+εk−1.
Podemos pensa que εjson a iables alea o ias independien es de media
1/2. La desigualdad de Che noff ( e [C] y pa a 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. Finalmen e, con
x=√log k,
Pn>5k/2+klog k≤2k−2.
Luego en e los 2k alo es de ncon 2k≤n<2k+1 alom´as (2/k2)2k
e ifican n>5k/2+√klog k.Losdem´as, la mayo pa e, cumplen
n≤5k
2+klog k=5
2
log n
log 2 +O(log nlog log n).
De alg´un modo podemos deci que pa a casi odos los alo es g andes de
nse iene
n≤5
2
log n
log 2 +O(log nlog log n).
La co a supe io L(n) es ex ao dina iamen e buena pa a alo es pe-
que˜nos de n. Po ejemplo, en e los p ime os 220 alo es de n,L(n)=n,
sal o pa a los indicados en la abla siguien e:
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 es os casos la co a L2(n) es igual o mayo que L(n), sal o pa a el
alo 161.
Las dos unciones L(n)yncoinciden en 771 alo es de npa a 1 ≤
n≤1000, siendo la di e encia igual a 1 en los o os 229 casos, sal o unas
pocas excepciones.
LAGACETA 237
4.VALORES PARTICULARES
5.N´
UMEROS CON COMPLEJIDAD PEQUE˜
NA
Una co a in e io pa a la complejidad n esul ade esol e lacues-
i´on de qu´en´ume o Npodemos alcanza con munos. Es o es, dado m,
cu´al es el mayo n´ume o na u al N al que N=m. La espues a, g osso
modo, es que debemos ag upa los munos disponibles en g upos de 3 y
mul iplica los. Pa a e es o definimos el concep o de exp esi´on ex emal.
Sea Mmuna exp esi´on con Mm=m, (es deci , Mmes ´a o madaconm
xsy las ope aciones de suma y p oduc o), y al que su alo (Mm)sea
m´aximo en e las exp esiones o madas con munos, es o es
N= (Mm)= sup
A=m
(A).
Di emos que Mmes ex emal.
Afi mamos en onces que N=m. En e ec o, po se N= (Mm)y
Mm=m,se ieneN≤m. Supongamos, po con a, que uese N<
m.Exis i ´ıa en onces una exp esi´on B al que (B)=NyB=N<m.
Sea d al que m=d+B. Podemos cons ui una exp esi´on Cde la o ma
C=B+x+···+x,y alqueC=B+d=my (C)= (B)+d>N.
Es o con adice la definici´on de Mm.
Es ´acil comp oba que las siguien es exp esiones son ex emales
M1=x,M2=(x + x),M3=(x + (x+x)),
M4=(x+x)(x+x),M5=(x+(x+x))(x+x),...
Como emos, dado m,laexp esi´on ex emal Mmno es ´unica, po ejemplo
M4=(x+(x+(x+x))) es o a posibilidad.
Usa emos una no aci´on poco p ecisa, po ejemplo, esc ibi emos Ma
3M2
pa a deno a cualquie exp esi´on que enga esa o ma sin p ecisa c´omo
cons uimos el p oduc o a pa i de los ac o es. As´ıM4
3puede deno a
cualquie a de las exp esiones ((M3M3)(M3M3)),(M3(M3(M3M3))),ocualquie
o a o ma de ag upa los ac o es.
P oposici´on 7 Sean M2=(x + x),M3=(x + (x+x)) yM4=(x+x)(x+x).
Pa a n>1, las exp esiones Mnde inidas po
Mn=
⎧
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎩
Mk
3si n=3k,
Mk−1
3M4si n=3k+1,
Mk
3M2si n=3k+2,
son ex emales.
238 COMPLEJIDAD DE LOS N´
UMEROS NATURALES
P ueba. Di ec amen e podemos comp oba que el esul ado es ´alido
pa a n=2,3y4.
Supongamos que es ´alida pa a odo s<ny a emos de p oba lo pa a
n≥5. Cie amen e exis e una exp esi´on ex emal Kcon K=n.Exis en
en onces dos exp esiones AyB ales que K=(A+B) obienK=(AB).Tan o
Acomo Bson ex emales, en o o caso Kno lo se ´ıa. Podemos cambia
AyBpo exp esiones ex emales de la misma complejidad y la exp esi´on
esul an e Ksegui ´a siendo ex emal. Po an o sin es ingi la gene alidad
podemos supone , usando la hip´o esis de inducci´on, que AyBson de la
o ma dada en el enunciado, o bien A=xyBcomo en el enunciado
El caso de se K=(A+B) s´olo es posible si (A)o (B) = 1, (en o o
caso la exp esi´on (AB) con adice la ex emalidad de K). Pe o K=(x+Mk
3),
K=(x+Mk−1
3M4),oK=(x+Mk
3M2)es imposible con n≥5. Pues es as
exp esiones cla amen e no son ex emales. (Compa a las con Mk−1
3M4,Mk
3M2,
oMk+1
3 espec i amen e).
Llegamos pues a la conclusi´on de que K=(AB), siendo AyBde la o ma
dada en el enunciado. Algunas de las combinaciones no son posibles: po
ejemplo, A=Mk
3M2yB=Mj−1
3M4no es posible pues Mk+j−1
3M4M2es mejo ada
po Mk+j−1
3yKno se ´ıa ex emal. Un es udio caso po caso, demues a que
Kes de la o ma dada en el enunciado.
De lo an e io se sigue
Co ola io 8 Pa a a=0,1´o 2yb∈Nse iene
2a3b=2a+3b, a =0,1,2.
Todo n´ume o na u al n>1 se esc ibe de mane a ´unica en la o ma
n=2a+3bsiendo a=0,1´o 2. En ese caso 2a3bes el mayo n´ume o m
al que m=n.Po an om>2a3bimplica m>2a+3b.
Definimos g:N→Nen la o ma
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 iene en onces que pa a odo n,g(n)≤n.
Co ola io 9 Pa a odo n≥1 enemos
3log n
log 3 ≤n≤L(n)≤3log n
log 2 .
LAGACETA 245
sea en onces a
b(x12,...,x
a−1,a) la unci´on que ale 1 si y s´olo si exis en b
´e ices ales que es ´en odos conec ados en el g a o.
Cabe pensa que  a
b≥a
b, ya que pa a conoce el alo de a
ben un
g a o necesi amos comp oba cada conjun o de b ´e ices. Se puede p oba
que, si es o es as´ı, en onces P=NP.Dees emodop oba  a
b≥a
b
se con ie e, a mi pa ece , en el camino m´as p ome edo de p oba que
P=NP.
Vol iendo a la complejidad de los na u ales, un p oblema an´alogo al
an e io es el siguien e, plan eado po Guy [G]:
P oblema ¿Exis e una sucesi´on de na u ales (an) ales que
lim
n→∞ an
log an
>3
log 3 ?(1)
Un candida o es la sucesi´on 2n. Todos los alo es calculados has a
aho a cumplen 2n=2n. Sel idge p egun a (c . [G]) si exis e n al que
2n<2n.
Si pa a alg´un alo de nexis ie a k al que 2n=3
k, (cosa imposi-
ble po o a pa e), la segunda exp esi´on da ´ıa un alo de 2n<2n.
Na u almen e la en aja se ´ıa mayo mien as mayo ue a n. Aunque lo
an e io es imposible, no cabe desca a que se den o o ipo de casualida-
des que hagan posible 2n<2n. Po ejemplo, si el desa ollo en base 3 de
2n u ie a ci as con poco peso. De nue o es o iene pocas p obabilidades
de ocu i ; aho a bien, pod ´ıa a a se de o o ipo de exp esi´on de 2n.
La si uaci´on aqu´ıesque,si engounn´ume o que ya puedo exp esa en la
o ma
(1 + 1)(1 + 1) ···(1 + 1),
pa ece dificil encon a o a exp esi´on que con menos unos conduzca al
mismo esul ado. Tenemos un casi-ejemplo i ial 4 = (1 + 1)(1 + 1) =
1+1+1+1.Aqu´ı apa ece el mismo n´ume o de unos en ambos lados, po
es o lo llamo casi-ejemplo. Pe o pueden da se casi ejemplos no i iales,
como el que sigue:
227 =1+(1+2·3)(1 + 23·32)(1 + 29·33(1 + 2 ·32)).
Bas asus i ui 2po 1+1y3po 1+1+1pa aob ene unaexp esi´on
al e na i a de 227 con 57 unos, y en la que la es uc u a mul iplica i a del
n´ume o 227 deja de usa se.
La igualdad an e io p ueba que 227 −1≤56. A pesa de una in ensa
b´usqueda no he conseguido encon a n>2 alque2n−1<2n−1, sin
emba go c eo que es o puede ocu i .

246 COMPLEJIDAD DE LOS N´
UMEROS NATURALES
La e idencia pa ece es a del lado de que exis e la sucesi´on que cumpla
(1). Bas a obse a el g ´afico en la figu a 2. En ´el se ha si uado un peque˜no
disco con cen o en cada pun o (n, n)con1≤n≤2000 y ambi´en se
han dibujado las g ´aficas de las cu as sua es que aco an a n, es deci
3(log )/log 3 y 3(log )/log 2, as´ıcomodelacu a5log /2 log 2. Los pun-
os se unen y o man en la figu a unas lineas pa alelas al eje x.Vemosquela
co a supe io pa ece muy mala y que apa en emen e n≤5log /2 log 2,
cuando s´olo hemos p obado que ap oximadamen e es a desigualdad se cum-
ple pa a casi odo n∈N.
500 1000 1500 2000
15
20
25
30
Figu a 2
Pe o es a figu a nada dice sob e la exis encia del l´ımi e lim n/log n,
queesdeloquese a a.S´olo emos que en e los 2000 p ime os alo es
de nes a sucesi´on oscila en e unos l´ımi es p ´oximos a 5/2log2 y 3/log 3.
6.CONJETURAS
He calculado median e la p oposici´on 1 la complejidad de los p ime os
200.000 n´ume os na u ales. Obse ando es os n´ume os, sal an a la is a
cie as egula idades. Las llama ´e conje u as sob e el compo amien o de
la unci´on ·, aunque no engo mucha confianza de que se man engan
pa a n´ume os mayo es.
LAGACETA 247
Los o ´ıgenes de es as conje u as son ablas 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 enemos esc i os en columna los n´ume os de complejidad 3n(n=1,
2, ... , 8), esc i os en base 3 y o denados de mayo a meno .
La p ime a obse aci´on: 3n=3+nes e ´onea. 107=16y
321=1+2
65= 18. Las que s´ı pa ecen cie as son las siguien es
conje u as:
Conje u a 1 Pa a cada n´ume o na u al n, exis e un en e o a≥0 al que
3jn=3(j−a)+3an,pa a odon´ume o na u al j≥a.
Definimos el conjun o A={n∈N:3jn=3j+npa a odo j}.
Conje u a 2 Pa a odo pa de n´ume os na u ales pyq, exis e a≥0 al
que, pa a j≥a,se ienep(q3j+1)=3j+1+p+q.
Al obse a la abla an e io , emos que los mayo es n´ume os de com-
plejidad 3nson los n´ume os na u ales con enidos en la sucesi´on (3nan),
248 COMPLEJIDAD DE LOS N´
UMEROS NATURALES
donde an iene dada po
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 ,...
Conje u a 3 Exis en es sucesiones ans ini as de n´ume os acionales
(aα)α<ξ,(bα)α<ξ,(cα)α<ξ, ales que los (mayo es) n´ume os de complejidad
3n( espec i amen e 3n+1,3n+2) son los (p ime os) n´ume os na u ales
con enidos en la sucesi´on (3naα),( esp.(3nbα),(3ncα)).
ξes un o dinal nume able in ini o al que ωξ =ξ.
Es as sucesiones comienzan del siguien e 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 pun os suspensi os indican sucesiones infini as, y los l´ımi es in-
dicados no pe enecen a las sucesiones.
Conje u a 4 Las es sucesiones son dec ecien es. Los denominado es
de cada ´e mino aα,bαocαson po encias de 3.
Conje u a 5 Los n´ume os de la sucesi´on (aα),sonlosn´ume os del
conjun o
n
3n/3:n≡0mod3,yn∈A,
o denados en o den dec ecien e.
Conje u a 6 Los n´ume os de la sucesi´on (bα),sonlosn´ume os del
conjun o
n
3(n−1)/3:n≡1mod3,yn∈A,
o denados en o den dec ecien e.
Conje u a 7 Los n´ume os de la sucesi´on (cα),sonlosn´ume os del
conjun o
n
3(n−2)/3:n≡2mod3,yn∈A,
o denados en o den dec ecien e.
LAGACETA 249
Lo que sigue es m´as en a i o y s´olo es ´a basado en unos pocos casos.
Conje u a 8 Pa a odo o dinal β<ξ,se iene
lim
n→∞ aβω+n=cβ/3,lim
n→∞ bβω+n=aβ,lim
n→∞ cβω+n=bβ.
Es a es la base pa a la afi maci´on sob e el alo de ξ, que pa ece debe
se al menos ξ=ωω, ya que es la meno soluci´on de ωξ =ξ.
Las siguien es afi maciones, jun o con la conje u a 8, pe mi en p edeci
has a cie o pun o los alo es de las sucesiones ansfini as.
Conje u a 9 Los n´ume os de la sucesi´on bβω+nque con e ge a aβ=b/3a
(con b=3a)sonn´ume os de las sucesiones
p(q3j+1)
3a+j,donde b=pq, y, p(q3j+1)=3a+3j+1,
y aquellos ´e minos espo ´adicos de la sucesi´on 23j+2/32j+1 que es ´en con-
enidos en e supγ<β aγyaβ.
Conje u a 10 Los n´ume os de la sucesi´on cβω+nque con e ge a bβ=
b/3a(con b=3a+1)sonn´ume os de las sucesiones
p(q3j+1)
3a+j,donde b=pq, y, p(q3j+1)=3a+3j+2,
y aquellos ´e minos espo ´adicos de la sucesi´on 23j+1/32jque es ´en con e-
nidos en e supγ<β aγyaβ.
Conje u a 11 Los n´ume os de la sucesi´on aβω+nque con e ge a cβ/3=
b/3a(con b=3a−1)sonn´ume os de las sucesiones
p(q3j+1)
3a+j,donde b=pq, y, p(q3j+1)=3a+3j,
y aquellos ´e minos espo ´adicos de la sucesi´on 23j/32jque es ´en con enidos
en e supγ<β aγyaβ.
En las conje u as 9, 10 y 11 debe ene se en cuen a que algunos
´e minos p o ienen de sucesiones pos e io es. As´ı, el ´e mino cω= 320/243
es el ´e mino co espondien e a j= 0 de la sucesi´on 26(4·3j+1)/3j+5,que
con e ge a b3= 256/243.
Las an e io es conje u as pe mi en p edeci , po ejemplo, los 200 ma-
yo es n´ume os de complejidad 30.
250 COMPLEJIDAD DE LOS N´
UMEROS NATURALES
Los n´ume os de complejidad 14 di ididos po 81, son los n´ume os
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 cua o ´ul imos no engo suficien es da os pa a asigna les el o -
dinal co espondien e.
Bibliog a ´ıa
[AS] ALON, N., SPENCER, J.H.: “The p obabilis ic me hod”, John Wiley and Sons, New
Yo k, (1992)
[C] CHERNOFF, H.: “A measu e o he asymp o ic efficiency o es s o a hypo hesis based
on he sum o obse a ions”, Annals o Ma hema ical S a is ics,23 (1952), 493—509
[GJ] GAREY, M.R., JOHNSON, D.S.: “Compu e s and In ac abili y, a guide o he heo y
o NP-comple eness”, W. H. F eeman and Co., (1979)
[G] GUY, R.K.: “Wha is he leas numbe o ones needed o ep esen nusing only + and
×(and pa en heses)?”, Ame ican Ma hema ical Mon hly,93 (1986), 189—190
[H] HASTAD, J.The Sh inkage exponen o de Mo gan o mulas is 2,Siam J. Compu . 27,
(1998), 48–64
[MP] MAHLER, K., POPKEN, P.: “On a maximum p oblem in a i hme ic (Du ch)”, Nieuw.
A ch. Wiskunde,(3)1(1953), 1—15
[R] RAWSTHO R N E , D.A.: “How many 1’s a e needed?”, Fibonacci Qua .,27 (1989), 14—17
[SP] SLOANE, N.J.A., PLOUFFE, S.: “The Encyclopedia o In ege Sequences”, Academic
P ess, London, (1995)
[Z] ZWICK, U.: “A 4nlowe bound on he combina o ial complexi y o ce ain symme ic
boolean unc ions o e he basis o una e dyadic boolean unc ions”, Siam J. Compu .,
20 (1991), 499—505
J. A ias de Reyna. Facul ad de Ma em´a icas, Uni e sidad de Se illa.
P.O. Box 1160, 41080 Se illa.
e-mail: [email p o ec ed]