login
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}.
11
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,2
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)
LINKS
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.
FORMULA
a(n) = A019565(A303767(n)).
a(n) = A019565(A052331(A303771(n))).
A052330(A048675(a(n))) = A303771(n).
EXAMPLE
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)
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 *)
PROG
(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];
CROSSREFS
Cf. also A303761, A303762 (variants).
Sequence in context: A100113 A300012 A302781 * A330919 A303770 A303762
KEYWORD
nonn
AUTHOR
Antti Karttunen, May 02 2018
STATUS
approved