The answer is $4$

Whoa. Sorry to revive, but is there an elementary solution? (e.g. without Lagrange Interpolation Formula)

Yes, I know of another solution. But I don't think Lagrange's Interpolation is something non-elementary. Anyway , Solution: The fact that $p$ has period of $3$, suggest that there could be something to do with cube root of unity.Note that $p(j)- 1=\frac{2}{\sqrt{3}}\text{Im}(e^{\pi i/3}\omega^j)$ , $j= 0,1,2\cdots,3n$. where $\omega= e^{2\pi i/3}$. We claim $p(x)= 1+ \frac{2}{\sqrt{3}}\sum_{k=0}^{3n}\binom{x}{k}\text{Im}(e^{\pi i/3}(\omega-1)^k)$ (*). Just check that it meets all the conditions of the problem.From (*), using binomial theorem we get $p(3n+1)= 1+ \frac{2}{\sqrt{3}}\text{Im}e^{\pi i/3}(\omega^{3n+1}- (\omega-1)^{3n+1})$. We have $\omega -1 = i\sqrt{3}(e^{\pi i/3})$, and by De Moivre's theorem , $p(3n+1) = 1+ 2(\sqrt{3})^{3n}\sin \left (\frac{(3n+1)\pi}{6} \right )$. We are given $p(3n+1)= 730 = 1+ 3^6$ and it is obvious that this requires $n=4$. $\square$

Here is another elementary solution.

Let \[f(m)=\begin{cases}1 & m\equiv 0\pmod{3} \\ 0 & m\equiv 1\pmod{3} \\ -1 & m\equiv 2\pmod{3}\end{cases}.\]Note that \[f(m)=\frac{1}{3}(1+\omega^m+\omega^{2m})-\frac{1}{3}(1+\omega^{m-2}+\omega^{2m-4})=\frac{1}{3}(1-\omega)\omega^m + \frac{1}{3}(1-\omega^2)\omega^{2m}\]where $\omega=e^{2\pi i/3}$. By the binomial theorem, we have that \[f(m)=\sum_{k=0}^\infty\left[\frac{1}{3}(1-\omega)^{k+1}+\frac{1}{3}(1-\omega^2)^{k+1}\right]\binom{m}{k}.\]The problem tells us that $P(x)=f(x)+1$ for $x\in\{0,1,\ldots,3n\}$ and $\deg P=3n$, so we must have \[P(x)=1+\sum_{k=0}^{3n}\left[\frac{1}{3}(1-\omega)^{k+1}+\frac{1}{3}(1-\omega^2)^{k+1}\right]\binom{x}{k}\]since $P(x)$ is a polynomial of the correct degree that agrees with $f(m)$ for $\deg P+1$ points. Thus, we have \[P(3n+1)=1+f(3n+1)-\left[\frac{1}{3}(1-\omega)^{3n+2}+\frac{1}{3}(1-\omega^2)^{3n+2}\right],\]and since $f(3n+1)=0$, we have \[\frac{1}{3}(1-\omega)^{3n+2}+\frac{1}{3}(1-\omega^2)^{3n+2}=-729.\]Note that \[1-\omega=\frac{3}{2}-\frac{\sqrt{3}}{2}i=\sqrt{3}i\omega^2,\]so the given equation reads \[\frac{2}{3}\Re((\sqrt{3}i\omega^2)^{3n+2})=-729.\]It is easy to check that the only positive integer solution to this is $\boxed{n=4}$.

Here is the useful information for solving the problem. Firstly, expand the equation $(1-x)^k$. Secondly, put $x=1$, $x=\omega$ and $x=\omega^2$ in the expansion, where $\omega= e^{2\pi i/3}$ is a cubic root of unity. Finally, add all these three equations and take $k=3n+1$. Recall that $\omega^3=1$ and $1+\omega+\omega^2=0$ and remember the De Moivre's theorem: \[ \left(r \cdot \cos \left(\theta\right)+r \cdot i \cdot \sin \left(\theta\right)\right)^{n} = r^{n} \cdot \cos \left(n \cdot \theta\right)+r^{n} \cdot i \cdot \sin \left(n\cdot\theta\right)\].

Nice...Thanks