Permutation of the positive integers

This article page is a stub, please help by expanding it.

A permutation of the positive integers is a sequence in which each of the positive integers (the members of

ℤ + = {1, 2, 3, 4, 5, 6, 7, ...}

) occurs exactly once, generally in a position other than its usual position in ascending order. The identity permutation of the positive integers is given by A000027.

The following sequence has been proved to be a permutation of the positive integers.

A064413 EKG sequence or electrocardiogram sequence:

a (1) = 1; a (2) = 2;

for

n > 2, a (n) =

smallest number not already used which shares a factor with 

a (n  −  1)

.

{1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11, 33, 27, 30, 25, 35, 28, 26, 13, 39, 36, 32, 34, 17, 51, 42, 38, 19, 57, 45, 40, 44, 46, 23, 69, 48, 50, 52, 54, 56, 49, 63, 60, 55, 65, 70, 58, ...}

Blockwise permutation of the positive integers

A blockwise permutation of the positive integers is a permutation of the positive integers consisting of consecutive blocks of positive integers, which are then blockwise permuted.

Without the initial 0, A014681 (fix 0, exchange even and odd numbers) is a very simple example of such a blockwise (blocks of two consecutive integers) permutation:

{2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, 16, 15, 18, 17, 20, 19, 22, 21, 24, 23, 26, 25, 28, 27, 30, 29, 32, 31, 34, 33, 36, 35, 38, 37, 40, 39, 42, 41, 44, 43, 46, 45, 48, 47, 50, 49, 52, 51, 54, 53, 56, 55, ...}

Sequences like these are known to be permutations because they were so defined. Certain sequences arise in other problems and are proved to be permutations. Others are conjectured to be permutations, until a repeated, omitted, or nonpositive term can be found.

Results

The LCM of consecutive terms must be at least 3.25 times the term index infinitely often; more specifically,

$\limsup _{i}{\frac {\operatorname {lcm} (a_{i},a_{i+1})}{i}}\geq {\frac {1}{1-\log 2}}\approx 3.25889.$^{[dead link]}

Erdős, Freud, & Hegyvári write, “Very probably this lim sup must be infinite, and one can expect an even sharper rate of growth.” There exists a permutation with

$\operatorname {lcm} (a_{i},a_{i+1})<i\exp \left((2{\sqrt {2}}+\varepsilon ){\sqrt {\log i\log \log i}}\right).$

Similarly, the GCD of consecutive terms cannot be too large:

$\liminf _{i}{\frac {\operatorname {gcd} (a_{i},a_{i+1})}{i}}\leq {\frac {61}{90}},$

but

gcd (ai, ai + 1) > i / 2

for all

i

is possible, see A064736.

Permutation of the positive integers (conjectured)

A conjectured permutation (proof?) of the primes interleaved with the sequence of nonprime numbers

• Eric Angelini, Non-primes and non-prime sums, posting to SeqFan on Jan 15 2013

A?????? Write down the non prime numbers in ascending order, insert between two non-primes the smallest prime not yet present in the sequence such that two neighboring integers sum to a nonprime.

{1, 5, 4, 2, 6, 43, 8, 7, 9, 11, 10, 23, 12, 13, 14, 31, 15, 17, 16,...}

A?????? Bisection (containing the primes) of the above sequence. (Is this a permutation of the primes?)

{5, 2, 43, 7, 11, 23, 13, 31, 17, ...}

Permutation of the positive integers (open problem)

A055265

In May 2009, Dmitry Kamenetsky wondered if every integer eventually occurs. Robert G. Wilson v is convinced of this on probabilistic grounds. In April 2011, this sequence was pondered again, obtaining more questions than answers. Since even integers alternate with odd integers, this would imply that the sequence has permutations for two disjoint subsets of the positive integers: a permutation of the even integers and a permutation of the odd integers.

A055265:

a (n)

is the smallest positive integer not already in the sequence for which

a (n) + a (n  −  1)

is an odd prime,

a (1) = 1, a (2) = 2

.

{1, 2, 3, 4, 7, 6, 5, 8, 9, 10, 13, 16, 15, 14, 17, 12, 11, 18, 19, 22, 21, 20, 23, 24, 29, 30, 31, 28, 25, 34, 27, 26, 33, 38, 35, 32, 39, 40, 43, 36, 37, 42, 41, 48, 49, 52, 45, 44, 53, 50, 47, 54, 55, 46, 51, 56, ...}

See also

• Orderings of algebraic numbers and permutation of the algebraic numbers
• Orderings of rational numbers and permutation of the rational numbers
• Orderings of integers and permutation of the integers
• Orderings of positive integers