A173675 - OEIS

%I #49 Dec 23 2024 14:53:42

%S 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,

%T 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,

%U 1,4,72,1,8,4,72,1,62,1,4,8,8,4,72,1,22,1,4

%N 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).

%C 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.

%C From _Andrew Howroyd_, Oct 26 2019: (Start)

%C 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.

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

%H Andrew Howroyd, <a href="/A173675/b173675.txt">Table of n, a(n) for n = 1..2048</a>

%H V. Shevelev, <a href="http://arxiv.org/abs/1105.3154">Combinatorial minors of matrix functions and their applications</a>, arXiv:1105.3154 [math.CO], 2011-2014.

%H V. Shevelev, <a href="https://www.math.bgu.ac.il/~shevelev/comb_meth2014.pdf">Combinatorial minors of matrix functions and their applications</a>, Zesz. Nauk. PS., Mat. Stosow., Zeszyt 4, pp. 5-16. (2014).

%H Robert G. Wilson v, <a href="https://web.archive.org/web/*/http://list.seqfan.eu/oldermail/seqfan/2010-August/005453.html">Re: A combinatorial problem</a>, SeqFan (Aug 02 2010)

%F From _Andrew Howroyd_, Oct 26 2019: (Start)

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

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

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

%e a(1) = 1: [1].

%e a(2) = 1: [1,2].

%e a(6) = 4: [1,2,6,3], [1,3,6,2], [2,1,3,6], [3,1,2,6].

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

%p with(numtheory):

%p q:= (i, j)-> is(i/j, integer) and isprime(i/j):

%p b:= proc(s, l) option remember; `if`(s={}, 1, add(

%p      `if`(q(l, j) or q(j, l), b(s minus{j}, j), 0), j=s))

%p     end:

%p a:= proc(n) option remember; ((s-> add(b(s minus {j}, j),

%p        j=s))(divisors(n)))/`if`(n>1, 2, 1)

%p     end:

%p seq(a(n), n=1..100);  # _Alois P. Heinz_, Nov 26 2017

%t 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}]];

%t a[n_] := a[n] = Function[s, Sum[b[s ~Complement~ {j}, j], {j, s}]][ Divisors[n]] / If[n > 1, 2, 1];

%t Array[a, 100] (* _Jean-François Alcover_, Nov 28 2017, after _Alois P. Heinz_ *)

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

%Y See A295557 for another version.

%K nonn

%O 1,6

%A _N. J. A. Sloane_, Nov 24 2010

%E _Alois P. Heinz_ corrected and clarified the definition and provided more terms. - Nov 07 2014