Numeracja bijektywna - Bijective numeration

Numeracja bijective to dowolny system liczbowy, w którym każdą nieujemną liczbę całkowitą można przedstawić dokładnie w jeden sposób za pomocą skończonego ciągu cyfr . Nazwa wywodzi się z tej bijekcji (korespondencja jeden do jednego) między zbiorem nieujemnych liczb całkowitych a zbiorem skończonych ciągów przy użyciu skończonego zbioru symboli („cyfry”).

Większość zwykłych systemów liczbowych, takich jak powszechny system dziesiętny , nie jest bijektywna, ponieważ więcej niż jeden ciąg cyfr może reprezentować tę samą dodatnią liczbę całkowitą. W szczególności dodanie wiodących zer nie zmienia reprezentowanej wartości, więc „1”, „01” i „001” reprezentują liczbę jeden . Chociaż zwykle jest tylko pierwszy, fakt, że pozostałe są możliwe, oznacza, że ​​liczba dziesiętna nie jest bijektywna. Jednak jednoargumentowy , z tylko jedną cyfrą, jest bijektywny.

Bijective podstawa - k numeracja jest bijective pozycyjny zapis . Używa ciągu cyfr ze zbioru {1, 2, ..., k } (gdzie k ≥ 1) do kodowania każdej dodatniej liczby całkowitej; pozycja cyfry w łańcuchu określa jej wartość jako wielokrotność potęgi k . Smullyan (1961) nazywa tę notację k -adic, ale nie należy jej mylić z liczbami p -adycznymi : liczby bijective to system reprezentacji zwykłych liczb całkowitych przez skończone ciągi niezerowych cyfr, podczas gdy liczby p -adyczne są systemem wartości matematyczne, które zawierają liczby całkowite jako podzbiór i mogą wymagać nieskończonych sekwencji cyfr w dowolnej reprezentacji numerycznej.

Definicja

System bijective base- k używa zestawu cyfr {1, 2, ..., k } ( k ≥ 1) do jednoznacznego reprezentowania każdej nieujemnej liczby całkowitej, w następujący sposób:

• Liczba całkowita zero jest reprezentowana przez pusty ciąg .
• Liczba całkowita reprezentowana przez niepusty ciąg cyfr

za _n za _{n -1} ... za ₁ za ₀

jest

a _n k ⁿ + a _{n -1} k ^{n -1} + ... + a ₁ k ¹ + a ₀ k ⁰ .

• Ciąg cyfr reprezentujący liczbę całkowitą m > 0 to

za _n za _{n -1} ... za ₁ za ₀

gdzie

${\ Displaystyle {\ zacząć {wyrównany} a_ {0}& = m-q_ {0}k, & q_ {0}& = f \ lewo ({\ Frac {m} {k}} \ po prawej) & \ \ a_ {1}&=q_{0}-q_{1}k,&q_{1}&=f\lewo({\frac {q_{0}}{k}}\prawo)&\\a_{2}& =q_{1}-q_{2}k,&q_{2}&=f\lewo({\frac {q_{1}}{k}}\prawo)&\\&\,\,\,\vdots &&\,\,\,\vdots \\a_{n}&=q_{n-1}-0k,&q_{n}&=f\left({\frac {q_{n-1}}{k} }\right)=0\end{wyrównany}}}$

i

${\ Displaystyle f (x) = \ lceil x \ rceil -1,}$

${\displaystyle \lceil x\rceil}$będąca najmniejszą liczbą całkowitą nie mniejszą niż x ( funkcja sufitu ).

W przeciwieństwie do tego, standardową notację pozycyjną można zdefiniować za pomocą podobnego algorytmu rekurencyjnego, gdzie

${\displaystyle f(x)=\lpodłoga x\rpodłoga,}$

Rozszerzenie na liczby całkowite

W przypadku podstawy , bijective system liczb podstawowych może być rozszerzony do ujemnych liczb całkowitych w taki sam sposób, jak standardowy system liczb podstawowych przy użyciu nieskończonej liczby cyfry , gdzie , reprezentowany jako lewostronnie nieskończony ciąg cyfr . Dzieje się tak, ponieważ sumowanie Eulera${\displaystyle k>1}$${\displaystyle k}$${\displaystyle b}$${\displaystyle d_{k-1}}$${\ Displaystyle f (d_ {k-1}) = k-1}$${\ Displaystyle \ ldots d_ {k-1} d_ {k-1} d_ {k-1} = {\ nadkreślenie {d_ {k-1}}}}$

${\ Displaystyle g ({\ overline {d_ {k-1}}}) = \ suma _ {i = 0} ^ {\ infty} f (d_ {k-1}) k ^ {i} = - {\ szczelina {k-1}{k-1}}=-1}$

