A203907 Successor function for Conway's PRIMEGAME.

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,1

Comments

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

Simple regularities seen in the first terms do not necessarily hold beyond. It is true that a(2k)/15 = a(4k)/30 for all k, but this is not equal to k (often not even an integer) when k has a prime factor 11 <= p <= 29. Also, a(2k-1) = 55k holds for more than 60%, but not for all k >= 1. - M. F. Hasler, Jun 15 2017

Links

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

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, Mathematics Magazine, Vol. 56, No. 1 (1983), pp. 26-33, available at JSTOR.org/stable/2690263.

OEIS Wiki, Conway's PRIMEGAME.

Eric Weisstein's World of Mathematics, FRACTRAN.

Wikipedia, FRACTRAN, created Sep. 23, 2007.

Formula

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.

From M. F. Hasler, Apr 25 2026: (Start)

In other words: if 91 | n, then a(n) = 17*n, else if 85 | n, then a(n) = 78*n, and so on, until reaching the last fraction of the list, whence:

a(n) = 55*n iff n has no divisor in {2, 7, 11, 13, 17, 19, 23, 29}. (End)

Mathematica

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

Prog

(Haskell)
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..]
(PARI) {A203907(n)=foreach([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], f, denominator(f*n)==1 && return(f*n))} \\ Charles R Greathouse IV, Jul 31 2016, edited by M. F. Hasler, Jun 15 2017, Apr 25 2026
(Python)
A202138=17, 78, 19, 23, 29, 77, 95, 77, 1, 11, 13, 15, 1, 55 # PRIMEGAME
A203363=91, 85, 51, 38, 33, 29, 23, 19, 17, 13, 11, 2, 7, 1  # fractions
A203907=lambda n: next(n//d*c for c, d in zip(A202138, A203363) if n%d==0) # M. F. Hasler, Apr 25 2026

Crossrefs

Cf. A007542 (trajectory of 2 under iterations of this map), A185242 (trajectory of 3), A273091 (trajectory of 6).

Cf. A202138, A203363 (numerators and denominators of Conway's PRIMEGAME fractions).

Sequence in context: A227856 A057965 A083516 * A391528 A220134 A178509

Adjacent sequences: A203904 A203905 A203906 * A203908 A203909 A203910

Keyword

nonn,easy,nice

Author

Reinhard Zumkeller, Jan 24 2012

Status

approved