A007542 -id:A007542 - cp's OEIS frontend

A034785 a(n) = 2^(n-th prime).

4, 8, 32, 128, 2048, 8192, 131072, 524288, 8388608, 536870912, 2147483648, 137438953472, 2199023255552, 8796093022208, 140737488355328, 9007199254740992, 576460752303423488, 2305843009213693952

Offset: 1

Asher Auel

These are the "outputs" in Conway's PRIMEGAME (see A007542). - Alonso del Arte, Jan 03 2011

Multiplicative encoding of the n-th prime. - Daniel Forgues, Feb 26 2017

			a(4) = 128 because the fourth prime number is 7 and 2^7 = 128.

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Index to divisibility sequences.

Cf. A000040, A000430, A051006, A073718 (2^(n-th composite)), A074736.

Cf. A184082, A184083.

a034785 = (2 ^) . a000040
-- Reinhard Zumkeller, Feb 07 2015, Jan 24 2012

[2^p: p in PrimesUpTo(100)]; // Vincenzo Librandi, Apr 29 2014

2^Prime@Range@40  (* Vladimir Joseph Stephan Orlovsky, Apr 11 2011 *)

a(n)=1<Charles R Greathouse IV, Apr 07 2012

from sympy import prime
def A034785(n): return 1<Chai Wah Wu, Aug 09 2024

From Amiram Eldar, Aug 11 2020: (Start)
a(n) = 2^A000040(n).
Sum_{n>=1} 1/a(n) = A051006. (End)
From Amiram Eldar, Nov 22 2022: (Start)
Product_{n>=1} (1 + 1/a(n)) = A184083.
Product_{n>=1} (1 - 1/a(n)) = A184082. (End)

More terms from James Sellers, Feb 04 2000

A203363 Denominators of Conway's PRIMEGAME.

Original entry on oeis.org

91, 85, 51, 38, 33, 29, 23, 19, 17, 13, 11, 2, 7, 1

Offset: 1

Alonso del Arte, Dec 31 2011

Numerators are in A202138.

Notice that the last number of this sequence is 1, meaning that the last number in the "prime producing machine" is an integer, namely 55. Thus, if each multiplication by the previous numbers of the "machine" fails to give an integer, this one will, and it will be a multiple of 55.

Cf. A007542

a203363_list = [91, 85, 51, 38, 33, 29, 23, 19, 17, 13, 11, 2, 7, 1]
-- Reinhard Zumkeller, Jan 24 2012

A007546 Number of steps to compute n-th prime in PRIMEGAME (fast version).

Original entry on oeis.org

19, 69, 280, 707, 2363, 3876, 8068, 11319, 19201, 36866, 45551, 75224, 101112, 117831, 152025, 215384, 293375, 327020, 428553, 507519, 555694, 700063, 808331, 989526, 1273490, 1434366, 1530213, 1710923, 1818254, 2019962, 2833089, 3104685, 3546320, 3720785

Offset: 1

N. J. A. Sloane

D. Olivastro, Ancient Puzzles. Bantam Books, NY, 1993, p. 21.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..5000
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.
R. K. Guy, Conway's prime producing machine, Math. Mag. 56 (1983), no. 1, 26-33.
Wikipedia, Conway's PRIMEGAME

Cf. A007542, A007547.

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

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 *)

More terms from Alois P. Heinz, Aug 12 2009

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

Original entry on oeis.org

19, 69, 281, 710, 2375, 3893, 8102, 11361, 19268, 36981, 45680, 75417, 101354, 118093, 152344, 215797, 293897, 327571, 429229, 508284, 556494, 701008, 809381, 990746, 1274952, 1435957, 1531854, 1712701, 1820085, 2021938, 2835628, 3107393, 3549288, 3723821

Offset: 1

N. J. A. Sloane

D. Olivastro, Ancient Puzzles. Bantam Books, NY, 1993, p. 21.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Bert Dobbelaere, Table of n, a(n) for n = 1..1000
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.
R. K. Guy, Conway's prime producing machine, Math. Mag. 56 (1983), no. 1, 26-33.

