In the book *Genius at play* by Siobhan Roberts, pp.xx-xxi and in an online talk, the following sequence of John Conway is defined:

First if a and b are positive integers, then f(a,b) = a+b if a+b is a prime, whereas if a+b is composite and p is its least prime factor, then f(a,b) = (a+b)/p.

Now given positive integers a and b, define the sequence x_{0} = a, x_{1} = b, ... recursively by x_{n+2} = f(x_{n+1}, x_{n}) for n ≥ 0.

Conway asserted that the sequence eventually becomes periodic.

Apart from cycles of length 1 such as arising from initial values (2,2), in the range a, b ≤ 500, we have found six cycles:

- 507 382 127 509 318 827 229 528 757 257 (length 10)
- 188 419 607 513 560 37 199 118 317 145 231 (length 11)
- 48 13 61 37 49 43 46 89 45 67 56 41 97 69 83 76 53 43 (length 18)
- 63 55 59 57 58 23 27 25 26 17 43 30 73 103 88 191 93 142 47 (length 19)
- 5693 1739 3716 1091 437 764 1201 655 928 1583 837 1210 89 433 261 347 304 217 521 369 445 407 426 119 109 114 223 337 280 617 299 458 757 405 581 493 537 515 526 347 291 319 305 312 617 929 773 851 812 1663 825 1244 2069 3313 2691 3002 (length 56)
- 41 63 52 23 25 24 7 31 19 25 22 47 23 35 29 32 61 31 46 11 19 15 17 16 11 9 10 19 29 24 53 11 32 43 25 34 59 31 45 38 83 11 47 29 38 67 35 51 43 47 45 46 13 59 36 19 11 15 13 14 9 23 16 13 29 21 25 23 24 47 71 59 65 62 127 63 95 79 87 83 85 84 13 97 55 76 131 69 100 13 113 63 88 151 239 195 217 206 141 347 244 197 147 172 29 67 48 23 71 47 59 53 56 109 55 82 137 73 105 89 97 93 95 94 63 157 110 89 199 144 49 193 121 157 139 148 (length 136)

To determine a period, we apply Floyd's theorem to the sequence X_{n} defined
recursively by X_{n+1} = F(X_{n}), where F(a,b) = (b,f(a,b)) and
X_{n} = (x_{n}, x_{n+1}).

We get cycling of the sequence X_{n} (and hence the sequence x_{n}), if and only if there exists an n ≥ 1, such that X_{n} = X_{2n}, i.e.,
x_{n} = x_{2n} and x_{n+1} = x_{2n+1}.

We test the latter condition here.

Program 1 is a BCMath version of the BC program `conwaycycles` in BC file phi and tests Conway's conjecture that all sequences eventually enter a cycle.

Program 2 is a BCMath version of the BC program `conwaysequence1` and tests the conjecture that all sequences eventually enter a cycle, which if its length is greater than 1, will be one of the six cycles mentioned above.

The program will occasionally exit prematurely if the underlying factorization algorithm (which uses only Brent-Pollard and Pollard p-1) fails to find a factor.

Return to main page