Interesting $0, 1$ sequence of numbers,after $n>2, a_n$is composite.

Question

Let us have a finite sequence with only $0$ and $1$ digit in our numbers(it can begin with $0$ too). $a_n$ is the number, which we get if we write our number $n$ times next to each other. Prove, that if $n>2$, our numbers are composite.

It is quite hard to understand, here is some examples. Let us have the $01$ sequence, then:

$a_1=1, a_2=101, a_3=10101...$(the 0 at the beginning doesn't count, you can see that $a_3$ can't be a prime)

If we have the $101$ sequence, then:

$a_1=101, a_2=101101...$

How do I prove this in general? It seems hard, but maybe there is a good tactic? :) Thanks.

Answer 1

So for the 101 sequence, this is obvious as $101|a_n$ for all $n$.

The same reasoning will suffice for any sequence beginning with 1 (eg: $10001$, etc.)

If your sequence begins with 0, such as the 01 sequence mentioned, you begin with a truncated sequence due to ignoring the initial zeroes in $a_1$, so the same reasoning won't work.

Let $s=0\ldots1\ldots$ denote your string of length $N$ where the first $n$ digits are 0. let $r=1\ldots$ be the reduced string obtained form deleting the $n$ initial 0's of $s$, so $r$ is of length $N-n$.

If $r \neq 1$, then $a_2 = rs= r0\ldots0r$ is divisible by $r$, and this same idea works inductively for $a_n$.

For $r=1$, then this seems more subtle. I will edit when I figure it out.

Answer 2

If the finite sequence has length $l$, then $a_n$ is divisible by $1 + 10^l + 10^{2l} + \cdots + 10^{(n-1)l}$

So the question reduces to, "is $1 + 10^l + 10^{2l} + \cdots + 10^{(n-1)l}$ composite?"

We have $(1 + 10^l + 10^{2l} + \cdots + 10^{(n-1)l})(10^l - 1) = (1+10^n+10^{2n}+ \cdots +10^{(l-1)n})(10^n - 1)$

Thus if $l>1, n>l$, letting $d = \gcd(10^n - 1, 10^l - 1)$ we have $10^n-1 \over d$ divides $1 + 10^l + 10^{2l} + \cdots + 10^{(n-1)l}$

This shows that $a_n$ is eventually composite for any initial sequence other than $1$.

If the initial sequence is one, the question is, "is $1\cdots11$ composite?"

The answer is, not neccesarily. See http://oeis.org/A004023. This has previously been discussed on math.se at When is the number 11111....1 a prime number?.