login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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).
4
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
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
See A295557 for another version.
Sequence in context: A340227 A351942 A351230 * A364360 A085731 A131301
KEYWORD
nonn,changed
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