A303760 Divisor-or-multiple permutation of squarefree numbers: a(0) = 1, and for n >= 1, a(n) is either the least divisor of a(n-1) not already present in the sequence, or (if all divisors already used), a(n-1) * {the least prime p such that p does not divide a(n-1) and p*a(n-1) is not already present}.

1, 2, 6, 3, 15, 5, 10, 30, 210, 7, 14, 42, 21, 105, 35, 70, 770, 11, 22, 66, 33, 165, 55, 110, 330, 2310, 77, 154, 462, 231, 1155, 385, 5005, 13, 26, 78, 39, 195, 65, 130, 390, 2730, 91, 182, 546, 273, 1365, 455, 910, 10010, 143, 286, 858, 429, 2145, 715, 1430, 4290, 30030, 1001, 2002, 6006, 3003, 15015, 255255, 17, 34, 102, 51, 255, 85, 170, 510, 3570, 119

Offset: 0

Author

Antti Karttunen, May 02 2018

Keywords

• nonn

Comments

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

If a(n+1) > a(n), then A001222(a(n+1)) = 1 + A001222(a(n)).

From Antti Karttunen, May 23 2018: (Start)

For n >= 1, A006530(a(n)) = A000040(A070939(n)), thus the greatest prime dividing n, or equally, its index (A061395), is monotonic and follows the length of binary representation of n. This follows by induction on the size of the binary representation of n, and the fact that the "least possible unused divisor" part of a greedy rule can find all the unused divisors of A002110(k) before the next larger prime A000040(1+k) is needed as a factor.

For n >= 1, a((2^k)+1) = A000040(k+1), that is, after the first term with the next larger prime factor, which always occurs at 2^k, the next term is that prime itself, which is prime(k+1).

(A) For r in range 1 .. (2^(k-1)), a((2^k)+r) = A000040(k+1) * a(r-1), and prime A000040(k) is not present in the factorization. Because we cannot divide prime(k+1) out, as that would give a term already encountered, and because every term in this range has it as a largest prime factor, the relative magnitude-wise order of the terms in this range follows the relative magnitude-wise order of terms in a(0) .. a((2^(k-1))-1).

(B) For r in range (2^(k-1))+1 .. (2^k)-1, a((2^k)+r) = A000040(k+1) * a(r-1), and prime A000040(k) is present in the factorization.

Now it might be case that prime(k) > a product m of some subset of primes prime(k-1) .. prime(1). Even though the algorithm in those cases "would like" to divide by prime(k) instead of dividing by that product m, because then the divisor would be smaller, it cannot, because dividing by prime(k) (or by any other divisor containing it) would give an already used term.

(End)

Examples

			From _Michael De Vlieger_, May 23 2018: (Start)
Table below shows the initial 32 terms at right. First column is index n, second shows "." if a(n) = largest divisor of a(n-1), or factor p. Third shows presence "1" or absence "." of prime k among prime divisors of a(n).
   n      p\d     MN(n)       a(n)
  --------------------------------
   0       .      .             1
   1       2      1             2
   2       3      11            6
   3       .      .1            3
   4       5      .11          15
   5       .      ..1           5
   6       2      1.1          10
   7       3      111          30
   8       7      1111        210
   9       .      ...1          7
  10       2      1..1         14
  11       3      11.1         42
  12       .      .1.1         21
  13       5      .111        105
  14       .      ..11         35
  15       2      1.11         70
  16      11      1.111       770
  17       .      ....1        11
  18       2      1...1        22
  19       3      11..1        66
  20       .      .1..1        33
  21       5      .11.1       165
  22       .      ..1.1        55
  23       2      1.1.1       110
  24       3      111.1       330
  25       7      11111      2310
  26       .      ...11        77
  27       2      1..11       154
  28       3      11.11       462
  29       .      .1.11       231
  30       5      .1111      1155
  31       .      ..111       385
  ... (End)
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..16383
• Michael De Vlieger, Patterns in the multiplicities of prime divisors of terms m in A303760.
• Michael De Vlieger, Image of multiplicities of distinct prime divisors of first 1024 terms, vertical axis increases downward, horizontal axis increases rightward and exaggerated 20 x.

Crossrefs

Cf. A005117, A019565, A303767, A303771.

Cf. also A303761, A303762 (variants).

Programs

Mathematica

Nest[Append[#, Block[{d = Divisors@ #[[-1]], p = 2}, If[Complement[d, #] != {}, Complement[d, #][[1]], While[Nand[Mod[#[[-1]], p] != 0, FreeQ[#, p #[[-1]] ] ], p = NextPrime@ p]; p #[[-1]] ] ] ] &, {1}, 71] (* Michael De Vlieger, May 23 2018 *)

PARI

up_to = 2^7;
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];

Formula

a(n) = A019565(A303767(n)).

a(n) = A019565(A052331(A303771(n))).

A052330(A048675(a(n))) = A303771(n).