I need to construct a simplest function with period $P$. (Inputs are $n\in \mathbb N$)
One additional condition is that its output is either $0$ or $1$.
I need it be "algebraic" and by that I mean that:
It is written down using only "numbers" (no trigonometric functions or limits for example)
You can only use operations: $+, -, \times, \div, x^t$ (where $x^t$ stands for raising numbers to rational exponents), also absolute value $|x|$ is allowed in the form of $\sqrt{x^2}$
It contains a finite number of terms.
Constructions
I suspect that the function should have a template like:
$$f(n)=\frac{1+(-1)^X}{2}$$
Where $X$ is the rest of the function. (This is just for readability)
For period $P=2$, I'll write $f_2(n)$, then
$$X=n$$
This yields: $0,1,0,1,0,1\dots$
For period $P=4$, I'll write$f_4(n)$, then
$$X=(1-(\sqrt{-1})^n)^4$$
Which yields $0,0,0,1\dots$ repeating.
These are two examples I found.
Can we find all such functions for any $P$ ?
$$f_P(n)= \text{?}$$
Let its period be some zeroes ending with a $1$ for consistency.
Update - $f_{2P}(n)$
For $P>2, P=2k$, I found a recursive generalization:
$$f_{2k}(n)=\sqrt{\left(\frac{f_k(n)}{(-1)^{n/k} }+\frac{1}{2}\right)^2}+\frac{1}{2}$$
Which yields $1$ if $n=2k$ and $0$ otherwise.
Without $(-1)^r$ I don't think it's possible.
With it, let $s(n,k) =\frac1{n}\sum_{j=0}^{n-1}(-1)^{2jk/n} =1$ if $n|k$ and $0$ otherwise.