Circle Cover Numbers

It is clear that we have $2a_{i}\equiv a_{i}+1(modn)$ . Thus it follows that a sequence $A$ is in fact $\left \{ k,2k,4k,...\right \}$ except with its values taken modulo $n$ .

Now, suppose $n$ has circle cover $2$ . Clearly $n$ must occur infinitely many times in one of the sequences. But once that sequence has hit $n$ as a value of some $a_{i}$ , it stays at $n$ forever. Thus $1,2,...,n-1$ only occur finitely many times in that sequence. Therefore it follows that the other sequence achieves all of the values $1,2,...,n-1$ infinitely many times. This implies that $ord_{n}(2)=n-1$ (if it were less, the sequence would begin to repeat before reaching all $n-1$ numbers) and therefore $n$ is a prime for which $2$ is a primitive root. As $2$ is a primitive root, it is a quadratic nonresidue and thus $n\equiv 3,5(mod8)$ . Then by checking the primes under $100$ which are $3$ or $5\quad modulo 8$ we find that $2$ is a primitive root for $n=3,5,11,13,19,29,37,53,59,61,67,83,$ implying the answer is $12$ .

Relabel the points with 0, 1, ..., n-1. After relabelling, at each point $a_i$ , the next is obtained via $a_{i+1} \equiv 2a_i + 1 \pmod n$ which gives

$a_{i+1}+1 \equiv 2(a_i+1) \pmod n \implies a_k + 1\equiv 2^k(a_0+1) \pmod n$ .

Letting $b_k = a_k + 1\pmod n$ for k=0, ..., we have

$b_k \equiv 2^k b_0 \pmod n$ .

Suppose the Circle Cover Number of n is 2 and n>2.

Thus, there are two sequences $b_k \equiv 2^k b_0 \pmod n$ and $c_k \equiv 2^k c_0 \pmod n$ such that each of i = 0, ..., n-1 occurs infinitely many times in one of the sequences.

If $b_k = 0$ for some k, then $b_{k+1} = b_{k+2} = \ldots = 0$ so the remaining points only occur finitely many times in this sequence. Thus, the remaining points 1, ..., n-1 must occur infinitely many times in the other sequence $(c_k)$ , i.e. the powers of 2 run through all 1, 2, ..., n-1. If n is composite, this is impossible since if prime p divides n, by the time $c_k = p \pmod n$ all the subsequent terms $c_{k+1}, c_{k+2}, \ldots$ are divisible by p, which means the values which are not divisible by p only occur finitely many times.

Thus n=p is prime and powers of 2 run through all {1, 2, ..., p-1} mod p. Hence, we wish to look for all primes p such that 2 is a generator (or primitive root) modulo p. We can test this one at a time for all p<100, but the process can be sped up by observing that if 2 is a square mod p, then $2^{(p-1)/2} \equiv 1\pmod p$ so 2 is not a generator mod p. Hence, we only need to look at primes $p \equiv 3, 5\pmod 8$ . Out of these, only 43 fails. Hence, p = 3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83. Together with n=1 (note: n=2 is not a solution), we have 13 values of n.

It is clear that we have $2a_i \equiv a_{i+1} \pmod{n}$ . Thus it follows that a sequence $A$ is in fact $\{k, 2k, 4k, ... \}$ except with its values taken modulo $n$ .

Now, suppose $n$ has circle cover $2$ . Clearly $n$ must occur infinitely many times in one of the sequences. But once that sequence has hit $n$ as a value of some $a_i$ , it stays at $n$ forever. Thus $1,2,...,n-1$ only occur finitely many times in that sequence. Therefore it follows that the other sequence achieves all of the values $1,2,...,n-1$ infinitely many times. This implies that $\text{ord}_n(2) = n-1$ (if it were less, the sequence would begin to repeat before reaching all $n-1$ numbers) and therefore $n$ is a prime for which $2$ is a primitive root. As $2$ is a primitive root, it is a quadratic nonresidue and thus $n \equiv 3,5 \pmod{8}$ . Then by checking the primes under $100$ which are $3$ or $5$ modulo $8$ we find that $2$ is a primitive root for $n=3,5,11,13,19,29,37,53,59,61,67,83$ , implying the answer is $12$ .

