User:Thebigh/mysandbox: Difference between revisions
(tweak) |
m (tweak) |
||
| (18 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
Some FRACTRAN programs in case we ever have a category for it |
|||
The '''Calkin-Wilf sequence''' contains every nonnegative rational number exactly once. It can be calculated recursively as follows: |
|||
==A+B== |
|||
{{math|a<sub>0</sub>}} = {{math|0}} |
|||
Input a number of the form 2^a 3^b |
|||
{{math|a<sub>n+1</sub>}} = {{math|1/(2⌊a<sub>n</sub>⌋+1-a<sub>n</sub>)}} for n > 0 |
|||
<lang fractran> |
|||
2/3 |
|||
</lang> |
|||
The output is 2^(a+b) |
|||
==Empty program== |
|||
* Show on this page terms 0 through 20 of the Calkin-Wilf sequence. To avoid floating point error, you may want to use a rational number data type. |
|||
A list of no fractions does nothing, then immediately stops. |
|||
<lang fractran></lang> |
|||
==Integer Sequence== |
|||
It is also possible, given a nonnegative rational number, to determine where it appears in the sequence without calculating the sequence. The procedure is to get the continued fraction representation of the rational and use it as the run-length encoding of the binary representation of the term number, beginning from the end of the continued fraction. |
|||
Given the number 1 as input the following program will, as its (3n-2)th step, produce the number 2^n. |
|||
It only works if the number of terms in the continued fraction is odd- use either of the two equivalent representations to achieve this: |
|||
<lang fractran> 2/3, 9/2, 2/1</lang> |
|||
==Logical operations== |
|||
{{math|[a<sub>0</sub>; a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>]}} = {{math|[a<sub>0</sub>; a<sub>1</sub>, a<sub>2</sub> ,..., a<sub>n</sub>-1, 1]}} |
|||
It's not so hard to code up all sixteen possible two-input logic gates, so here they are. The input is 2^a 3^b where a,b are zero or one and the output is 5^1 for true and 5^0 for false. Gates that return true when all their inputs are false additionally require the flag 11 to be set as input (ie 2^a*3^b*11)- any FRACTRAN program with the number 1 as input either stops without doing anything or loops forever. |
|||
<lang fractran> |
|||
Thus, for example, the fraction 9/4 has odd continued fraction representation {{math|2; 3, 1}}, giving a binary representation of 100011, which means 9/4 appears as the 35th term of the sequence. |
|||
5/6, 1/2, 1/3 AND gate |
|||
5/6, 5/2, 5/3 OR gate |
|||
1/22, 5/11 NOT gate (uses 11 as a halt flag, result of 2^a*11 is 5^not(a)) |
|||
1/6, 5/2, 5/3 XOR gate |
|||
1/66, 5/22, 5/33, 5/11 NAND gate (needs 11 flag) |
|||
5/66, 1/22, 1/33, 5/11 NXOR gate (needs flag) |
|||
1/66, 1/22, 1/33, 5/11 NOR gate (needs flag) |
|||
so much for all the commonly encountered ones, but there's still another eight to go. Most are obscure and of limited utility. |
|||
* Find the position of the number {{math|83116/51639}} in the Calkin-Wilf sequence. |
|||
1/2, 1/3 ZERO gate, returns false regardless of its input |
|||
;See also: |
|||
1/6, 5/2, 1/3 "A and not B", true only if A is true and B is false |
|||
5/2, 1/3 A , returns the state of A regardless of B |
|||
1/6, 1/2, 5/3 "B and not A", true only if B is true and A is false |
|||
1/2, 5/3 B , returns the state of B regardless of A |
|||
1/66, 1/33, 5/11 "A or not B" (needs flag) |
|||
1/66, 1/22, 5/11 "B or not A" (needs flag) |
|||
5/66, 5/22, 5/33, 5/11 ONE gate, returns true regardless of its input, needs flag |
|||
NOT A and NOT B are omitted because the one-input NOT gate is already up there. |
|||
* Wikipedia entry: [[wp:Calkin%E2%80%93Wilf_tree|Calkin-Wilf tree] |
|||
</lang> |
|||
==Sort three variables== |
|||
FRACTRAN's only data type is positive integers. Suppose (a,b,c) are the integers to be sorted. Give the following as input: |
|||
2^a 3^b 5^c |
|||
<lang fractran> |
|||
1001/30, 143/6, 143/10, 143/15, 13/2, 13/3, 13/5 |
|||
</lang> |
|||
Returns 7^A 11^B 13^C where (A,B,C) are (a,b,c) in ascending order. |
|||
Latest revision as of 11:27, 28 November 2021
Some FRACTRAN programs in case we ever have a category for it
A+B
Input a number of the form 2^a 3^b <lang fractran> 2/3 </lang> The output is 2^(a+b)
Empty program
A list of no fractions does nothing, then immediately stops. <lang fractran></lang>
Integer Sequence
Given the number 1 as input the following program will, as its (3n-2)th step, produce the number 2^n. <lang fractran> 2/3, 9/2, 2/1</lang>
Logical operations
It's not so hard to code up all sixteen possible two-input logic gates, so here they are. The input is 2^a 3^b where a,b are zero or one and the output is 5^1 for true and 5^0 for false. Gates that return true when all their inputs are false additionally require the flag 11 to be set as input (ie 2^a*3^b*11)- any FRACTRAN program with the number 1 as input either stops without doing anything or loops forever.
<lang fractran> 5/6, 1/2, 1/3 AND gate 5/6, 5/2, 5/3 OR gate 1/22, 5/11 NOT gate (uses 11 as a halt flag, result of 2^a*11 is 5^not(a)) 1/6, 5/2, 5/3 XOR gate 1/66, 5/22, 5/33, 5/11 NAND gate (needs 11 flag) 5/66, 1/22, 1/33, 5/11 NXOR gate (needs flag) 1/66, 1/22, 1/33, 5/11 NOR gate (needs flag)
so much for all the commonly encountered ones, but there's still another eight to go. Most are obscure and of limited utility.
1/2, 1/3 ZERO gate, returns false regardless of its input 1/6, 5/2, 1/3 "A and not B", true only if A is true and B is false 5/2, 1/3 A , returns the state of A regardless of B 1/6, 1/2, 5/3 "B and not A", true only if B is true and A is false 1/2, 5/3 B , returns the state of B regardless of A 1/66, 1/33, 5/11 "A or not B" (needs flag) 1/66, 1/22, 5/11 "B or not A" (needs flag) 5/66, 5/22, 5/33, 5/11 ONE gate, returns true regardless of its input, needs flag
NOT A and NOT B are omitted because the one-input NOT gate is already up there. </lang>
Sort three variables
FRACTRAN's only data type is positive integers. Suppose (a,b,c) are the integers to be sorted. Give the following as input: 2^a 3^b 5^c <lang fractran> 1001/30, 143/6, 143/10, 143/15, 13/2, 13/3, 13/5 </lang> Returns 7^A 11^B 13^C where (A,B,C) are (a,b,c) in ascending order.