Is this a recurrence for the characteristic sequence of composite numbers?

Question

The characteristic sequence of composite numbers is equal to 1 if $n$ is not a prime number and equal to 0 if $n$ is a prime number, starting:

$$1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1,...$$

where the zeros are at positions of prime numbers: $2,3,5,7,11,...$

Is this a recurrence for the characteristic sequence of composite numbers:

$$t(\text{n},1)=1$$

$$t(1,\text{k})=1$$

$$t(n,k)=\text{If} \; n\geq k: 1-\prod _{i=1}^{k-1} t(n-i,k) \;\text{else}: 1-\prod _{i=1}^{n-1} t(k-i,n)$$

which is a matrix $t$ starting:

$$t=\left( \begin{array}{cccccccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 \end{array} \right)$$

where the main diagonal is a sequence $t(n,n)$ starting:

$$t(n,n) = 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1,...$$

I realize that there is multiplication by zero, and recurrence might be the wrong word.

Mathematica 8:

Clear[nn, t, n, k, i];
nn = 90;
t[n_, 1] = 1;
t[1, k_] = 1;
t[n_, k_] := 
  t[n, k] = 
   If[n >= k, 1 - Product[t[n - i, k], {i, 1, k - 1}], 
    1 - Product[t[k - i, n], {i, 1, n - 1}]];
Table[t[n, n], {n, 1, nn}]

A simpler program for a more Riemann zeta like table is possible:

Clear[t, n, k, i, nn];
nn = 105;
t[n_, k_] := 
  t[n, k] = 
   If[n == k, 1, 
    If[k == 1, 1 - Product[t[n, k + i], {i, 1, n - 1}], 
     If[Mod[n, k] == 0, t[n/k, 1], 1], 1]];
Table[t[n, 1], {n, 1, nn}]

which gives a table $t$ starting:

$$t = \left( \begin{array}{cccccccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \end{array} \right)$$

---

Edit 5.7.2014: Just for memory:

Clear[t];
nn = 94
t[1, 1] = 1;
t[n_, k_] := 
  t[n, k] = 
   If[n == k, n*(1 - Product[t[n, k - i], {i, 1, k - 1}]), 
    If[n > k, t[n - k, k], 1]];
Table[t[n, n], {n, 1, nn}]

Output:

{1, 0, 0, 4, 0, 6, 0, 8, 9, 10, 0, 12, 0, 14, 15, 16, 0, 18, 0, 20, 21, 22, 0,...}

Answer 1

Yes. First, note that $t(n,k)=t(k,n)$ for all $(n,k)$ (this is trivial by induction). Now we prove a couple lemmas.

Lemma 1: If $\gcd(n,k)=1$ then $t(n,k)=1$.

Proof: We prove the contrapositive by induction on $(n,k)$. Suppose $t(n,k)=0$, and WLOG suppose $n\geq k$. We know this cannot happen for $n=k=1$, and if $n=k>1$ then $\gcd(n,k)=k>1$. So let us assume $n>k$. Since $t(n,k)=0$, we have $t(m,k)=1$ for $m=n-k+1,\dots,n-1$. But since $n>k$, we also have $n-1\geq k$, so $t(n-1,k)=1$ implies $t(j,k)=0$ for some $j$ from $n-k$ to $n-2$. The only possiblity is thus that $t(n-k,k)=0$. By induction, this implies $\gcd(n-k,k)>1$. But $\gcd(n,k)=\gcd(n-k,k)$, and thus $\gcd(n,k)>1$, as desired.

[Note that this argument is closely related to the Euclidean algorithm. Indeed, if you unravel what the induction is doing, it is saying that if $t(n,k)=0$, then $t(n',k')=0$ for all pairs $(n',k')$ obtained when performing the Euclidean algorithm on $(n,k)$. In particular, at the end of the Euclidean algorithm you have $t(d,d)=0$ for $d=\gcd(n,k)$, which implies $d\neq 1$.]

Lemma 2: If $k$ is prime and $k\mid n$, then $t(n,k)=0$.

Proof: Suppose $k$ is prime and $k\mid n$. Then $k\leq n$, so $t(n,k)$ is defined to be $0$ iff $t(m,k)=1$ for $m=n-k+1,\dots,n-1$. Since $k$ divides $n$, none of these values of $m$ are divisible by $k$. Since $k$ is prime, this means they are all relatively prime to $k$, and so by Lemma 1, $t(m,k)=1$ for all of them. Thus $t(n,k)=0$.

Finally, we can prove your desired statement.

Theorem: $t(n,n)=0$ iff $n$ is prime.

Proof: The case $n=1$ is true by definition. If $n$ is prime, then $t(n,n)=0$ by Lemma 2 with $k=n$. If $n$ is composite, then $t(n,n)$ is defined to be $1$ iff $t(m,n)=0$ for some $m<n$. Taking $m$ to be a prime factor of $n$, we have $t(m,n)=t(n,m)=0$ by Lemma 2, and therefore $t(n,n)=1$.