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.
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
Offset: 1
Keywords
Examples
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).
Links
Crossrefs
Cf. A077866.
Programs
-
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,siz-1,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 links-section.
Formula
It seems that for n >= 3, a(p^n) = A077866(n-3). - Antti Karttunen, Nov 24 2017
Extensions
Edited by David Wasserman, Mar 26 2003
Comments