Sunday, May 31, 2009

Greatest prime factor sequences


The greatest prime factor function (gpf) can be used to generate a class of prime sequences as follows: x(1) = p (an arbitrary prime) and x(n+1) = gpf (a*x(n) + b) for n ≥ 1 (a, b are fixed positive integers). Computer evidence suggests that all "linear gpf sequences" are ultimately periodic, regardless the values chosen for a and b. For example, the sequences corresponding to a = 2, b = 1 and p arbitrary appear to enter the period 3, 7, 5, 11, 23, 47, 19, 13. For a = 6, b = 5, x(1) = 2, the period is pretty long: 23, 13, 83, 503, 3023, 18143, 108863, 9749, 137, 827, 4967, 727, 397, 31, 191, 1151, 6911, 367, 2207, 1019, 211, 41, 251, 1511, 193, 1163, 69. Multiple limit cycles are possible - for example in the case a = 16 and b = 1, the choice x(1)=2 leads to the period 37, 593, 3163, 229, 733, 317, 89, 19, 61, 977, 193, 3089, 659, while the choice x(1) = 47 leads to the period 251, 103, 97, 1553. So far we proved the "gpf conjecture" in the special case in which a is a divisor of b.
REFERENCES:
1. Caragiu, M. and Scheckelhoff, L. The Greatest Prime Factor and Related Sequences., JP J. of Algebra, Number Theory and Appl. 6, 403-409 (2006).
2. Mihai Caragiu. Recurrent sequences based on the greatest prime factor function. In Abstracts of the Papers Presented to the American Mathematical Society, Meeting #1020, University of Cincinnati, 1020-11-247 (2006).