A280866 Lexicographically earliest sequence of distinct terms such that, for any prime p, any run of consecutive multiples of p has at least length 2.

1, 2, 4, 3, 6, 8, 5, 10, 12, 9, 7, 14, 16, 11, 22, 18, 15, 20, 24, 21, 28, 26, 13, 17, 34, 30, 45, 19, 38, 32, 23, 46, 36, 27, 25, 35, 42, 48, 29, 58, 40, 50, 31, 62, 44, 33, 39, 52, 54, 51, 68, 56, 49, 37, 74, 60, 75, 41, 82, 64, 43, 86, 66, 99, 47, 94, 70

Offset: 1

Author

Rémy Sigrist, Jan 09 2017

Keywords

• nonn

Comments

In other words, each multiple of a prime p has at least one neighbor that is also a multiple of p.

This sequence is similar to A280864; the first difference oocurs at n=42: a(42)=50 whereas A280864(42)=55.

Conjectured to be a permutation of the natural numbers.

Comment from N. J. A. Sloane, Jan 14 2017, with minor edits May 08 2024: (Start)

Theorem: This is a permutation of the natural numbers.

Proof. 1. By definition no term is repeated.

2. The sequence is clearly infinite, since we can always use a very large prime G to build the next term. (G*a(n) is always a candidate for a(n+1).)

3. So for any integer m, either it appears in the sequence, or there is an n_0 such that for n > n_0, a(n) > m. (Let w(m) = index where m appears, or -1 if m does not appear. Let W(m) = max{w(i): 1 <= i <= m}. Then for n > W(m), a(n) > m.)

4. For any prime p, there is a term a(n) that is divisible by p. For if not, no prime greater than p can appear either, or we could have used p instead. This would mean all terms are products of the primes less than p. Go out a long way in the sequence until the terms exceed p!. Then one of the finite set of numbers p times {a possibly empty product of distinct primes less than p} will be a smaller candidate for the next term. So p will appear. Contradiction.

5. Call a(n) free if all its prime factors already appeared in a(n-1). If a(n) is free then there are no constraints on a(n+1) and so a(n+1) will be the smallest number not yet in the sequence.

6. For a prime p, let a(n) be the first term divisible by p. Either a(n) = k*p, where k is a product of the distinct primes needed to link a(n) to a(n-1), in which case a(n+1) = p and is free; or else a(n) = p, in which case a(n-1) was free. So in either case there is a free term associated with the prime p. (Except if there are two consecutive primes, like 13 and 17, when we only get one free term, not two. We will ignore this complication! There cannot be three consecutive primes.)

7. Since there are infinitely many primes, the sequence contains infinitely many free terms, and so every number will eventually appear. For suppose k never appears. Consider the first free term a(n) > k. Then a(n+1) = k, a contradiction. QED

(End)

The second occurrence of two consecutive primes is at n = 1324 .. 1325: a(1324) = 691, a(1325) = 701. - Antti Karttunen, May 18 2018

Alternative definition: a(1,2) = 1,2 then for n > 2 a(n) is the least novel multiple of rad(a(n-2)*a(n-1))/rad(a(n-2)), where rad is A007947. - David James Sycamore, Jan 27 2024

Examples

			The first terms, alongside their required prime factors are:
n   a(n)  Required
--  ----  --------
1      1  none
2      2  none
3      4  2
4      3  none
5      6  3
6      8  2
7      5  none
8     10  5
9     12  2
10     9  3
11     7  none
12    14  7
13    16  2
14    11  none
15    22  11
16    18  2
17    15  3
18    20  5
19    24  2
20    21  3
21    28  7
22    26  2
23    13  13
24    17  none
25    34  17
26    30  2
27    45  3, 5
28    19  none
29    38  19
30    32  2
31    23  none
32    46  23
33    36  2
34    27  3
35    25  none
36    35  5
37    42  7
38    48  2, 3
39    29  none
40    58  29
41    40  2
42    50  5
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000
• Michael De Vlieger, Log log scatterplot of a(n), n = 1..2^20.
• Michael De Vlieger, Log log scatterplot of a(n), n = 1..1024, showing primes in red, composite prime powers in gold, squarefree composites in greens, and numbers neither squarefree nor prime powers in blue and purple, with the latter pertaining to squareful numbers.
• Rémy Sigrist, PARI program for A280866
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A280864.

Cf. A304741 (inverse permutation), A304742, A304743.

Cf. A007947.

Programs

Mathematica

nn = 1000;
c[] := False; m[] := 1;
a[1] = i = 1; a[2] = j = m[1] = m[2] = 2; c[1] = c[2] = True;
f[x_] := f[x] = Times @@ FactorInteger[x][[All, 1]];
Do[While[c[Set[k, #  m[#]]], m[#]++] &[f[i  j]/f[i]];
 Set[{a[n], c[k], i, j}, {k, True, j, k}], {n, 3, nn}];
Array[a, nn] (* Michael De Vlieger, Jan 27 2024 *)

PARI

\\ After Rémy Sigrist's original PARI-program given in Links section:
up_to = (2^14);
A007947(n) = factorback(factorint(n)[, 1]);
v280866 = vector(up_to);
m304741 = Map(); k=0; prevprev = prev = 1;
for(n=1,up_to, m = A007947(prev)/A007947(gcd(prev,prevprev)); try = m; while(mapisdefined(m304741,try), try += m); prevprev = prev; prev = try; mapput(m304741,v280866[n] = try,n));
A280866(n) = v280866[n];
A304741(n) = mapget(m304741,n); \\ Antti Karttunen, May 18 2018