cp's OEIS Frontend

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

%I A303751 #73 Sep 29 2018 18:48:38
%S A303751 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 A303751 27,54,270,135,540,108,2700,25,50,150,75,300,100,900,225,450,3150,7,
%U A303751 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 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}.
%C A303751 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 A303751 From _Antti Karttunen_ & _David A. Corneth_, May 01 - 04 2018: (Start)
%C A303751 No two successive descending terms, that is, a(n) > a(n+1) > a(n+2) never occurs.
%C A303751 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 A303751 If a(n) < a(n+1) < a(n+2) then (a(n+1) / a(n)) is a divisor of a(n+2).
%C A303751 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 A303751 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 A303751 (End)
%C A303751 From _David A. Corneth_, May 04 2018: (Start)
%C A303751 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 A303751 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 A303751 See also "observed scaling patterns" in the Formula section.
%C A303751 A303750 gives the positions of odd terms.
%C A303751 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 A303751 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 A303751 Antti Karttunen, <a href="/A303751/b303751.txt">Table of n, a(n) for n = 1..16384</a>
%H A303751 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A303751 Observed scaling patterns:
%F A303751 For n =     2 ..     2 +     0, a(n) =  2*a(n-1).
%F A303751 For n =     4 ..     4 +     0, a(n) =  3*a(n-3).
%F A303751 For n =    11 ..    11 +     7, a(n) =  5*a(n-10).
%F A303751 For n =    42 ..    42 +    23, a(n) =  7*a(n-41).
%F A303751 For n =   176 ..   176 +    80, a(n) = 11*a(n-175).
%F A303751 For n =  1343 ..  1343 +   683, a(n) = 13*a(n-1342).
%F A303751 For n =  8470 ..  8470 +  3610, a(n) = 17*a(n-8469).
%F A303751 For n = 57949 .. 57949 + 18554, a(n) = 19*a(n-57948).
%e A303751 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 A303751 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 A303751 (PARI)
%o A303751 up_to = 2^14;
%o A303751 A053669(n) = forprime(p=2, , if (n % p, return(p))); \\ From A053669
%o A303751 v303751 = vector(up_to);
%o A303751 m303752 = Map();
%o A303751 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 A303751(n) = v303751[n];
%o A303751 A303752(n) = mapget(m303752,n);
%Y A303751 Cf. A303752 (inverse).
%Y A303751 Cf. A053669, A303750.
%Y A303751 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 A303751 Cf. also A303761.
%Y A303751 Cf. A304728, A304729 (see their scatter plots for alternative views to this process).
%Y A303751 Differs from a variant A304531 for the first time at n = 66, where a(66) = 72, while A304531(66) = 189.
%K A303751 nonn
%O A303751 1,2
%A A303751 _Antti Karttunen_, May 01 2018