

A069023


Define a subset of divisors of n to be a dedicated subset if the product of any two members is also a divisor of n. 1 is not allowed as a member as it gives trivially 1*d = d a divisor. a(n) is the number of dedicated subsets of divisors of n with at least two members.


1



0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 3, 0, 1, 1, 2, 0, 3, 0, 3, 1, 1, 0, 9, 0, 1, 1, 3, 0, 7, 0, 5, 1, 1, 1, 9, 0, 1, 1, 9, 0, 7, 0, 3, 3, 1, 0, 17, 0, 3, 1, 3, 0, 9, 1, 9, 1, 1, 0, 20, 0, 1, 3, 8, 1, 7, 0, 3, 1, 7, 0, 28, 0, 1, 3, 3, 1, 7, 0, 17, 2, 1, 0, 20, 1, 1, 1, 9, 0, 20, 1, 3, 1, 1, 1, 35, 0, 3, 3, 9, 0, 7
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,12


COMMENTS

a(n) is determined by the prime signature of n.


LINKS

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Schemeprogram for computing this sequence
Index entries for sequences computed from exponents in factorization of n


FORMULA

It seems that for n >= 3, a(p^n) = A077866(n3).  Antti Karttunen, Nov 24 2017


EXAMPLE

a(12) = 3. The divisors of 12 are 1,2,3,4,6,12. The divisor subsets (2,3),(2,6) and (3,4) are such that their product is also a divisor of 12. a(24) = 9 and the dedicated divisor subsets are (2,3),(2,4),(2,6),(2,12),(3,4),(3,8),(4,6),(2,3,4),(2,4,6).


PROG

(PARI)
\\ The following program is very inefficient:
A069023(n) = { if(bigomega(n)<2, return(0)); my(pds=(divisors(n)[2..numdiv(n)]), subsets = select(v > (length(v)>=2), powerset(pds)), pair_products = apply(ss > podp(ss), subsets), prodsmodn = apply(pps > vector(#pps, i, n%pps[i]), pair_products)); length(select(s > 0==vecsum(s), prodsmodn)); };
powerset(v) = { my(siz=2^length(v), pv=vector(siz)); for(i=0, siz1, pv[i+1] = choosebybits(v, i)); pv; };
choosebybits(v, m) = { my(s=vector(hammingweight(m)), i=j=1); while(m>0, if(m%2, s[j] = v[i]; j++); i++; m >>= 1); s; };
podp(v) = { my(siz=binomial(length(v), 2), rv=vector(siz), k=0); for(i=1, length(v)1, for(j=i+1, length(v), k++; rv[k] = v[i]*v[j])); rv; }; \\ podp = product of distinct pairs
\\ Antti Karttunen, Nov 24 2017
(Scheme) ;; See in the linkssection.


CROSSREFS

Cf. A077866.
Sequence in context: A059341 A249442 A131802 * A275336 A091614 A249767
Adjacent sequences: A069020 A069021 A069022 * A069024 A069025 A069026


KEYWORD

nonn


AUTHOR

Amarnath Murthy, Apr 02 2002


EXTENSIONS

Edited by David Wasserman, Mar 26 2003


STATUS

approved



