login
A370843
Lexicographically earliest sequence of distinct positive integers such that for any n > 1, a(n) is neither coprime to a(2*n) nor to a(2*n+1).
4
1, 2, 3, 4, 6, 9, 12, 8, 10, 14, 15, 18, 21, 16, 20, 22, 24, 5, 25, 7, 26, 27, 30, 28, 32, 33, 35, 34, 36, 38, 40, 11, 42, 39, 44, 45, 50, 55, 60, 49, 56, 13, 46, 48, 51, 52, 54, 58, 62, 64, 66, 57, 63, 65, 70, 17, 68, 69, 72, 19, 74, 75, 76
OFFSET
1,2
COMMENTS
This sequence can be seen as an infinite complete binary tree where each node (except the root node) shares a prime factor with its two children:
|
._______1_______.
| |
.___2___. .___3___.
| | | |
._4_. ._6_. ._9_. .12_.
| | | | | | | |
8 10 14 15 18 21 16 20
This sequence combines features of the EKG sequence (A064413) (as each term beyond a(3) shares a prime factor with some prior term) and of A291603 (as each term constrains two child terms).
This sequence is a permutation of the positive integers (with inverse A370868):
- for any pair of prime numbers p, q such that 3 < p < q, if the sequence contains a multiple of q then it must contain a multiple of p (for if a(n) = m*q is the first multiple of q, then a(n) = m*p would have been a better choice),
- for any prime number p > 3, if a(n) is the first multiple of p, then a(2*n) = p,
- every prime number appear in the sequence: if p is the greatest prime number in the sequence, then all terms are p-smooth, and we have infinitely many multiples of some prime number q <= p, as eventually all multiples of q must appear in the sequence, and some of them are not p-smooth, this leads to a contradiction,
- for any prime number p, 2*p appears in the sequence (either as the parent of p or as a child of p),
- as we have infinitely many even terms, all even numbers eventually appear in the sequence,
- for any v > 1, we have infinitely many even numbers sharing a prime factor with v, so v must eventually appear.
EXAMPLE
a(1), a(2) and a(3) have no special constraints; we take a(1) = 1, a(2) = 2, a(3) = 3.
a(4) must share a factor with a(2) = 2; we take a(4) = 4.
a(5) must share a factor with a(2) = 2; we take a(5) = 6.
a(6) must share a factor with a(3) = 3; we take a(6) = 9.
etc.
PROG
(PARI) See Links section.
CROSSREFS
Cf. A064413, A291603, A370868 (inverse).
Sequence in context: A371839 A338914 A048249 * A377151 A288734 A332034
KEYWORD
nonn
AUTHOR
Rémy Sigrist, Mar 03 2024
STATUS
approved