Complexidade inteira - Integer complexity

Na teoria dos números , a complexidade inteira de um inteiro é o menor número de uns que pode ser usado para representá-lo usando uns e qualquer número de adições , multiplicações e parênteses. Está sempre dentro de um fator constante do logaritmo do inteiro fornecido.

Exemplo

Por exemplo, o número 11 pode ser representado usando oito uns:

11 = (1 + 1 + 1) × (1 + 1 + 1) + 1 + 1.

No entanto, não tem representação usando sete ou menos unidades. Portanto, sua complexidade é oito.

As complexidades dos números 1, 2, 3, ... são

1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, ... (sequência A005245 no OEIS )

Os menores números com complexidade 1, 2, 3, ... são

1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, ... (sequência A005520 no OEIS )

Limites superior e inferior

A questão de expressar inteiros desta forma foi originalmente considerada por Mahler & Popken (1953) . Eles pediram o maior número com uma determinada complexidade $k$ ; mais tarde, Selfridge mostrou que este número é

{\ displaystyle 2 ^ {x} 3 ^ {(k-2x) / 3} {\ text {onde}} x = -k {\ bmod {3}}.}

Por exemplo, quando $k = 10$ , $x = 2$ e o maior número inteiro que pode ser expresso usando dez unidades é $2232 = 36$ . Sua expressão é

(1 + 1) × (1 + 1) × (1 + 1 + 1) × (1 + 1 + 1).

Assim, a complexidade de um número inteiro $n$ é de pelo menos $3 log 3 n$ . A complexidade de $n$ é no máximo $3 log 2 n$ (aproximadamente $4,755 log 3 n$ ): uma expressão desse comprimento para $n$ pode ser encontrada aplicando o método de Horner à representação binária de $n$ . Quase todos os inteiros têm uma representação cujo comprimento é limitado por um logaritmo com um fator constante menor, $3,529 log 3 n$ .

Algoritmos e contra-exemplos

As complexidades de todos os inteiros até algum limite $N$ podem ser calculadas no tempo total $O (N 1.222911236)$ .

Algoritmos para calcular a complexidade inteira têm sido usados para refutar várias conjecturas sobre a complexidade. Em particular, não é necessariamente o caso em que a expressão ótima para um número $n$ é obtida subtraindo um de $n$ ou expressando $n$ como o produto de dois fatores menores. O menor exemplo de um número cuja expressão ótima não é desta forma é 353942783. É um número primo e, portanto, também refuta a conjectura de Richard K. Guy de que a complexidade de todo número primo $p$ é um mais a complexidade de $p - 1$ . Na verdade, isso pode ser demonstrado . Além disso, Venecia Wang deu alguns exemplos interessantes, ou seja , , , mas . ${\ displaystyle || p || = || p-1 || = 63}$ ${\ displaystyle || 743 \ times 2 || = || 743 || = 22}$ ${\ displaystyle || 166571 \ times 3 || = || 166571 || = 39}$ ${\ displaystyle || 97103 \ times 5 || = || 97103 || = 38}$ ${\ displaystyle || 23 ^ {2} || = 20}$ ${\ displaystyle 2 || 23 || = 22}$