px+1 map


The px+1 map is a generalizationPlanetmathPlanetmath of the 3x+1 map, or Collatz problemMathworldPlanetmath, in which an input number x is tested for divisibility by primes less than an odd prime p: if x is divisible by any such prime, it is divided by the smallest such prime; otherwise it is multiplied by p and incremented by 1. In the case p=3, the test for the input number simplifies to a parity test, because 2 is the only prime less than 3. The map can be iteratively applied, generally resulting in sequencesMathworldPlanetmath that rise and fall aperiodically before reaching 1 in ways that are not readily apparent from the original x (with the obvious exception of x being a power of two, in which case the resulting sequence from the original x to 1 is a listing of powers of two in strictly descending order; a similar pattern occurs when x is a power of a prime). Once the sequence reaches 1, continued iteration produces a predictable cycle, especially when p is a Mersenne primeMathworldPlanetmath.

For example, with the 7x+1 map, an input x is tested for divisibility by 2, 3 and 5 (in that order), and whichever test passes first causes the output to be x divided by that prime; but if all tests fail, then the output is 7x+1. Applied to 19, the map gives the sequence 19, 134, 67, 470, 235, 47, 330, 165, 55, 11, 78, 39, 13, 92, 46, 23, 162, 81, 27, 9, 3, 1. (Notice that 470 is followed by 235 and then 47; similarly 330 is followed by 165, 55 and then 11). It is believed that for any p, iteration on any x will eventuallyMathworldPlanetmath reach 1, but just as the original p=3 problem remains unsolved, so does the generalized problem.

Title px+1 map
Canonical name Px1Map
Date of creation 2013-03-22 18:56:32
Last modified on 2013-03-22 18:56:32
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 4
Author PrimeFan (13766)
Entry type Definition
Classification msc 11B37