A085229 -id:A085229 - cp's OEIS frontend

A085230 Inverse of A085229.

1, 3, 2, 5, 4, 7, 6, 9, 10, 11, 8, 13, 12, 15, 16, 17, 14, 19, 18, 21, 22, 23, 20, 25, 24, 27, 28, 29, 26, 31, 30, 33, 34, 35, 36, 37, 32, 39, 40, 41, 38, 43, 42, 45, 46, 47, 44, 49, 48, 51, 52, 53, 50, 55, 54, 57, 58, 59, 56, 61, 60, 63, 64, 65, 66, 67, 62, 69, 70

Offset: 1

Reinhard Zumkeller, Jun 22 2003

nonn

Permutation of natural numbers: a(A085229(n)) = A085229(a(n)) = n.

Odd numbers appear in order, at a(2k) for k > 0. - Michael De Vlieger, Apr 13 2022

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Index entries for sequences that are permutations of the natural numbers

Cf. A085229, A093715.

nn = 10000; c[] = 0; a[1] = c[1] = 1; a[2] = 3; c[3] = u = 2; Do[k = u; While[Nand[c[k] == 0, CoprimeQ[a[i-1], k]], k++]; Set[{a[i], c[k]}, {k, i}]; If[a[i] == u, While[c[u] > 0, u++]], {i, 3, nn}]; Array[c, nn] (* _Michael De Vlieger, Apr 13 2022 *)

A093714 a(n) = smallest number coprime to a(n-1), not equal to a(n-1)+1, and not occurring earlier; a(1)=1.

Original entry on oeis.org

1, 3, 2, 5, 4, 7, 6, 11, 8, 13, 9, 14, 17, 10, 19, 12, 23, 15, 22, 21, 16, 25, 18, 29, 20, 27, 26, 31, 24, 35, 32, 37, 28, 33, 38, 41, 30, 43, 34, 39, 44, 47, 36, 49, 40, 51, 46, 45, 52, 55, 42, 53, 48, 59, 50, 57, 56, 61, 54, 65, 58, 63, 62, 67, 60, 71, 64, 69, 68, 73, 66, 79

Offset: 1

Reinhard Zumkeller, Apr 12 2004

nonn

Lexicographically earliest infinite sequence of distinct positive numbers such that gcd(a(n-1), a(n)) = 1, a(n) != a(n-1) + 1. - N. J. A. Sloane, May 02 2022
Permutation of natural numbers with inverse A093715: a(A093715(n))=A093715(a(n))=n.
Comments from N. J. A. Sloane, May 02 2022: (Start)
Proof that this is a permutation of the natural numbers.
1. As usual for a "lexicographically earliest sequence" of this class, there is a function B(k) such that a(n) > k for all n > B(k).
2. For any prime p, p divides a(n) for some n. [Suppose not. Using 1, find n_0 such that a(n) > p^2 for all n >= n_0. But if a(n) > p^2, then p is a smaller choice for a(n+1), contradiction.]
3. For any prime p, p divides infinitely many terms. [Suppose not. Let p^i be greater than any multiple of p in the sequence. Go out a long way, and find a term greater than p^i. Then p^i is a smaller candidate for the next term. Contradiction.]
4. Every prime p appears naked. [If not, using 3, find a large multiple of p, G*p, say. But then p would have been a smaller candidate than G*p. Contradiction.]
5. The next term after a prime p is the smallest number not yet in the sequence which is relatively prime to p. Suppose k is missing from the sequence, and find a large prime p that does not divide k. Then the term after p will be k.  So every number appears.
This completes the proof.
Conjecture 1: If p is a prime >= 3, p-1 appears after p.
Conjecture 2: If p is a prime, the first term divisible by p is p itself.
Conjecture 3: If a(n) = p is a prime >= 5, then n < p.
(End)
Coincides with A352588 for n >= 17. - Scott R. Shannon, May 02 2022

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Index entries for sequences that are permutations of the natural numbers

Cf. A085229, A347113, A352588, A352928 (smallest missing number).
A352929 gives indices of prime terms, A352930 = first differences, A352931 = a(n)-n. See also A352932.
See Comments in A109812 for a set-theory analog.

