FRACTRAN

FRACTRAN is a Turing-completeesoteric programming language invented by the mathematician John Conway. A FRACTRAN program is an ordered list of positive fractions together with an initial positive integer input n. The program is run by updating the integer n as follows:

1. for the first fraction f in the list for which nf is an integer, replace n by nf
2. repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt.

Conway 1987 gives the following FRACTRAN program, called PRIMEGAME, which finds successive prime numbers:

$${\displaystyle \left({\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}}\right)}$$

Starting with n=2, this FRACTRAN program generates the following sequence of integers:

• 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... (sequence A007542 in the OEIS), i.e. the sequence of PRIMEGAME numbers

After 2, this sequence contains the following powers of 2:

$${\displaystyle 2^{2}=4,\,2^{3}=8,\,2^{5}=32,\,2^{7}=128,\,2^{11}=2048,\,2^{13}=8192,\,2^{17}=131072,\,2^{19}=524288,\,\dots }$$(sequence A034785 in the OEIS)

The exponent part of these powers of two are primes, 2, 3, 5, etc.

A FRACTRAN program can be seen as a type of register machine where the registers are stored in prime exponents in the argument ${\displaystyle n}$.

Using Gödel numbering, a positive integer ${\displaystyle n}$ can encode an arbitrary number of arbitrarily large positive integer variables.^{[note 1]} The value of each variable is encoded as the exponent of a prime number in the prime factorization of the integer. For example, the integer

$${\displaystyle 60=2^{2}\times 3^{1}\times 5^{1}}$$

represents a register state in which one variable (which we will call ${\displaystyle v_{2}}$) holds the value 2 and two other variables (${\displaystyle v_{3}}$ and ${\displaystyle v_{5}}$) hold the value 1. All other variables hold the value 0.

A FRACTRAN program is an ordered list of positive fractions. Each fraction represents an instruction that tests one or more variables, represented by the prime factors of its denominator. For example:

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

tests ${\displaystyle v_{2}}$ and ${\displaystyle v_{5}}$. If ${\displaystyle v_{2}\geq 2}$ and ${\displaystyle v_{5}\geq 1}$, then it subtracts 2 from ${\displaystyle v_{2}}$ and 1 from ${\displaystyle v_{5}}$ and adds 1 to ${\displaystyle v_{3}}$ and 1 to ${\displaystyle v_{7}}$. For example:

$${\displaystyle 60\cdot f_{1}=2^{2}\times 3^{1}\times 5^{1}\cdot {\frac {3\times 7}{2^{2}\times 5^{1}}}=3^{2}\times 7^{1}}$$

Since the FRACTRAN program is just a list of fractions, these test-decrement-increment instructions are the only allowed instructions in the FRACTRAN language. In addition the following restrictions apply:

• Each time an instruction is executed, the variables that are tested are also decremented.
• لا يمكن إنقاص قيمة المتغير نفسه وزيادتها في نفس التعليمة (وإلا لما كان الكسر الذي يمثل تلك التعليمة في أبسط صورة ). لذلك، تستهلك كل تعليمة في لغة FRACTRAN متغيرات أثناء اختبارها.
• لا يمكن لتعليمات FRACTRAN أن تختبر بشكل مباشر ما إذا كان المتغير يساوي 0 (ومع ذلك، يمكن تنفيذ اختبار غير مباشر عن طريق إنشاء تعليمات افتراضية يتم وضعها بعد التعليمات الأخرى التي تختبر متغيرًا معينًا).

خوارزمية توليد الأعداد الأولية لكونواي المذكورة أعلاه هي في الأساس خوارزمية قسمة وباقي ضمن حلقتين. مع الأخذ في الاعتبار المدخلات بالشكل التالي:${\displaystyle 2^{n}7^{m}}$حيث 0 ≤ m < n ، تحاول الخوارزمية قسمة n + 1 على كل عدد من n إلى 1، حتى تجد أكبر عدد k يقسم n + 1. ثم تُرجع 2n ^{+ 1} 7k ^{- 1} وتُكرر العملية . لا ينتج عن سلسلة أعداد الحالات التي تُولدها الخوارزمية قوة للعدد 2 إلا عندما يكون k يساوي 1 (بحيث يكون أس 7 يساوي 0)، وهذا لا يحدث إلا إذا كان أس 2 عددًا أوليًا. يمكن الاطلاع على شرح مُفصّل لخوارزمية كونواي في هافيل (2007).

بالنسبة لهذا البرنامج، يتطلب الوصول إلى الأعداد الأولية 2، 3، 5، 7... على التوالي 19، 69، 281، 710،... خطوات (التسلسل A007547 في OEIS ) .

