**This forum is closed to new posts due to low activity and a deluge of spam.** It is kept online as a static historical record. If you want to read about or discuss esoteric programming languages, the Esolang wiki is the place to go. An archive of the forum is available.

Does anyone know of a reasonably simple FRACTRAN program that,

for every positive integer starting value of*n*, always eventually halts with *n* = 2?

(Either I'm missing something obvious, or this is more complicated than it sounds.)

for every positive integer starting value of

(Either I'm missing something obvious, or this is more complicated than it sounds.)

For any fractran program, let p be any prime not used in the program. If your starting value is divisible by p,

then the program has no way of removing it. So it cannot be done, alas.

Oops ... I misstated the question.

For any starting value*n* = 2^{x}, where *x* is a nonnegative integer, the program must eventually halt with *n* = 2^{1}.

(Alternatively, a different output convention could be used, such that, starting with any*n* = 2^{x}, the program

eventually halts with*n* = *p*^{1} for some prime number *p*.)

I.e., the program is to compute the constant function*C*_{1} such that *C*_{1}(*x*) = 1 for every nonnegative integer *x*.

A similar question applies to any*positive* constant function. (For the constant 0, the program (1/2) will do.)

For any starting value

(Alternatively, a different output convention could be used, such that, starting with any

eventually halts with

I.e., the program is to compute the constant function

A similar question applies to any

Well, there still is no such program, because of the faulty i/o convention that I was imposing ...

There is no FRACTRAN program that halts with a value other than 2^0 when started with the value 2^0.

(Only an integral fraction can alter the value 1, and any program containing such a fraction will never halt.)

So, the i/o convention of starting with 2^x and stopping with 2^f(x) (or p^f(x) for a given prime p)

is not generally adequate to compute functions f: N -> N.

The simplest remedy may be to start with 2^(x+1) and stop with 3^(f(x)+1). Using this i/o encoding,

here are programs for all the constant functions:

`ZERO = [7/10, 11/5, 5/14, 11/7, 5/2, 3/11]`

ONE = [7/10, 11/5, 5/14, 11/7, 39/11, 5/2, 3/13]

TWO = [7/10, 11/5, 5/14, 11/7, 39/11, 51/13, 5/2, 3/17]

THREE = [7/10, 11/5, 5/14, 11/7, 39/11, 51/13, 57/17, 5/2, 3/19]

etc. Each successive program is obtained from its predecessor by increasing the denominator prime p

in the final fraction to the next larger prime, say q, and inserting 3q/p before the 5/2.

Are there "smaller" versions of these programs? (I'm supposing that whatever i/o encoding scheme

is used, the same one is used for all the functions.)

Absolutely. For a start, remember you can have exponents larger than 1 in the program itself. So, if I've thought correctly:

CONST N = [2/25, 5/2, 3^(N+1)/5]

For large enough N, I suspect you could compress that further textually (since 3^(N+1) is pretty big, plus there is that whole Kolmogorov complexity thing that should apply.) For example powers of 2:

CONST 2^N = [2/25, 5/2, 49/5, 121/7, ..., 9/last prime]

Those are nice little programs. (BTW, I didn't actually write mine in FRACTRAN, but wrote them first as counter machine

programs, then translated them instruction-by-instruction into FRACTRAN -- clearly not a way to get "optimized" code!)

Borrowing your basic idea, here's a version, I hope, of the successor function (x -> x+1):

`SUCC = [55/2, 3/5, 11/49, 7/11, 3/7].`

In an obvious symbolic notation, with i, o, a, b, c denoting any five distinct prime numbers, this is

`SUCC = [ab/i, o/b, a/cc, c/a, o/c],`

which should halt with final value o^(x+2) if started with initial value i^(x+1) (x >= 0).

That can be shortened too:

SUCC = [6/5 , 5/4, 9/2]

I notice that in a variant of FRACTRAN that tests whether state/denom is integral, instead of whether state*numer/denom

is integral, your program can be shortened even further to SUCC = [6/4, 9/2] (symbolically, [io/ii, oo/i]). Your Bag language

(http://home.nvg.org/~oerjan/esoteric/bag/) appears to be equivalent to a variant of this kind.