Finding the number of subsets of a set such that an element divides the succeeding element.

We denote with $a[n], n\geq 1$ the number of special sequences and with $b[n], n\geq 1$ the number of special sequences where each element contains $n$ as greatest element. We observe $a[n]$ contains all special sequences of $a[n-1]$ together with all special sequences $b[n], (n>1)$.

We have \begin{align*} &a[1]=b[1]=\left|\{(1)\}\right|=1\\ &a[n]=a[n-1]+b[n ] \qquad\qquad n> 1 \end{align*}

In order to find $b[n]$ we need to analyse the prime factor decomposition of $n$. We create a small knowledge base of numbers which we need to factorise $K=1,\ldots,22$.

Let $p,q$ be primes. We obtain \begin{align*} b[p]&=\left|\{(p),(1,p)\}\right|=2\\ b[p^2]&=\left|\{(p^2),(1,p^2),(p,p^2),(1,p,p^2)\}\right|=4\\ b[p^3]&=\left|\{(p^3),(1,p^3),(p,p^3),(p^2,p^3),(1,p,p^3),(1,p^2,p^3),(1,p,p^2,p^3)\}\right|=8\\ b[p^4]&=2^4=16\\ b[pq]&=\left|\{(pq),(1,pq),(p,pq),(q,pq),(1,p,pq),(1,q,pq)\}\right|=6\\ b[p^2q]&=\left|\{(p^2q),(1,p^2q),(p,p^2q),(q,p^2q),(p^2,p^2q),(pq,p^2q),\right.\\ &\qquad(1,p,p^2q),(1,q,p^2q),(1,p^2,p^2q),(1,pq,p^2q),\\ &\qquad(p,p^2,p^2q),(p,pq,p^2q),(q,pq,p^2q),\\ &\qquad\left.(1,p,p^2,p^2q),(1,p,pq,p^2q),(1,q,pq,p^2q))\}\right|=16\\ \end{align*}

Now it's time to harvest. We obtain \begin{align*} \color{blue}{a[15]}&=a[14]+b[13]=a[13]+b[12]+b[13]\\ &=a[1]+\sum_{j=2}^{13}b[j]\\ &=1+\sum_{j\in\{2,3,5,7,11,13\}}b[j]+\sum_{j\in\{4,9\}}b[j]+\sum_{j\in\{6,10,14,15\}}b[j]+b[8]+b[12]\\ &=1+6b[p]+2b[p^2]+4b[pq]+b[p^3]+b[p^2q]\\ &=1+12+8+24+8+16\\ &\,\,\color{blue}{=69}\\ \color{blue}{a[19]}&=a[15]+b[16]+b[17]+b[18]+b[19]\\ &=69+b[2^4]+b[17]+b[3^2\cdot 2]+b[19]\\ &=69+b[p^4]+2b[p]+b[p^2q]\\ &=69+16+4+16\\ &\,\,\color{blue}{=105}\\ \color{blue}{a[22]}&=a[19]+b[20]+b[21]+b[22]\\ &=105+b[2^2\cdot5]+b[3\cdot7]+b[2\cdot11]\\ &=105+b[p^2q]+2b[pq]\\ &=105+16+12\\ &\,\,\color{blue}{=133}\\ \end{align*}

Note: Interestingly, the sequence $\left(a[n]\right)_{n\geq 1}=(1,3,5,9,11,17,19,27,31,\ldots)$ doesn't seem to be archived in OEIS, but the sequence $\left(b[n]\right)_{n\geq1}=(1,2,2,4,2,6,2,8,4,6,2,16,2,\ldots)$ is archived in OEIS as A067824.