I don't think this is right, but here we go. If $f(n)$ is the number of non-empty subsets, then $f(n)$ is $n(n+1)/2$, as shown through this method. As I learned from Jason Batterson's book, think it geometrically. Draw a diagram, representing the number of non-empty subsets. There are n rows in the diagram (number of different subsets), and n+1 columns in the diagram. (number of objects in each row). If you draw a diagram, the geometric figure is a triangle. So, the answer is $(n)(n+1)/2$, and that can't be a square, an even and an odd number multiplied together makes 2 different factors. However, there is an exception. The only exception is if the even number is 2, leaving only $n+1$ or $n$ for an shorter side equation, and crossing out the even factor. Let's try n+1. $2*3/2=3$, so n+1 can't work. Now, that leaves us with n, let's check! $1*2/2=1$. 1 is a perfect square, so $f(n)$ is a perfect square ONLY WHEN n is 1.

That sounds like a trolling post - no word there makes any sense

I appreciate the attempt but I would like to point out a few things: 1) $f(n)$ is not $\frac{n(n+1)}{2}$ 2) If $f(n)$ was $\frac{n(n+1)}{2}$ then there would exist more solutions to the equation $\frac{n(n+1)}{2}=x^2$ (in fact there would exist infinite by pell equations!) I'm not 100% sure if this is correct or not but I believe this is the intended method:

I may be missing something, but what exactly are you counting? If I got the problem right, not only you don't need every number from $ \mathcal{N}$ to be prime with $n$, but actually you don't need any of those numbers to be prime with $n$. For example, take $n=6$ and $ \mathcal{N}=\{2,3,4\}$. No one of these numbers is prime with $n$, yet this set satisfies the given condition. Also, your formula gives $f(3)=3$. A simple check shows that $f(3)=5: \{1\},\{1,2\},\{1,3\}, \{2,3\}, \{1,2,3\}$.

odnerpmocon wrote: If I got the problem right, not only you don't need every number from $ \mathcal{N}$ to be prime with $n$, but actually you don't need any of those numbers to be prime with $n$. Exactly. The value $2^{\varphi(n)}-1$ counts the number of possible non-empty subsets $\mathcal{M} \subseteq \{1,\ldots,n\}$ such that $\text{gcd}(n,m)=1$ for all $m \in \mathcal{M}$, that is clearly smaller than $f(n)$..

Okay, wait. Do we consider sets with only $1$ element or not? I counted them but they can be easily eliminated out anyway. I got a recursion that's kinda useless (but, hopefully correct ). Let $g(n)$ be the number of subsets not having the given property. Then, we have $g(n)=2^n-1-f(n)$. Now, $g(n)$ includes the number of subsets of ${ 1,2, \cdots n-1 } $ without the property and also those which contain $n$ and don't have the property. Again, the second type of subsets are chosen only from the $n- \phi(n)$ numbers which aren't co-prime with $n$. So, we arrive at \[ g(n)=g(n-1)+2^{n- \phi(n)}-1 \] Substituting $g(n) = 2^n-1-f(n)$, we get \[ f(n)-f(n-1)= 2^{n-1} - 2^{n- \phi(n)-1}+1 \] I cannot understand how to handle the $2^{\phi(n)}$ thing, so this is as far as I got.

dibyo_99 wrote: Again, the second type of subsets are chosen only from the $n- \phi(n)$ numbers which aren't co-prime with $n$. So, we arrive at \[ g(n)=g(n-1)+2^{n- \phi(n)}-1 \] Your argument works only for $n=p^k, p \in \mathbb P, k \in \mathbb N$. Look at the example I wrote above - not every choice of numbers which aren't coprime to $n$ leads to a set without the given property. I also thought about a recursion, and I think one can be found using inclusion-exclusion, but it would be very complicated and probably useless.

Indeed, it is not too difficult to come up with a recursive formula. Counting all non-empty subsets of $\{1,...,n\}$ and considering all possible values $d$ for the gcd, we get \[ 2^n-1 = \sum_{1 \le d \le n} f(\lfloor \frac n d \rfloor), \] which expresses $f(n)$ in terms of $f(1),...,f(n-1)$. This can be simplified a little bit by subtracting the same formula for $n-1$: \[ 2^{n-1} = \sum_{1 \le d \le n} f(\lfloor \frac n d \rfloor) - \sum_{1 \le d \le n-1} f(\lfloor \frac {n-1} d \rfloor) = \sum_{d \mid n} f(\frac n d) - f( \frac n d -1), \] where $f(0) := 0$. I don't really see how this is useful for the given problem, but at least this helps computing values for $f(n)$ for small $n$.

I didn't check your formula but its final form hints to Möbius inversion, so it might be quite useful, if correct.

