

A267572


Number of steps J. H. Conway's Fractran program needs to calculate the nth prime.


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


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


REFERENCES

Dominic Olivastro, Ancient Puzzles, Bantam Books, 1993, pp. 2021.


LINKS

Table of n, a(n) for n=1..30.
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. 426.
Esolang Wiki "Fractran".
R. K. Guy, Conway's prime producing machine, Math. Mag. 56 (1983), no. 1, 2633.
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 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.


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.
Sequence in context: A130413 A156376 A063306 * A349554 A190267 A066775
Adjacent sequences: A267569 A267570 A267571 * A267573 A267574 A267575


KEYWORD

nonn


AUTHOR

Ivan N. Ianakiev, Jan 17 2016


STATUS

approved



