Heltallskompleksitet - Integer complexity

I tallteori er heltallskompleksiteten til et helt tall det minste antallet av dem som kan brukes til å representere det ved hjelp av et og et hvilket som helst antall tillegg , multiplikasjoner og parenteser. Det er alltid innenfor en konstant faktor for logaritmen til det gitte heltallet.

Eksempel

For eksempel kan tallet 11 være representert ved hjelp av åtte:

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

Imidlertid har den ingen representasjon ved bruk av syv eller færre. Derfor er kompleksiteten åtte.

Kompleksiteten til tallene 1, 2, 3, ... er

1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, ... (sekvens A005245 i OEIS )

De minste tallene med kompleksitet 1, 2, 3, ... er

1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, ... (sekvens A005520 i OEIS )

Øvre og nedre grense

Spørsmålet om å uttrykke heltall på denne måten ble opprinnelig vurdert av Mahler & Popken (1953) . De ba om det største antallet med en gitt kompleksitet $k$ ; senere viste Selfridge at dette tallet er

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

For eksempel når $k = 10$ , $x = 2$ og det største heltallet som kan uttrykkes ved hjelp av ti, er $2232 = 36$ . Dets uttrykk er

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

Dermed er kompleksiteten til et helt tall $n$ minst $3 log 3 n$ . Kompleksiteten til $n$ er maksimalt $3 log 2 n$ (omtrent $4,755 log 3 n$ ): et uttrykk av denne lengden for $n$ kan bli funnet ved å anvende Horners metode på den binære representasjonen av $n$ . Nesten alle heltall har en representasjon hvis lengde er avgrenset av en logaritme med en mindre konstant faktor, $3,529 log 3 n$ .

Algoritmer og moteksempler

Kompleksiteten til alle heltall opp til en eller annen terskel $N$ kan beregnes i total tid $O (N 1.222911236)$ .

Algoritmer for beregning av heltallskompleksiteten har blitt brukt for å motbevise flere antagelser om kompleksiteten. Spesielt er det ikke nødvendigvis slik at det optimale uttrykket for et tall $n$ oppnås verken ved å trekke en fra $n$ eller ved å uttrykke $n$ som produktet av to mindre faktorer. Det minste eksemplet på et tall hvis optimale uttrykk ikke er av denne formen, er 353942783. Det er et primtall , og motbeviser derfor også en antagelse av Richard K. Guy om at kompleksiteten til hvert primtall $p$ er ett pluss kompleksiteten til $p - 1$ . Man kan faktisk vise det . Videre Venecia Wang ga noen interessante eksempler, det vil si , , , men . ${\ 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}$