A267572 Number of steps J. H. Conway's Fractran program needs to calculate the n-th prime when starting from 2^n.

19, 50, 211, 577, 2083, 3469, 7361, 10395, 17915, 35249, 43188, 72392, 97236, 113324, 146556, 209098, 285307, 317925, 417234, 494939, 541264, 684114, 789130, 968524, 1249354, 1408123, 1500944, 1679217, 1781388, 1980305, 2787538, 3055965, 3493110, 3664004, 4486873

Offset

1,1

Comments

The program consists of the fractions {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}.

From Pontus von Brömssen, Apr 28 2026: (Start)

This is the version of the program given by R. K. Guy's 1983 paper, which differs from the version in A007547. (See comment in A202138.)

Note that a(n) is the number of steps needed to reach 2^prime(n) starting from 2^n, not from 2^prime(n-1) or from 2 as might be expected. The number of steps to 2^prime(n) starting from 2 is A007546(n).

(End)

References

Dominic Olivastro, Ancient Puzzles, Bantam Books, 1993, pp. 20-21.

Links

Table of n, a(n) for n=1..35.

J. H. Conway, FRACTRAN: a simple universal programming language for arithmetic, in T. M. Cover and Gopinath, eds., Open Problems in Communication and Computation, Springer, NY 1987, pp. 4-26.

Esolang Wiki "Fractran".

R. K. Guy, Conway's prime producing machine, Math. Mag. 56 (1983), no. 1, 26-33.

Eric Weisstein's World of Mathematics, FRACTRAN.

Example

For n = 1, start with 2^n and find the first fraction (fraction1 = 15/2) where the product (2^n)*fraction1 is an integer (integer1 = 15). With integer1 repeat the above, i.e., find the first fraction (fraction2 = 55/1) where integer1*fraction2 is an integer (integer2 = 825). Repeat until 2^prime(n) is reached (2^2 in this case). a(1) = 19 is the number of steps to reach it.

Mathematica

fracList = {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};
stepCount[n_] := n * fracList[[First[Flatten[Position[n * fracList, First[Select[n * fracList, IntegerQ]]]]]]];
A267572[n_] := Length[NestWhileList[stepCount[#] &, 2^n, stepCount[#] != 2^Prime[n] &]];
Table[tempVar = A267572[n]; Print["a(", n, ") = ", tempVar]; tempVar, {n, 30}]

Crossrefs

Cf. A007542, A007546, A007547, A183132, A183133, A202138.

Sequence in context: A378051 A156376 A063306 * A378179 A349554 A190267

Adjacent sequences: A267569 A267570 A267571 * A267573 A267574 A267575

Keyword

nonn

Author

Ivan N. Ianakiev, Jan 17 2016

Extensions

a(31)-a(35) from Pontus von Brömssen, Apr 28 2026

Status

approved