Firstly note that the circle cover number of 1 is 1. Also, note that $a_{i+1}\equiv2a_i\pmod n$ .

Assume that the circle cover number of $n$ is 2; we shall find out some properties that $n$ must have.

If $n$ is even then note that for every sequence $\{a_j\}_{j=0}^\infty$ , every term (except possibly the first term) is even. Hence every set $S$ of sequences contains only a finite number of odd numbers, so $S$ cannot cover the circle. Thus $n$ is odd and greater than 1.

Note that $a_i\equiv2^ia_0\equiv0\pmod n$ if and only if $a_0\equiv0\pmod n$ . Hence if $a_0\neq n$ then the sequence cannot contain the number $n$ . Also, if $a_0=n$ then clearly the sequence only contains the number $n$ . Hence the numbers 1 and $n$ cannot appear in the same sequence, and thus the circle cover number of $n$ is at least 2.

Furthermore, $a_i\equiv2^ia_0\pmod n$ , so $a_i$ is coprime to $n$ if and only if $a_0$ is coprime to $n$ (because $n$ is odd). Thus if $n$ has a prime factor $p<n$ , then the numbers 1 and $p$ cannot appear in the same sequence, and the numbers $p$ and $n$ cannot appear in the same sequence. This means that the circle cover number of $n$ is at least 3, contradiction. Thus $n$ is an odd prime.

We know that a set of two sequences covers the circle for $n$ . From the above discussion we know that one of these sequences must be the constant sequence $(n,n,n,\ldots)$ . Hence the other sequence (call it $B=\{b_j\}_{j=0}^\infty$ ) must contain all the numbers from 1 to $n-1$ .

Let $d$ be the smallest positive integer solution to $2^k\equiv1\pmod n$ . Note that $d$ must exist and satisfies $d\leq n-1$ , because $2^{n-1}\equiv1\pmod n$ by Fermat's Little Theorem. In fact, let $l$ be any other solution to $2^k\equiv1\pmod n$ , and let $r$ be the remainder when $l$ is divided by $d$ ; then $0\leq r<d$ . Write $l=qd+r$ with some integer $q$ ; then $2^r\equiv2^l(2^d)^{-q}\equiv1\pmod n$ This contradicts the minimality of $d$ if $r$ is a positive integer. Thus $r=0$ , and so $d|l$ . In particular, $d|n-1$ .

(Note: $d$ is known as the (multiplicative) order of 2 (mod $n$ ).)

Now $2^d\equiv1\pmod n$ implies $b_{k+d}\equiv2^db_k\equiv b_k\pmod n$ implies $b_{k+d}=b_k$ for all $k$ , so $B$ is periodic with period $d$ . But $B$ contains all numbers from 1 to $n-1$ , so $d\geq n-1$ . Therefore $d=n-1$ .

Conversely, if $d=n-1$ then the sequence $B$ has minimal period $n-1$ , so it contains $n-1$ distinct terms before repeating, so the circle cover number of $n$ is 2. Hence the circle cover number of $n$ is 2 if and only if $d=n-1$ .

In particular, $d=n-1$ implies $d\nmid\frac{n-1}2$ , so $2^{\frac{n-1}2}\not\equiv1\pmod n$ . This happens if and only if $n\equiv3,5\pmod8$ by a special case of the Quadratic Reciprocity Theorem.

This leaves us with 13 possible values of $n$ : 3, 5, 11, 13, 19, 29, 37, 43, 53, 59, 61, 67, 83. But how do we know for which of these values does $d=n-1$ hold? For example, when $n=29$ , how do we check if $d=28$ ?

