cp's OEIS Frontend

Permutation of the positive natural numbers with inverse A225047: a(A225047(n)) = A225047(a(n)) = n. - Reinhard Zumkeller, Apr 25 2013

I confirm that this is a permutation. - N. J. A. Sloane, Mar 28 2015 [This can be proved using an argument similar to (but simpler than) the proof in A093714. - N. J. A. Sloane, May 05 2022]

A set-theory analog of A084937.

Conjecture: This is a permutation of the nonnegative numbers.

Other possible conditions on a(n) with respect to its common factors with a(n-2) and a(n-1) lead to the following:

Coprime to both: A084937.

Coprime to the latter and not the former: A098550.

Coprime to the former and not the latter: with any initial conditions, the sequence "paints itself into a corner", i.e., is finite. With the added condition of a(n) having an extra prime factor not contained in a(n-1), it is A336957.

Coprime to the latter, regardless of the former: simply A000027.

Coprime to the former, regardless of the latter: A121216.

Non-coprime to the latter, regardless of the former: A064413.

Non-coprime to the former, regardless of the latter: A121217.

Permutation of natural numbers with inverse A085230: a(A085230(n))=A085230(a(n))=n.

From Michael De Vlieger, Apr 13 2022: (Start)

Theorem 1: 2 | a(2k+1) for k > 0, consequence of the lexically earliest and coprimality axioms. Even numbers appear in order as a consequence of the latter axiom and since numbers are either even or odd.

Corollary: the only fixed point is a(1) = 1.

Theorem 2: Generally, if prime p | a(n) then p is coprime to a(n +/- 1). For p = 2, 2 | a(2k+1) for k > 0 since 2 is the smallest prime. For odd p it is not necessarily true that given p | a(n) -> p | a(n+2) or p | a(n-2), since there may be a smaller m such that (a(n-1), m) = 1, q | m for prime q < p, and is not in a(1..n-1).

For these reasons, if we also set a(2) = 3, then we need not also check (n, a(n)) = 1, since it isn't possible. If we do not check (n, a(n)) = 1 and set a(2) = 3, 2 would follow 1 since 1 is coprime to all numbers.

Theorem 3: 3 | a(3k+1) for k > 1. Proof: For even k, 6 | a(3k+1), i.e., 6 | a(n) : n mod 6 = 1, and it is easy to see that since even numbers appear in order in the sequence, these even multiples of 3 are also in order. Because 3 | a(n) : n mod 6 = 1, we cannot have 3 | a(n) for n congruent to 0 or 2 (mod 6). Furthermore, we know that 2 | a(n) for n congruent to 3 or 5 (mod 6). So 3 | a(n) odd : n mod 6 = 4, that is, 3 | a(3k+1) for k > 1.

Theorem 4: Odd primes q set records. Proof: (q, a(n-1)) = 1 as a consequence of lexically earliest axiom that rules out equality, and by the definition of prime. 2 is displaced on account of the axiom that bans equality between n and a(n). Therefore, whereupon q is the smallest unused odd number, it enters the sequence.

A consequence of theorems 1 and 3 is that powers of 2 and those of 3 excepting 3 itself do not set records, since their adjacency is governed by a(n-1). The powers of other primes do set records since coprimality does not depend on multiplicity.

The smallest composite record is a(24) = 25. Smallest record m with omega(m) > 1 is a(54) = 55. Powers of 2 and 3 are absent from records for n <= 2^20. (End)

Conjectured to be not a permutation of the natural numbers.

Charles R Greathouse IV extended this, and confirms that primes occur in natural order. - Jonathan Vos Post and M. F. Hasler, Jan 18 2011

Conjecture: for n >= 67, a(n) is even if and only if n == 2 (mod 4) and divisible by 3 if and only if n == 3 (mod 4). In particular, this implies the last value divisible by 6 is a(66) = 36. - Robert Israel, May 12 2015

a(102982) = 42, see A105214. Conjecture above is false. - Sergio Pimentel, Apr 18 2022

The sequence preserves throughout the coprime relations found in the first four positive integers 1,2,3,4 (4 is prime to 1 and 3 but not to 2).

A prime term p at a(n) is necessarily preceded at a(n-2) by a multiple m*p of p, and followed at a(n+2) by a different multiple w*p of p (m,w > 1).

The sequence is infinite. Proof: For successive terms a,b,c,d we can choose a multiple e = q*c of c, where q is any prime which divides neither b nor d and such that e is not a prior term. Then e is prime to b and d but not to c, and since it has not been seen before we have at least one candidate for the term following d, which we choose as the least such number.

