|
| |
|
|
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.
|
|
7
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,6
|
|
|
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
|
|
|
LINKS
|
|
|
|
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).
|
|
|
EXAMPLE
|
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]
|
|
|
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)):
|
|
|
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]];
|
|
|
PROG
|
(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}
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
