|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Each a(n+1) is either a divisor or a multiple of a(n).
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
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
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;
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]);
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
