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 x0 = a, x1 = b, ... recursively by xn+2 = f(xn+1, xn) 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:
To determine a period, we apply Floyd's theorem to the sequence Xn defined
recursively by Xn+1 = F(Xn), where F(a,b) = (b,f(a,b)) and
Xn = (xn, xn+1).
We get cycling of the sequence Xn (and hence the sequence xn), if and only if there exists an n ≥ 1, such that Xn = X2n, i.e., xn = x2n and xn+1 = x2n+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.
Last modified 26th May 2016