A179926 Number of permutations of the divisors of n of the form d_1=n, d_2, d_3, ..., d_tau(n) such that d_(i+1)/d_i is a prime or 1/prime for all i.

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 18, 1, 1, 2, 2, 2, 8, 1, 2, 2, 4, 1, 18, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 106, 1, 2, 3, 1, 2, 18, 1, 3, 2, 18, 1, 17, 1, 2, 3, 3, 2, 18, 1, 5, 1, 2, 1, 106, 2, 2, 2, 4, 1, 106, 2, 3, 2, 2, 2, 6, 1, 3, 3, 8, 1, 18, 1, 4, 18, 2, 1, 17, 1, 18, 2, 5, 1, 18, 2, 3, 3, 2, 2, 572

Offset: 1

Author

Vladimir Shevelev, Aug 02 2010

Keywords

• nonn

Comments

In view of formulas given below, there are many common first terms with A001221. Note that, for n >= 1, a(n) is positive; it is function of exponents of prime power factorization of n only; moreover, it is invariant with respect to permutations of them.

An equivalent multiset formulation of the problem: for a given finite multiset A, we should, beginning with A, to get all submultisets of A, if, by every step, we remove or join 1 element. How many ways are there to do this?

Via Seqfan Discussion List (Aug 03 2010), Alois P. Heinz proved that every subsequence of the form a(p), a(p*q), a(p*q*r), ..., where p, q, r, ... are distinct primes, coincides with A003043. - Vladimir Shevelev, Aug 09 2010

The parity (odd or even) of bigomega(d_i) in a permutation of divisors of n alternates. - David A. Corneth, Nov 25 2017

Equivalently, the number of Hamiltonian paths in a graph with vertices corresponding to the divisors of n and edges connecting divisors that differ by a prime with the path starting on the vertex associated with 1. - Andrew Howroyd, Oct 26 2019

Examples

			a(12)=3:
[12, 6, 3, 1, 2, 4]
[12, 4, 2, 6, 3, 1]
[12, 4, 2, 1, 3, 6]
a(45)=3:
[45, 15, 5, 1, 3, 9]
[45, 9, 3, 15, 5, 1]
[45, 9, 3, 1, 5, 15]
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1259 (first 719 terms from David A. Corneth)
• David A. Corneth, The permutations of divisors for a(60) ordered by their last element.
• V. Shevelev, Combinatorial minors of matrix functions and their applications, arXiv:1105.3154 [math.CO], 2011-2014.
• V. Shevelev, Combinatorial minors of matrix functions and their applications, Zesz. Nauk. PS., Mat. Stosow., Zeszyt 4, pp. 5-16. (2014).
• Index entries for sequences computed from exponents in factorization of n

Crossrefs

Cf. A000005, A001221, A180026, A003043, A003042. - Vladimir Shevelev, Aug 09 2010

See A173675 for another version.

Cf. A119842, A295785.

Programs

Maple

q:= (i, j)-> is(i/j, integer) and isprime(i/j):
b:= proc(s, l) option remember; `if`(s={}, 1, add(
     `if`(q(l, j) or q(j, l), b(s minus{j}, j), 0), j=s))
    end:
a:= n-> (s-> b(s minus {n}, n))(numtheory[divisors](n)):
seq(a(n), n=1..100);  # Alois P. Heinz, Nov 26 2017

Mathematica

q[i_, j_] := PrimeQ[i/j];
b[s_, l_] := b[s, l] = If[s == {}, 1, Sum[If[q[l, j] || q[j, l], b[s  ~Complement~ {j}, j], 0], {j, s}]];
a[n_] := Function[s, b[s ~Complement~ {n}, n]][Divisors[n]];
Array[a, 120] (* Jean-François Alcover, Dec 13 2017, after Alois P. Heinz *)

PARI

a(n) = {my(f = factor(n), l = List(), chain = List()); res = 0; forvec(x = vector(#f~, i, [0, f[i, 2]]), listput(l, x)); listput(chain, l[#l]); listpop(l, #l); iterate(chain, l); res}
iterate(c, l) = {if(#l == 1, if(vecsum(abs(c[#c] - l[1])) == 1, res++), my(cc, cl);
for(i = 1, #l, if(vecsum(abs(c[#c] - l[i])) == 1, cc = c; cl = l; listput(cc, l[i]); listpop(cl, i); iterate(cc, cl))))}
first(n) = {my(res = vector(n), m = Map()); res[1] = 1; for(i = 2, n, cn = a046523(i); if(cn == i, mapput(m, i, a(i))); res[i] = mapget(m, cn)); res}
a046523(n)=my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f,(p=nextprime(p+1))^f[i]) \\ (a046523 from Charles R Greathouse IV), David A. Corneth, Nov 24 2017

Formula

a(p^k)=1, a(p^k*q)=k+1, a(p^2*q^2)=8, a(p^2*q^3)=17, a(pqr)=18, a(p^2*q*r)=106, a(p^3*q*r)=572, etc. (here p,q,r are distinct primes, k >= 0).

Extensions

Corrected by D. S. McNeil and Alois P. Heinz and extended by Alois P. Heinz from a(46) via the Seqfan Discussion List (Aug 02 2010)