login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..1259 (first 719 terms from David A. Corneth)

David A. Corneth, The permutations of divisors for a(60) ordered by their last element.

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

Index entries for sequences computed from exponents in factorization of n

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

seq(a(n), n=1..100);  # Alois P. Heinz, Nov 26 2017

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

Array[a, 120] (* Jean-Fran├žois Alcover, Dec 13 2017, after Alois P. Heinz *)

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}

a046523(n)=my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]) \\ (a046523 from Charles R Greathouse IV), David A. Corneth, Nov 24 2017

CROSSREFS

Cf. A000005, A001221, A180026, A003043, A003042. - Vladimir Shevelev, Aug 09 2010

See A173675 for another version.

Cf. A119842.

Sequence in context: A168324 A303838 A285572 * A066882 A300831 A068347

Adjacent sequences:  A179923 A179924 A179925 * A179927 A179928 A179929

KEYWORD

nonn

AUTHOR

Vladimir Shevelev, Aug 02 2010

EXTENSIONS

Corrected by D. S. McNeil and Alois P. Heinz and extended by Alois P. Heinz from a(46) via the Seqfan Discussion List (Aug 02 2010)

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 14 19:12 EST 2018. Contains 317214 sequences. (Running on oeis4.)