login
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.
12
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,2
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
LINKS
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.
EXAMPLE
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
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 *)
PROG
(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
CROSSREFS
Cf. A280864.
Cf. A304741 (inverse permutation), A304742, A304743.
Cf. A007947.
Sequence in context: A265667 A338743 A358267 * A280864 A364884 A369825
KEYWORD
nonn
AUTHOR
Rémy Sigrist, Jan 09 2017
STATUS
approved