A113552 -id:A113552 - cp's OEIS frontend

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

Rémy Sigrist, Feb 11 2017

nonn

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)

			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

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

Cf. A113552, A281978, A282304, A304531, A302853, A304099.
Cf. A304097, A304098 (see the scatter plots for alternative perspectives).
Cf. A304090 (inverse).

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 *)

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

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

A304531 Suspected divisor-or-multiple permutation: a(1) = 1, and for n > 1, a(n) is either the least unitary divisor of a(n-1) not already present, or (if all unitary divisors already used), a(n) = a(n-1) * {the least power of the least prime not dividing a(n-1) such that the term is not already present}.

Original entry on oeis.org

1, 2, 6, 3, 12, 4, 36, 9, 18, 90, 5, 10, 30, 15, 60, 20, 180, 45, 360, 8, 24, 120, 40, 1080, 27, 54, 270, 135, 540, 108, 2700, 25, 50, 150, 75, 300, 100, 900, 225, 450, 3150, 7, 14, 42, 21, 84, 28, 252, 63, 126, 630, 35, 70, 210, 105, 420, 140, 1260, 315, 2520, 56, 168, 840, 280, 7560, 189, 378, 1890, 945, 3780, 756, 18900, 175, 350, 1050, 525, 2100, 700

Offset: 1

Antti Karttunen, May 14 2018

nonn

The greedy algorithm which constructs the sequence is easiest to grasp in terms of Heinz encodings of partitions (see A215366): Any term a(n) corresponds to a particular integer partition. The choices for constructing the next partition are: either remove some parts from the partition, but with the condition that if any summand k is removed, then all copies of k present in partition must be removed in toto. 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. On the other hand, if all partitions obtained by such removals have already occurred in the sequence, then one adds to the current partition the least number of copies of the least positive integer that is not yet a part of the partition (see A257993), until a partition is found which is not yet in the sequence. This process also implies that one never removes the summand(s) that was/were just added in the previous step.
It has not yet been rigorously proved that all partitions can be reached this way, i.e., that this sequence is a permutation of natural numbers.
Each a(n+1) is always either a divisor or a multiple of a(n).
No two successive descending terms, that is, a(n) > a(n+1) > a(n+2) never occurs.
For n > 1, if a(n) is odd then a(n-1) = 2^h * k * a(n) and a(n+1) = 2^j * a(n) for some h, k and j, that is, odd terms occur between two larger even numbers.
If a(n) < a(n+1) then (a(n+1) / a(n)) is a divisor of a(n+2). This follows because clearly (in case A) when a(n) < a(n+1) < a(n+2) then (a(n+1) / a(n)) is a divisor of a(n+2) because on ascending subsections each successive term is obtained by multiplying by some prime (or its power) not already present. But it is also true (in case B) when a(n) < a(n+1) > a(n+2), as:
In contrast to A303751, this permutation is specified with an additional constraint that gcd(a(n+1), a(n)/a(n+1)) = 1, whenever a(n) > a(n+1). From this then follows that also when a(n) < a(n+1) > a(n+2) then (a(n+1) / a(n)) is guaranteed to be a divisor of a(n+2). It also follows from this that also the squarefree version A304537(n) = A019565(A052331(a(1+n))) satisfies the divisor-or-multiple property.
Odd numbers occur at A304530.
Primes occur at : 2, 4, 11, 42, 237, 1798, 7192, 69611, 431203, 2401568, ...
Primorials (A002110) occur at: 1, 2, 3, 13, 54, 290, 2087, 11333, 118777, 934737, ...

			a(64) = 280 = 2^3 * 5 * 7 = prime(1)^3 * prime(3) * prime(4), which by Heinz-encoding corresponds to integer partition {1+1+1+3+4}. We try to remove all 1's (to get {3+4}, i.e. prime(3)*prime(4) = 35, but that has already been used as a(52)), or to remove either 3 or 4 or both, but also 8, 40 and 56 have already been used, and if we remove all 1's and either 3 or 4, then also prime(3) and prime(4), 5 and 7 have already been used. So we must add one or more copies of 2 (the least missing part) to find a partition that has not already been used. And it turns out we need to add three copies, to get {1+1+1+2+2+2+3+4} to obtain value prime(1)^3 * prime(2)^3 * prime(3) * prime(4) = 7560 not used before, so a(65) = 7560.
