cp's OEIS Frontend

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.

%I A280866 #46 May 08 2024 17:32:35
%S A280866 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,
%T A280866 45,19,38,32,23,46,36,27,25,35,42,48,29,58,40,50,31,62,44,33,39,52,54,
%U A280866 51,68,56,49,37,74,60,75,41,82,64,43,86,66,99,47,94,70
%N 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.
%C A280866 In other words, each multiple of a prime p has at least one neighbor that is also a multiple of p.
%C A280866 This sequence is similar to A280864; the first difference oocurs at n=42: a(42)=50 whereas A280864(42)=55.
%C A280866 Conjectured to be a permutation of the natural numbers.
%C A280866 Comment from _N. J. A. Sloane_, Jan 14 2017, with minor edits May 08 2024: (Start)
%C A280866 Theorem: This is a permutation of the natural numbers.
%C A280866 Proof. 1. By definition no term is repeated.
%C A280866 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).)
%C A280866 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.)
%C A280866 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.
%C A280866 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.
%C A280866 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.)
%C A280866 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
%C A280866 (End)
%C A280866 The second occurrence of two consecutive primes is at n = 1324 .. 1325: a(1324) = 691, a(1325) = 701. - _Antti Karttunen_, May 18 2018
%C A280866 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
%H A280866 Rémy Sigrist, <a href="/A280866/b280866.txt">Table of n, a(n) for n = 1..10000</a>
%H A280866 Michael De Vlieger, <a href="/A280866/a280866.png">Log log scatterplot of a(n)</a>, n = 1..2^20.
%H A280866 Michael De Vlieger, <a href="/A280866/a280866_1.png">Log log scatterplot of a(n)</a>, 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.
%H A280866 Rémy Sigrist, <a href="/A280866/a280866.gp.txt">PARI program for A280866</a>
%H A280866 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e A280866 The first terms, alongside their required prime factors are:
%e A280866 n   a(n)  Required
%e A280866 --  ----  --------
%e A280866 1      1  none
%e A280866 2      2  none
%e A280866 3      4  2
%e A280866 4      3  none
%e A280866 5      6  3
%e A280866 6      8  2
%e A280866 7      5  none
%e A280866 8     10  5
%e A280866 9     12  2
%e A280866 10     9  3
%e A280866 11     7  none
%e A280866 12    14  7
%e A280866 13    16  2
%e A280866 14    11  none
%e A280866 15    22  11
%e A280866 16    18  2
%e A280866 17    15  3
%e A280866 18    20  5
%e A280866 19    24  2
%e A280866 20    21  3
%e A280866 21    28  7
%e A280866 22    26  2
%e A280866 23    13  13
%e A280866 24    17  none
%e A280866 25    34  17
%e A280866 26    30  2
%e A280866 27    45  3, 5
%e A280866 28    19  none
%e A280866 29    38  19
%e A280866 30    32  2
%e A280866 31    23  none
%e A280866 32    46  23
%e A280866 33    36  2
%e A280866 34    27  3
%e A280866 35    25  none
%e A280866 36    35  5
%e A280866 37    42  7
%e A280866 38    48  2, 3
%e A280866 39    29  none
%e A280866 40    58  29
%e A280866 41    40  2
%e A280866 42    50  5
%t A280866 nn = 1000;
%t A280866 c[_] := False; m[_] := 1;
%t A280866 a[1] = i = 1; a[2] = j = m[1] = m[2] = 2; c[1] = c[2] = True;
%t A280866 f[x_] := f[x] = Times @@ FactorInteger[x][[All, 1]];
%t A280866 Do[While[c[Set[k, #  m[#]]], m[#]++] &[f[i  j]/f[i]];
%t A280866  Set[{a[n], c[k], i, j}, {k, True, j, k}], {n, 3, nn}];
%t A280866 Array[a, nn] (* _Michael De Vlieger_, Jan 27 2024 *)
%o A280866 (PARI)
%o A280866 \\ After _Rémy Sigrist_'s original PARI-program given in Links section:
%o A280866 up_to = (2^14);
%o A280866 A007947(n) = factorback(factorint(n)[, 1]);
%o A280866 v280866 = vector(up_to);
%o A280866 m304741 = Map(); k=0; prevprev = prev = 1;
%o A280866 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));
%o A280866 A280866(n) = v280866[n];
%o A280866 A304741(n) = mapget(m304741,n); \\ _Antti Karttunen_, May 18 2018
%Y A280866 Cf. A280864.
%Y A280866 Cf. A304741 (inverse permutation), A304742, A304743.
%Y A280866 Cf. A007947.
%K A280866 nonn
%O A280866 1,2
%A A280866 _Rémy Sigrist_, Jan 09 2017