FRACTRAN

FRACTRAN – ezoteryczny język programowania wynaleziony przez matematyka Johna Conwaya, będący zupełny w sensie Turinga.

Program w języku FRACTRAN ma postać ciągu dodatnich ułamków nieskracalnych. Wejściem dla programu jest dodatnia liczba całkowita n. Wykonanie programu polega na wielokrotnym zmienianiu wartości n przez następującą operację: „znajdź pierwszy w ciągu ułamek f, dla którego iloczyn nf jest liczbą całkowitą, i zastąp n przez nf”. Jeśli żaden ułamek w ciągu nie daje liczby całkowitej po pomnożeniu przez obecną wartość n, wykonywanie programu zostaje zatrzymane.

Nazwa stanowi połączenie słowa „fraction” (ułamek) oraz nazwy języka programowania FORTRAN.

Przykładowym programem w języku FRACTRAN jest PRIMEGAME autorstwa Conwaya, który po uruchomieniu znajduje kolejne liczby pierwsze:

$(\frac{17}{91},\frac{78}{85},\frac{19}{51},\frac{23}{38},\frac{29}{33},\frac{77}{29},\frac{95}{23},\frac{77}{19},\frac{1}{17},\frac{11}{13},\frac{13}{11},\frac{15}{2},\frac{1}{7},\frac{55}{1}).$

Jeśli na wejściu zostanie podana liczba $n=2,$ program ten generuje następujący ciąg liczb:

• 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, ... Szablon:OEIS

Nie licząc początkowej dwójki, ciąg ten zawiera następujące potęgi 2: $4=2^2,8=2^3,32=2^5,128=2^7,2048=2^{11},8192=2^{13},131072=2^{17},524288=2^{19},\dots$Szablon:OEIS. Wykładniki tych potęg są kolejnymi liczbami pierwszymi.

Zasada działania programu FRACTRAN

Program FRACTRAN można rozumieć jako rodzaj maszyny rejestrowej, gdzie zawartość rejestrów jest przechowywana w wykładnikach potęg czynników pierwszych w rozkładzie argumentu n. Na przykład wartość n równa $60=2^2\times 3^1\times 5^1$ reprezentuje stan rejestrów, w którym jedna zmienna (nazwana v2) ma wartość 2, a dwie inne zmienne (v3 i v5) mają wartość 1. Wszystkie inne zmienne mają wartość 0.

Program FRACTRAN ma postać uporządkowanej listy dodatnich ułamków nieskracalnych. Każdy ułamek reprezentuje instrukcję, która przeprowadza operacje na zawartości jednej lub więcej zmiennych, określonych przez czynniki pierwsze mianownika danego ułamka. Na przykład instrukcja

$f_1=\frac{21}{20}=\frac{3^1\times 7^1}{2^2\times 5^1}$

sprawdza zawartość v2 i v5. Jeśli $v_2⩾2$ i $v_5⩾1,$ instrukcja $f_1$ odejmie 2 od v2 i 1 od v5 oraz doda 1 do v3 i 1 do v7. Na przykład:

$60\cdot f_1=2^2\times 3^1\times 5^1\cdot \frac{3^1\times 7^1}{2^2\times 5^1}=3^2\times 7^1.$

Tego rodzaju instrukcje „sprawdź-odejmij-dodaj” są w języku FRACTRAN jedynymi dozwolonymi instrukcjami.

Przykładowe programy FRACTRAN

Dodawanie

Najprostszy program FRACTRAN składa się z pojedynczej instrukcji, na przykład

$\left(\frac{3}{2}\right).$

Program ten oblicza sumę dwóch liczb całkowitych, $a$ i $b.$ Dla początkowej wartości $n=2^a{3}^b$ program generuje sekwencję $2^{a-1}{3}^{b+1},$ $2^{a-2}{3}^{b+2}$ itd., aż w końcu, po $a$ krokach, program zatrzyma się z końcowym wynikiem $3^{a+b}.$

Nieco bardziej skomplikowany wariant programu dodającego składa się z dwóch instrukcji:

$(\frac{10}{3},\frac{3}{5}).$

Dla wejściowej wartości $n=2^a{3}^b$ program zatrzyma się z wynikiem $2^{a+b}{3}^b.$ Dzięki temu informacja o wartościach $a$ i $b$ nie zostaje zniszczona.

W tym wariancie zmienna v5 tymczasowo przechowuje początkową wartość v3 = $b.$ Pierwsza instrukcja $\frac{10}{3}=\frac{2\cdot 5}{3}$ przenosi zawartość v3 do v2 oraz v5; gdy v3 osiągnie wartość zero, program zaczyna wykonywać drugą instrukcję $\frac{3}{5},$ która odtwarza wartość v3 z v5.

Mnożenie – przykład pętli

Następujący program przyjmuje na wejściu liczbę $n=2^a\cdot 3^b\cdot 7^c\cdot 11$ i zatrzymuje się z końcowym wynikiem $n=2^{a+bc}\cdot 3^b\cdot 11,$ tym samym obliczając wynik mnożenia $bc:$

$(\frac{13}{77},\frac{170}{39},\frac{13}{17},\frac{19}{13},\frac{69}{95},\frac{19}{23},\frac{11}{19}).$

Działanie programu polega na wykonywaniu procedury dodającej w pętli, tak, by dodać $b$ do $a$ dokładnie $c$ razy.

