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,6

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)

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)

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)

Example

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

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 *)

Crossrefs

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

See A295557 for another version.

Sequence in context: A340227 A351942 A351230 * A364360 A085731 A131301

Adjacent sequences: A173672 A173673 A173674 * A173676 A173677 A173678

Keyword

nonn

Author

N. J. A. Sloane, Nov 24 2010

Extensions

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

Status

approved