Fractran: Difference between revisions

echo "First ten steps for program to find primes:"

echo "\nFirst twenty prime numbers:"

First ten steps for program to find primes:

First twenty prime numbers:

</pre>

===Using decomposition in prime factors===

With this algorithm, we no longer need big numbers. To avoid overflow, value at each step is displayed using

its decomposition in prime factors.

<lang Nim>

import algorithm

import sequtils

import strutils

import tables

const PrimeProg = "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"

type

Fraction = tuple[num, denom: int]

Factors = Table[int, int]

FractranProg = object

primes: seq[int]

nums, denoms: seq[Factors]

exponents: seq[int] # Could also use a CountTable.

iterator fractions(fractString: string): Fraction =

## Extract fractions from a string and yield them.

for f in fractString.split():

let fields = f.strip().split('/')

assert fields.len == 2

yield (fields[0].parseInt(), fields[1].parseInt())

iterator factors(val: int): tuple[val, exp: int] =

## Extract factors from a positive integer.

# Extract factor 2.

var val = val

var exp = 0

while (val and 1) == 0:

inc exp

val = val shr 1

if exp != 0:

yield (2, exp)

# Extract odd factors.

var d = 3

while d <= val:

exp = 0

while val mod d == 0:

inc exp

val = val div d

if exp != 0:

yield (d, exp)

inc d, 2

func newProg(fractString: string; init: int): FractranProg =

## Initialize a Fractran program.

for f in fractString.fractions():

# Extract numerators factors.

var facts: Factors

for (val, exp) in f.num.factors():

result.primes.add(val)

facts[val] = exp

result.nums.add(facts)

# Extract denominator factors.

facts.clear()

for (val, exp) in f.denom.factors():

result.primes.add(val)

facts[val] = exp

result.denoms.add(facts)

# Finalize list of primes.

result.primes.sort()

result.primes = result.primes.deduplicate(true)

# Allocate and initialize exponent sequence.

result.exponents.setLen(result.primes[^1] + 1)

for (val, exp) in init.factors():

result.exponents[val] = exp

func doOneStep(prog: var FractranProg): bool =

## Execute one step of the program.

for idx, factor in prog.denoms:

block tryFraction:

for val, exp in factor.pairs():

if prog.exponents[val] < exp:

# Not a multiple of the denominator.

break tryFraction

# Divide by the denominator.

for val, exp in factor.pairs():

dec prog.exponents[val], exp

# Multiply by the numerator.

for val, exp in prog.nums[idx]:

inc prog.exponents[val], exp

return true

func `$`(prog: FractranProg): string =

## Display a value as a product of prime factors.

for val, exp in prog.exponents:

if exp != 0:

if result.len > 0:

result.add('.')

result.add($val)

if exp > 1:

result.add('^')

result.add($exp)

proc run(fractString: string; init: int; maxSteps = 0) =

## Run a Fractran program.

var prog = newProg(fractString, init)

var stepCount = 0

while stepCount < maxSteps:

if not prog.doOneStep():

echo "*** No more possible fraction. Program stopped."

return

inc stepCount

echo stepCount, ": ", prog

proc findPrimes(maxCount: int) =

## Search and print primes.

var prog = newProg(PrimeProg, 2)

let oddPrimes = prog.primes[1..^1]

var primeCount = 0

while primeCount < maxCount:

discard prog.doOneStep()

block powerOf2:

if prog.exponents[2] > 0:

for p in oddPrimes:

if prog.exponents[p] != 0:

# Not a power of 2.

break powerOf2

inc primeCount

echo primeCount, ": ", prog.exponents[2]

#------------------------------------------------------------------------------

echo "First ten steps for program to find primes:"

run(PrimeProg, 2, 10)

echo "\nFirst twenty prime numbers:"

findPrimes(20)

</lang>

{{out}}

<pre>

First ten steps for program to find primes:

1: 3.5

2: 3.5^2.11

3: 5^2.29

4: 5^2.7.11

5: 5^2.7.13

6: 5^2.17

7: 2.3.5.13

8: 2.3.5.11

9: 2.5.29

10: 2.5.7.11

First twenty prime numbers:

1: 2

2: 3

3: 5

4: 7

5: 11

6: 13

7: 17

8: 19

9: 23

10: 29

11: 31

12: 37

13: 41

14: 43

15: 47

16: 53

17: 59

18: 61

19: 67

20: 71