Aby zaimplementować w języku FRACTRAN pętlę, należy wprowadzić pojęcie stanu. W tym celu należy wybrać pewne liczby pierwsze jako wskaźniki stanu: dla powyższego programu mnożącego są to 11, 13, 17, 19 i 23. Na przykład jeśli w danym kroku wartość n jest podzielna przez 11 i niepodzielna przez żadną inną z tych liczb, oznacza to, że program jest w stanie „11”.

By przeanalizować działanie programu, dla większej jasności można go zapisać w następujący sposób:

$(\frac{13}{7\cdot 11},\frac{2\cdot 5\cdot 17}{3\cdot 13},\frac{13}{17},\frac{19}{13},\frac{3\cdot 23}{5\cdot 19},\frac{19}{23},\frac{11}{19}).$

Działanie programu można opisać następująco:

• w chwili początkowej (wejściowa wartość $n=2^a\cdot 3^b\cdot 7^c\cdot 11$) program jest w stanie 11. W pierwszym kroku – jeśli v7 > 0 – odejmuje 1 od v7 i przechodzi do stanu 13;
• w kolejnych krokach program przechodzi na przemian między stanami 13 a 17 (pierwsza pętla). W każdym przebiegu tej pętli wykonuje pierwszą instrukcję algorytmu dodającego („odejmij 1 od v3 i dodaj 1 do v2, v5”);
• gdy v3 osiągnie zero, pętla kończy się – ze stanu 13 program przechodzi do 19;
• w kolejnych krokach program przechodzi na przemian między stanami 19 a 23 (druga pętla). W każdym przebiegu tej pętli wykonuje drugą instrukcję algorytmu dodającego („odejmij 1 od v5, dodaj 1 do v3”);
• gdy v5 osiąga zero, druga pętla kończy się, a program przechodzi do początkowego stanu 11 i wykonywanie instrukcji zaczyna się od nowa.

Po każdym wykonaniu tego ciągu instrukcji zawartość v2 wzrasta o $b,$ a zawartość v7 maleje o 1. Gdy v7 osiąga zero, program zatrzymuje się.

Algorytm generowania liczb pierwszych (PRIMEGAME)

Zaprezentowany na wstępie program PRIMEGAME, po wprowadzeniu na wejściu liczby $n=2^1,$ przeprowadza kolejno test pierwszości dla liczb $N=2,3,4,5...$ w następujący sposób. Program wykonuje pętlę, próbując podzielić liczbę N przez wszystkie możliwe dzielniki $d=N-1,N-2,\dots 1.$ (Dzielenie zaimplementowane jest jako wielokrotne odejmowanie d od N, aż do uzyskania całkowitej części ilorazu oraz reszty z dzielenia.) Gdy program natrafi na największą wartość d, która dzieli N bez reszty, wyprowadza wartość $n=2^N{7}^{d-1}$ i wykonuje algorytm od nowa dla kolejnej wartości N. Wartość $2^N{7}^{d-1}$ jest potęgą dwójki tylko wtedy, gdy d wynosi 1 – co ma miejsce tylko wtedy, gdy N jest liczbą pierwszą. Dokładniejsze wyjaśnienie krok po kroku algorytmu Conwaya można znaleźć u Guya (1983) bądź Havila (2007).

Dotarcie do liczby pierwszej 2, 3, 5, 7... zajmuje temu programowi odpowiednio 19, 69, 281, 710,... kroków od momentu uruchomienia Szablon:OEIS.

Istnieje także wariant programu Conwaya, który różni się od powyższej wersji dwoma ułamkami:

$(\frac{17}{91},\frac{78}{85},\frac{19}{51},\frac{23}{38},\frac{29}{33},\frac{77}{29},\frac{95}{23},\frac{77}{19},\frac{1}{17},\frac{11}{13},\frac{13}{11},\frac{15}{14},\frac{15}{2},\frac{55}{1})$

Zasada działania tego wariantu jest taka sama, ale jest on nieco szybszy: by dotrzeć do kolejnych liczb pierwszych 2, 3, 5, 7..., potrzebuje on odpowiednio 19, 69, 280, 707... kroków Szablon:OEIS. Pojedynczy przebieg programu, sprawdzający, czy liczba N jest pierwsza, wymaga następującej liczby kroków:

$N-1+(6N+2)(N-b)+2\sum _{d=b}^{N-1}\lfloor \frac{N}{d}\rfloor ,$

gdzie $b<N$ jest największym dzielnikiem całkowitym N, a $\lfloor x\rfloor$ jest częścią całkowitą x.

W roku 1999 matematyk Devin Kilminster zademonstrował krótszy program znajdujący liczby pierwsze, składający się z dziesięciu instrukcji:

$(\frac{7}{3},\frac{99}{98},\frac{13}{49},\frac{39}{35},\frac{36}{91},\frac{10}{143},\frac{49}{13},\frac{7}{11},\frac{1}{2},\frac{91}{1})$

Dla początkowego wejścia $n=10$ kolejne liczby pierwsze są otrzymywane jako wykładniki potęg liczby 10.

Linki zewnętrzne

• Szablon:MathWorld
• Fractran – hasło na wiki Esolang
• Szablon:Cytuj stronę – blog programisty Johna Biesneckera
• Implementacja kompilatora do języka FRACTRAN w języku Lisp – blog programisty Michaela Malisa
• Szablon:Cytuj stronę – blog programisty Chrisa Lomonta