login
Number of steps to compute n-th prime in PRIMEGAME (slow version).
(Formerly M5075)
7

%I M5075 #43 Jun 12 2024 14:10:27

%S 19,69,281,710,2375,3893,8102,11361,19268,36981,45680,75417,101354,

%T 118093,152344,215797,293897,327571,429229,508284,556494,701008,

%U 809381,990746,1274952,1435957,1531854,1712701,1820085,2021938,2835628,3107393,3549288,3723821

%N Number of steps to compute n-th prime in PRIMEGAME (slow version).

%D D. Olivastro, Ancient Puzzles. Bantam Books, NY, 1993, p. 21.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Bert Dobbelaere, <a href="/A007547/b007547.txt">Table of n, a(n) for n = 1..1000</a>

%H 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 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.

%p a:= proc(n) option remember; local l, p, m, k;

%p l:= [17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23,

%p 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1]:

%p if n=1 then b(0):= 2; a(0):= 0 else a(n-1) fi;

%p p:= b(n-1);

%p for m do for k while not type(p*l[k], integer) do od;

%p p:= p*l[k];

%p if 2^ilog2(p)=p then break fi

%p od:

%p b(n):= p;

%p m + a(n-1)

%p end:

%p seq(a(n), n=1..10); # _Alois P. Heinz_, May 01 2011

%t Clear[a]; a[n_] := a[n] = Module[{l, p, m, k}, l = {17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1}; If[n == 1, b[0] = 2; a[0] = 0, a[n-1]]; p = b[n-1]; For[m=1, True, m++, For[k=1, !IntegerQ[p*l[[k]]], k++]; p = p*l[[k]]; If[2^(Length[IntegerDigits[p, 2]]-1) == p, Break[]]]; b[n] = p; m + a[n-1]]; Table[Print[a[n]]; a[n], {n, 1, 30}] (* _Jean-François Alcover_, Nov 25 2014, after _Alois P. Heinz_ *)

%o (Haskell)

%o import Data.List (elemIndices)

%o a007547 n = a007547_list !! n

%o a007547_list = tail $ elemIndices 2 $ map a006530 a007542_list

%o -- _Reinhard Zumkeller_, Jan 24 2012

%Y Cf. A007542, A007546.

%Y Cf. A006530, A034785.

%K easy,nonn,nice

%O 1,1

%A _N. J. A. Sloane_

%E More terms from _Alois P. Heinz_, May 01 2011