For the next partition, we remove all 1's and the sole 3, to get {2+2+2+4}, with Heinz-encoding prime(2)^3 * prime(4) = 27 * 7 = 189 to obtain the smallest not yet present in sequence, thus a(66) = 189. Note that the partition {1+1+1+2+2} would give even a smaller Heinz-code 2^3 * 3^2 = 72, which also has not been used before, but 72 is not a unitary divisor of 7560, which can be seen from the fact that just one 2 (but not all 2's) was removed from the partition {1+1+1+2+2+2+3+4} that corresponds to 7560. At this point A303751 selects 72 as it has no unitary divisor constraint.

Antti Karttunen, Table of n, a(n) for n = 1..8447
Index entries for sequences that are permutations of the natural numbers

Cf. A304532 (inverse).
Cf. A304530 (positions of odd terms).
Cf. A053669, A215366, A257993, A304533, A304535, A304536, A304537.
Cf. A113552, A282291, A303751 for other variants.
Differs from A303751 for the first time at n=66, where a(66) = 189, while A303751(66) = 72.

up_to = 2^12;
A053669(n) = forprime(p=2, , if (n % p, return(p))); \\ From A053669
v304531 = vector(up_to);
m304532 = Map();
prev=1; for(n=1,up_to,fordiv(prev,d,if(!mapisdefined(m304532,d) && (1==gcd(d, prev/d)),v304531[n] = d;mapput(m304532,d,n);break)); if(!v304531[n], p = A053669(prev); while(mapisdefined(m304532,prev), prev *= p); v304531[n] = prev; mapput(m304532,prev,n)); prev = v304531[n]);
A304531(n) = v304531[n];
A304532(n) = mapget(m304532,n);

Observed patterns:
For n = 2 .. 2+0, a(n) = 2*a(n-1).
For n = 4 .. 4+0, a(n) = 3*a(n-3).
For n = 11 .. 11+7, a(n) = 5*a(n-10).
For n = 42 .. 42+38, a(n) = 7*a(n-41).
For n = 237 .. 237+64, a(n) = 11*a(n-236).
For n = 1798 .. 1798+336, a(n) = 13*a(n-1797).
For n = 7192 .. 7192+1255, a(n) = 17*a(n-7191).
For n = 69611 .. 69611+4820, a(n) = 19*a(n-69610).
For n = 431203 .. 431203+41802, a(n) = 23*a(n-431202).
For n = 2401568 .. 2401568+131366, a(n) = 29*a(n-2401567).
Derived sequences. For all n >= 1:
A052331(a(n)) = A304533(n-1).
A064547(a(n)) = A304536(n-1).

A303751 Suspected divisor-or-multiple permutation: a(1) = 1, and for n > 1, a(n) is either the least divisor of a(n-1) not already present, or (if all divisors already used), a(n) = a(n-1) * {the least power of the least prime not dividing a(n-1) such that the term is not already present}.

Original entry on oeis.org

Offset: 1

Antti Karttunen, May 01 2018

