A173675 Let d_1, d_2, d_3, ..., d_tau(n) be the divisors of n; a(n) = number of permutations p of d_1, d_2, d_3, ..., d_tau(n) such that p_(i+1)/p_i is a prime or 1/prime for i = 1,2,...,tau(n)-1 and p_1 <= p_tau(n).

1, 1, 1, 1, 1, 4, 1, 1, 1, 4, 1, 8, 1, 4, 4, 1, 1, 8, 1, 8, 4, 4, 1, 14, 1, 4, 1, 8, 1, 72, 1, 1, 4, 4, 4, 20, 1, 4, 4, 14, 1, 72, 1, 8, 8, 4, 1, 22, 1, 8, 4, 8, 1, 14, 4, 14, 4, 4, 1, 584, 1, 4, 8, 1, 4, 72, 1, 8, 4, 72, 1, 62, 1, 4, 8, 8, 4, 72, 1, 22, 1, 4

Offset: 1

Author

N. J. A. Sloane, Nov 24 2010

Keywords

• nonn

Comments

Variant of A179926 in which the permutation of the divisors may start with any divisor but the first term may not be larger than the last term.

From Andrew Howroyd, Oct 26 2019: (Start)

Equivalently, the number of undirected Hamiltonian paths in a graph with vertices corresponding to the divisors of n and edges connecting divisors that differ by a prime.

a(n) depends only on the prime signature of n. See A295786. (End)

Examples

			a(1) = 1: [1].
a(2) = 1: [1,2].
a(6) = 4: [1,2,6,3], [1,3,6,2], [2,1,3,6], [3,1,2,6].
a(12) = 8: [1,2,4,12,6,3], [1,3,6,2,4,12], [1,3,6,12,4,2], [2,1,3,6,12,4], [3,1,2,4,12,6], [3,1,2,6,12,4], [4,2,1,3,6,12], [6,3,1,2,4,12].
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..2048
• 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).
• Robert G. Wilson v, Re: A combinatorial problem, SeqFan (Aug 02 2010)

Crossrefs

Cf. A000005, A000040, A002110, A101296, A179926, A284673, A295786.

See A295557 for another version.

Programs

Maple

with(numtheory):
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:= proc(n) option remember; ((s-> add(b(s minus {j}, j),
       j=s))(divisors(n)))/`if`(n>1, 2, 1)
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Nov 26 2017

Mathematica

b[s_, l_] := b[s, l] = If[s == {}, 1, Sum[If[PrimeQ[l/j] || PrimeQ[j/l], b[s ~Complement~ {j}, j], 0], {j, s}]];
a[n_] := a[n] = Function[s, Sum[b[s ~Complement~ {j}, j], {j, s}]][ Divisors[n]] / If[n > 1, 2, 1];
Array[a, 100] (* Jean-François Alcover, Nov 28 2017, after Alois P. Heinz *)

Formula

From Andrew Howroyd, Oct 26 2019: (Start)

a(p^e) = 1 for prime p.

a(A002110(n)) = A284673(n).

a(n) = A295786(A101296(n)). (End)

Extensions

Alois P. Heinz corrected and clarified the definition and provided more terms. - Nov 07 2014