nn = 120; c[] = 0; a[1] = c[1] = 1; u = 2; Do[k = u; While[Nand[c[k] == 0, CoprimeQ[#, k], k != # + 1], k++] &@ a[i - 1]; Set[{a[i], c[k]}, {k, i}]; If[a[i] == u, While[c[u] > 0, u++]], {i, 2, nn}]; Array[a, nn] (* _Michael De Vlieger, May 02 2022 *)

from math import gcd
from itertools import islice
def agen(): # generator of terms
    an, aset, mink = 1, {1}, 2
    while True:
        yield an
        k = mink
        while k in aset or gcd(an, k) != 1 or k-an == 1: k += 1
        an = k
        aset.add(an)
        while mink in aset: mink += 1
print(list(islice(agen(), 72))) # Michael S. Branicky, May 02 2022

A352950 Lexicographically earliest infinite sequence of distinct nonnegative integers commencing 1,3,5,7 such that any four consecutive terms are pairwise coprime.

Original entry on oeis.org

1, 3, 5, 7, 2, 9, 11, 13, 4, 15, 17, 19, 8, 21, 23, 25, 16, 27, 29, 31, 10, 33, 37, 41, 14, 39, 43, 47, 20, 49, 51, 53, 22, 35, 57, 59, 26, 55, 61, 63, 32, 65, 67, 69, 28, 71, 73, 45, 34, 77, 79, 75, 38, 83, 89, 81, 40, 91, 97, 87, 44, 85, 101, 93, 46, 95, 103, 99, 52, 107, 109, 105

Offset: 1

David James Sycamore, Apr 10 2022

nonn

The pairwise coprime relations found in the first four odd numbers 1,3,5,7 are preserved throughout in any run of four consecutive terms.
a(4n+5) is always even (and < a(4n+2)); n>=0.
The plot exhibits two distinct rays at first (upper/odd, lower/even), with no terms divisible by 6 until a(229), at which point the even ray switches to producing just 28 multiples of 6 until a(337)=168. At this point the original even ray is re-established, the odd ray divides into two (quasi-parallel) rays, and no further multiples of 6 are seen. Therefore it seems very unlikely that the sequence is a permutation of the nonnegative integers.
Primes p other than p = 2 appear in their natural order.

			3,5,7 are pairwise coprime and 2 is the smallest unused number coprime to all of them, therefore a(5)=2.

Michael De Vlieger, Log-log scatterplot of a(n), n = 1..2^14, highlighting primes in green, numbers divisible by 6 in gold, other even numbers in red, odd numbers divisible by 3 in blue.

Cf. A085229, A103683, A350359.

ina := proc(n) false end: # adapted from code for A103683
a := proc (n) option remember; local k;
if n < 5 then k := 2*n-1
else for k from 2 while ina(k) or igcd(k, a(n-1)) <> 1 or igcd(k, a(n-2)) <> 1 or igcd(k, a(n-3)) <> 1
do
end do
end if; ina(k):= true; k
end proc;
seq(a(n), n = 1 .. 100);

Block[{a, c, k, m, u, nn}, nn = 86; c[] = 0; MapIndexed[Set[{a[First[#2]], c[#1]}, {#1, First[#2]}] &, {1, 3, 5, 7}]; u = 2; Do[k = u; m = LCM @@ Array[a[i - #] &, 3]; While[Nand[c[k] == 0, CoprimeQ[m, k]], k++]; Set[{a[i], c[k]}, {k, i}]; If[a[i] == u, While[c[u] > 0, u++]], {i, 5, nn}]; Array[a, nn] ] (* _Michael De Vlieger, Apr 12 2022 *)

from math import gcd
from itertools import islice
def agen(): # generator of terms
    aset, b, c, d = {1, 3, 5, 7}, 3, 5, 7
    yield from [1, b, c, d]
    while True:
        k = 1
        while k in aset or any(gcd(t, k) != 1 for t in [b, c, d]): k+= 1
        b, c, d = c, d, k
        aset.add(k)
        yield k
print(list(islice(agen(), 107))) # Michael S. Branicky, Apr 10 2022

A366908 Lexicographically earliest infinite sequence of distinct positive integers such that, for n > 1, a(n) shares a factor with n but does not equal n, while not sharing a factor with a(n-1).

Original entry on oeis.org

1, 4, 9, 2, 15, 8, 21, 10, 3, 5, 22, 27, 26, 7, 25, 6, 85, 12, 95, 14, 33, 16, 69, 28, 45, 13, 18, 35, 58, 39, 155, 24, 11, 17, 20, 51, 74, 19, 36, 55, 82, 49, 86, 77, 30, 23, 94, 57, 56, 65, 34, 91, 106, 63, 40, 119, 38, 29, 118, 75, 122, 31, 81, 32, 105, 44, 201, 46, 87, 50, 213, 52, 219, 37

Offset: 1

Scott R. Shannon, Oct 27 2023

nonn

To ensure the sequence is infinite a(n) must be chosen so that it does not have as prime factors all the distinct prime factors of n+1. The first time this rule is required is when determining a(15); see the examples below.
For the terms studied the primes appear in their natural order except for 11 and 13 which are reversed. The sequence is conjectured to be a permutation of the positive integers.
Observation: apart from a(4) = 2, a(9) = 3, and a(33) = 11, prime a(n) is such that n is congruent to +- 2 (mod 12). - Michael De Vlieger, Oct 29 2023

			a(4) = 2 as 2 does not equal 4, shares the factor 2 with 4 while not sharing a factor with a(3) = 9.
a(15) = 25 as 25 does not equal 15, shares the factor 5 with 15 while not sharing a factor with a(14) = 7. Note that 6 is unused and satisfies these requirements but as 15 + 1 = 16 = 2^4 only contains 2 as a distinct prime factor, a(15) cannot also contain 2 as a factor else a(16) would not exist.

Scott R. Shannon, Table of n, a(n) for n = 1..10000
Michael De Vlieger, Log log scatterplot of a(n), n = 1..2^12, showing primes in red, composite prime powers in gold, squarefree composites in green, and numbers neither squarefree nor prime powers in blue, with numbers in the last category that are squareful in light blue.
Michael De Vlieger, List of a(n), n = 1..576, read left to right in 24 rows of 24 terms each, demonstrating the confinement of most prime a(n) to n congruent to +/- 2 (mod 12). Primes appear in red, following the color convention established immediately above.
Scott R. Shannon, Image of the first 100000 terms. The green line is a(n) = n.

Cf. A159193, A093714, A085229, A119018, A000027.

nn = 1000;
  c[] := False; m[] := 1;
  f[x_] := f[x] = Times @@ FactorInteger[x][[All, 1]];
  a[1] = 1; j = a[2] = 4; c[1] = c[4] = True; u = 2;
  Do[k = u;
    If[PrimePowerQ[n], p = FactorInteger[n][[1, 1]]; k = m[p];
     While[
      Or[c[#], ! CoprimeQ[j, #], Divisible[#, f[n + 1]], # == n] &[k p],
       k++]; k *= p; While[c[p m[p]], m[p]++],
    While[
      Or[c[k], ! CoprimeQ[j, k], CoprimeQ[k, n], Divisible[k, f[n + 1]],
        k == n], k++] ];
    Set[{a[n], c[k], j}, {k, True, k}];
    If[k == u, While[c[u], u++]], {n, 3, nn}];
Array[a, nn] (* Michael De Vlieger, Oct 29 2023 *)

A366952 a(1) = 1, a(2) = 4; for n > 2, a(n) is the smallest positive number that has not yet appeared that shares a factor with n but does not equal n, and shares a factor with a(n-1).

Original entry on oeis.org

1, 4, 6, 2, 10, 8, 14, 12, 3, 15, 33, 9, 39, 18, 20, 22, 34, 16, 38, 24, 27, 30, 46, 26, 40, 28, 21, 7, 203, 35, 155, 50, 36, 32, 42, 44, 74, 48, 45, 5, 205, 60, 86, 52, 54, 56, 94, 58, 70, 25, 75, 65, 265, 80, 66, 62, 72, 64, 118, 68, 122, 76, 57, 78, 13, 104, 134, 82, 84, 49, 497, 63, 219

Offset: 1

Scott R. Shannon, Oct 29 2023

nonn

The sequence is conjectured to be a permutation of the positive integers, although the primes typically take many terms to appear, e.g., a(95890) = 223. When a prime does appear it is often followed by a term that is significantly larger than the average-sized term. See the examples below. The primes do not occur in their natural order.

			a(3) = 6 as 6 does not equal 3, shares the factor 3 with 3 while sharing the factor 2 with a(2) = 4.
a(29) = 203 as 203 does not equal 29, shares the factor 29 with 29 while sharing the factor 7 with a(28) = 7. This is an example of both n and a(n-1) being primes which forces a(n) to be significantly larger than the average-sized term.

Scott R. Shannon, Table of n, a(n) for n = 1..10000
Scott R. Shannon, Image of the first 100000 terms with a(n) < 300000. The green line is a(n) = n.

Cf. A366908, A159193, A093714, A085229, A119018, A000027.

A352849 a(n) is the least k not already in the sequence such that k is pairwise coprime to a(n-1) and a(n-2), starting with a(1) = 1, a(2) = 3, and a(3) = 5.

Original entry on oeis.org

1, 3, 5, 2, 7, 9, 4, 11, 13, 6, 17, 19, 8, 15, 23, 14, 25, 27, 16, 29, 21, 10, 31, 33, 20, 37, 39, 22, 35, 41, 12, 43, 47, 18, 49, 53, 24, 55, 59, 26, 45, 61, 28, 51, 65, 32, 57, 67, 34, 63, 71, 38, 69, 73, 40, 77, 79, 30, 83, 89, 36, 85, 91, 44, 75, 97, 46, 81

Offset: 1

Michael De Vlieger, Apr 14 2022

nonn

Sequence begins with 1 and the first 2 odd primes.
a(3k+1) is even for k > 0 as consequence of definition and since 2 is the smallest prime and numbers are either even or odd. Unlike A085229, even numbers in this sequence do not appear in order. Hence a(3k) and a(3k+2) are odd.
The smallest missing number u is even, and there is a smallest missing odd number v that applies to a(3k) and a(3k+2).
Let q be odd and prime. In a given interval i <= n <= j, we either have 2q | a(n) or we have q | a(n) odd.
Regarding 6 | a(n), there are phases i <= n <= j where 6 | a(3k+1) and no a(n) mod 6 = 3 appear. These begin when 3 | a(3k+1) and prevent the entry of 3 | v. Whereupon all u such that 6 | u have been consumed, 3 | a(3k+r), r != 1 occurs, and we move into a phase where we have a(n) mod 6 = 3, but no 6 | a(3k+1) appear. This occurs until all v such that 3 | v have been consumed, and 3 | a(3k+1) once again.
Conjecture: the sequence is a permutation of the natural numbers.

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Michael De Vlieger, Annotated log-log scatterplot of a(n), n = 1..2^12, showing odd numbers congruent to 1 or 5 (mod 6) in green, odd numbers congruent to 3 (mod 6) in blue, even numbers congruent to 2 or 4 (mod 6) in red, and numbers divisible by 6 in amber.

Cf. A085229, A352950.

ina := proc(n) false end: # adapted from code for A352950
a := proc (n) option remember; local k;
if n < 4 then k := 2*n-1
else for k from 2 while ina(k) or igcd(k, a(n-1)) <> 1 or igcd(k, a(n-2)) <>1
do
end do
end if; ina(k):= true; k
end proc:
seq(a(n), n = 1 .. 100); # -David James Sycamore, Apr 17 2022

nn = 66, c[_] = 0; Array[Set[{a[#1], c[#2]}, {#2, #1}] & @@ {#, 2 # - 1} &, 3]; u = 2; Do[k = u; m = LCM @@ Array[a[i - #] &, 2]; While[Nand[c[k] == 0, CoprimeQ[m, k]], k++]; Set[{a[i], c[k]}, {k, i}]; If[a[i] == u, While[c[u] > 0, u++]], {i, 4, nn}]; Array[a, nn]

from math import gcd
from itertools import islice
def agen(): # generator of terms
    aset, b, c = {1, 3, 5}, 3, 5
    yield from [1, b, c]
    while True:
        k = 1
        while k in aset or any(gcd(t, k) != 1 for t in [b, c]): k+= 1
        b, c = c, k
        aset.add(k)
        yield k
print(list(islice(agen(), 68))) # Michael S. Branicky, Apr 14 2022

A353905 a(1) = 1; for n > 1, a(n) = smallest positive number that has not appeared that has a common factor with a(n-1) + the smallest unseen positive number.

Original entry on oeis.org

1, 3, 5, 7, 6, 2, 4, 8, 17, 10, 19, 12, 9, 14, 15, 13, 16, 18, 29, 20, 31, 21, 22, 11, 24, 47, 25, 26, 28, 27, 30, 53, 32, 33, 34, 36, 59, 38, 61, 35, 40, 39, 42, 45, 44, 67, 46, 23, 48, 50, 51, 52, 89, 49, 43, 54, 56, 57, 58, 55, 60, 97, 62, 63, 64, 101, 66, 103, 65, 68, 69, 70, 107, 72, 109

Offset: 1

Scott R. Shannon, May 10 2022

nonn

The sequence is conjectured to be a permutation of the positive integers. In the first 100000 terms the number 18869 holds the record for the greatest number of terms for which it is the lowest unseen number, 4769 terms in all. In the same range there are fifteen fixed points, the last being a(1204), and it is likely no more exist.

			a(2) = 3 as a(1) = 1, the smallest unseen positive number is 2, and 1 + 2 = 3, and 3 is the smallest number that has not yet appeared that shares a factor with 3.
a(5) = 6 as a(4) = 7, the smallest unseen positive number is 2, and 7 + 2 = 9, and 6 is the smallest number that has not yet appeared that shares a factor with 9.

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Michael De Vlieger, Annotated log-log scatterplot of a(n), n = 1..2^14, showing records in red and local minima in blue. Primes and fixed points are highlighted in green and gold, respectively.
Scott R. Shannon, Image of the first 100000 terms. The green line is y = n.

Cf. A337136, A089088, A064413, A085229, A093714.

nn = 120; a[1] = c[1] = 1; u = 2; Do[k = u; While[Nand[c[k] == 0, ! CoprimeQ[#, k]], k++] &[a[i - 1] + u]; Set[{a[i], c[k]}, {k, i}]; If[k == u, While[c[u] > 0, u++]], {i, 2, nn}]; Array[a, nn] (* Michael De Vlieger, May 15 2022 *)

A366909 Lexicographically earliest infinite sequence of distinct positive integers such that, for n > 2, a(n) shares a factor with a(n-1) but not with n.

Original entry on oeis.org

1, 5, 10, 15, 21, 35, 20, 25, 55, 33, 30, 65, 40, 85, 17, 51, 39, 13, 26, 91, 52, 117, 42, 7, 14, 49, 70, 45, 57, 19, 38, 95, 50, 75, 66, 11, 22, 77, 28, 63, 60, 115, 23, 69, 161, 105, 56, 119, 34, 187, 44, 99, 78, 143, 104, 169, 130, 125, 110, 121, 88, 165, 80, 135, 84, 133, 76, 171, 152, 209

Offset: 1

Scott R. Shannon, Oct 27 2023

nonn

To ensure the sequence is infinite a(n) must be chosen so that it has at least one distinct prime factor that is not a factor of n+1. The first time this rule is required is when determining a(5); see the examples below. It also does not allow a(2) to equal 3 as that would then share its only prime factor with n = 3. As 2 and 4 share a factor with n = 2, this leaves a(2) = 5 as the first valid value.
One can easily show that no 3-smooth number, see A003586, can be a term; these are all blocked by the requirement that a(n) shares no factor with n, else are blocked as such a choice would violate this condition when choosing a(n+1).
For the terms studied beyond the prime a(855) = 277 all subsequent primes appear in their natural order. The earlier primes 7, 11, 13, 17, 19, 197, 199, 211, 223, 277, 281 are either out of order or reversed. The behavior of prime ordering for larger values of n is unknown.

			a(4) = 15 as 15 does not share a factor with 4 while sharing the factor 5 with a(3) = 10.
a(5) = 21 as 21 does not share a factor with 5 while sharing the factor 3 with a(4) = 15. Note that 3 is unused and satisfies these requirements but as 5 + 1 = 6 = 2*3 contains 3 as a prime factor, a(5) cannot contain 3 as its only distinct prime factor else a(6) would not exist. Likewise a(5) cannot equal 6, 9, 12 or 18.

Scott R. Shannon, Table of n, a(n) for n = 1..10000
Scott R. Shannon, Image of the first 100000 terms. The green line is a(n) = n.

Cf. A366952, A366908, A003586, A159193, A093714, A085229, A119018, A000027.

cp's OEIS Frontend

A085230 Inverse of A085229.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A093714 a(n) = smallest number coprime to a(n-1), not equal to a(n-1)+1, and not occurring earlier; a(1)=1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

A352950 Lexicographically earliest infinite sequence of distinct nonnegative integers commencing 1,3,5,7 such that any four consecutive terms are pairwise coprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

A366908 Lexicographically earliest infinite sequence of distinct positive integers such that, for n > 1, a(n) shares a factor with n but does not equal n, while not sharing a factor with a(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A366952 a(1) = 1, a(2) = 4; for n > 2, a(n) is the smallest positive number that has not yet appeared that shares a factor with n but does not equal n, and shares a factor with a(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A352849 a(n) is the least k not already in the sequence such that k is pairwise coprime to a(n-1) and a(n-2), starting with a(1) = 1, a(2) = 3, and a(3) = 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

A353905 a(1) = 1; for n > 1, a(n) = smallest positive number that has not appeared that has a common factor with a(n-1) + the smallest unseen positive number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A366909 Lexicographically earliest infinite sequence of distinct positive integers such that, for n > 2, a(n) shares a factor with a(n-1) but not with n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs