Fractran is a Turing-complete esoteric 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 n*f is an integer, replace n by n*f
2) repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt.
Conway 1987 gives the following formula for primes in Fractran:
Starting with n=2, this Fractran program generates the following sequence of integers:
After 2, this sequence contains the following powers of 2:
2^13 = 8192, 2^17 = 131072, 2^19 = 5244288, ...
which are the prime powers of 2.
Represent the Fractran program as a list:
(77L 29L) (95L 23L) (77L 19L) (1L 17L) (11L 13L) (13L 11L) (15L 14L) (15L 2L) (55L 1L) (55L 1L)))
The "fractran" function takes the program and an initial value and returns the next value or stops if no integer value is found.
(local (value stop)
(setq stop nil)
(dolist (el prog stop)
(setq value (/ (* (first el) n) (last el)))
(cond ((null? prog) (setq stop true))
((= 0 (% (* (first el) n) (last el)))
(setq stop true))))
value))
Note: Since the numbers soon exceed the 64-bit integer limit we must use big-integers.
The "run" function runs the entire fractran program:
(dotimes (x step)
(println start)
(setq start (fractran program start)))
'stop)
Let's try running the fractran program:
; -> 2L
; -> 15L
; -> 825L
; -> 725L
; -> 1925L
; -> 2275L
; -> 425L
; -> 390L
; -> 330L
; -> 290L
; -> stop
To extract the prime numbers it is necessary to verify if a given integer is a power of two.
We define two function "ipow" (calculate the integer power of a number) and "ilog" (calculate the integer logarithm of a number):
(cond ((zero? n) 1)
((even? n) (ipow (* x x) (/ n 2)))
(true (* x (ipow (* x x) (/ (- n 1) 2))))))
(define (ilog n b)
(if (zero? n) -1
(+ (ilog (/ n b) b) 1L)))
A number n is the power of two if it is:
(= 1122 (ipow 2 (ilog 1122 2)))
; -> nil
(= 4096 (ipow 2 (ilog 4096 2)))
; -> true
Now write the "run2" function which ends the prime numbers:
(dotimes (x step)
(if (= start (ipow 2 (ilog start 2)))
(print (ilog start 2) {, }))
(setq start (fractran program start)))
'stop)
Run the program to generate the prime numbers:
; -> 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, stop
Conway is a very 'bad' guy :-)
Interesting.
To gain speed, you could specialize the power-of-2 test into the following
That method is 1-2 magnitudes faster than "proper math's", and using
(dotimes (x step)
(let (b (bits x))
(or (find "1" (1 b)) (print (dec (length b)) ", ")))
(setq start (fractran program start)))
'stop)
:)
Hi ralph.ronnquist,
i have some problems with your function.
I think that the
Have a nice day
Ah. I didn't think about that. One might make a
(constant 'MAXINT (pow 2 62))
(define (prep s) (string (dup "0" (- 62 (length s))) s))
(define (bitsL n)
(if (<= n MAXINT) (bits (int n))
(string (bitsL (/ n MAXINT))
(prep (bits (int (% n MAXINT)))))))
Thanks for another function for big integer :-)
Arabic is my first language Then follows English even though im better at it and now im learning French Im not too good at it though... I want to learn French first until im fluent enough to depend on my own then probably move on to Spanish or Italian since i heard theyre similar
Well - I think english will be a global business/tech language follwed by chinese. And then spanish/chinese/russian/english as the main languages used in the community... and a local language thrown in for home...
So yes - and no... mostly no...
Quote
Your kind words warmed my heart))
Quote
At all I do not know, as to tell...