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

%I M5074 #36 Dec 17 2021 11:04:42

%S 19,69,280,707,2363,3876,8068,11319,19201,36866,45551,75224,101112,

%T 117831,152025,215384,293375,327020,428553,507519,555694,700063,

%U 808331,989526,1273490,1434366,1530213,1710923,1818254,2019962,2833089,3104685,3546320,3720785

%N Number of steps to compute n-th prime in PRIMEGAME (fast 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 Alois P. Heinz, <a href="/A007546/b007546.txt">Table of n, a(n) for n = 1..5000</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.

%H Wikipedia, <a href="https://oeis.org/wiki/Conway&#39;s_PRIMEGAME">Conway's PRIMEGAME</a>

%p with(numtheory): f:= proc(n) local l, b, d; l:= sort([divisors (n)[]]); b:= l[nops(l)-1]; n-1 +(6*n+2)*(n-b) +2*add(floor(n/d), d=b..n-1) end: a:= proc(n) option remember; `if`(n=1, f(2), a(n-1) +add(f(i), i=ithprime(n-1)+1..ithprime(n))) end: seq(a(n), n=1..40); # _Alois P. Heinz_, Aug 12 2009

%t f[n_] := Module[{l, b, d}, l = Divisors [n]; b = l[[-2]]; n-1 + (6*n+2)*(n-b) + 2*Sum[Floor[n/d], {d, b, n-1}]]; a[n_] := a[n] = If[n == 1, f[2], a[n-1] + Sum[f[i], {i, Prime[n-1]+1, Prime[n]}]]; Table[a[n], {n, 1, 32}] (* _Jean-François Alcover_, Oct 04 2013, translated from Alois P. Heinz's Maple program *)

%Y Cf. A007542, A007547.

%K easy,nonn,nice

%O 1,1

%A _N. J. A. Sloane_

%E More terms from _Alois P. Heinz_, Aug 12 2009