The definition implies that there can be no consecutive even terms (since then they would not be coprime). However, consecutive odd terms are not excluded, and do occur (eg 21 can follow 25 because they are coprime). Although two adjacent primes is possible, and does occur (a(9)=5, a(10)=7), three is not, since consecutive distinct primes p,q,r would imply gcd(p,r)>1.

Similar sequences with the same coprime relations as in 1,2,3,4 can be generated from any start terms a,b,c,d with b=a+1,c=b+1,d=c+1, provided a is congruent to 1 or 5 mod 6 (A007310).

Conjecture: The sequence is a permutation of the positive integers in which the primes appear in their natural order.

The sequence differs from A352976 after twenty-six terms. See the examples below.

In the first 100000 terms the maximum run of even and odd terms is three and five respectively; it is unknown if these runs have a maximum number of terms or are unbounded. The fixed points beyond 2 are 15, 25, 35, and it is likely no more exist. The primes appear in their natural order, and it is conjectured that this is a permutation of the positive integers.

From Michael De Vlieger, May 08 2022: (Start)

Let u be the smallest missing number in a(1..n-1) and let record r = max(a(1..n-1)).

Theorem: For odd prime q, r = mq -> q. Proof: generally, q may either divide or be coprime to r, but since equality and coprimality are prohibited by definition, primes may only divide records. This implies q serves as local minima, hence u > 2 is always an odd prime and r > 1 is always even.

Since r is always even, r is nondecreasing and even numbers appear in natural order. Also, r = 2q -> q, similar to the Lagarias-Rains-Sloane chain in the EKG sequence but without the successor 3q.

Theorem: a(n) = k such that k is odd iff least prime factor q | k and q | r. Proof: sequence definition demands smallest missing number such that (r,k) > 1. Otherwise, a(n) = a(n-1) + 2, since (a(n-1), a(n-1) + 2) > 1, and all smaller even numbers have already appeared.

All even numbers and primes appear, and every odd composite k has a least prime factor that admits k into the sequence on the occasion of (r,k) > 1.

There are 3 trajectories in scatterplot for a(n) > 1. The trajectory with lowest apparent slope is that of the primes, i.e., local minima. The trajectory with highest slope is that of records, i.e., even numbers, and the remaining numbers are odd composites. (End)

The sequence contains no primes or prime powers other than the powers of 2. As the sequence starts with 2 and 4, these terms being the largest and second largest values, the following terms will be even. This pattern continues until a term equal to the product of two or more odd primes occurs that shares a factor with the previous two largest even values and is smaller than the largest value plus 2. It is not possible for this value to be a prime larger than 2, or a power of such a prime, as the two terms with which it must share a factor differ by 2. It therefore cannot be between them either so it must be less than the second largest even term. Thus the next term after this odd composite must still share a factor with the two largest even values, and this will be the largest value plus 2 or another smaller odd composite. Therefore two more even values eventually become the two largest terms again, and thus the pattern of the two largest even terms, differing by two, interrupted by odd composites continues. Therefore no primes or prime powers other than powers of 2 will occur.

In the first 200000 terms the maximum run of even and odd terms is twelve and seven respectively; it is unknown if these runs have a maximum number of terms or are unbounded. The fixed points beyond 2 in the same range are 573, 597, 633, 6487, 21865, 22115, although it is likely more exist.

The sequence contains long runs on even terms, differing by 2, and odd terms, differing by various small even numbers. These runs are often interrupted by a large prime that becomes the new largest term. As this and the previous largest term are typically much larger than any other value the sequence then begins a long series of steadily increasing values that share a factor with the sum of these two largest terms.

The sequence is conjectured to be a permutation of the positive integers, although it apparently takes many terms for some primes to appear, e.g., after 200000 terms 73 has not occurred. The primes do not occur in their natural order. Beyond the first three terms there are nine fixed points in the first 200000 terms, although it is likely more exist.

Although all primes likely appear they do not occur in their natural order, e.g., 17 appears before 13. In the range studied each time a prime appears, beyond the initial 2 and 3, the next term is a multiple of the same prime. The largest multiple in the first 500000 terms is eight, first occurring at a(446271) = 64403, a(446272) = 515224. It is unknown if this ratio is unbounded for large n. Similarly the smaller of the two terms before a prime is a multiple of the prime. The largest ratio found being seven, first occurring at a(446271) = 64403, the same term as above.

In the first 500000 terms there are thirty-eight fixed points - 1, 2, 3, 4, 14, 32, 85, ..., 3277, 8651, 9223. It is likely no more exist. The sequence is conjectured to be a permutation of the positive integers.