A163820 -id:A163820 - cp's OEIS frontend

A293900 Number of permutations of the divisors of n that are greater than 1, in which consecutive elements are not coprime and no divisor d may occur later than any divisor e if e < d and A007947(e) = A007947(d). That is, any subset of divisors sharing the same squarefree part occur always in ascending order inside the permutation.

0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 9, 1, 2, 2, 1, 1, 9, 1, 9, 2, 2, 1, 40, 1, 2, 1, 9, 1, 348, 1, 1, 2, 2, 2, 110, 1, 2, 2, 40, 1, 348, 1, 9, 9, 2, 1, 175, 1, 9, 2, 9, 1, 40, 2, 40, 2, 2, 1, 138660, 1, 2, 9, 1, 2, 348, 1, 9, 2, 348, 1, 1127, 1, 2, 9, 9, 2, 348, 1, 175, 1, 2, 1, 138660, 2, 2, 2, 40, 1, 138660, 2, 9, 2, 2, 2, 756, 1, 9, 9, 110

Offset: 1

Antti Karttunen, Oct 22 2017

nonn

This is a more restricted variant of A163820, inspired by David A. Corneth's suggestion (personal e-mail) for optimizing its computation.

			The proper divisors of 12 are 2, 3, 4, 6, 12. a(12) = 9 because we can find nine permutations of them such that consecutive elements d and e are not coprime (that is, gcd(d,e) > 1) and where no divisor d is ever followed by divisor e such that A007947(d) = A007947(e) and e < d. These nine allowed permutations are (note that 2 must become before 4 and 6 must become before 12):
  [2, 4, 6, 3, 12],
  [2, 4, 6, 12, 3],
  [2, 6, 3, 12, 4],
  [2, 6, 4, 12, 3],
  [3, 6, 2, 4, 12],
  [3, 6, 2, 12, 4],
  [3, 6, 12, 2, 4],
  [6, 2, 4, 12, 3],
  [6, 3, 12, 2, 4].

Antti Karttunen, Table of n, a(n) for n = 1..179 (based on b-file of A163820 provided by David A. Corneth)
Antti Karttunen, Scheme-program for computing this sequence
Index entries for sequences computed from exponents in factorization of n