Ok, so let me post my solution (and indeed, the PIE formulae will work). Computing (with ease) $f(n)$ for small values of $n$ yields $f(1)=1$, $f(2)=2$, $f(3)=5$, $f(4)=11$, $f(5)=26$, $f(6)=53$. Since for these values $2\leq n\leq 6$ we have $f(n) \equiv -1 \pmod{3}$, this suggests the hidden truth is that $f(n) \equiv -1 \pmod{3}$ for all $n>1$, and thus not a perfect square. Let us take, for ease of notations, $f(0) = 0$. Denote $g(n) = f(n) - f(n-1)$ for all $n\geq 1$; then $f(n) = f(n-1) + g(n)$, so it is enough to prove $g(n) \equiv 0 \pmod{3}$ for all $n > 2$. We have $g(1)=g(2) = 1$, and let us assume $g(\nu) \equiv 0 \pmod{3}$ for all $2< \nu < n$, in order to prove our claim by strong induction. Let $\displaystyle n = \prod_{k=1}^m p_k^{\alpha_k} > 1$; then clearly, by the Principle of Inclusion/Exclusion, \[g(n) = \dfrac {1} {2} \left (2^n - \sum_{1\leq k\leq m} 2^{n/p_k} + \sum_{1\leq i<j\leq m} 2^{n/p_ip_j} - \cdots + (-1)^m 2^{n/p_1p_2\cdots p_m}\right ).\] (For any prime $p\mid n$ consider $A_p = \{1 < k < n \ ; \ p\mid k\}$. Then $|A_p| = (n/p) - 1$ and $\displaystyle \left |\bigcap_{p\in P} A_p\right | = \left (n/\prod_{p\in P} p\right ) - 1$ for any set $P$ of distinct primes dividing $n$. Now, for any set $\mathcal{N}$ containing $n$, such that $\gcd(\nu \in \mathcal{N}) > 1$, there must exist a prime $p \mid \nu \mid n$. The number of such sets $\mathcal{N}$ is then equal to $2^{|A_p|}$, and the total count of all sets $\mathcal{N}$ will be given by PIE.) But this writes (the terms with $d$ not squarefree matter not, since then $\mu(d)=0$) as $\displaystyle g(n) = \dfrac {1} {2} \sum_{d\mid n} \mu(d)2^{n/d}$, so by Möbius' inversion formula, $\displaystyle 2^{n-1} = \sum_{d\mid n} g(d)$. By the induction step $g(\nu) \equiv 0 \pmod{3}$ for all $2<\nu<n$, this rewrites as $\bullet$ for $n$ odd $\displaystyle \ g(n) = 2^{n-1} - g(1) \equiv 1 - 1 = 0\pmod{3}$; $\bullet$ for $n$ even $\displaystyle g(n) = 2^{n-1} - (g(1) + g(2)) \equiv 2 - (1 + 1) = 0\pmod{3}$. Thus the claim is proved, achieving $g(n) \equiv 0 \pmod{3}$ in both cases. Alternatively, once we reach the formula $\displaystyle 2g(n) = \sum_{d\mid n} \mu(d)2^{n/d}$, we may avoid using Möbius' inversion formula; instead just using $\displaystyle \sum_{d\mid n} \mu(d) = 0$ for all $n>1$, and the fact $\mu$ is a multiplicative arithmetic function. Let now have $n=2^\alpha n'$, with $\alpha \geq 0$ and odd $n'$; moreover $n>2$, so \makebox{$(\alpha+1)n' > 2$.} Then when $2^\alpha \mid d$ take $d=2^\alpha d'$, so $\mu(d) = \mu(2^\alpha)\mu(d')$, and split the sum into $\displaystyle \mu(2^\alpha)\sum_{d'\mid n'} \mu(d')2^{n'/d'} + \sum_{d\mid n/2} \mu(d)2^{n/d}$. Now, for $0\leq \alpha \leq 1$ we have $n' > 1$ and so $\displaystyle \sum_{d'\mid n'} \mu(d')2^{n'/d'} \equiv 2\sum_{d'\mid n'} \mu(d') = 0 \pmod{3}$, while $n'=1$ forces $\alpha \geq 2$ and so $\mu(2^\alpha) = 0$; on the other hand (just for $\alpha > 0$, when needed) $\displaystyle \sum_{d\mid n/2} \mu(d)2^{n/d} = \sum_{d\mid n/2} \mu(d)(2^2)^{(n/2)/d} \equiv \sum_{d\mid n/2} \mu(d) = 0 \pmod{3}$, since $n/2>1$. Remark. The recurrence formula obtained even allows us to iterate and compute $\displaystyle f(n) = \sum_{\nu=1}^n g(\nu) = \dfrac {1} {2} \sum_{\nu=1}^n \sum_{d\mid \nu} \mu(d)2^{\nu/d}$.

solyaris wrote: \[ 2^n-1 = \sum_{1 \le d \le n} f(\lfloor n/d \rfloor), \] Even without Moebius inversion, $f(1)=1$ and $f(2)=2$. Suppose that in $\mathbb{Z}/3\mathbb{Z}$ we have $f(m)\equiv 2$ for all $2\le m\le n-1$, then: \[{ f(n)\equiv 2^n-1-(\sum_{2\le i\le \lfloor n/2 \rfloor}{\underbrace{f(\lfloor n/i\rfloor )}_{\equiv 2}}+\sum_{\lfloor n/2\rfloor +1\le i\le n}{\underbrace{f(\lfloor n/i\rfloor )}_{\equiv 1}}})\equiv2.\] The claim follows by induction and from the fact that $(\frac{2}{3})=-1$. Another solution here (Pr.3), which I posted some years ago..