nonn

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: If by removing any parts from the partition we can find any smaller partitions that have not already occurred in the sequence, then we choose the one which has the smallest Heinz encoding value. On the other hand, if all partitions obtained by such removals have already occurred in the sequence, then we add to the current partition the least number of copies of the least positive integer that is not yet a part of the partition (A257993), until a partition is found which is not yet in the sequence.
From Antti Karttunen & David A. Corneth, May 01 - 04 2018: (Start)
No two successive descending terms, that is, a(n) > a(n+1) > a(n+2) never occurs.
For n > 1, if a(n) is odd then a(n-1) = 2^h * k * a(n) and a(n+1) = 2^j * a(n) for some h, k and j, that is, odd terms occur between two larger even numbers.
If a(n) < a(n+1) < a(n+2) then (a(n+1) / a(n)) is a divisor of a(n+2).
However, when a(n) < a(n+1) > a(n+2) then (a(n+1) / a(n)) might not be a divisor of a(n+2). The first such case occurs at n=64..66, as a(64) = 280 = 2^3 * 5 * 7, a(65) = 7560 = 2^3 * 3^3 * 5 * 7, and a(66) = 72 = 2^3 * 3^2. We have 7560/280 = 27, which is not a divisor of 72 (72/27 = 8/3).
In most cases, when a(n+1) < a(n) then gcd(a(n+1), a(n)/a(n+1)) = 1 (about 87% for the first 100000 descents). However, there are many exceptions to this, the first case occurring at a(65) = 7560 = 2^3 * 3^3 * 5 * 7 and a(66) = 72 =  2^3 * 3^2, with gcd(72,7560/72) = 3.
(End)
From David A. Corneth, May 04 2018: (Start)
The sequence can be partitioned into a tabf sequence with rows having the first element odd and the others even. It would give (1, 2, 6), (3, 12, 4, 36), (9, 18, 90), (5, 10, 30), (15, 60, 20, 180), (45, 360, 8, 24, 120, 40, 1080), (27, 54, 270), ...
It turns out that some rows are multiples of others; for example, the row (5, 10, 30) is five times the row (1, 2, 6). (End)
See also "observed scaling patterns" in the Formula section.
A303750 gives the positions of odd terms.
A282291 and A304531 are unitary divisor variants that satisfy the condition gcd(a(n+1), a(n)/a(n+1)) = 1, whenever a(n) > a(n+1).
The primes 2, 3, 5, 7, 11, 13, 19, 23 and 29 occur at positions 2, 4, 11, 42, 176, 1343, 8470, 57949, 302739, 1632898, thus after 7 and except for 13, a little earlier than they occur in variant A304531.

			a(64) = 280 = 2^3 * 5 * 7 = prime(1)^3 * prime(3) * prime(4), which by Heinz-encoding corresponds to integer partition {1+1+1+3+4}. We try to remove all 1's (to get {3+4}, i.e., prime(3)*prime(4) = 35, but that has already been used as a(52)), or to remove either 3 or 4 or both, but also 8, 40 and 56 have already been used, and if we remove all 1's and either 3 or 4, then also prime(3) and prime(4), 5 and 7 have already been used. So we must add one or more copies of 2 (the least missing part) to find a partition that has not already been used. And it turns out we need to add three copies, to get {1+1+1+2+2+2+3+4} to obtain value prime(1)^3 * prime(2)^3 * prime(3) * prime(4) = 7560 not used before, so a(65) = 7560.
For the next partition, we remove two 2's and both 3 and 4, to get {1+1+1+2+2} which gives Heinz-code 2^3 * 3^2 = 72, which is the smallest divisor of 7560 that has not been used before in the sequence, thus a(66) = 72.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences that are permutations of the natural numbers

Cf. A303752 (inverse).
Cf. A053669, A303750.
Cf. A113552, A282291, A304531, A304755 for similarly defined sequences, and also A064736, A207901, A281978, A302350, A302781, A302783, A303771 for other permutations satisfying the divisor-or-multiple property.
Cf. also A303761.
Cf. A304728, A304729 (see their scatter plots for alternative views to this process).
Differs from a variant A304531 for the first time at n = 66, where a(66) = 72, while A304531(66) = 189.

up_to = 2^14;
A053669(n) = forprime(p=2, , if (n % p, return(p))); \\ From A053669
v303751 = vector(up_to);
m303752 = Map();
prev=1; for(n=1,up_to,fordiv(prev,d,if(!mapisdefined(m303752,d),v303751[n] = d;mapput(m303752,d,n);break)); if(!v303751[n], p = A053669(prev); while(mapisdefined(m303752,prev), prev *= p); v303751[n] = prev; mapput(m303752,prev,n)); prev = v303751[n]);
A303751(n) = v303751[n];
A303752(n) = mapget(m303752,n);

Observed scaling patterns:
For n =     2 ..     2 +     0, a(n) =  2*a(n-1).
For n =     4 ..     4 +     0, a(n) =  3*a(n-3).
For n =    11 ..    11 +     7, a(n) =  5*a(n-10).
For n =    42 ..    42 +    23, a(n) =  7*a(n-41).
For n =   176 ..   176 +    80, a(n) = 11*a(n-175).
For n =  1343 ..  1343 +   683, a(n) = 13*a(n-1342).
For n =  8470 ..  8470 +  3610, a(n) = 17*a(n-8469).
For n = 57949 .. 57949 + 18554, a(n) = 19*a(n-57948).

A303771 Divisor-or-multiple permutation of natural numbers, "Fermi-Dirac piano played with May code": a(n) = A052330(A303767(n)).