Well, we do know in this case that $d|28$ . Also, since $2^{\frac{n-1}2}\not\equiv1\pmod n$ we have $d\nmid14$ . From this we deduce that 2 must divide exactly twice into $d$ , i.e. $2^2|d$ and $2^3\nmid d$ , so either $d=4$ or $d=28$ . The first case cannot hold since $2^4\not\equiv1\pmod{29}$ , so $d=28$ .

Checking similarly for the other 12 cases, we see that $d=n-1$ for all these values of $n$ except one (when $n=43$ , $d=14$ ). Hence there are $\boxed{12}$ values of $n$ from 1 to 100 with circle cover number equal to 2.

The problem is about make sequences in that way: a(i+1)=2ai(modn). If n is even (n=2k) we have that when ai=k a(i+1)=2k and then for every t>I at=n so we can't have any sequence with infinite numbers k's. So n is odd. But, with n odd don't exist k such that 2k=n(modn). Só or of the sequences A is n, n, n, n,... . The other sequence will have all the other numbers. So we can choose a0=1 and the sequence will be 2^k(modn) and he must have n-1 numbers. But orda(n) <=phi(n) <=n-1 where we have the equality if and only if n is prime and a is a primitive root modn. For the values of the problem we have that 2 is a primitive root for 12 values

For a fix $n$ , consider a circle placed with number $1,2,...,n$ around a circle clockwise.

Note that if we start from $k < n$ , the next position traversed by $k$ position will be $p$ where $p$ is in the complete residue system $\{1,2,...,n\}$ and $p=2k$ (since we will be travel around with period $n$ ). So this sequence can be written as $\{p_i\}^{\infty}_{i=0}$ where $p_i$ is in the complete residue system $\{1,2,...,n\}$ and $p_i = 2^{i}k$ .

We can see that the next position of $n$ will always be $n$ for the rest of the sequence that contains $n$ . So we can let $A_0 = \{n,n,n,...\}$ be the sequence that covers $n$ . In order to make Circle Cover Number of n to be 2, the numbers $1,2,...,n-1$ must be covered in one sequence. Therefore, such $n$ must satisfies that $\{2^0, 2^1, ... , 2^{n-1}\}$ is a complete residue system, i.e., it has $2$ as a primitive root modulo $n$ .

It can be checked by direct computation or by the aid of Euler's criterion that such $n\leq100$ are: $3,5,11,13,19,29,37,53,59,61,67,83$ .

Therefore, the answer is 12.

We define that a sequence covers a set if all the elements of the set are present infinitely many times in the sequence.

It is obvious that the numbers in each sequence are defined by $a_{i+1} \equiv 2a_i (mod n)$

*Claim:- The necessary and sufficient condition for the Circle Cover number of $n$ to be $2$ is that the numbers $(2^i)_{i= 0}^{n-2}$ have distinct residues modulo $n$ and that $2^{n-1} \equiv 1 (mod n)$ *

*Proof:- * Note that if finitely many terms of any sequence are deleted from the left, the condition of an integer appearing infinitely many times in the sequence still remains unaltered. Now consider any sequence that contains $n$ . Delete the terms of this sequence which appear before $n$ . Then note that the terms after $n$ will be $n, n, n, ...$ . So any sequence which contains $n$ must cover $n$ and only $n$ . Since the set of two sequences cover the entire set $1, 2, ..., n$ , the other sequence must cover the set $1, 2, ..., n-1$ . Delete the terms of this sequence which appear before $1$ . Then note that the resultant sequence will be of the form $2^0, r_n(2^1), r_n(2^2), ..., r_n(2^{n-2})$ , where $r_n(x)$ is the remainder when $x$ is divided by $n$ if $n$ does not divide $x$ , $r_n(x) = n$ if $n \mid x$ . For this sequence to cover $1, 2, ..., n-1$ , the residues of the powers of $2$ must vary through $1$ to $n-2$ , i.e they must all be distinct. Also note that we don't want any number to be skipped after once the sequence $1, 2, ..., n-2$ appears, or else we can delete the terms before the skipped number, and obtain a sequence which does not contain that number. So we must have the next number equal to $1$ , so $2^{n-1} \equiv 1(mod n)$ . Hence the claim is proved.