يوجد أيضًا شكل مختلف من برنامج كونواي، ^{[ 1 ]} والذي يختلف عن النسخة المذكورة أعلاه بكسرين: $${\displaystyle \left({\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}}\right)}$$

هذا المتغير أسرع قليلاً: الوصول إلى 2، 3، 5، 7... يستغرق 19، 69، 280، 707... خطوة (التسلسل A007546 في OEIS ) . تستغرق دورة واحدة من هذا البرنامج، للتحقق من كون عدد معين N أوليًا، عدد الخطوات التالي: $${\displaystyle N-1+(6N+2)(N-b)+2\sum \limits _{d=b}^{N-1}\left\lfloor {\frac {N}{d}}\right\rfloor ,}$$ أين${\displaystyle b<N}$هو أكبر قاسم صحيح للعدد N و${\displaystyle \lfloor x\rfloor }$هي دالة الجزء الصحيح . ^{[ 2 ]}

في عام 1999، قدم ديفين كيلمنستر برنامجًا أقصر يتكون من عشر تعليمات: ^{[ 3 ]}$${\displaystyle \left({\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}}\right).}$$ بالنسبة للمدخل الأولي n = 10، يتم توليد الأعداد الأولية المتتالية بواسطة قوى متتالية للعدد 10.

برنامج FRACTRAN التالي:

$${\displaystyle \left({\frac {3\cdot 11}{2^{2}\cdot 5}},{\frac {5}{11}},{\frac {13}{2\cdot 5}},{\frac {1}{5}},{\frac {2}{3}},{\frac {2\cdot 5}{7}},{\frac {7}{2}}\right)}$$

يحسب البرنامج وزن هامينغ H( a ) للعدد الثنائي a، أي عدد الآحاد في التمثيل الثنائي للعدد a . ^{[ 4 ]} عند إدخال 2a ^، يكون الناتج 13H ^{( a )} . يمكن تحليل البرنامج كما يلي:

تعليمات FRACTRAN	الوضع الحالي	مؤشرات الدولة	حالة	فعل	الولاية التالية
${\displaystyle {\frac {3\cdot 11}{2^{2}\cdot 5}},{\frac {5}{11}}}$	أ	${\displaystyle v_{5}}$،${\displaystyle v_{11}}$	${\displaystyle v_{2}}$> 1	اطرح 2 من${\displaystyle v_{2}}$ أضف 1 إلى${\displaystyle v_{3}}$	أ
${\displaystyle {\frac {13}{2\cdot 5}}}$			${\displaystyle v_{2}}$= 1	اطرح 1 من${\displaystyle v_{2}}$ أضف 1 إلى${\displaystyle v_{13}}$	ب
${\displaystyle {\frac {1}{5}}}$			${\displaystyle v_{2}}$= 0	لا أحد	ب
${\displaystyle {\frac {2}{3}}}$	ب	لا أحد	${\displaystyle v_{3}}$> 0	اطرح 1 من ${\displaystyle v_{3}}$ أضف 1 إلى${\displaystyle v_{2}}$	ب
${\displaystyle {\frac {2\cdot 5}{7}}}$			${\displaystyle v_{3}}$= 0 و ${\displaystyle v_{7}}$> 0	اطرح 1 من${\displaystyle v_{7}}$ أضف 1 إلى${\displaystyle v_{2}}$	أ
${\displaystyle {\frac {7}{2}}}$			${\displaystyle v_{3}}$= 0 و ${\displaystyle v_{7}}$= 0 و ${\displaystyle v_{2}}$> 0	اطرح 1 من${\displaystyle v_{2}}$ أضف 1 إلى${\displaystyle v_{7}}$	ب
			${\displaystyle v_{2}}$= 0 و ${\displaystyle v_{3}}$= 0 و ${\displaystyle v_{7}}$= 0	قف

• حاسوب ذو مجموعة تعليمات واحدة
• تخمين كولاتز

• محاضرة لجون كونواي: "فراكتران: لغة منطقية سخيفة"
• "علم أمراض الأعداد الأولية: فراكتران"
• وايسشتاين، إريك دبليو. "FRACTRAN" . عالم الرياضيات .
• علم أمراض الأعداد الأولية
• FRACTRAN - (Esolang wiki)
• تطبيق روبي وبرامج نموذجية
• مسألة مشروع أويلر رقم 308
• "بناء Fizzbuzz في Fractran من الأسفل إلى الأعلى"
• كريس لومونت، "مترجم عالمي لـ FRACTRAN في FRACTRAN"