newlispfanclub.alh.net

Posted: **Mon Nov 18, 2019 3:51 pm**

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:

Code: Select all

(17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1)

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

Code: Select all

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ...

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

Code: Select all

2^2 = 4, 2^3 = 8, 2^5 = 32, 2^7 = 128, 2^11 = 2048
2^13 = 8192, 2^17 = 131072, 2^19 = 5244288, ...

which are the prime powers of 2.

Represent the Fractran program as a list:

Code: Select all

(setq primegame '((17L 91L) (78L 85L) (19L 51L) (23L 38L) (29L 33L)
(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.

Code: Select all

(define (fractran prog n)
  (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:

Code: Select all

(define (run program start step)
  (dotimes (x step)
    (println start)
    (setq start (fractran program start)))
  'stop)

Let's try running the fractran program:

Code: Select all

(run primegame 2L 10)
; -> 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):

Code: Select all

(define (ipow x n)
  (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:

Code: Select all

  (= n (ipow 2 (ilog n 2)))
(= 1122 (ipow 2 (ilog 1122 2)))
; -> nil
(= 4096 (ipow 2 (ilog 4096 2)))
; -> true

Now write the "run2" function which ends the prime numbers:

Code: Select all

(define (run2 program start step)
  (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:

Code: Select all

(run2 primegame 2L 1e6)
; -> 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 :-)

Posted: **Wed Nov 20, 2019 6:21 am**

Interesting.

To gain speed, you could specialize the power-of-2 test into the following

Code: Select all

(nil? (find "1" (1 (bits n))))

That method is 1-2 magnitudes faster than "proper math's", and using bits for ilog2 as well, it could become the following, faster run function:

Code: Select all

(define (run2 program start step)
  (dotimes (x step)
    (let (b (bits x)) 
       (or (find "1" (1 b)) (print (dec (length b)) ", ")))
    (setq start (fractran program start)))
  'stop)

:)

Posted: **Wed Nov 20, 2019 7:20 pm**

Hi ralph.ronnquist,
i have some problems with your function.
I think that the bits function don't work with big integer.

Have a nice day

Posted: **Wed Nov 20, 2019 9:38 pm**

Ah. I didn't think about that. One might make a bitsL function for that, eg:

Code: Select all

; Compute "bits" for bigint and int
(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)))))))

but then I'm less sure about the gain in speed.

Posted: **Thu Nov 21, 2019 8:03 am**

Thanks for another function for big integer :-)

Posted: **Sun Jun 26, 2022 10:04 am**

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

Posted: **Sun Jun 26, 2022 11:01 am**

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...

Posted: **Fri Jul 01, 2022 1:46 am**

Ah. I didn't think about that. One might make a bitsL function for that, eg: Code: Select all; Compute "bits" for bigint and int (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)))))))

Your kind words warmed my heart))

Posted: **Fri Jul 01, 2022 2:08 am**

Interesting. To gain speed, you could specialize the power-of-2 test into the following Code: Select all(nil? (find "1" (1 (bits n))))

At all I do not know, as to tell...

newlispfanclub.alh.net

Fractran language

Fractran language

Re: Fractran language

Re: Fractran language

Re: Fractran language

Re: Fractran language

-

-

hi!

hi!