A282291 Lexicographically earliest sequence of distinct terms such that every pair of consecutive terms contains a term that is a unitary divisor of the other term.

1, 2, 6, 3, 12, 4, 20, 5, 10, 30, 15, 60, 420, 7, 14, 42, 21, 84, 28, 140, 35, 70, 210, 105, 840, 8, 24, 120, 40, 280, 56, 168, 1848, 11, 22, 66, 33, 132, 44, 220, 55, 110, 330, 165, 660, 4620, 77, 154, 462, 231, 924, 308, 1540, 385, 770, 2310, 1155, 9240, 88

Offset: 1

Author

Rémy Sigrist, Feb 11 2017

Keywords

• nonn

Comments

This sequence has connections with A113552 and A281978: each pair of consecutive terms contains a term that divides the other term.

The derived sequence A282304 gives some insights about the fractal nature of this sequence.

Conjectures:

- All prime numbers appear in this sequence, in increasing order,

- the derived sequence A282304 is unbounded,

- this sequence is a permutation of the natural numbers.

From Antti Karttunen, May 17 2018: (Start)

The greedy algorithm which constructs this sequence can be understood also in terms of Heinz encodings of partitions (see A215366): Any term a(n) corresponds to a particular integer partition {s1+...+sk} via mapping a(n) = prime(s1)*...*prime(sk), where s1 .. sk are the summands of an integer partition. The choices for constructing the next partition are: either remove some parts from the partition, but with the constraint that if any summand k is removed, then all copies of k present in partition must be removed in too. One may remove all copies of several distinct summands as well. If by such a removal of parts we can find any smaller partitions that have not yet occurred in the sequence, then we choose the one which has the smallest Heinz encoding value to be a(n+1). On the other hand, if all partitions obtained by such removals have already occurred in the sequence, one must then add one or more parts to the current partition, but with the constraint that one is allowed to use only summands that do not already occur in partition (but any number of such summands may be used, also of more than one kind, as long as such summands are not already present in the partition that corresponds to a(n)). Of all such valid new partitions not already encountered, one with the smallest Heinz encoding value is chosen to be a(n+1). Compare this to the rules given for similar A304531 and A303751.

Primes 2 .. 61 occur at: 2, 4, 8, 14, 34, 96, 193, 386, 770, 1538, 3074, 14647, 30533, 60824, 122349, 245225, 688293, 1535694.

Terms just before primes are: 1, 6, 20, 420, 1848, 6552, 556920, 1511640, 6953544, 11090902680, 26447537160, 444799488600, 411767273946600, 1361999444592600, 448097817270965400, 2159016755941924200, 768250528363503385200, 3827047701385526108400.

Primorials (A002110) occur at: 1, 2, 3, 10, 23, 56, 151, 343, 728, 1497, 3034, 6107, 20753, 51285, 112674, 235085, 655721, 1525973, 3151033, ...

Powers of 2: 2 .. 32 occur at: 2, 6, 26, 6531, 1210614, and immediately following terms are: 6, 20, 24, 48, 96.

Immediately preceding terms are: 1, 12, 840, 1163962800, 1479723952477818247200. After 1 these factor as: (2^2 * 3^1), (2^3 * 3^1 * 5^1 * 7^1), (2^4 * 3^2 * 5^2 * 7^1 * 11^1 * 13^1 * 17^1 * 19^1), (2^5 * 3^2 * 5^2 * 7^2 * 11^1 * 13^1 * 17^1 * 19^1 * 23^1 * 29^1 * 31^1 * 41^1 * 43^1 * 47^1 * 53^1).

Observed recurrences: From n>=4 and k>=2 onward, there is a following general pattern:

For n = x .. x+(y-1), a(n) = prime(1+k)*a(n-(x-1)),

where y is the k-th record in A282304, and x is the position of that record in A282304, starting from the k = 2nd record in that sequence:

For n = 8 .. 8+4, a(n) = 5*a(n-7).

For n = 14 .. 14+10, a(n) = 7*a(n-13).

For n = 34 .. 34+30, a(n) = 11*a(n-33).

For n = 96 .. 96+89, a(n) = 13*a(n-95).

For n = 193 .. 193+184, a(n) = 17*a(n-192).

For n = 386 .. 386+382, a(n) = 19*a(n-385).

For n = 770 .. 770+766, a(n) = 23*a(n-769).

For n = 1538 .. 1538+1534, a(n) = 29*a(n-1537).

For n = 3074 .. 3074+3070, a(n) = 31*a(n-3073).

For n = 14647 .. 14647+11104, a(n) = 37*a(n-14646).

For n = 30533 .. 30533+29454, a(n) = 41*a(n-30532).

For n = 60824 .. 60824+30061, a(n) = 43*a(n-60823).

For n = 122349 .. 122349+91330, a(n) = 47*a(n-122348).

For n = 245225 .. 245225+121950, a(n) = 53*a(n-245224).

For n = 688293 .. 688293+367237, a(n) = 59*a(n-688292).

For n = 1535694 .. 1535694+596154, a(n) = 61*a(n-1535693).

Note how this forces values like prime powers to gaps between. E.g. 49 = a(367278) occurs 103 steps after the subsection a(n) = 53*a(n-245224) has ended at 245225+121950 (= 367175), but before the next regular subsection a(n) = 59*a(n-688292) starts at 688293.

(End)

Examples

			The first terms, alongside their p-adic valuations with respect to p=2, 3, 5 and 7 (with 0's omitted), are:
n  a(n)  v2 v3 v5 v7
-- ----  -- -- -- --
1     1
2     2   1
3     6   1  1
4     3      1
5    12   2  1
6     4   2
7    20   2     1
8     5         1
9    10   1     1
10   30   1  1  1
11   15      1  1
12   60   2  1  1
13  420   2  1  1  1
14    7            1
15   14   1        1
16   42   1  1     1
17   21      1     1
18   84   2  1     1
19   28   2        1
20  140   2     1  1
21   35         1  1
22   70   1     1  1
23  210   1  1  1  1
24  105      1  1  1
25  840   3  1  1  1
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000
• Rémy Sigrist, Logarithmic scatterplot of the first 250000 terms (the two blue sections are equal up to a scaling factor of 47)
• Rémy Sigrist, PARI program for A282291

Crossrefs

Cf. A113552, A281978, A282304, A304531, A302853, A304099.

Cf. A304097, A304098 (see the scatter plots for alternative perspectives).

Cf. A304090 (inverse).

Programs

Mathematica

a = {1}; Do[k = 1; While[Or[MemberQ[a, k], Nand[Divisible[#2, #1], CoprimeQ[#1, #2/#1]]] & @@ Sort@ # &@{k, Last@ a}, k++]; AppendTo[a, k], {n, 58}]; a (* Michael De Vlieger, Feb 12 2017 *)

PARI

up_to = 2^23;
v282291 = vector(up_to);
m304090 = Map();
prev=1; for(n=1,up_to,fordiv(prev,d,if(!mapisdefined(m304090,d) && (1==gcd(d, prev/d)),v282291[n] = d;mapput(m304090,d,n);break)); if(!v282291[n], m = 2; try = m*prev; while(mapisdefined(m304090,try) || (gcd(prev, try/prev)!=1), m++; try = m*prev); v282291[n] = try; mapput(m304090,try,n)); prev = v282291[n]);
A282291(n) = v282291[n];
A304090(n) = mapget(m304090,n); \\ Antti Karttunen, May 17 2018

Formula

For all n >= 1, A052331(a(n)) = A302853(n-1), A001222(a(n)) = A304099(n). - Antti Karttunen, May 17 2018