cp's OEIS Frontend

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

%I A267572 #23 Feb 16 2025 08:33:29
%S A267572 19,50,211,577,2083,3469,7361,10395,17915,35249,43188,72392,97236,
%T A267572 113324,146556,209098,285307,317925,417234,494939,541264,684114,
%U A267572 789130,968524,1249354,1408123,1500944,1679217,1781388,1980305
%N A267572 Number of steps J. H. Conway's Fractran program needs to calculate the n-th prime.
%C A267572 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}.
%D A267572 Dominic Olivastro, Ancient Puzzles, Bantam Books, 1993, pp. 20-21.
%H A267572 J. H. Conway, <a href="http://dx.doi.org/10.1007/978-1-4612-4808-8_2">FRACTRAN: a simple universal programming language for arithmetic</a>, in T. M. Cover and Gopinath, eds., Open Problems in Communication and Computation, Springer, NY 1987, pp. 4-26.
%H A267572 Esolang Wiki "<a href="http://www.esolangs.org/wiki/Fractran">Fractran</a>".
%H A267572 R. K. Guy, <a href="http://www.jstor.org/stable/2690263">Conway's prime producing machine</a>, Math. Mag. 56 (1983), no. 1, 26-33.
%H A267572 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/FRACTRAN.html">FRACTRAN</a>
%e A267572 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.
%t A267572 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};
%t A267572 stepCount[n_] := n * fracList[[First[Flatten[Position[n * fracList, First[Select[n * fracList, IntegerQ]]]]]]];
%t A267572 A267572[n_] := Length[NestWhileList[stepCount[#] &, 2^n, stepCount[#] != 2^Prime[n] &]];
%t A267572 Table[tempVar = A267572[n]; Print["a(", n,") = ", tempVar]; tempVar, {n, 30}]
%Y A267572 Cf. A007542, A007546, A007547, A183132, A183133.
%K A267572 nonn
%O A267572 1,1
%A A267572 _Ivan N. Ianakiev_, Jan 17 2016