For each day, $d$, let $E_d$ be the event that there is a birthday on day $d$, but there are not any birthdays on days $d+1,d+2,\dots,d+g$. A gap of length $g$ occurs if and only if $E_d$ occurs for some $d$. That is,
$$
P(\text{no gaps of length $g$})=P(E_1^c\cap E_2^c\cap \dots\cap E_{365}^c)
$$
To compute this, we use the principle of inclusion exclusion:
$$
P(\text{no gaps of length $g$})=\sum_S(-1)^{|S|}P(E_{d(1)}\cap E_{d(2)}\cap \dots \cap E_{d(k)})
$$
where $S=\{d(1),d(2),\dots,d(k)\}$ ranges over all $2^{365}$ subsets of days.
We must figure out the probabilities of the intersections $E_{d(1)}\cap E_{d(2)}\cap \cdots \cap E_{d(k)}$. If any of the intervals $[d(i),d(i)+g]$ and $[d(j),d(j)+g]$ overlap, then this probability of this intersection is zero; the $E_d$ were defined carefully so this would be true. Otherwise, we use the principle of inclusion exclusion on this smaller problem to compute
$$
p_k:= P(E_{d(1)}\cap \cdots\cap E_{d(k)}) = \sum_{j=0}^k(-1)^j\binom{k}j\left(1-\frac{kg+j}{365}\right)^n
$$
Finally, we must count for each $k$ the number of ways to choose $\{n(1),\dots,n(k)\}\subseteq \{1,2,\dots,365\}$ so the intervals $[n(i),n(i)+g]$ are pairwise non-overlapping. I claim this number is
$$
n_k=\binom{365-gk}{k}+g\binom{365-gk-1}{k-1}
$$
I leave it to you to verify this is correct. As a hint, the first summand counts choices where none of the gaps cross between two different years, and the second counts ones that do.
We finally get that
$$
P(\text{no gaps of length $g$})=\sum_{k=0}^{\left\lfloor \frac{365}{g+1}\right\rfloor }(-1)^{k}n_kp_k
$$
You've shown that one set of $14$ relatively prime and non-prime values cannot be extended to $15.$ But that doesn't show it for all sets of $14$ non-prime relatively prime values. Another $n=14$ example set is $\{2p_{27},3p_{26},5p_{25},\cdots,41p_{15},43^2\},$ where $p_{15}=47,p_{16}=53,\dots,p_{27}=103.$
Your instinct is correct, but it is just not a complete proof.
This is a neat problem, because the intuition feels instinctive, but proving it correctly requires some technique.
Given any $m>1$, define $d(m)$ to be the smallest prime divisor of $m.$
Claim 1: If $2\leq m\leq 2004$ is not prime, $d(m)\leq 43.$
Proof: Otherwise, $m\geq p_1p_2$ for some pair of primes $p_1,p_2$ and $p_i\geq 47.$ But then $m\geq 47^2=2209.$
Claim 2: If $m_1,m_2>1$ are relatively prime, then $d(m_1)\neq d(m_2).$
Proof: If $p=d(m_1)=d(m_2)$ then $p$ us a common factor of $m_1$ and $m_2.$
Claim 3: Given any set $S=\{m_1,\cdots,m_{15}\}$ of non-prime values with $2\leq m_i\leq 2004.$ Then the set is not pairwise relatively prime
Proof: There are at most $14$ distinct possible values of $d(m_i)$ by claim $1,$ since there are $14$ distinct primes $\leq 43$. Thus $d(m_i)=d(m_j)$ for some $i\neq j.$ Then by claim $2,$ $m_i$ and $m_j$ are not relatively prime.
Your example of the squares $S=\{2^2,\cdots,43^2\}$ shows that $n=15$ is the smallest such $n$ for which it is true.
Best Answer
You want to minimize the telescopic sum for $a_{20}$: