summation - Summing over Subsets of ${2, 3, 4, 5, 6, ... n }$

I came across the function which counts distinct prime factors of a number. I then generalized the function $w$ to take as argument a set instead of a number and return the number of prime factors that are shared between them.

If $\underline{n} = \{2, 3, 4, 5, 6, ... n \}$, then $w(\; \underline{6}\; ) = 0.$ Some other examples: $w(\{2, 4, 6, 8 \}) = 1, w(\{15, 30, 45, 60 \}) = 2$.

Now, I'd like to sum all subsets of $\underline{n}$ by applying the function $w(J)$ to each subset $J$ of $\underline{n}$, where $|J|>1$. To put this into math form, let $\mathcal{P}(\underline{n})$ be the power set of $\underline{n}$. Then the set of sets $D(\underline{n}) = \mathcal{P}(\underline{n}) \backslash \{J; J \subseteq \underline{n}, |J| \le 1 \}$.

The quantity I would like to find is:
$$\sum_{J \in D(\underline{n})} w(J)$$

in terms of $w$. $J$ ranges across the sets in $D(A)$. I have tried using the binomial coefficient to get all possible subsets of one specific type of set, for instance those sets sharing one factor, two factors, etc., but I think I'm missing a basic trick for finding the relevant sets of $D(A)$ because there is always some subsets I've missed.

What is the best way to calculate the above sum in terms of $w$? I do not want to evaluate $w$ since I'd like to be able to apply the strategy you use in your answer to a variety of functions that take as argument a set and return an integer based on the factors of the elements in the set. I want to know how to break up $D(n)$ into all the relevant subsets to count them.

Answer

Calculating your desired sum is easier if you "partition" the sets in $D(
\underline{n})$ not into those with zero, one, two, etc. prime factors but into those divisible by $2$, $3$, $5$, $7$, and so forth. ("Partition" is quoted here because obviously this isn't a true partition; some sets will reoccur.) Let $w_p(J)$ be $1$ if every element in $J$ is divisible by $p$, and $0$ otherwise. Let $S_p(n) = \sum_{J \in D(\underline{n})} w_p(J)$. The number of subsets of $\{1, \ldots, n\}$ (starting from $2$ instead of $1$ makes no difference) in which every element is divisible by $p$ is the same as the number of nonempty subsets of $\{1, \ldots, \left\lfloor \frac{n}{p} \right\rfloor\}$, namely $2^{\lfloor n/p \rfloor}$. Elimintating the zero- and one-element sets gives $$S_p(n) = 2^{\lfloor n/p \rfloor} - \left\lfloor \frac{n}{p} \right\rfloor- 1$$ and of course $$S(n) = \sum_{\substack{2 \leq p \leq n/2 \\ p\, \text{prime}}} S_p(n)$$ which is a sum for which I wouldn't expect a convenient closed form to exist.