cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

This page as a plain text file.
%I A303760 #30 Jun 07 2018 22:09:43
%S A303760 1,2,6,3,15,5,10,30,210,7,14,42,21,105,35,70,770,11,22,66,33,165,55,
%T A303760 110,330,2310,77,154,462,231,1155,385,5005,13,26,78,39,195,65,130,390,
%U A303760 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
%N 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}.
%C A303760 Each a(n+1) is either a divisor or a multiple of a(n).
%C A303760 If a(n+1) > a(n), then A001222(a(n+1)) = 1 + A001222(a(n)).
%C A303760 From _Antti Karttunen_, May 23 2018: (Start)
%C A303760 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.
%C A303760 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).
%C A303760 (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).
%C A303760 (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.
%C A303760 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.
%C A303760 (End)
%H A303760 Antti Karttunen, <a href="/A303760/b303760.txt">Table of n, a(n) for n = 0..16383</a>
%H A303760 Michael De Vlieger, <a href="/A303760/a303760.txt">Patterns in the multiplicities of prime divisors of terms m in A303760</a>.
%H A303760 Michael De Vlieger, <a href="/A303760/a303760.png">Image of multiplicities of distinct prime divisors of first 1024 terms</a>, vertical axis increases downward, horizontal axis increases rightward and exaggerated 20 x.
%F A303760 a(n) = A019565(A303767(n)).
%F A303760 a(n) = A019565(A052331(A303771(n))).
%F A303760 A052330(A048675(a(n))) = A303771(n).
%e A303760 From _Michael De Vlieger_, May 23 2018: (Start)
%e A303760 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).
%e A303760    n      p\d     MN(n)       a(n)
%e A303760   --------------------------------
%e A303760    0       .      .             1
%e A303760    1       2      1             2
%e A303760    2       3      11            6
%e A303760    3       .      .1            3
%e A303760    4       5      .11          15
%e A303760    5       .      ..1           5
%e A303760    6       2      1.1          10
%e A303760    7       3      111          30
%e A303760    8       7      1111        210
%e A303760    9       .      ...1          7
%e A303760   10       2      1..1         14
%e A303760   11       3      11.1         42
%e A303760   12       .      .1.1         21
%e A303760   13       5      .111        105
%e A303760   14       .      ..11         35
%e A303760   15       2      1.11         70
%e A303760   16      11      1.111       770
%e A303760   17       .      ....1        11
%e A303760   18       2      1...1        22
%e A303760   19       3      11..1        66
%e A303760   20       .      .1..1        33
%e A303760   21       5      .11.1       165
%e A303760   22       .      ..1.1        55
%e A303760   23       2      1.1.1       110
%e A303760   24       3      111.1       330
%e A303760   25       7      11111      2310
%e A303760   26       .      ...11        77
%e A303760   27       2      1..11       154
%e A303760   28       3      11.11       462
%e A303760   29       .      .1.11       231
%e A303760   30       5      .1111      1155
%e A303760   31       .      ..111       385
%e A303760   ... (End)
%t A303760 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 *)
%o A303760 (PARI)
%o A303760 up_to = 2^7;
%o A303760 A053669(n) = forprime(p=2, , if (n % p, return(p))); \\ From A053669
%o A303760 v303760 = vector(up_to);
%o A303760 m_inverses = Map();
%o A303760 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]);
%o A303760 A303760(n) = v303760[n+1];
%Y A303760 Cf. A005117, A019565, A303767, A303771.
%Y A303760 Cf. also A303761, A303762 (variants).
%K A303760 nonn
%O A303760 0,2
%A A303760 _Antti Karttunen_, May 02 2018