Вывести замкнутую формулу предиката из рекуррентной

[IgorSukharev]

Дан предикат $p(n)$, где $n \in \mathbb{Z}_{>0}$.
Дана рекуррентная формула:
\begin{cases} p(1)=\text{F};\\ p(2n)=p(n);\\ p(2n+1) = p(n) \equiv p(n+1). \end{cases}$$
Найти замкнутую формулу для $p(n)$.
Я уже решал эту задачу, но мне интересно, как её решите вы и есть ли более короткие решения.

[Not_Al]

Сделаем гипотезу:

$$p(n)=\begin{cases}T, 3|n;\\ F,\text{иначе}\end{cases}$$

Покажем по индукции. $p(1)=p(2)=F$, и $p(3)=(p(1)\equiv p(2))=T$, пусть это верно для всех $n<N$, докажем ее для $N$.
1) Предположим $p(N)=T$, тогда если $2|N$, то $p(N)=p(\frac{N}{2})$ , получается $3|\frac{N}{2}$, а значит и делит $N$.
Если $N$ нечетно, то $N=2k+1$ и $p(N)=(p(k)\equiv p(k+1))$. Покажем, что $p(k)=p(k+1)=F$. Предположим, что $3|k$ , тогда, $p(k+1)\neq p(k) $, противоречие с предположением 1. Следовательно, 3 не делит ни $k$, ни $k+1$ , значит $k=3t+1$ и $N=2(3t+1)+1=6t+3$, то что надо.
2) Предположим, что $p(N)=F$, тогда, если $2|N$, то 3 не делит $p(\frac{N}{2})$ и все доказано.
Если $N=2k+1$, то если $3|k$, то 3 не делит $N$ и все доказано, аналогично, если $k=3t+2$. Рассмотрим случай $k=3t+1$, тогда $p(k)=p(k+1)$ , но это противоречит предположению 2.