cp's OEIS Frontend

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.

%I A069023 #10 Nov 26 2017 07:16:02
%S A069023 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,
%T A069023 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,
%U A069023 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
%N 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.
%C A069023 a(n) is determined by the prime signature of n.
%H A069023 Antti Karttunen, <a href="/A069023/b069023.txt">Table of n, a(n) for n = 1..16384</a>
%H A069023 Antti Karttunen, <a href="/A069023/a069023.txt">Scheme-program for computing this sequence</a>
%H A069023 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%F A069023 It seems that for n >= 3, a(p^n) = A077866(n-3). - _Antti Karttunen_, Nov 24 2017
%e A069023 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).
%o A069023 (PARI)
%o A069023 \\ The following program is very inefficient:
%o A069023 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)); };
%o A069023 powerset(v) = { my(siz=2^length(v),pv=vector(siz)); for(i=0,siz-1,pv[i+1] = choosebybits(v,i)); pv; };
%o A069023 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; };
%o A069023 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
%o A069023 \\ _Antti Karttunen_, Nov 24 2017
%o A069023 (Scheme) ;; See in the links-section.
%Y A069023 Cf. A077866.
%K A069023 nonn
%O A069023 1,12
%A A069023 _Amarnath Murthy_, Apr 02 2002
%E A069023 Edited by _David Wasserman_, Mar 26 2003