A007546 -id:A007546 - cp's OEIS frontend

A007542 Successive integers produced by Conway's PRIMEGAME.

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, 2340, 1980, 1740, 4620, 4060, 10780, 12740, 2380, 2184, 408, 152

Offset: 1

N. J. A. Sloane

Conway's PRIMEGAME produces the terms 2^prime in increasing order.
From Daniel Forgues, Jan 20 2016: (Start)
Pairs (n, a(n)) such that a(n) = 2^k are (1, 2^1), (20, 2^2), (70, 2^3), (282, 2^5), (711, 2^7), (2376, 2^11), (3894, 2^13), (8103, 2^17), ...
Numbers n such that a(n) = 2^k are 1, 20, 70, 282, 711, 2376, 3894, 8103, ... [This is 1 + A007547. - N. J. A. Sloane, Jan 25 2016] (End)

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..8103
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.
Richard K. Guy, Conway's prime producing machine, Math. Mag. 56 (1983), no. 1, 26-33. [Gives slightly different version of the program which produces different terms, starting from n=132.]
OEIS Wiki, Conway's PRIMEGAME
Kevin I. Piterman and Leandro Vendramin, Computer algebra with GAP, 2023. See p. 40.
Leandro Vendramin, Mini-couse on GAP - Exercises, Universidad de Buenos Aires (Argentina, 2020).
Eric Weisstein's World of Mathematics, FRACTRAN
Wikipedia, FRACTRAN

Cf. A007546, A007547, A183132, A202138, A203363.

a007542 n = a007542_list !! (n-1)
a007542_list = iterate a203907 2  -- Reinhard Zumkeller, Jan 24 2012

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]: a:= proc(n) option remember; global l; local p, k; if n=1 then 2 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); # Alois P. Heinz, Aug 12 2009

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}; a[1] = 2; A007542[n_] := A007542[n] = (p = A007542[n - 1]; k = 1; While[ ! IntegerQ[p * conwayFracs[[k]]], k++]; p * conwayFracs[[k]]); Table[A007542[n], {n, 42}] (* Jean-François Alcover, Jan 23 2012, after Alois P. Heinz *)

from fractions import Fraction
nums = [17, 78, 19, 23, 29, 77, 95, 77,  1, 11, 13, 15, 1, 55] # A202138
dens = [91, 85, 51, 38, 33, 29, 23, 19, 17, 13, 11,  2, 7,  1] # A203363
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(2, PRIMEGAME, steps=42)) # Michael S. Branicky, Feb 15 2021

a(n+1) = A203907(a(n)), a(1) = 2. [Reinhard Zumkeller, Jan 24 2012]

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

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

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

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

Original entry on oeis.org

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

Offset: 1

Ivan N. Ianakiev, Jan 17 2016

nonn

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

			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.

Dominic Olivastro, Ancient Puzzles, Bantam Books, 1993, pp. 20-21.

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".
R. K. Guy, Conway's prime producing machine, Math. Mag. 56 (1983), no. 1, 26-33.
Eric Weisstein's World of Mathematics, FRACTRAN

Cf. A007542, A007546, A007547, A183132, A183133.

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

cp's OEIS Frontend

A007542 Successive integers produced by Conway's PRIMEGAME.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Formula

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

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

Python

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica