OFFSET
1,36
COMMENTS
For prime powers there is only one solution. For integers with prime signature p1^2 * p2 there's exactly one solution, for p1^4 * p2 there are two and in general for p1^(2k) * p2 there are A000108(k) solutions. - Mitch Harris, Apr 27 2006
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..10000
T. Y. Chow, H. Eriksson, C. K. Fan, Chess Tableaux, The Electronic Journal of Combinatorics, vol. 11(2), 2004.
T. Y. Chow, H. Eriksson, C. K. Fan, Chess Tableaux and Chess Problems, slides for MIT Combinatorics Seminar, 20 October 2004.
EXAMPLE
In other words, the number of ways to arrange the divisors of n in such a way that no divisor has any of its own divisors following it AND the divisors d_i, d_j, d_k, etc. are arranged so that values bigomega(d_i) (cf. A001222), bigomega(d_j), bigomega(d_k) are alternatively even and odd. E.g., a(12)=1, as of the five arrangements shown in A114717, here the only one allowed is 1,2,4,3,6,12, with A001222(1)=0, A001222(2)=1, A001222(4)=2, A001222(3)=1, A001222(6)=2, A001222(12)=3. a(36) = 2, as there are two solutions for 36: 1,2,4,3,6,12,9,18,36 and 1,3,9,2,6,18,4,12,36.
MAPLE
with(numtheory):
b:= proc(s, t) option remember; `if`(nops(s)<1, 1, add(
`if`(irem(bigomega(x), 2)=1-t and nops(select(y->
irem(y, x)=0, s))=1, b(s minus {x}, 1-t), 0), x=s))
end:
a:= proc(n) option remember; local l, m;
l:= sort(ifactors(n)[2], (x, y)-> x[2]>y[2]);
m:= mul(ithprime(i)^l[i][2], i=1..nops(l));
b(divisors(m) minus {1, m}, irem(bigomega(m), 2))
end:
seq(a(n), n=1..100); # Alois P. Heinz, Feb 26 2016
MATHEMATICA
b[s_, t_] := b[s, t] = If[Length[s] < 1, 1, Sum[If[Mod[PrimeOmega[x], 2] == 1-t && Length[Select[s, Mod[#, x] == 0&]] == 1, b[s ~Complement~ {x}, 1-t ], 0], {x, s}]]; a[n_] := a[n] = Module[{l, m}, l = Sort[FactorInteger[n ], #1[[2]] > #2[[2]]&]; m = Product[Prime[i]^l[[i]][[2]], {i, 1, Length[ l]}]; b[Divisors[m][[2 ;; -2]], Mod[PrimeOmega[m], 2]]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Feb 27 2016, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Antti Karttunen, Jun 04 2006
STATUS
approved