Cf. A007542, A007546.

Cf. A006530, A034785.

import Data.List (elemIndices)
a007547 n = a007547_list !! n
a007547_list = tail $ elemIndices 2 $ map a006530 a007542_list
-- Reinhard Zumkeller, Jan 24 2012

a:= proc(n) option remember; local 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 then b(0):= 2; a(0):= 0 else a(n-1) fi;
      p:= b(n-1);
      for m do for k while not type(p*l[k], integer) do od;
               p:= p*l[k];
               if 2^ilog2(p)=p then break fi
      od:
      b(n):= p;
      m + a(n-1)
    end:
seq(a(n), n=1..10);  # Alois P. Heinz, May 01 2011

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 *)

More terms from Alois P. Heinz, May 01 2011

A202138 Numerators of Conway's PRIMEGAME.

Original entry on oeis.org

17, 78, 19, 23, 29, 77, 95, 77, 1, 11, 13, 15, 1, 55

Offset: 1

Alonso del Arte, Dec 31 2011

Denominators are in A203363.
Conway's PRIMEGAME (also called "Conway's prime producing machine") is a fascinating (and very inefficient) method for obtaining the prime numbers.
The "machine" consists of 14 rational numbers. Starting with 2, one finds the first number in the machine that multiplied by 2 gives an integer; then for that integer we find the first number in the machine that generates another integer. This process is repeated for each new integer obtained. Thus A007542 is generated. Except for the initial 2, each number in A007542 having an integer for a binary logarithm is a prime number.
Note that in R. K. Guy's 1983 paper, the last four numbers of the machine are 13/11, 15/14, 15/2 and 55 rather than 13/11, 15/2, 1/7 and 55.

R. K. Guy, Conway's prime producing machine, Math. Mag. 56 (1983), no. 1, 26-33.

Cf. A007546, A007547.

a202138_list = [17, 78, 19, 23, 29, 77, 95, 77, 1, 11, 13, 15, 1, 55]
-- Reinhard Zumkeller, Jan 24 2012

A203907 Successor function for Conway's PRIMEGAME.

Original entry on oeis.org

55, 15, 165, 30, 275, 45, 1, 60, 495, 75, 13, 90, 11, 105, 825, 120, 1, 135, 77, 150, 3, 26, 95, 180, 1375, 22, 1485, 210, 77, 225, 1705, 240, 29, 2, 5, 270, 2035, 23, 33, 300, 2255, 315, 2365, 52, 2475, 190, 2585, 360, 7, 375, 19, 44, 2915, 405, 65, 420

Offset: 1

Reinhard Zumkeller, Jan 24 2012

a(n) <= 55 * n, as 55/1 is the last and largest FRACTRAN fraction.
Iterations, starting with 2, give A007542. A185242 begins with 3.
A quasipolynomial of order 6469693230 = 29#. - Charles R Greathouse IV, Jul 31 2016
Apparent simple regularities do not necessarily hold. It is true that a(2n)/15 = a(4n)/30, but for n = 11, 13, 17, 19, 22, 23, ... this is not equal to n. Also, a(2k-1) = 55k holds for more than 60%, but not for all k >= 1. - M. F. Hasler, Jun 15 2017

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, FRACTRAN
Wikipedia, Conway's PRIMEGAME

Cf. A007542.

import Data.Ratio ((%), numerator, denominator)
a203907 n = numerator $ head
   [x | x <- map (* fromInteger n) fracts, denominator x == 1]
   where fracts = zipWith (%) a202138_list a203363_list
a203907_list = map a203907 [1..]

conwayFracs = {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}; conwayProc[n_] := Module[{curr = 1/2, iter = 1}, While[Not[IntegerQ[curr]], curr = conwayFracs[[iter]]n; iter++]; Return[curr]]; Table[conwayProc[n], {n, 60}] (* Alonso del Arte, Jan 24 2012 *)

