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}.

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

Author

Antti Karttunen, May 14 2018

Keywords

• nonn

Comments

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, ...

Examples

			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.
		

Links

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

Crossrefs

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.

Programs

PARI

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

Formula

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