co oznacza, że

${\ Displaystyle g ({\ overline {d_ {k-1}}} d_ {k}) = f (d_ {k}) \ suma _ {i = 1} ^ {\ infty} f (d_ {k-1 })k^{i}=1+\sum _{i=0}^{\infty }f(d_{k-1})k^{i}=0}$

a dla każdej liczby dodatniej z numeracją bijektywną reprezentacja cyfry jest reprezentowana przez . Do podstawy , wartości ujemne są przedstawione z , a dla zasady , wartości ujemne są przedstawione . Jest to podobne do tego, w jaki sposób w reprezentacjach ze znakiem cyfrowym wszystkie liczby całkowite z reprezentacjami cyfrowymi są reprezentowane jako gdzie . Ta reprezentacja nie jest już bijektywna, ponieważ cały zestaw lewostronnie nieskończonych sekwencji cyfr służy do reprezentowania -adic liczb całkowitych , których liczby całkowite są tylko podzbiorem. ${\ Displaystyle n}$${\displaystyle d}$${\ Displaystyle {\ overline {d_ {k-1}}} d_ {k} d}$${\displaystyle k>2}$${\displaystyle n<-1}$${\ Displaystyle {\ overline {d_ {k-1}}} d_ {i} d}$${\displaystyle i<k-1}$${\ Displaystyle k = 2}$${\displaystyle n<-1}$${\displaystyle {\overline {d_{k}}}d}$${\ Displaystyle n}$${\displaystyle d}$${\displaystyle {\overline {d_{0}}}d}$${\ Displaystyle f (d_ {0}) = 0}$${\displaystyle k}$

Własności bijektywnych liczb bazowych k

Dla danej podstawy k ≥ 1,

• istnieje dokładnie k ⁿ bijective base- k liczb o długości n ≥ 0.
• jeśli k ≥ 2, liczba cyfr w bijektywnej liczbie o podstawie k reprezentującej nieujemną liczbę całkowitą n wynosi , w przeciwieństwie do zwykłych liczb o podstawie k ; jeśli k = 1 (tzn. jednoargumentowy), to liczba cyfr to po prostu n ;${\ Displaystyle \ l piętro \ log _ {k} ((n + 1) (k-1)) \ r podłoga}$${\ Displaystyle \ lceil \ log _ {k} (n + 1) \ rceil}$
• jeśli k ≥ 2, liczby bijektywne o podstawie k i zwykłe liczby o podstawie k dla nieujemnej liczby całkowitej n są identyczne wtedy i tylko wtedy, gdy liczba zwykła nie zawiera cyfry 0 (lub równoważnie liczba bijektywna nie jest ani pustym ciągiem, ani zawiera cyfrę k ).
• lista bijektywnych liczb bazowych k , w naturalnym porządku reprezentowanych liczb całkowitych, jest automatycznie w porządku shortlex (najkrótszy pierwszy, leksykograficzny w obrębie każdej długości). Tak więc, używając λ do oznaczenia pustego ciągu , liczby o podstawie 1, 2, 3, 8, 10, 12 i 16 są następujące (gdzie dla porównania wymieniono zwykłe reprezentacje):

Przykłady

34152 (w bijective base-5) = 3×5 ⁴ + 4×5 ³ + 1×5 ² + 5×5 ¹ + 2×1 = 2427 (dziesiętnie).

119A (w bijective podstawy-10, przy czym "A" reprezentujący cyfrową wartość dziesięć) = 1 x 10 ³ + 1 x 10 ² + 9 x 10 ¹ + 1 x 10 = 1200 (dziesiętnie).

Typowa lista alfabetyczna zawierająca więcej niż 26 elementów jest bijektywna i używa kolejności A, B, C...X, Y, Z, AA, AB, AC...ZX, ZY, ZZ, AAA, AAB, AAC. ...

System bijective base-10

Bijektywny system o podstawie 10 to pozycyjny system liczbowy o podstawie dziesięciu , który nie używa cyfry do reprezentowania zera . Zamiast tego ma cyfrę reprezentującą dziesięć, na przykład A .

Podobnie jak w przypadku konwencjonalnego dziesiętnego , każda pozycja cyfry reprezentuje potęgę dziesiątki, więc na przykład 123 to „sto plus dwie dziesiątki plus trzy jednostki”. Wszystkie dodatnie liczby całkowite, które są reprezentowane wyłącznie cyframi niezerowymi w konwencjonalnym systemie dziesiętnym (takim jak 123), mają taką samą reprezentację w systemie dziesiętnym bez zera. Te, które używają zera, muszą zostać przepisane, więc na przykład 10 staje się A, konwencjonalny 20 staje się 1A, konwencjonalny 100 staje się 9A, konwencjonalny 101 staje się A1, konwencjonalny 302 staje się 2A2, konwencjonalny 1000 staje się 99 A, konwencjonalny 1110 staje się AAA, konwencjonalny 2010 staje się 19AA , i tak dalej.