{A203907(n,V=[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])=for(i=1,#V, denominator(V[i]*n)==1 && return(V[i]*n))} \\ Charles R Greathouse IV, Jul 31 2016, edited by M. F. Hasler, Jun 15 2017

Let [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] be the list of FRACTRAN fractions = [A202138(k)/A203363(k) : 1<=k<=14], then a(n) = n*f, where f is the first term yielding an integral product.

A183132 Successive integers produced by Conway's PRIMEGAME using Kilminster's Fractran program with only nine fractions.

Original entry on oeis.org

10, 5, 36, 858, 234, 5577, 1521, 3549, 8281, 910, 100, 50, 25, 180, 3388, 924, 252, 6006, 1638, 39039, 10647, 24843, 57967, 6370, 700, 300, 7150, 1950, 46475, 12675, 29575, 3250, 360, 6776, 1848, 504, 12012, 3276, 78078, 21294, 507507, 138411, 322959, 753571

Offset: 1

Alois P. Heinz, Dec 26 2010

The exponents of exact powers of 10 in this sequence are 1, followed by the successive primes (A008578).

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

Alois P. Heinz, Table of n, a(n) for n = 1..10547
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
Chaim Goodman-Strauss, Can’t Decide? Undecide!, Notices of the AMS, Volume 57, Number 3, pp. 343-356, March 2010.
R. K. Guy, Conway's prime producing machine, Math. Mag. 56 (1983), no. 1, 26-33.
Eric Weisstein's World of Mathematics, FRACTRAN.
Wikipedia, FRACTRAN.

Cf. A183133, A008578, A007542, A007546, A007547.

l:= [3/11, 847/45, 143/6, 7/3, 10/91, 3/7, 36/325, 1/2, 36/5]:
a:= proc(n) option remember;
      global l;
      local p, k;
      if n=1 then 10
             else p:= a(n-1);
                  for k while not type(p*l[k], integer)
                  do od; p*l[k]
      fi
    end:
seq(a(n), n=1..50);

l = {3/11, 847/45, 143/6, 7/3, 10/91, 3/7, 36/325, 1/2, 36/5};
a[n_] := a[n] = Module[{p, k}, If[n == 1, 10, p = a[n - 1]; For[k = 1, !IntegerQ[p*l[[k]]], k++]; p*l[[k]]]];
Array[a, 50] (* Jean-François Alcover, May 28 2018, from Maple *)

from fractions import Fraction
nums = [ 3, 847, 143, 7, 10, 3,  36, 1, 36]
dens = [11,  45,   6, 3, 91, 7, 325, 2,  5]
PRIMEGAME = [Fraction(num, den) for num, den in zip(nums, dens)]
def succ(n, program):
    for i in range(len(program)):
      if (n*program[i]).denominator == 1: return (n*program[i]).numerator
def orbit(start, program, steps):
    orb = [start]
    for s in range(1, steps): orb.append(succ(orb[-1], program))
    return orb
print(orbit(10, PRIMEGAME, steps=44)) # Michael S. Branicky, Oct 05 2021

A185242 Successive integers produced by Conway's PRIMEGAME, starting with 3 rather than 2.

Original entry on oeis.org

3, 165, 145, 385, 455, 85, 78, 66, 58, 154, 182, 34, 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30, 225, 12375, 10875, 28875, 25375, 67375, 79625, 14875, 13650, 2550

Offset: 1

Alonso del Arte, Jan 24 2012

nonn

2 is nevertheless reached fairly soon, and after that the sequence proceeds exactly the same as A007542.

			After 3, we have 3 * 55 = 165 because none of the other fractions give an integer. Then we can use 29/33, and thus 165 * 29/33 = 145, and so on and so forth.

Wikipedia, Conway's PRIMEGAME

Cf. A007542, A203907, A273091.

a185242 n = a185242_list !! (n-1)
a185242_list = iterate a203907 3
-- Reinhard Zumkeller, Jan 25 2012

(* First run the program for A203907 to define conwayProc *) NestList[conwayProc, 3, 50]

a(n+12) = A007542 (n) for n > 0. - Charles R Greathouse IV, Jan 24 2012

a(n+1) = A203907(a(n)), a(1) = 3. - Reinhard Zumkeller, Jan 25 2012

A183133 Number of steps to compute the n-th prime in PRIMEGAME using Kilminster's Fractran program with only nine fractions.

Original entry on oeis.org

10, 46, 196, 500, 1428, 2488, 4588, 6840, 10546, 17118, 23064, 33332, 44472, 55848, 70330, 90836, 115136, 137912, 168802, 201000, 233542, 276680, 320332, 373198, 439722, 503810, 568334, 640092, 712314, 792186, 917090, 1023878, 1146632, 1263818, 1419298

Offset: 1

Alois P. Heinz, Dec 26 2010

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

Alois P. Heinz, Table of n, a(n) for n = 1..100
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".
Chaim Goodman-Strauss, Can’t Decide? Undecide!, Notices of the AMS, Volume 57, Number 3, pp. 343-356, March 2010.
R. K. Guy, Conway's prime producing machine, Math. Mag. 56 (1983), no. 1, 26-33.
Eric Weisstein's World of Mathematics, FRACTRAN.
Wikipedia, FRACTRAN.

Cf. A183132, A008578, A007542, A007546, A007547.

a:= proc(n) option remember;
      local l,p,m,k;
      l:= [3/11, 847/45, 143/6, 7/3, 10/91, 3/7, 36/325, 1/2, 36/5]:
      if n=1 then b(0):= 10; a(0):= 0
             else a(n-1)
      fi;
      p:= b(n-1);
      for m do
         for k while not type(p*l[k], integer)
         do od; p:= p*l[k];
         if 10^ilog10(p)=p then break fi
      od:
      b(n):= p;
      m + a(n-1)
    end:
seq(a(n), n=1..20);

a[n_] := a[n] = Module[{l, p, m, k},
     l = {3/11, 847/45, 143/6, 7/3, 10/91, 3/7, 36/325, 1/2, 36/5};
     If[n == 1, b[0] = 10; 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[10^(Length@IntegerDigits[p]-1) == p, Break[]]];
     b[n] = p; m + a[n - 1]];
Array[a, 20] (* Jean-François Alcover, Apr 02 2021, after Alois P. Heinz *)

A273091 Successive integers produced by Conway's PRIMEGAME, starting with 6 rather than 2.

Original entry on oeis.org

6, 45, 2475, 2175, 5775, 5075, 13475, 15925, 2975, 2730, 510, 468, 396, 348, 924, 812, 2156, 2548, 476, 28, 210, 1575, 225, 12375, 10875, 28875, 25375, 67375, 79625, 14875, 13650, 2550, 2340, 1980, 1740, 4620, 4060, 10780, 12740, 2380, 2184, 408, 152, 92, 380, 230, 950, 575, 2375, 9625

Offset: 1

Alonso del Arte, May 14 2016

Upon reaching 225, this sequence becomes the same as A007542, having skipped over 4 (which corresponds to the prime 2) and then goes on to 8 (which corresponds to the prime 3).

			Multiply 6 by 15/2 to obtain 45. Then for 45, multiplying by the first thirteen fractions fails to produce an integer, so 45 * 55 = 2475.

Cf. A185242.

(* First run the program for A203907 to define conwayProc *) NestList[conwayProc, 6, 50]

cp's OEIS Frontend

A034785 a(n) = 2^(n-th prime).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Python

Formula

Extensions

A203363 Denominators of Conway's PRIMEGAME.

Views

Author

Keywords

Comments

Crossrefs

Programs

Haskell

A007546 Number of steps to compute n-th prime in PRIMEGAME (fast version).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Extensions

A202138 Numerators of Conway's PRIMEGAME.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A203907 Successor function for Conway's PRIMEGAME.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A183132 Successive integers produced by Conway's PRIMEGAME using Kilminster's Fractran program with only nine fractions.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica