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

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

Offset: 1

Author

Ivan N. Ianakiev, Jan 17 2016

Keywords

• nonn

Comments

The sieve 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}.

Examples

			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 a power of 2 is reached (2^2 in this case). The exponent of 2 is prime(1) and a(1) = 19 is the number of steps to reach it.
		

References

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

Links

• 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

Crossrefs

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

Programs

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}]