Dodawanie i mnożenie w systemie dziesiętnym bez zera jest zasadniczo takie samo, jak w przypadku konwencjonalnego dziesiętnego, z wyjątkiem tego, że przeniesienia występują, gdy pozycja przekracza dziesięć, a nie gdy przekracza dziewięć. Aby obliczyć 643 + 759, mamy dwanaście jednostek (zapisz 2 po prawej i przenieś 1 do dziesiątek), dziesięć dziesiątek (zapisz A bez konieczności przenoszenia do setek), trzynaście setek (zapisz 3 i przenieś 1 do tysiące) i tysiąc (zapisz 1), aby dać wynik 13A2 zamiast konwencjonalnego 1402.

Bijective base-26 system

W bijective base-26 można użyć liter alfabetu łacińskiego „A” do „Z” do przedstawienia 26-cyfrowych wartości od jednego do dwudziestu sześciu . (A=1, B=2, C=3, ..., Z=26)

Przy takim wyborze zapisu sekwencja liczb (zaczynająca się od 1) zaczyna się od A, B, C, ..., X, Y, Z, AA, AB, AC, ..., AX, AY, AZ, BA, BB , PNE, ...

Każda pozycja cyfry reprezentuje potęgę dwudziestu sześciu, więc na przykład liczebnik ABC reprezentuje wartość 1 × 26 ² + 2 × 26 ¹ + 3 × 26 ⁰ = 731 przy podstawie 10.

Wiele arkuszy kalkulacyjnych, w tym Microsoft Excel, używa tego systemu do przypisywania etykiet do kolumn arkusza kalkulacyjnego, zaczynając od A, B, C, ..., Z, AA, AB, ..., AZ, BA, ..., ZZ, AAA , itp. Na przykład w Excel 2013 może być do 16384 kolumn (2 ¹⁴ w kodzie binarnym), oznaczonych od A do XFD. Wariant tego systemu służy do nazywania gwiazd zmiennych . Można go zastosować do każdego problemu, w którym pożądane jest systematyczne nazewnictwo za pomocą liter, przy użyciu możliwie najkrótszych ciągów.

Notatki historyczne

Fakt, że każda nieujemna liczba całkowita ma unikalną reprezentację w bijektywnej bazie k ( k ≥ 1) jest „ twierdzeniem ludowym ”, które było wielokrotnie odkrywane. Wczesne przykłady to Foster (1947) dla przypadku k = 10 oraz Smullyan (1961) i Böhm (1964) dla wszystkich k ≥ 1. Smullyan używa tego systemu do zapewnienia numeracji Gödla ciągów symboli w systemie logicznym; Böhm używa tych reprezentacji do wykonywania obliczeń w języku programowania P′′ . Knuth (1969) wspomina szczególny przypadek k = 10, a Salomaa (1973) omawia przypadki k ≥ 2. Forslund (1995) wydaje się być kolejnym odkryciem i stawia hipotezę, że gdyby starożytne systemy liczbowe używały bijective base- k , mogłyby nie mogą być uznane za takie w dokumentach archeologicznych, ze względu na ogólną nieznajomość tego systemu.

Uwagi

Bibliografia

• Böhm, C. (lipiec 1964), „O rodzinie maszyn Turinga i powiązanym języku programowania”, Biuletyn ICC , 3 : 191.
• Forslund, Robert R. (1995), „logiczna alternatywa dla istniejącego systemu liczb pozycyjnych”, Southwest Journal of Pure and Applied Mathematics , 1 : 27-29, MR  1386376 , S2CID  19010664.
• Foster, JE (1947), „System liczbowy bez symbolu zera”, Matematyka Magazine , 21 (1): 39-41, doi : 10.2307/3029479 , JSTOR  3029479.
• Knuth, DE (1969), Sztuka programowania komputerowego, tom. 2: Seminumerical Algorithms (1st ed.), Addison-Wesley, Solution to Exercise 4.1-24, s. 195. (Omawia bijective base 10.)
• Salomaa, A. (1973), Języki formalne , Academic Press, Note 9.1, s. 90-91. (Omawia bijective base- k dla wszystkich k ≥ 2.)
• Smullyan, R. (1961), „9. Leksykograficzne porządkowanie; n -adyczna reprezentacja liczb całkowitych” , Theory of Formal Systems , Annals of Mathematics Studies, 47 , Princeton University Press, s. 34-36.