Original entry on oeis.org

1, 2, 6, 3, 12, 4, 8, 24, 120, 5, 10, 30, 15, 60, 20, 40, 280, 7, 14, 42, 21, 84, 28, 56, 168, 840, 35, 70, 210, 105, 420, 140, 1260, 9, 18, 54, 27, 108, 36, 72, 216, 1080, 45, 90, 270, 135, 540, 180, 360, 2520, 63, 126, 378, 189, 756, 252, 504, 1512, 7560, 315, 630, 1890, 945, 3780, 41580, 11, 22, 66, 33, 132, 44, 88, 264, 1320, 55, 110, 330, 165, 660, 220

Offset: 0

Antti Karttunen, May 02 2018

nonn

Consider A019565. Imagine that it is an automatic piano that "plays sequences" when an appropriate punched "tape" is fed to it (as its input), i.e., when it is composed from the right with an appropriate sequence p, as A019565(p(n)). The 1-bits in the binary expansion of each p(n) are the "holes" in the tape, and they determine which "tunes" are present on beat n. The "tunes" are actually primes that are multiplied together. Of course only "squarefree music" (sequences containing only squarefree numbers, A005117) is possible to generate this way, thus we call A019565 a "squarefree piano".
There is a more sophisticated instrument, called "Fermi-Dirac piano" (A052330), with which it is possible to produce sequences that may contain any numbers.
If the tape is constructed in such a way that between the successive beats (when moving from p(n) to p(n+1)), either a subset of 0-bits are toggled on (changed to 1's), or a subset of 1-bits are toggled off (changed to 0's), but no both kind of changes occur simultaneously, then when fed as an input to either of these pianos, the resulting sequence "s" (the output) is guaranteed to satisfy the condition that s(n+1) is either a multiple or a divisor of s(n). For example, Gray code A003188 and its inverse A006068 are examples of such tapes, and they produce sequences A302033, A207901 and A284003, A302783.
This divisor-or-multiple permutation is obtained by playing "Fermi-Dirac piano" with the same tape which yields A303760 when "squarefree piano" is played with it. Note that A303760 is not a subsequence of this sequence, as its terms occur in different order than the squarefree terms here.
See also Peter Munn's Apr 11 2018 message on SeqFan-mailing list and comments in A304537.

Antti Karttunen, Table of n, a(n) for n = 0..16383
Michel Marcus, Peter Munn, et al., Discussion on SeqFan-list about similar permutations, April 2018
Index entries for sequences that are permutations of the natural numbers

Cf. A303772 (inverse).
Cf. A019565, A048675, A052330, A303760.
Cf. also A064736, A113552, A207901, A281978, A282291, A302350, A302781, A302783, A303751, A304085, A304531 for similar permutations.