Now $2^{n-1} \equiv 1(mod n)$ implies $n$ is prime. Also we must have $2$ a primitive root modulo $n$ . (the next part of my solution is similar to that of $C L.$ )
If $2$ is a quadratic residue modulo $n$ , $2^{(n-1)/2} \equiv 1(mod n)$ , so $n$ does not satisfy the conditions [the conditions for $a$ to be a primitive root modulo $n$ is that $a^{\frac{\phi(n)}{k}}$ is not congruent to $1$ modulo $n$ , where $k$ ranges over all positive prime divisors of $\phi(n)$ ). From quadratic reciprocity we conclude that the primes are of the form $8m+3$ and $8m+5$ . All such primes from $1$ to $100$ are $3, 5, 11, 13, 19, 29, 37, 41, 43, 53, 59, 61, 67, 83$ . But checking these we find out that $41$ and $43$ do not satisfy the conditions. So our answer will be $12$ .

Note several facts:

1. Because $S$ has finite size, for a number to appear an infinite number of times in the sequences of $S$ , it must appear an infinite number of times in at least one sequence in $S$ .
2. Because $n$ is finite and the sequences are finite-step iterative, any sequence $A_i$ will repeat. Then the numbers that appear an infinite number of times in $A_i$ are exactly the numbers in the periodic part. We can throw away any initial elements as irrelevant to our problem, defining sequences only by their repeating parts.
3. If a sequence contains $n$ , then it has the repeating part $[n]$ . This can be proven inductively, from $[a_i=n]\Rightarrow [a_{i+1}=n]$ . So, for a set $S$ to cover $\{1,2,...,n\}$ , one of the sequences in $S$ must have periodic part $n$ .
4. If $n=jk$ for positive integers $j,k$ , then any sequence containing $j$ would only follow multiples of $j$ from then on (and so the repeating part would be only multiples of $j$ . This can be proven inductively again, from $[a_i=j]\Rightarrow [a_{i+x}=2^xj\textrm{ mod }kj = (2^x\textrm{ mod }k)j]$ .
5. If the set $S=\{A_0,A_1\}$ covers the circle of size $n$ , then one sequence must have periodic part $[n]$ by fact 3 and the other must have a periodic part that contains every number except $n$ . By fact 4, this means that $n$ cannot be composite, or else the second sequence's repeating part could not contain both $1$ and one of the positive factors of $n$ .

Therefore, $n$ must be prime and we must be able to find a repeating part that goes through every number in $\{1,2,...,n-1\}$ . We can rotate the repeating part to start with any of its elements, so we can assume without loss of generality that it starts with $1$ . Then the repeating sequence would be: $[1,2,4,8,...,2^{n-2}]\textrm{ mod }n$ would contain all of the numbers in $\{1,2,...,n-1\}$ and $2^{n-1}=1\textrm{ mod }n$ , which is equivalent to $2$ being a primitive root modulo $n$ .

Looking at the primes below $100$ for which $2$ is a primitive root, we get that the possible choices for $n$ are in $\{3,5,11,13,19,29,37,53,59,61,67,83\}$ . Therefore, there are $12$ possible choices for $n$ which have Circle Cover Number 2.

The problem is about make sequences in that way: a(i+1)=2ai(modn). If n is even (n=2k) we have that when ai=k a(i+1)=2k and then for every t>I at=n so we can't have any sequence with infinite numbers k's. So n is odd. But, with n odd don't exist k such that 2k=n(modn). Só or of the sequences A is n, n, n, n,... . The other sequence will have all the other numbers. So we can choose a0=1 and the sequence will be 2^k(modn) and he must have n-1 numbers. But orda(n) <=phi(n) <=n-1 where we have the equality if and only if n is prime and a is a primitive root modn. For the values of the problem we have that 2 is a primitive root for 12 values