Koko sarja - Complete sequence

On matematiikka , joka on sekvenssi on luonnollisia lukuja kutsutaan täydellinen sekvenssi , jos jokainen positiivinen kokonaisluku voidaan ilmaista summa arvojen sekvenssin, käyttäen kunkin arvo korkeintaan kerran.

Esimerkiksi kahden (1, 2, 4, 8, ...) tehosekvenssi , binäärisen numeerisen järjestelmän perusta , on täydellinen sekvenssi; mikä tahansa luonnollinen luku, voimme valita arvot, jotka vastaavat 1 bittiä sen binäärisessä esityksessä, ja laskea ne yhteen kyseisen luvun saamiseksi (esim. 37 = 100101 ₂ = 1 + 4 + 32). Tämä jakso on minimaalinen, koska mitään arvoa ei voida poistaa siitä tekemättä joitakin luonnollisia lukuja mahdottomaksi edustaa. Yksinkertaiset esimerkit sekvensseistä, jotka eivät ole täydellisiä, sisältävät parilliset luvut , koska parillisten numeroiden lisääminen tuottaa vain parillisia numeroita - parittomia lukuja ei voida muodostaa.

Edellytykset täydellisyydelle

Ilman yleisyyden menetystä, oletetaan, että sekvenssi _n on ei-alenevassa järjestyksessä, ja määrittää osittaisten summien ja _n kuin:

${\ displaystyle s_ {n} = \ summa _ {m = 0} ^ {n} a_ {m}}$ .

Sitten olosuhteet

${\ displaystyle a_ {0} = 1 \,}$

${\ displaystyle s_ {k-1} \ geq a_ {k} -1 {\ text {kaikille}} k \ geq 1}$

ovat molemmat välttämättömiä ja riittäviä _n olla täydellinen sekvenssi.

Edellä esitetyn seurauksena todetaan, että

${\ displaystyle a_ {0} = 1 \,}$

${\ displaystyle 2a_ {k} \ geq a_ {k + 1} {\ text {kaikille}} k \ geq 1}$

ovat riittäviä _n olla täydellinen sekvenssi.

On kuitenkin olemassa kokonaisia ​​sekvenssejä, jotka eivät tyydytä tätä seurausta, esimerkiksi (sekvenssi A203074 on OEIS ), joka koostuu numero 1 ja ensimmäisen prime jokaisen 2: n potenssi.

Muut täydelliset sekvenssit

Täydelliset sekvenssit sisältävät:

• Numeron 1 sekvenssi, jota seuraavat alkuluvut (tutkivat SS Pillai ja muut); tämä seuraa Bertrandin postulaatista .
• Käytännön numeroiden sekvenssi, jolla on 1 ensimmäinen termi ja joka sisältää kaikki muut 2: n voimat osajoukkona. (sekvenssi A005153 on OEIS )
• Fibonacci numerot , sekä Fibonacci numerot Jonkin numero poistetaan. Tämä seuraa identiteetistä, että ensimmäisen n Fibonacci-luvun summa on ( n  + 2) toinen Fibonacci-luku miinus 1 (katso Fibonacci_numbers # Second_identity ).

Sovellukset

Aivan kuten kahden potenssi muodostaa täydellisen sekvenssin binäärisen numerojärjestelmän ansiosta, itse asiassa mitä tahansa täydellistä sekvenssiä voidaan käyttää kokonaislukujen koodaamiseen bittijonoina. Oikea bittiasema osoitetaan sekvenssin ensimmäiselle, pienimmälle jäsenelle; seuraava oikealle seuraavaan jäseneen; ja niin edelleen. Bitit, jotka on asetettu arvoon 1, sisältyvät summaan. Nämä esitykset eivät välttämättä ole ainutlaatuisia.

Fibonacci-koodaus

Esimerkiksi Fibonacci-aritmeettisessa järjestelmässä, joka perustuu Fibonacci-sekvenssiin, numero 17 voidaan koodata kuudella eri tavalla:

  110111 (F ₆ + F ₅ + F ₃ + F ₂ + F ₁ = 8 + 5 + 2 + 1 + 1 = 17, suurin muoto)

  111001 (F ₆ + F ₅ + F ₄ + F ₁ = 8 + 5 + 3 + 1 = 17)

  111010 (F ₆ + F ₅ + F ₄ + F ₂ = 8 + 5 + 3 + 1 = 17)

1000111 (F ₇ + F ₃ + F ₂ + F ₁ = 13 + 2 + 1 + 1 = 17)

1001001 (F ₇ + F ₄ + F ₁ = 13 + 3 + 1 = 17)

1001010 (F ₇ + F ₄ + F ₂ = 13 + 3 + 1 = 17, minimaalinen muoto, kuten käytetään Fibonacci-koodauksessa )

Yllä olevassa maksimilomakkeessa käytetään aina arvoa F ₁ ja sillä on aina jäljessä oleva muoto. Täyden koodaussekvenssin ilman perään yksi löytyy (sekvenssi A104326 on OEIS ). Hylkäämällä jälkimmäinen, yllä olevan koodaus 17: lle tapahtuu A104326: n 16. terminä. Pienimmässä muodossa ei koskaan käytetä arvoa F ₁ ja sillä on aina loppu nolla. Täyden koodaussekvenssin ilman perään nolla löytyy (sekvenssi A014417 on OEIS ). Tämä koodaus tunnetaan nimellä Zeckendorf-esitys .

Tässä numerojärjestelmässä mikä tahansa alaosuus "100" voidaan korvata "011": llä ja päinvastoin Fibonacci-numeroiden määrittelyn vuoksi. Näiden sääntöjen jatkuva soveltaminen kääntää muodon mahdollisimman pieneksi ja päinvastoin. Se, että mikä tahansa numero (suurempi kuin 1) voidaan esittää päätelaitteella 0, tarkoittaa, että aina on mahdollista lisätä 1, ja kun otetaan huomioon, että luvut 1 ja 2 voidaan esittää Fibonacci-koodauksessa, täydellisyys seuraa induktiota .

Katso myös

• Ostrowskin numerointi

Viitteet

Ulkoiset linkit

• Weisstein, Eric W. "Täydellinen jakso" . MathWorld .