default(parisizemax,2^31);
up_to_e = 16;
up_to = (1 + 2^up_to_e);
v050376 = vector(2+up_to_e);
A050376(n) = v050376[n];
ispow2(n) = (n && !bitand(n,n-1));
i = 0; for(n=1,oo,if(ispow2(isprimepower(n)), i++; v050376[i] = n); if(i == 2+up_to_e,break));
A052330(n) = { my(p=1,i=1); while(n>0, if(n%2, p *= A050376(i)); i++; n >>= 1); (p); };
A053669(n) = forprime(p=2, , if (n % p, return(p))); \\ From A053669
v303760 = vector(up_to);
m_inverses = Map();
prev=1; for(n=1,up_to,fordiv(prev,d,if(!mapisdefined(m_inverses,d),v303760[n] = d;mapput(m_inverses,d,n);break)); if(!v303760[n], apu = prev; while(mapisdefined(m_inverses,try = prev*A053669(apu)), apu *= A053669(apu)); v303760[n] = try; mapput(m_inverses,try,n)); prev = v303760[n]);
A303760(n) = v303760[n+1];
A048675(n) = { my(f = factor(n)); sum(k=1, #f~, f[k, 2]*2^primepi(f[k, 1]))/2; };
A303771(n) = A052330(A048675(A303760(n)));

a(n) = A052330(A303767(n)) = A052330(A048675(A303760(n))). [See comments].

Name amended by Antti Karttunen, May 16 2018

A304085 Divisor-or-multiple permutation of natural numbers: a(n) = A052330(A304083(n)).

Original entry on oeis.org

1, 2, 6, 3, 24, 12, 4, 8, 120, 60, 20, 5, 40, 10, 30, 15, 840, 420, 140, 35, 7, 280, 70, 14, 210, 105, 21, 168, 84, 28, 56, 7560, 42, 1890, 945, 315, 63, 9, 3780, 1260, 252, 36, 2520, 630, 126, 18, 1512, 756, 189, 27, 378, 54, 1080, 540, 180, 45, 360, 90, 270, 135, 83160, 504, 72, 216, 108, 41580, 13860, 3465, 693, 99, 11, 27720, 6930, 1386, 198, 22, 20790

Offset: 0

Antti Karttunen, May 06 2018

nonn

Each a(n) is always either a divisor or a multiple of a(n+1).

Antti Karttunen, Table of n, a(n) for n = 0..16383
Index entries for sequences that are permutations of the natural numbers

Cf. A304086 (inverse).
Cf. A304083, A304087.
Cf. also A064736, A113552, A207901, A281978, A282291, A302350, A302781, A302783, A303751, A303771 for similar permutations.

up_to_e = 16; \\ Good for computing up to n = (2^16)-1
v050376 = vector(up_to_e);
ispow2(n) = (n && !bitand(n,n-1));
i = 0; for(n=1,oo,if(ispow2(isprimepower(n)), i++; v050376[i] = n); if(i == up_to_e,break));
A050376(n) = v050376[n];
A052330(n) = { my(p=1,i=1); while(n>0, if(n%2, p *= A050376(i)); i++; n >>= 1); (p); };
A304085(n) = A052330(A304083(n)); \\ Needs also code from A304083

a(n) = A052330(A304083(n)).

A338221 Square spiral of distinct positive integers built by greedy algorithm such that each new value (except the initial one) is a divisor or a multiple of some earlier horizontally or vertically adjacent value.

Original entry on oeis.org

1, 2, 4, 3, 6, 5, 10, 7, 8, 16, 12, 20, 40, 24, 9, 18, 36, 30, 15, 45, 90, 50, 14, 28, 32, 64, 48, 60, 80, 120, 240, 160, 72, 27, 54, 108, 216, 144, 150, 25, 75, 180, 360, 270, 100, 42, 21, 63, 126, 252, 84, 96, 192, 320, 480, 720, 1440, 288, 576, 432, 81, 162

Offset: 0

Rémy Sigrist, Jan 30 2021

This sequence has similarities with A113552 and A282291, as each term is adjacent to one of its divisors or multiples.

			The spiral begins:
      216--108---54---27---72--160--240
        |                             |
      144   36---18----9---24---40  120
        |    |                   |    |
      150   30    6----3----4   20   80
        |    |    |         |    |    |
       25   15    5    1----2   12   60
        |    |    |              |    |
       75   45   10----7----8---16   48
        |    |                        |
      180   90---50---14---28---32---64
        |
      360--270--100---42---21---63--126

Rémy Sigrist, Table of n, a(n) for n = 0..10200
Rémy Sigrist, Colored representation of the spiral for -500 <= x, y <= 500 (where the color is function of a(n))
Rémy Sigrist, Colored representation of the spiral for -500 <= x, y <= 500 (where the color is function of A006530(a(n)))
Rémy Sigrist, PARI program for A338221

Cf. A006530, A113552, A282291.

PARI
```
See Links section.
```

A304752 Beginning with a(1) = 1, for n > 1, a(n) = the least divisor of a(n-1) not included earlier, otherwise a(n) = the least multiple ma(n-1) such that m is not a divisor of a(n-1) and ma(n-1) is not included earlier.

Original entry on oeis.org

1, 2, 6, 3, 12, 4, 20, 5, 10, 30, 15, 60, 420, 7, 14, 42, 21, 84, 28, 140, 35, 70, 210, 105, 630, 9, 18, 72, 8, 24, 120, 40, 240, 16, 48, 336, 56, 168, 840, 280, 1680, 80, 480, 32, 96, 672, 112, 560, 3360, 160, 960, 64, 192, 1344, 224, 1120, 6720, 320, 1920, 128, 384, 2688, 448, 2240, 13440, 640, 3840, 256, 768, 5376, 896, 4480, 26880, 1280, 7680, 512

Offset: 1

Antti Karttunen, Michael De Vlieger, and Robert G. Wilson v, May 19 2018

nonn

This is a variant of A113552.
From Michael De Vlieger, May 20 2018: (Start)
In the table below, we note a cycle that subtends for 41 <= n <= 2^14.
Let e = floor(n/8). We write multiple k if the condition is false, or the parity of divisor d if d does not occur in a. We can express a(n) as the product of the smallest four primes as shown below.
n (mod 8)   k or d     2     3     5     7
-------------------------------------------
   0           5      2^(e-2)       5     7
   1           6      2^(e-1) 3     5     7
   2           EVEN   2^(e-1)       5
   3           6      2^(e-1) 3     5
   4           EVEN   2^e
   5           3      2^e     3
   6           7      2^e     3           7
   7           EVEN   2^(e-1)             7
Conjectures:
1. All terms are divisible only by some combination of the smallest 4 primes.
2. Powers 2^e, positive integer e, are at n = {1, 2, 6, 29, 34, 44, 52, 60, 68, ...}; first differences are {1, 4, 23, 5, 10, 8, 8, 8, ...}, and 8 thereafter.
3. For n > 41 such that n (mod 8) = 4, a(n) = 2^((n-4)/8).
4. For n > 26 all terms are even. Odd terms are {1, 3, 5, 15, 7, 21, 35, 105, 9} at indices {1, 4, 8, 11, 14, 17, 21, 24, 26}. (End)

			After a(27) = 18 = 2 * 3^2, the next term a(28) is neither 2*18 = 2^2 * 3^2, nor 3*18 = 2 * 3^3 as both 2 and divide 18. But 4 does not divide 18, and 4*18 = 72 haven't yet been used in the sequence, thus a(28) = 72.

Antti Karttunen & Michael De Vlieger, Table of n, a(n) for n = 1..16384

Differs from A113552 for the first time at n=28, where a(28) = 72, while A113552(28) = 90.

lim:=60: with(numtheory): membera := proc(val) global a, n: local j: for j from 1 to n-1 do if(a[j]=val)then return true: fi: od: return false: end: a[1]:=1:for n from 2 to lim do d:=sort([divisors(a[n-1])[]]): s:=true: for k from 1 to nops(d) do if(not membera(d[k]))then a[n]:=d[k]:s:=false: break:fi:od: if(s)then for j from 2 do if(not member(j, d) and not membera(j*a[n-1]))then a[n]:=j*a[n-1]:break: fi:od:fi:od: seq(a[n], n=1..lim); # Nathaniel Johnston, May 10 2011, given originally for A113552
# second Maple program:
b:= proc(n) is(n=1) end:
a:= proc(n) option remember; local j, l, i, m;
      j:= a(n-1): l:= sort([numtheory[divisors](j)[]]);
      for i to nops(l) do if not b(l[i])
        then b(l[i]):=true; return l[i]
      fi od;
      for m while m in l or b(m*j) do od;
      b(m*j):=true; m*j
    end: a(1):=1:
seq(a(n), n=1..100);  # Alois P. Heinz, May 22 2018

f[s_] := Append[s, d = Divisors[ s[[ -1]]]; If[ Complement[d, s] != {}, Complement[d, s][[1]], k = 2; While[ Mod[ s[[ -1]], k] == 0 || MemberQ[s, k*s[[ -1]]], k++ ]; k*s[[ -1]] ]]; Nest[f, {1}, 60] (* Robert G. Wilson v, Aug 20 2006, given originally for A113552 *)

up_to = (2^14)+1;
v304752 = vector(up_to);
m_occurrences = Map();
k=0; prev=1; for(n=1,up_to,fordiv(prev,d,if(!mapisdefined(m_occurrences,d),v304752[n] = d;mapput(m_occurrences,d,n);break)); if(!v304752[n], m = 1; try = prev; while(!(prev%m) || mapisdefined(m_occurrences,try), m++; try = prev*m); mapput(m_occurrences,v304752[n] = try,n)); prev = v304752[n]);
A304752(n) = v304752[n];

A304752(n,a=1,list=List(a)/*set to 0 to get just a(n)*/,U=[])={ for(i=2,n, U=setunion(U,[a]); fordiv(a,d,setsearch(U,d)||[a=-d,break]); if(a>0, for(m=2,oo, a%m && !setsearch(U,m*a)&& (a*=m)&& break),a=-a);list&& listput(list,a); /*a%2&&printf("a(%d)=%d, ",i,a)*/);if(list,list,a)} \\ M. F. Hasler, Dec 26 2020

A352394 a(n) = n for n <= 3; let i = a(n-2) and j = a(n-1); a(n+1) = least k not already in the sequence such that (j, k) = 1 and (i, k) = m > 1 and only one of either omega(i) or omega(k) exceed omega(m), where omega = A001221, and either i | k or k | i.

Original entry on oeis.org

1, 2, 3, 10, 21, 5, 7, 15, 14, 165, 182, 11, 13, 22, 39, 110, 273, 55, 91, 220, 819, 4, 9, 20, 63, 260, 693, 26, 33, 130, 231, 65, 77, 195, 154, 3315, 2926, 17, 19, 34, 57, 170, 399, 85, 133, 255, 266, 51, 38, 357, 190, 119, 95, 238, 285, 2618, 3705, 187, 247

Offset: 1

Michael De Vlieger, Jun 23 2022

nonn

Theorem: i | k implies i < k, otherwise k | i implies i > k, a consequence of definition.
Theorem: Prime i implies i < k, since prime i is forced into i | k. Conversely, prime k implies i > k.
Theorem: even terms cannot be adjacent. Proof: If prime p | j, then p cannot divide k as well, because then (j, k) >= p and by definition of "prime", p > 1, which contradicts the axiom (j, k) = 1. Since 2 is prime, consecutive even terms are prohibited.
A restriction on the Yellowstone sequence A098550 analogous to A113552 regarding its relationship to A064413.
Conjecture: sequence is not a permutation of natural numbers. Proof sketch: Since either i | k or k | i, and defining m as the smaller of the 2 terms, as n increases, it becomes harder to reach all numbers through multiplication or division by m. Therefore it would seem that there is strong tendency for the sequence to fall into multiplicative recurrence as does A113552.

Michael De Vlieger, Table of n, a(n) for n = 1..5000
Michael De Vlieger, Annotated log-log scatterplot of a(n), n = 1..2^12, labeling records in red and local minima in blue, highlighting primes in green, composite prime powers in cyan, with fixed points in gold.

Cf. A001221, A098550, A113552.

nn = 120; c[_] = False; a[1] = 1; i = a[2] = 2; j = a[3] = 3; u = 4; c[1] = c[2] = True; facs = {2}; Do[k = u; While[Nand[! c[k], Xor[And[Length@ Complement[facs, #] > 0, Divisible[i, k]], And[Length@ Complement[#, facs] > 0, Divisible[k, i]]] &[FactorInteger[k][[All, 1]]], CoprimeQ[j, k]], k++]; Set[{a[n], c[k]}, {k, True}]; i = j; j = k; facs = FactorInteger[i][[All, 1]]; If[k == u, While[c[u], u++]], {n, 4, nn}]; Array[a, nn]

cp's OEIS Frontend

A113553 Numbers k such that A113552(k) is odd.

Views

Author

Keywords

Comments

Crossrefs

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A303751 Suspected divisor-or-multiple permutation: a(1) = 1, and for n > 1, a(n) is either the least divisor of a(n-1) not already present, or (if all divisors already used), a(n) = a(n-1) * {the least power of the least prime not dividing a(n-1) such that the term is not already present}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A303771 Divisor-or-multiple permutation of natural numbers, "Fermi-Dirac piano played with May code": a(n) = A052330(A303767(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A304085 Divisor-or-multiple permutation of natural numbers: a(n) = A052330(A304083(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A338221 Square spiral of distinct positive integers built by greedy algorithm such that each new value (except the initial one) is a divisor or a multiple of some earlier horizontally or vertically adjacent value.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A304752 Beginning with a(1) = 1, for n > 1, a(n) = the least divisor of a(n-1) not included earlier, otherwise a(n) = the least multiple m*a(n-1) such that m is not a divisor of a(n-1) and m*a(n-1) is not included earlier.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A304752 Beginning with a(1) = 1, for n > 1, a(n) = the least divisor of a(n-1) not included earlier, otherwise a(n) = the least multiple ma(n-1) such that m is not a divisor of a(n-1) and ma(n-1) is not included earlier.