Cf. A000961 (positions of 0 and 1's), A163820, A293902.

Cf. also A114717, A119842.

Iff n = p^k for some prime p and k >= 1 [that is, n is a term of A000961 > 1], then a(n) = 1.

a(n) = A163820(n)/A293902(n).

A293902 If n = p_1^e_1 * ... * p_k^e_k, p_1, ..., p_k primes, then a(n) = Product c! where c ranges over products of all combinations of exponents e_1, ..., e_k as {e_1, e_1e_2, e_1e_3, e_2e_3, e_1e_2e_3, ..., e_1e_2...e_k}.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 6, 2, 1, 1, 4, 1, 1, 1, 24, 1, 4, 1, 4, 1, 1, 1, 36, 2, 1, 6, 4, 1, 1, 1, 120, 1, 1, 1, 96, 1, 1, 1, 36, 1, 1, 1, 4, 4, 1, 1, 576, 2, 4, 1, 4, 1, 36, 1, 36, 1, 1, 1, 16, 1, 1, 4, 720, 1, 1, 1, 4, 1, 1, 1, 8640, 1, 1, 4, 4, 1, 1, 1, 576, 24, 1, 1, 16, 1, 1, 1, 36, 1, 16, 1, 4, 1, 1, 1, 14400, 1, 4, 4, 96, 1, 1, 1, 36, 1

Offset: 1

Antti Karttunen, Oct 22 2017

nonn

a(1) = 1 (an empty product).

			For n = 36 = 2^2 * 3^2 the combinations of the exponents are [], [2] (as exponent of 2), [2] (as exponent of 3) and [2, 2]. Taking products of these multisets we get 1 (as an empty product), 2, 2 and 4. Thus a(36) = 1! * 2! * 2! * 4! = 1*2*2*24 = 96.
For n = 72 = 2^3 * 3^2 the combinations of the exponents are [], [2], [3] and [2, 3]. Taking products of these multisets we get 1, 2, 3 and 6. Thus a(72) = 1! * 2! * 3! * 6! = 1*2*6*720 = 8640.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences computed from exponents in factorization of n

Cf. A000142, A163820, A293900.

Array[Apply[Times, Map[Times @@ # &, Subsets@ FactorInteger[#][[All, -1]]]!] &, 105] (* Michael De Vlieger, Oct 23 2017 *)

A293902(n) = { my(exp_combos=powerset(factor(n)[, 2]), m=1); for(i=1,#exp_combos,m *= vecproduct(exp_combos[i])!); m; };
vecproduct(v) = { my(m=1); for(i=1,#v,m *= v[i]); m; };
powerset(v) = { my(siz=2^length(v),pv=vector(siz)); for(i=0,siz-1,pv[i+1] = choosebybits(v,i)); pv; };
choosebybits(v,m) = { my(s=vector(hammingweight(m)),i=j=1); while(m>0,if(m%2,s[j] = v[i];j++); i++; m >>= 1); s; };

(define (A293902 n) (if (= 1 n) n (/ (A163820 n) (A293900 n))))

For n = p^k * q * ... * r (with only one of the prime factors occurring multiple times), a(n) = A000142(k)^(2^(A001221(n)-1)).
a(p^n) = A000142(n), for any prime p.
For n > 1, a(n) = A163820(n) / A293900(n).

A293782 a(n) is the number of permutations of {1, 2, 3, 4} that avoid the list of pairs encrypted in n (see comments below).

Original entry on oeis.org

24, 18, 18, 12, 18, 12, 12, 6, 18, 14, 12, 8, 14, 10, 8, 4, 18, 14, 14, 10, 12, 8, 8, 4, 12, 10, 8, 6, 8, 6, 4, 2, 18, 14, 14, 10, 12, 8, 8, 4, 14, 11, 10, 7, 10, 7, 6, 3, 12, 10, 10, 8, 6, 4, 4, 2, 8, 7, 6, 5, 4, 3, 2, 1, 18, 12, 14, 8, 14, 8, 10, 4, 12, 8, 8, 4

Offset: 0

David A. Corneth, Oct 24 2017

This sequence contains 2^(2 * 6) = 4096 terms; a(n) for n = 0..4095. We consider the digits of the binary expansion of n, i. e. the bits from the first (least significant) bit to the twelfth (most significant) bit. We define a correspondence between the bit number 1..16 and the pair or numbers 1..4: (1, [1, 2]), (2, [1, 3]), (3, [1, 4]), (4, [2, 3]), (5, [2, 4]), (6, [3, 4]), (7, [2, 1]), (8, [3, 1]), (9, [4, 1]), (10, [3, 2]), (11, [4, 2]), (12, [4, 3]). Then consider a permutation of {1, 2, 3, 4}; if a bit of n is 1 then the corresponding pair is not allowed in the permutation. The number of permutations that satisfy this restriction is a(n).
Distinct terms in this sequence are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 18 and 24 which occur 772, 936, 672, 328, 336, 288, 272, 120, 129, 48, 84, 24, 38, 36, 12 and 1 times respectively.
a(65 * n) lists number of permutations such that pairs avoided in permutations numbered by a(n) aren't adjacent to each other.

			The binary expansion of 195 is 11000011. The 1st, 2nd, 7th, and 8th bits are 1, so we avoid the corresponding pairs, which are [1, 2], [1, 3], [2, 1], and [3, 1] respectively. There are 4 permutations that avoid these completely; they are [1, 4, 2, 3], [1, 4, 3, 2], [2, 3, 4, 1] and [3, 2, 4, 1]. Therefore, a(195) = 4.
Note that 195 is a multiple of 65 and so a(195) gives the elements from pairs corresponding to a(195/65) = a(3), which are [1, 2] and [1, 3] aren't adjacent to each other.

Cf. A163820.

With[{p = Permutations[Range@4]}, Table[Count[p, ?(AllTrue[Pick[{{4, 3}, {4, 2}, {3, 2}, {4, 1}, {3, 1}, {2, 1}, {3, 4}, {2, 4}, {2, 3}, {1, 4}, {1, 3}, {1, 2}}, PadLeft[IntegerDigits[n, 2], 12], 1], Function[k, SequenceCount[#, k] == 0]] &)], {n, 0, 75}]] (* _Michael De Vlieger, Oct 30 2017 *)

a(n) = {my(b = binary(n), pairs, avoid = List(), perm); b = concat(vector(12-#b), b); pairs = [[4,3], [4,2], [3,2], [4,1], [3,1], [2,1], [3, 4], [2, 4], [2, 3], [1, 4], [1, 3], [1, 2]]; for(i=1, 12, if(b[i] == 1, listput(avoid, pairs[i]))); sum(i=0,23,avoids(numtoperm(4, i), avoid))}
avoids(perm, avoid) = {for(i=1, #perm - 1, for(j=1, #avoid, if(perm[i] == avoid[j][1], if(perm[i+1] == avoid[j][2], return(0))))); 1}

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A293902 If n = p_1^e_1 * ... * p_k^e_k, p_1, ..., p_k primes, then a(n) = Product c! where c ranges over products of all combinations of exponents e_1, ..., e_k as {e_1, e_1e_2, e_1e_3, e_2e_3, e_1e_2e_3, ..., e_1e_2...e_k}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

A293782 a(n) is the number of permutations of {1, 2, 3, 4} that avoid the list of pairs encrypted in n (see comments below).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A293902 If n = p_1^e_1 * ... * p_k^e_k, p_1, ..., p_k primes, then a(n) = Product c! where c ranges over products of all combinations of exponents e_1, ..., e_k as {e_1, e_1*e_2, e_1*e_3, e_2*e_3, e_1*e_2*e_3, ..., e_1*e_2*...*e_k}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

A293782 a(n) is the number of permutations of {1, 2, 3, 4} that avoid the list of pairs encrypted in n (see comments below).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

A293902 If n = p_1^e_1 * ... * p_k^e_k, p_1, ..., p_k primes, then a(n) = Product c! where c ranges over products of all combinations of exponents e_1, ..., e_k as {e_1, e_1e_2, e_1e_3, e_2e_3, e_1e_2e_3, ..., e_1e_2...e_k}.