A303751 - OEIS

%I #73 Sep 29 2018 18:48:38

%S 1,2,6,3,12,4,36,9,18,90,5,10,30,15,60,20,180,45,360,8,24,120,40,1080,

%T 27,54,270,135,540,108,2700,25,50,150,75,300,100,900,225,450,3150,7,

%U 14,42,21,84,28,252,63,126,630,35,70,210,105,420,140,1260,315,2520,56,168,840,280,7560,72,1800,200,600,4200

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

%C 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.

%C From _Antti Karttunen_ & _David A. Corneth_, May 01 - 04 2018: (Start)

%C No two successive descending terms, that is, a(n) > a(n+1) > a(n+2) never occurs.

%C 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.

%C If a(n) < a(n+1) < a(n+2) then (a(n+1) / a(n)) is a divisor of a(n+2).

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

%C 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.

%C (End)

%C From _David A. Corneth_, May 04 2018: (Start)

%C 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), ...

%C 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)

%C See also "observed scaling patterns" in the Formula section.

%C A303750 gives the positions of odd terms.

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

%C 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.

%H Antti Karttunen, <a href="/A303751/b303751.txt">Table of n, a(n) for n = 1..16384</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F Observed scaling patterns:

%F For n =     2 ..     2 +     0, a(n) =  2*a(n-1).

%F For n =     4 ..     4 +     0, a(n) =  3*a(n-3).

%F For n =    11 ..    11 +     7, a(n) =  5*a(n-10).

%F For n =    42 ..    42 +    23, a(n) =  7*a(n-41).

%F For n =   176 ..   176 +    80, a(n) = 11*a(n-175).

%F For n =  1343 ..  1343 +   683, a(n) = 13*a(n-1342).

%F For n =  8470 ..  8470 +  3610, a(n) = 17*a(n-8469).

%F For n = 57949 .. 57949 + 18554, a(n) = 19*a(n-57948).

%e 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.

%e 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.

%o (PARI)

%o up_to = 2^14;

%o A053669(n) = forprime(p=2, , if (n % p, return(p))); \\ From A053669

%o v303751 = vector(up_to);

%o m303752 = Map();

%o 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]);

%o A303751(n) = v303751[n];

%o A303752(n) = mapget(m303752,n);

%Y Cf. A303752 (inverse).

%Y Cf. A053669, A303750.

%Y 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.

%Y Cf. also A303761.

%Y Cf. A304728, A304729 (see their scatter plots for alternative views to this process).

%Y Differs from a variant A304531 for the first time at n = 66, where a(66) = 72, while A304531(66) = 189.

%K nonn

%O 1,2

%A _Antti Karttunen_, May 01 2018