Answer: only $n$ prime. If $n$ is composite, then let $p \mid n$ be prime, and take $(0, n/p, n/p, n/p, \dots, n/p)$. This fails. Conversely, suppose $n = p$. Assume for contradiction for every index $k$ assume $a_k + a_{k+1} + \dots + a_{\ell(k)} \equiv 0 \pmod p$ for some $\ell(k)$ depending on $k$. Consider the directed graph \[ k \to \ell(k) + 1 \]and find a cycle. This gives us a sum of the form, say \begin{align*} 0 &\equiv (a_1 + \dots + a_{\ell_1}) + \left( a_{\ell_1+1} + \dots + a_{\ell_2} \right) + \dots + \left( a_{\ell_r+1} + \dots + a_p \right) \\ &= c\left( a_1 + \dots + a_p \right) \end{align*}where $c$ is the number of ``complete revolutions''; here $c < p$. So $a_1 + \dots + a_p \equiv 0 \pmod p$, contradiction.

It was also India TST

Definitely one of my favorites from this shortlist The result is true if and only if $n$ is prime. First, if $n$ is composite, let $n = ab$ with $a, b \geq 2$. Choose $a_i = a$ if $1 \leq i \leq b + 1$ and $a_i = 0$ otherwise. The sum of everything is $ab + a$ which is not divisible by $n$, but for each $i$ there exists a $k$ such that $$a_i + a_{i + 1} + \dots + a_{i + k} = ab$$ Where the indices are taken modulo $n$, and this sum is divisible by $n$. Now assume that $n$ is prime. We proceed by contradiction, assuming that for every $i$ there exists a $k$ such that $$a_i + a_{i + 1} + \dots + a_{i + k}$$ Is divisible by $n$. We define a digraph with vertex set $\{1, 2, \dots, n\}$ such that there is a directed edge from $i$ to $j$ if and only if $$a_i + a_{i + 1} + \dots + a_{j - 1}$$ Is divisible by $n$. By hypothesis this graph is simple and every vertex has a positive outdegree, so it has a directed cycle. By summing the expression we considered over each edge of this cycle we find that the sum $$k(a_1 + a_2 + \dots + a_n)$$ Must be divisible by $n$, where $k \leq n - 1$, because each edge stands for a sum of less than $n$ consecutive elements, and thus the total sum has at most $n(n - 1)$ terms. However this is impossible because $n$ divides neither $a_1 + a_2 + \dots + a_n$ nor $k$, and $n$ is prime.

If $n$ is prime, assume we found a counterexample sequence. Visualize the n dots on a circle labeled $D_0, \ldots, D_{n-1}$, with the number $a_i$ assigned to the arc $D_{i-1}D_i$. We think of it as the weight of the arc. To each $0\le i\le n-1$, since the sequence is a counterexample, there must exist an $1\le j\le n$ such that $n|a_{i+1}+\cdots+a_{i+j}$. Assign the big arc $D_iD_{i+j}$ to the point $D_i$. (Call this big arc distinguished).The weight of this arc is thus divisible by $n$. Notice the weight of the whole circle, call it $T$, is not divisible by $n$. Thus, all distinguished arcs are strictly smaller than the whole circle. Now, start at $D_0$ and use its assigned arc $D_0D_i$ to reach $D_i$. Now use $D_i$'s big arc to reach, say, $D_j$, and repeat this process, until we walk over $D_0$ again. Say $D_{x_1}$ is the first dot we land on after walking over $D_0$ again. (Possibly $x_1=0$), and let $J_1$ be the weight of arc $D_0D_{x_1}$. Clearly $n| T+J_1$. Repeat this process again starting from $D_{x_1}$, walking over $D_0$ again and eventually reaching some $D_{x_2}$ (which might be $D_0$). Letting $J_2$ be the weight of $D_0D_{x_2}$, we get $n | 2T+J_2$. We do this $n$ times to get \[ n | T+J_1, 2T+J_2, \cdots, nT+J_n\]from which we see $J_1,\cdots, J_n$ are all different mod $n$, by primality. Thus all the $x_i$'s are different. In particular, there is some $D_{x_i}=D_{n-1}$. That means that we were traversing the circle, and we were at some point $D_a$, then used its assigned arc to go over $D_0$ and land on $D_{n-1}$. But then the arc assigned to $D_a$ is equal to (or more than) the complete circle, which we established was impossible, since all distinguished arcs were strictly smaller than the whole circle. This contradiction proves prime $n$ always works. If $n$ is composite, say $n=ab$ with $a,b>1$, then the sequence $aa\cdots a0$ (with $ab-1$ "$a$"'s) is the counterexample.

Muradjl wrote: Determine all integers $ n\geq 2$ having the following property: for any integers $a_1,a_2,\ldots, a_n$ whose sum is not divisible by $n$, there exists an index $1 \leq i \leq n$ such that none of the numbers $$a_i,a_i+a_{i+1},\ldots,a_i+a_{i+1}+\ldots+a_{i+n-1}$$is divisible by $M$. Here, we let $a_i=a_{i-n}$ when $i >n$. Proposed by Warut Suksompong, Thailand My solution at TST (same as post #3). For $n=pq$ with $p,q>1$ pick the numbers $\underbrace{p, \dots, p,}_{q+1} \underbrace{0 \dots 0}_{pq-q-1}$; then this fails. Now we prove that $n=p$ prime always works. Assume to the contrary. For each index $i$ assign to it the minimal index $f(i)>i$ such that $$p \mid a_i+\dots+a_{f(i)-1}$$and draw an arrow from $i$ to $f(i)$. Note that $f: \{1,2, \dots, p\} \mapsto \{1, 2, \dots, p\}$. Claim. $f$ is bijective. (Proof) Suppose $f(a)=f(b)=c$ and $a,b,c$ lie in the circle in clockwise order. Then $b$ is closer to $a$ (in clockwise order) than $c$ so by minimality, we must have drawn an arrow from $a$ to $b$ instead. Contradiction! $\blacksquare$ Now consider an arc that each arrow describes. We include the starting point of each arrow in the arc and exclude the ending point. Call the sum of all numbers on an arc the weight of the arc. Adding all weights we get a number $S \equiv 0 \pmod{p}$ (since $p$ divides weight of each arc). Now we compute $S$ in another way. Fix an $i$ and $i+1$. Note that all arcs that contain $i$ contain $i+1$ except the one arc whose arrow points towards $i+1$. Likewise all arcs that contain $i+1$ contain $i$ except the one whose arrow points away from $i+1$. Thus, $i$ and $i+1$ occur in an equal number of arcs. Consequently, each index occurs an equal number $j$ of times in $S$. However $1 \le j \le p-1$ (as an arrow points out/in of each index) and $p \mid S=j(a_1+\dots+a_{p}) \implies p \mid a_1+\dots+a_p$; clearly false. We obtain the desired contradiction! $\blacksquare$

I claim that the property holds iff $n$ is prime. If $n=ab$ is composite, then consider the set of integers $\{0,a,a,\dots,a,a\}$ where $a$ occurs $n-1$ times. Then for all $i \neq 1$, we have $\sum_{k=i}^{i+b-1} a_k = ab \equiv 0\pmod{n}$. If $i=1$, then $\sum_{k=1}^{i +b} a_k = ab \equiv 0 \pmod{n}$. Now suppose, for the sake of contradiction, that $n$ is prime and the property does not hold. Then for all $i$, there exists an integer $t_i>i$ such that \[a_i+a_{i+1} + \cdots + a_{t_i-1} \equiv 0 \pmod{n}\]and $t_i$ is as small as possible. Now consider a directed graph, $G$, with vertices labeled $1,2,\dots,n$ where we have $i \to t_i$. I claim that each vertex has indegree at most $1$. Suppose not; then there exists $i<j<t_i-1$ such that \begin{align*} a_i + a_{i+1} + \cdots + a_{t_i-1} &\equiv 0\pmod{n} \\ a_j + a_{j+1} + \cdots + a_{t_i-1} &\equiv 0\pmod{n} \end{align*}so $a_i + a_{i+1} + \cdots + a_{j-1} \equiv 0 \pmod{n}$, a contradiction since we assumed $t_i$ was minimal. Hence $G$ is the union of disjoint directed cycles. Suppose that $G$ contains a cycle consisting of elements $\{ a_{j_1},a_{j_2} ,\dots , a_{j_k} \}$ such that \begin{align*} a_{j_1} + a_{j_1+1} + \cdots + a_{j_2-1} &\equiv 0 \pmod{n} \\ a_{j_2} + a_{j_2+1} + \cdots + a_{j_3-1} &\equiv 0 \pmod{n} \\ \vdots \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \\ a_{j_k} + a_{j_k+1} + \cdots + a_{j_1-1} &\equiv 0 \pmod{n} \end{align*}Summing each of the congruences, we obtain $l \cdot (a_{j_1} + a_{j_1+2} + \cdots + a_{j_1 + n} ) \equiv 0\pmod{n}$ for some integer $n$ since they form some number of complete cycles of length $n$. In addition, each congruence contains less than $n$ terms so $l < k \le n$ and thus \[ a_{j_1} + a_{j_1+1} + \cdots + a_{j_1+n} \equiv a_1+ a_2 + \cdots a_n \equiv 0\pmod{n} \]a contradiction. $\blacksquare$

Muradjl wrote: Determine all integers $ n\geq 2$ having the following property: for any integers $a_1,a_2,\ldots, a_n$ whose sum is not divisible by $n$, there exists an index $1 \leq i \leq n$ such that none of the numbers $$a_i,a_i+a_{i+1},\ldots,a_i+a_{i+1}+\ldots+a_{i+n-1}$$is divisible by $M$. Here, we let $a_i=a_{i-n}$ when $i >n$. Proposed by Warut Suksompong, Thailand Could you change $M$ to $n$? I spent so much time trying to find all $n$ for a fixed $M$.

Fixed it!

Wow, this actually has such a nice solution. We claim the property holds if and only if $n$ is prime. If $n$ is composite, suppose it has a prime factor $p\ne n$. Then $(p,p,\ldots,p,0)$ fails. Now we show $n=p$ prime has the desired property. Suppose for sake of contradiction, that the property did not hold. Then, let $f(i)$ be such that \[a_i+a_{i+1}+\cdots+a_{f(i)-1}\equiv 0\pmod{p},\]All indices are obviously taken mod $p$. Now, consider the sequence \[0,f(0),f^2(0),f^3(0),\ldots.\]It eventually breaks into a cycle with length at most $p$ by PHP. Let the length of the cycle be $\ell$, so we have some $i$ such that $f^\ell(i)=i$, and $\ell\le p$. Then, we see that \[S:=\sum_{j=0}^{\ell-1}(a_{f^j(i)}+\cdots+a_{f^{j+1}(i)-1}) = (\ell-1)(a_1+\cdots+a_p).\]But by definition of $f$, we see that $p\mid S$, so $p\mid(\ell-1)(a_1+\cdots+a_p)$ where $\ell-1<p$, so $p\mid a_1+\cdots+a_p$, a contradiction.

I thought this was a very nice problem; here's another approach which I hope you'll find interesting. The answer is all prime numbers. If $n$ is composite, take a prime factor $p$ of $n$ greater than $1$. It's easy to see that the tuple $(0, p, p, ..., p)$ fails. For $n$ prime, suppose for contradiction that such an index described does not exist. Then, some partial sum beginning with $a_i$ is divisible by $n$ for all $i = 1, ..., n$. We'll make a few key claims, throwing out a couple of terms: the partial sum $a_i + a_{i+1} + \cdots + a_{j}$, corresponds to the endpoint $j$ and the beginning point $i$ (with the indices mod $n$ as expected). Claim 1: For each $i$, take only one partial sum divisible by $n$ with beginning point $i$. If the endpoints of these partial sums are distinct, then $n \mid a_1 + \cdots + a_n$. Proof: Initially, assign to each beginning point $i$ the endpoint $i$, so this way, all partial sums have just the single number $a_i$. We define a move to be the swapping of the two endpoints corresponding to two beginning points. Now consider the partial sums $S_1, S_2$ corresponding respectively to the two pairs of beginning and endpoints $(i_1, j_1)$ and $(i_2, j_2)$ with $j_1 < j_2$. Also noting that we can't assign the endpoint $i+n-1$ to beginning point $i$, there are three cases to consider. Both $j_1, j_2$ are in none of the two sums - Here, we take the sum $a_1 + \cdots + a_n$, append $a_{j_1+1} + \cdots + a_{j_2}$ to $S_1$, and append $a_{j_2+1} + \cdots + a_{j_1}$ to $S_2$. Then $i_1$ has to be from $j_2+2$ to $j_1$, and similarly with $i_2$. Both $j_1, j_2$ are in one of the two sums - If $j_1$ alone is in $S_1$, then transfer the $a_{j_1+1} + \cdots + a_{j_2}$ in $S_2$ to $S_1$. Again, $i_1$ has to be from $j_2+2$ to $j_1$. The reasoning is the same for $j_2$ alone being in $S_2$. Both $j_1, j_2$ are in both of the two sums - Then, subtract $a_{j_2+1} + \cdots + a_{j_1}$ from $S_1$ and $a_{j_1+1} + \cdots + a_{j_2}$ from $S_2$. In each case, a move results in changing the sum of all partial sums by a multiple of $a_1 + \cdots + a_n$. It's clear that we can get any configuration of distinct endpoints from our initial one by a series of moves. Hence, each partial sum also has at most $n-1$ terms, and the sum of the partial sums in this claim is $k(a_1 + \cdots + a_n)$, $k$ an integer at most $n-1$. Since $n$ is prime, $n \mid a_1 + \cdots + a_n$, proving this claim. Claim 2: For each $i$, take only one partial sum as described in Claim 1. If the endpoints are not distinct, then some partial sums can be subtracted from the others in a way that forces the resulting endpoints to eventually be distinct. Proof: Clearly, if two partial sums with different beginning points have the same endpoint, we can subtract one partial sum from the other. The total number of terms of the partial sums must decrease upon each subtraction, and this total can't drop below $n$, when for each $i$, the partial sum is just $a_i$. This total has to stop decreasing at some point, in which case the endpoints are all distinct. This solves the problem, as we have a contradiction. (To clarify, when an index has to be from $i$ to $j$, this means that if you arrange $0, ..., n-1$ evenly in a circle clockwise, then that index can be any number on the arc starting from $i$ and going clockwise to $j$.)

I claim that the answer is all primes. For a composite number, consider a prime divisor $p$, and choose the sequence $(0,0,\ldots,0,n/p,n/p,\ldots,n/p)$, where there are $p+1$ $n/p$s. Clearly, the sum isn't divisible by $n$, however every term will have a sequence of numbers beginning from it which has exactly $p$ $n/p$s. Now, if $n$ is prime, suppose a contradiction. In other words, there exists an index $f(i)$ for all $i$, such that $\sum_{j=i}^{f(i)-1}a_j\equiv 0\pmod n$. Consider the sequence of sums $\sum_{j=1}^{f(i)-1}a_j+\sum_{j=f(i)}^{f^2(i)-1}a_j+\sum_{j=f^2(i)}^{f^3(i)-1}a_j+\ldots$. Considering the numbers $1,f(i),f^2(i),\ldots\pmod n$, there of course will exist $x>y$ such that $f^x(i)\equiv f^y(i)$, and $|x-y|\le p$. So, taking the sum of the sums from the one beginning with $j=f^y(i)$ to the one ending with $f^x(i)-1$ will give $k(a_1+\ldots+a_n)\equiv 0\pmod n$ for some $k<n$, as we have looped through all the numbers a whole amount of times. As $n$ is prime though, $a_1+\ldots+a_n\equiv 0\pmod n$, which is a contradiction.

There's an interesting resemblance between this problem and the following Raney's Lemma: Let $n$ be a positive integer, and $x_1,x_2,\cdots,x_n$ be integers that sum up to $1$, there exists an integer $1\le i\le n$ such that $x_i,x_i+x_{i+1},\cdots,x_i+x_{i+1}+\cdots+x_{i+n-1}$ are all greater than $0$. The solution to these two problems are very similar.

We claim only $n$ prime works. If $n$ is composite, take $(a_1,\ldots,a_n)=(0,p,p,\ldots,p)$ for any $p\mid n$. Clearly $n\nmid a_1+\cdots+a_n=(n-1)p$, yet any group of $n/p$ $p$'s summed gives a multiple of $n$. Let $n=p$ be prime. Suppose for the sake of contradiction that $\exists a_1,\ldots,a_p \in \mathbb{Z}$ with $p\nmid a_1+\cdots+a_p$, such that $\forall i \in [1,p]$, at least one of $a_i, a_i+a_{i+1},\ldots,a_i+\cdots+a_{i+p-1}$ is divisible by $p$. For each $i$, let $f(i)$ be the guy such that $p\mid a_i+\cdots+a_{f(i)-1}$. Now, since the domain and range of $f(i)$ are constant, there exists some $k$ such that $f^k(2)=2$. Note that $k\le p-1$ by Pigeonhole. Then, we have \begin{align*} p&\mid a_2+\cdots+a_{f(2)-1} \\ p&\mid a_{f(2)} + \cdots + a_{f^2(2)-1} \\ &\vdots \\ p&\mid a_{f^{k-1}(2)} + \cdots + a_{f^k(2)-1}. \end{align*}Summing all these gives that $p$ divides some number less than $p$ times $a_1+\cdots+a_p$. Therefore, $p\mid a_1+\cdots+a_p$, contradiction.

The answer is all $n$ that is a prime. If n is not a prime, let $p$ the smallest factor of $n$, let $n=pq$, then it is straightforward to check that $a_1=a_2=...=a_{n-1}=q$ and $a_n=n$ is a counter-example. Suppose $n$ is a prime, suppose on the contrary that for all $1\leq i\leq n$ there exists $b_i$ such that $$\sum_{m=i}^{b_i}a_i\equiv 0\pmod n$$Let $S_i=\sum_{m=i}^{b_i}a_i$. Define the sequence $c_i$ by $c_1=b_1$ and $c_{i+1}=b_{c_i+1}$. Now, CLAIM. (i) For every $1\leq i\leq j\leq n$ we have $c_i\neq c_j$ (ii) For every $1\leq i\leq n$ we have $c_i\neq n$ Proof. Suppose $c_i=c_j$ then we have $$0\equiv S_{i+1}+S_{i+2}+...+S_j=k(a_1+a_2+...+a_n)\pmod n$$where $k<n$, which is a contradiction. Similarly if $c_i=n$ then $$0\equiv S_1+...+S_n=k(a_1+a_2+...+a_n)\pmod n$$contradiction. $\blacksquare$ However this is clearly impossible since this implies that $c_1,c_2,...,c_n$ are $n$ distinct integers in the range $[1,n-1]$, so we are done.

The answer is only prime $n.$ Claim: All composite $n$ fail. Proof. If $n = pk,$ consider the sequence $\underbrace{p, p,\dots, p}_{k+1}, 0,0,\dots,0.$ $\blacksquare$ Claim: $n$ must be prime. Proof. Suppose not. Work in $\mathbb Z_p.$ We extend the sequence to have infinitely many terms with $a_i = a_{n+i}$ and assume that every index has a partial sum divisible by $n.$ Given a partial sum of $a_1 + a_2 + \cdots + a_k = 0,$ there exists a partial sum starting with index $k+1$ summing to 0, so doing so finitely many times, we can extend the partial series to $n\le t < 2n.$ $$a_1+a_2+\cdots + a_k + a_{k+1} + \cdots + a_t = 0.$$If $S$ denotes the set of indices $2\le i\le n$ such that $a_1 + \cdots + a_i = 0,$ then $t\pmod n\not\in S.$ Indeed, if otherwise, then letting $t=i+sn,$ $a_{i+1} + \cdots + a_{i+sn} = m(a_1+a_2+\cdots + a_n) = 0,$ contradiction since $n$ is prime and $m<n$. As a result, repeating, we can extend to all indices not in $S$ and eventually the partial series becomes periodic and it must true that an index not in $S$ is repeated, implying that $$a_1+ a_2 + \cdots + a_t + a_{t+1} + \cdots + a_{t+kn} = a_{t+1} + \cdots + a_{t+kn} = m(a_1+a_2+\cdots + a_n) = 0,$$Where $m$ must be less than $n$ since there are strictly less than $n$ indices not in $S$ whence $a_1 + a_2 + \cdots + a_n = 0.$ Contradiction. $\blacksquare$

Wow amazing problem! Solved with Pujnk The answer is only $n$ which are prime To see that composite $n$ fail, let $p$ be a prime factor of $n$ and pick the sequence $(0,p,p,p,...,p)$. The interesting bit is when $n$ is prime. Suppose it fails, then for every index $i$, there is an index $j$ with $n | a_i + a_{i+1} + ... + a_j$. Call this index as $f(i)$ Define a new sequence $b_i$ with $b_1 = 1$ and $b_{i+1} = f(b_i) + 1$. Let $s_i = a_{b_i} + a_{b_i + 1} + ... + a_{b_{i+1}-1}$. Note that we have $n | s_i$ for all $i$, by definition. Since there are only a finite number of numbers in the $a_i$ sequence, we eventually have to come back to the same number, say $b_{k+1} = b_1$ with $k \le p$. Now, see that we have $n | s_1 + s_2 + s_3 + ... + s_{k-1} = z(a_1 + a_2 + ... + a_n)$ where $z$ is the number of times it goes "around" the sequence before coming back. Since $z < n$ and $n \nmid a_1 + a_2 + ... + a_n$ and $n$ is a prime, this is impossible. So $n$ prime must work, as desired. $\blacksquare$

Solved with nprime06. The answer is $n$=prime06. Suppose $n$ is not prime (such as $06$). Then, letting $p\mid n$ for a prime $p$, the sequence $(0,\underbrace{p,p,\cdots,p}_{n-1\text{ times}})$ is a counterexample. We now show that all $n$ prime work. Assume the contrary, that for all indices there exists atleast one number in that list that is divisible by $n$. For an index $i$, denote $f(i)$ to be the least index such that $n\mid a_i+a_{i+1}+\cdots+a_{f(i)-1}$. Claim: For indices $i\neq j, f(i)\neq f(j)$. Proof: WLOG let $j>i$. Suppose the contrary, and let $f(i) = f(j)$; note that \[a_i+a_{i+1}+\cdots+a_j+\cdots+a_{f(i)-1}\equiv a_j+a_{j+1}+\cdots+a_{f(i)-1}\equiv 0\pmod n\]which implies \[n\mid a_i+a_{i+1}+\cdots+a_{j-1},\]contradicting the minimality of $f$. $\square$ Let $g(i)$ be the least integer with $f^{g(i)}(i) = i$, which obviously exists; also $g(i)\le n$. Moreover, $n$ divides each of $a_i+\cdots+a_{f(i)-1},$ and after summing, we get that \[\sum_{l=0}^{g(i)-1}\left(a_{f^l(i)}+\cdots a_{f^{l+1}(i)-1}\right)\equiv k(a_1+\cdots+a_n)\equiv 0 \pmod n\]where $k$ is some positive integer. But since $g(i)\le n$, we must have $k<n$, which implies $a_1+\cdots+a_n\equiv 0\pmod n$, a contradiction.

The answer is all prime $n$. First, we prove that prime $n$ work. Assume that for all indices $1\le i\le n$, at least one of of the numbers displayed in the problem are divisible by $n$. Construct the directed graph with vertices $a_1$ through $a_n$, with an edge from $a_i$ to $a_j$ iff $a_i+a_{i+1}+\ldots+a_{n+j-1}$ is a multiple of $n$. By assumption, every vertex has outdegree at least $1$, therefore, a directed cycle exists. Consider the corresponding sums of all the edges (for an edge from $a_i$ to $a_j$, the corresponding sum is $a_i+\ldots+a_{n+j-1}$). By construction, the sum of all these sums is a multiple of $n$. However, taking the sums in the order of the edges in the cycle, we see that the addition of all these sums results in adding $a_1, a_2, \ldots, a_n$ the same amount of times. Since this amount is clearly less than $n$, $a_1+\ldots+a_n$ is not divisible by $n$, and $n$ is prime, the addition of all these sums cannot be divisible by $n$, contradiction. Now we prove that all composite $n$ do not work. Suppose that $n=xy$, where $x,y>1$. Let $a_1=0$ and $a_i=x$ for all $i\ne 1$. Clearly $a_1+\ldots+a_n$ is not a multiple of $n$. Moreover, starting from a multiple of $x$, after $y$ additions of $x$, we must have stumbled upon a number divisible by $n$. Starting from any $a_i$, adding the terms that follow one at a time must result in at least $y$ additions of $x$, implying after a certain addition that a multiple of $n$ was achieved.

Precise the primes. If $n$ is composite simply take $(0, p, p, \ldots)$ for any $p \mid n$. When $n$ is prime, assume that every row has a multiple of $p$, then assign each listed partial sum a pair $(s, e)$ where $s$ is the first element of the partial and $e$ is the first unused element of the partial ($e = s$ when the sum is over all $n$ numbers). Consider all such pairs whose sums are $0$, and impose the additional restriction that for each $s$, only choose the minimal such $e$. Clearly, no $(n, n)$ pair exists by condition. The function represented by these ordered pairs is injective by minimality, since if $(s_1, n) and (s_2, n)$ both are valid with $s_1<s_2$ then either $(s_1, s_2)$ or $(s_2, s_1)$ is superior depending on $n$. Since the domain is the codomain, the function is, therefore, bijective, so now sum over all partial sums involved in the function. The sum must equal 0, but additional must be a multiple of $a_1+a_2+\ldots+a_n$ less than the pth multiple due to cyclicity. This is a contradiction since this would imply $p \mid a_1+a_2+\ldots+a_n$.

Answer: All prime numbers $p$ Solution: If $n=mp$ isn't prime, consider $(a_1, a_2, \dots, a_n)=(0, m, \dots, m)$ for some prime $p\vert n$. This fails. Now we prove that if $n=p$ is prime, this index exists (from now on we consider indicies$\pmod p$). Else, we can define a function $f: \{1, 2, \dots n\}\to \{1, 2\dots n\}$ by $f(i)$ being the minimum index such that $$p\vert a_i+a_{i+1}+\cdots +a_{f(i)-1}$$and $f(i)-i\leq p-1$. Consider any cycle $\mathcal{C}$ (which must exist). Dispose the indicies $a_i$ around a circle in order, so that we are interested in the along the arcs. Now we can add the terms along the arcs of the elements of the cycle to get $$p\vert R(\sum_{i=1}^p a_i)$$where $R$ is the number of complete revolutions around the circle. As $R<p$ and $p\not\vert S$ we get a contradiction. Hence said function $f$ cannot exist. $\square$

The answer is $n$ prime only. For $n$ composite, let $n=ab$ for $a,b>1$, and take $(a_1,\ldots,a_n)=(a,\ldots,a,0)$, which can be checked to work. It remains to show that $n=p$ prime fail. Suppose for contradiction that for all $1 \leq k \leq p$, there exists a minimal $f(k) \geq k$ such that $p \mid a_k+\cdots+a_{f(k)-1}$. Considering the graph where we connect $k \to f(k)$, there must exist a cycle $x_1 \to x_2 \to \cdots \to x_m \to x_1$, whence $$p \mid (a_{x_1}+\cdots+a_{x_2-1})+(a_{x_2}+\cdots+a_{x_3-1})+\cdots+(a_{x_m}+\cdots+a_{x_1-1}),$$the RHS of which equals $c(a_1+\cdots+a_p)$ for some $c<p$, as there are less than $p^2$ terms of the RHS ($m \leq p$, and every term in parentheses has at most $p-1$ terms), from which we obtain $p \mid a_1+\cdots+a_p$, contradiction. $\blacksquare$

Cool problem, but easier than N2. I claim that all prime $n$ work. To see that composite $n$ fail, for some $d|n$ such that $d\neq 1,n$, put $\frac{n}{d}+1$ copies of $d$ and fill the rest of the array with zeroes. To see that primes work, first assume WLOG that nothing is divisible by $n$. Then, draw a directed graph on $n$ vertices with an edge from $i$ to $j$ whenever the (possibly cyclic) sum of all terms between $a_i$ and $a_j$ is a multiple of $n$, and remove some edges so that each vertex has outdegree $1$. We can see that there exists a cycle, corresponding to $c$ times the array sum being a multiple of $n$, and since the cycle contains at most $n$ edges, we have $c\le n-1$, which necessitates the sum of all elements being a multiple of $p$.

The answer is only prime $n$. For composite $n$, take an arbitrary divisor of $n$, call it $d$, and use the sequence $(\frac{n}d, \frac{n}d, \ldots, \frac{n}d, 0)$. Its easy to see that this fails. For prime $n$, let $S=a_1+a_2+\cdots a_n$ (taking all computations $\mod n$). Since, $S \neq 0$, we may assume by scaling that $S=1$. Suppose that there existed a sequence for which the condition was not true. Consider the numbers \[b_1=a_1, b_2=a_1+a_2,\quad \ldots \quad b_{n-1} = a_1+a_2+ \cdots + a_{n-1}, b_n= S\]The conditions translate as follows: For each $i$, there either exists a $j > i$ with $b_j=b_i$ or a $j<i$ with $1-[b_i-b_j]=0$, i.e $b_j-b_i=-1$. We can show by induction that if $a$ is in the sequence $b_i$, then $a-1$ is in the sequence. Choose the rightmost instance of $a$, clearly the first condition cannot hold, so there must be a $j$ with $b_j=a-1$. It follows that every residue $\mod n$ is included exactly once in this sequence $b_i$, however this is a contradiction as choosing $i=1$ there does not exist a $j>1$ with $b_j = b_1$, as desired.

The answer is primes. Suppose $n$ is composite then let $n=ab$ and $a,b>1$ then we see that $0,a,a,\dots, a$ is a sequence whose sum is $a(n-1)\equiv -a\not\equiv 0\pmod n$ and no matter what $i$ you choose, you can force $a_{i},\dots, a_{i+n-1}$ to have $b$ occurrences of $a$ since there are $n-1\ge b$ occurrences of $a$ in total. $~$ Suppose $n$ is prime then write down $a_{i_1}$. Suppose the contrary of what is trying to be proven. Then, increment $i_1\pmod n$ to $i_2-1$ until you get that \[n\mid a_{i_1}+a_{i_1+1}+\dots + a_{i_2-1}\]and write down $a_{i_2}$ and repeat until you get a number you have gotten before. WLOG assume that number is just $a_{i_1}$. Then, we have \[n\mid a_{i_1}+\dots + a_{i_2-1}\]\[n\mid a_{i_2}+\dots +a_{i_3-1}\]\[\dots \]\[n\mid a_{i_k}+\dots + a_{i_1-1}\]where $k\le n$ since there are only $n$ different possible values to take on for $i$. Each of those divisibility statements has at most $n-1$ on each right hand side since the full sequence does not work. Adding all those up we get something of the form \[n\mid l(a_{1}+\dots + a_n)\]where there are $ln$ terms on the right hand side, $l\le n-1$. Since $n$ is prime, $n\mid a_1+\dots + a_n$ but that's a contradiction.

Solved with GoodMorning. The answer is prime $n$ only. If $n$ is composite, letting $p$ be a prime divisor of $n$, we get that $(n/p,n/p,\ldots, n/p, n)$ fails. Now assume $n=p$, and suppose the result was not true (as in we have $p\nmid a_1 + \cdots + a_p$, and that at least one of $a_i, \cdots a_i + a_{i+1} + \cdots a_{i +n - 1}$ is divisible by $p$). Let $a_0 = a_p$. The result for $i=p$ is equivalent to $i=0$ now and $p$ doesn't divide $a_0 + a_1 + \cdots + a_{p-1}$. Consider the circle $(0,1,2,\ldots, p-1)$ in that order clockwise. For any arc of this circle, let the length of the arc be the number of integers contained in the arc minus 1, and the sum of an arc to be the sum of all $a_i$ over $i$ in the arc. Since we are assuming the problem statement is not true, for each $0\le k\le p-1$, there exists $j\in [0,p-1]$ such that the sum of the clockwise arc from $k$ to $j$ is divisible by $p$. Choose $j$ such that the length of this arc is minimal. Let $f(k) = j + 1$ (or equal to $0$ if $j = p-1$). Thus, we have $f\colon \{0,1,\ldots, p-1\} \to \{0,1,\ldots, p-1\}$. Claim: $f$ is bijective. Proof: Since $f$ is from a finite set to itself, we only have to prove injective. Suppose $f(x) = f(y) = z$, where $x,y,z$ are in a clockwise order in the circle. Then note that the arc from $x$ to $y$ must also have a sum divisible by $p$ and arc length less than the arc from $x$ to $z$, contradicting minimality. So $f$ is injective.$\square$ Now let $1, f(1), f(f(1))\ldots, $ denote a cycle of $f$. We have \[(a_1 + a_2 + \cdots + a_{f(1) - 1}) + (a_{f(1)} + a_{f(1) + 1} + \cdots + a_{f(f(1)) - 1}) + \cdots + (a_m + a_{m+1} + \cdots + a_0),\]is divisible by $p$, where $m = f^{-1}(1)$. The exact value of this is equal to $c \cdot (a_0 + a_1 +\cdots + a_{p-1})$, where $c$ is the number of times we hit $a_0$. If $f(1) = 1 $, then $p\mid a_0 + a_1 + \cdots + a_{p-1}$, contradiction. Now, in each group from $a_{f^k(1)}$ to $a_{f^{k+1}(1) - 1}$, we may hit $a_0$ at most one time, and when $k=0$, we cannot hit $a_0$ at all since $f(1)\ne 1$. However, the minimal $t$ such that $f^t(1) = 1$ is at most $p$, hence we can hit $a_0$ at most $p-1$ times and at least once. Thus, $c(a_0 + a_1 + \cdots + a_{p-1})$ is a multiple of $p$, and $p\nmid c$, so $p\mid a_0 + a_1 + \cdots + a_{p-1}$, contradiction.

The answer is only prime $n$. If $n$ is composite, take a prime divisor $p$ of $n$, and consider $(0, n/p,n/p,\ldots, n/p, n)$, which fails. On the other hand, suppose that $n=p$ is prime. Assume for contradiction for every index $k$ assume $a_k + a_{k+1} + \dots + a_{f(k)} \equiv 0 \pmod{p}$ for some function $f$ mapping $\mathbb{F}_p$ to $\mathbb{F}_p$. Let $G$ be the directed graph where we place an edge $k \rightarrow f(k)+1$ for each $k \in \mathbb{F}_p$. Note that this graph is simple and each vertex has outdegree of at least 1, from which there exists a cycle $\mathcal{C}$. For each vertex $k$, assign a sum $S_k=a_k+a_{k+1}\ldots+a_{f(k)}$. The key idea is that, after taking the assigned sums for each vertex in $\mathcal{C}$, their sum is \[ j(a_1+\ldots+a_p) \]for some $0<j<p$. However, by design, $S_k \equiv 0 \pmod{p}$ for each $k$, so $j(a_1+\ldots+a_p) \equiv 0 \pmod{p}$, which implies $a_1+\ldots+a_p \equiv 0 \pmod{p}$, a contradiction. Thus prime $n$ work.

The quintessential arrows problem! The answer is $n$ prime. If $n$ is composite, pick the smallest $p_1 \mid n$ and set $a_1 = 0$, $a_i = \frac n{p_1}$ for $i \geq 2$. For $n$ prime, assume the statement is false. Then there exists a $f(k)$ for every index $k$ such that $a_k+a_{k+1}+\cdots+a_{k+f(k)}$ is a multiple of $n$. Set $g(k) = k+f(k) + 1$; there must exist a cycle in $g$, or some element $k$ such that $g^r(k) = k$. Then, notice that \begin{align*} n &\mid a_k+a_{k+1}+\cdots+a_{k+f(k)} + a_{g(k)} + \cdots + a_{g^2(k)} + \cdots + a_{k-1} \\ &\mid i(a_k+a_{k+1}+\cdots+a_{k-1}) \end{align*}for some $i < n$. This is an obvious contradiction.

The answer is prime $n$. Suppose not. Then, arrange the numbers in a circle, so that each index has a "failing" index such that the sum of the interval is 0 mod $n$. Draw a directed graph with each index point to the one right after its first failing index. Since this is a function from a set to itself, this graph has a cycle (possibly of length 2). However, this cycle tells us that going around the circle some whole number of times less than $n$ gives a multiple of $n$, which clearly cannot happen if $n$ is prime. When $n$ is not prime, let $d$ be a divisor of $n$ that is not 1 or $n$, and have one number be 0 and all others be $d$ for a counterexample.

The answer is all prime $n$. Let $S=\{1,2, \ldots, n\}$. Assume $n$ is prime and no such $i$ exists. This implies that for all $k$, there is some other index $f(k)$ where \[ n \mid a_k + a_{k+1} + \cdots + a_{f(k)-1} = s_k \]Since $S$ is finite, this implies that there exists some $\ell \in S$ and $r \leq n-1$ where $f^r(\ell) = \ell$. Note that \[ n \mid s_{f^i(\ell)} \colon i \leq n-1 \]\[ \implies n \mid \sum_{i=0}^{r-1} s_{f^i(\ell)} = R \cdot (a_1+a_2+ \cdots +a_n) \]where $R$ is there number of times we wrapped around mod $n$. Recall that $n$ does not divide $a_1+a_2+ \cdots +a_n$ and $R \leq n-1$. So, $n$ does not divide $R \cdot (a_1+a_2+ \cdots +a_n)$ which is a contradiction. For $n$ composite, refer to any construction in an above post.

Nice question

Answer: All primes. Firstly, we'll prove that $n$ has to be prime. Assumen not. Then we can write $n = a \cdot b$, where $a, b$ are positive integers that are greater than $1$. Then the set $n$ integers $a, a, \dots, a, 0$ doesn't satisfy the condition. Now let $p = n$ be a prime. Draw arrow $i$ to $j$ if $p \mid a_i + a_{i+1} + \dots + a_{j-1}$. Then it suffices to prove that there exists index $k$ such that outdegree of $k$ is 0. Assume not. Then it's obvious that the graph contains directed cycle. Let $i_1 \to i_2 \to \dots \to i_k \to i_1$ be the directed cycle. Then $p \mid a_{i_1} + a_{i_1 + 1} + \dots + a_{i_2 - 1} + a_{i_2} + \dots + a_{i_1 - 1} = s(a_1 + a_2 + \dots + a_p)$ for some $s$. Since length of arrow doesn't exceed $p-1$, hence $s < p$. Therefore $p \mid a_1 + a_2 + \dots + a_p$, a contradiction. $\blacksquare$

We claim our answer is $n$ equal to a prime number. Now the construction where composite numbers fails: If $n=ab$ is composite, then consider the set of integers $\{0,a,a,\dots,a,a\}$ where $a$ occurs $n-1$ times. Now assume that $n$ is a prime, assume FTSOC that for all $1 \leq i \leq n $ there exists an index such that $n$ divides that partial sum. Call that index $f(i)$, so we have that $n | a_i+a_{i+1} + \dots + a_{f(i)-1}$, but note that the domain and range of $f$ are constant, meaning that there exists a $m$ such that $f^m (i)=i$ where $m \leq n-1 $ (by Pigeonhole), so we have that : $n \vert a_2+\cdots+a_{f(i)-1}$ $n \vert a_{f(i)} + \cdots + a_{f^2(i)-1} $ . . . $n \vert a_{f^{m-1}(i)} + \cdots + a_{f^m(i)-1}$ . Summing all these up will give us $j(a_1+a_2+ \dots+a_n)$ for some $j \leq n $ meaning that $n | a_1+a_2+ \dots+a_n$ a contradiction.

Really nice problem but I had to receive a tiny pointer to look at this in terms of a graph. The main idea is actually a carbon copy of the idea to CF1270G. We claim that the answer is all $n$ such that $n$ is a prime number. We first show that all other integers do not satisfy the given condition. We have two cases. If $n$ is composite and has a prime factor greater than 2, then we write $n=pk$ for some such prime $p$ and $k>1$. Then, consider the set of terms, \[a_1=(p-1)k \text{ and }a_2=a_3=\dots = a_{n}=k\]To see why this is a counterexample, first note that $a_1+\dots + a_n = 2pk-2k$ which is clearly not divisible by $n$. Now, note that $a_1+a_2=pk$ and for all $2\le i \le n-p+1$, $a_i + a_{i+1}+\dots + a_{i+p-1}=pk$. Then, for all $n-p+1 < i <n$, we can see that $a_i + \dots + a_n + a_1 + \dots + a_{p+i+1-n}=2pk$ which works since $p+i+1-n < i$ as $n > p+1$. If there does not exist such a prime factor, $n$ is a power of 2 so for $n=4$ we consider the set $\{4,2,2,2\}$ which is a counterexample quite clearly, and for all other powers of two, we let $n=4k$ and consider the set of integers \[a_1=2k \text{ and }a_2=a_3=\dots = a_n=k\]which clearly works. Now, we show that all prime numbers in fact do satisfy the given condition. By way of contradiction, we assume there exists a prime $p$ which does not satisfy this condition. Then, for each $1 \le i \le p$ there must exist some index $L(i)$ such that \[p \mid a_i + a_{i+1}+\dots + a_{L(i)}\]To do this, we introduce a directed graph $\mathcal{G}$ where the vertices are labeled with numbers from $1$ to $p$ and there exists a directed edge from vertex $v_1 \to v_2$ if and only if $L(v_1)+1=v_2$. Then, we have the following key claim. Claim : There does not exist a directed cycle $C$ in $\mathcal{G}$. Proof: Say there exists a directed cycle $v_1\to v_2 \to \dots \to v_r \to v_1$ (where $n_i$ is the number assigned to vertex $v_i$). Then, \begin{align*} a_{n_1} + (a_{n_1+1}) + \dots + (a_{n_2 -1}) &= 0\\ a_{n_2} + (a_{n_2+1}) + \dots + (a_{n_3-1}) &=0\\ &\vdots\\ a_{n_r} + (a_{n_r+1}) + \dots + (a_{n_1-1}) &=0\\ \end{align*}summing these equations give us an equation of the form, $k(a_1+\dots +a_pp)$. This is because we start from $v_1$ and move along the graph passing through every single vertex on the way until we return to $v_1$ (thus all numbers along the circle will be picked up), and thus the expression is of the above form where $k$ is the total number of rotations. Since clearly $k<p$, (we have only $p$ vertices) so if $k(a_1+\dots +a_p) \equiv 0 \pmod p$, since $\gcd(k,p)=1$ we conclude $ p \mid a_1+\dots + a_p$ which is a clear contradiction. Thus, there indeed exists no direct cycle as claimed. Now, this is clearly impossible since if we start at vertex $1$, and move it one of its vertices, and keep on moving, if the graph has no cycle, we never revisit a vertex twice so in each move we move to a new vertex (every vertex clearly must have a neighbor by assumption) but we only have finitely many vertices so we run out of vertices and are eventually forced to return to some vertex we visited before, which is a contradiction. Thus, all primes $p$ satisfy the given condition and we are done.

The answer is all prime $n$. For composite $n$, let $d$ be the largest proper divisor of $n$. Then the construction $d,d,\dots,d,0$ works. For prime $n$, suppose there is a sequence that fails. Then every index $i$ has some $j$ such that $a_i+a_{i+1}+\dots+a_{j-1}$ is divisible by $p$. Consider the graph that takes each $i$ to its $j$. Then there must exist a cycle. If we add up this sum over the cycle, we will get that some multiple of $a_1+a_2+\dots+a_p$ is divisible by $p$. The number of times of $a_1+a_2+\dots+a_p$ is less than $p$ because each vertex in the cycle contributes at most $p-1$ terms, contradiction. $\blacksquare$

The answer is prime $n$, since for composite $n=pq$, we can make $a_1, \dots, a_{q+1} = p$ and everything else $0$, which clearly works. If $n$ is prime, suppose the assertion were false. Along a circle with circumference $a_1 + \dots + a_n$, mark $n$ vertices so that vertex $i$ is $a_i$ units counterclockwise of vertex $(i+1)$. Place Turbo the snail at an arbitrary vertex. Each day, Turbo will slug clockwise along the circumference of the circle until he has both reached another vertex and travelled a multiple of $n$ units. Once this occurs, he stops and rests at that vertex for the night before waking up the next morning and leaving. By our assumption, in a single day, Turbo will never travel more than the circumference of the circle. After enough time, the pattern of vertices where Turbo rests at will become periodic. This period is, by pigeonhole, at most $n$ days long. Take some vertex which Turbo rests at periodically – suppose that between any two consecutive stays, Turbo makes $k$ loops around the circle. Because these stays are at most $n$ days apart and Turbo traverses less than a whole circle in a single day, we have $k < n$. Between these two stays, if Turbo has travelled $D$ units total, the circumference of the circle is $\tfrac{D}{k}$. Each day, Turbo travels a multiple of $n$ units, so $D$ is a multiple of $n$; since $k < n$ and $n$ is prime, it follows that $\tfrac{D}{k}$ is also a multiple of $n$. This is a contradiction, since $a_1 + a_2 + \dots + a_n$ cannot be a multiple of $n$.

Suppose that for a prime $p$ for every $k$ there was a value $f(k)$ such that $\sum_{i=k}^{f(k)}a_{i}\equiv 0\pmod p$, thus we can clearly see that there is a cycle, now if this cycle goes over one revolution of all the values, we can remove overlaps until its just the sum and because all the overlaps have sum 0, this is a contradicition and implies that all the values have sum $0$. For non primes, let $m$ be a divisor that isn't $1$, and have the values be $\frac{n}{m}+1$ copies of $m$ and the rest be $n$.

Only prime $n$ work. For the construction, take a proper divisor $d$ of $n$ and note that $(0, d, d, \dots, d)$ is a counterexample. For the bound, suppose otherwise. Draw a graph $G$ on $n$ vertices labelled $1$, $2$, $\dots{}$, $n$ and connect $i \rightarrow j + 1$ if $n \mid a_i + \dots + a_j$. Now $G$ clearly has a cycle; by summing over that cycle we get that $n \mid k(a_1 + \dots + a_n)$ for some $k < n$, contradiction.

Lets do the cook. First I claim that any composite numbers. For this take a $d$ such that $n>d>1$ and $d\mid n$ then $$ \underbrace{b,b,b\dots b}_{n-1},n $$ As for a prime, consider a function $f$ such that for any $k$, $f(k)$ is the first number in the sequence $\{k+1,k+2,\dots k+n-1\}$ such that $$ \sum_{i=k}^{f(k)} a_i \equiv 0 \pmod{p} $$ My premise is that the function $f$ is injective, as for the proof a simple argument on the minimum works. Next let $g(x)=f(x)+1$. Consider a directed graph that $$ x\mapsto g(x)$$Claim: there are no Will complete later sorry ppl.

The answer is all primes. Notice that if $n$ is composite, consider the largest prime $p$ of $n$ and take $(0, p, p, \dots, p)$. Now for primes $p$, for the sake of contradiction assume that no such index exists. Define $f(i)$ to be the index such that $p \mid a_i + a_{i+1} + \cdots + a_{f(i)}$ such that the length of the sequence is minimum. Now if $f(i) = f(j)$ with $i < j$, it's easy to see that $f(i) = j-1$ which is a contradiction thus $f$ is injective and it's also bijective since the function is from $\{1, 2, \dots,p \} \rightarrow \{1, 2, \dots, p \}$. Now every index $i$ can be paired with an index $j = f(i)$ such that the sequence of numbers associated with $a_i$ and $a_{f(i)}$ which covers all the numbers $a_1, a_2, \dots a_p$ counting $a_i$ and $a_{f(i)}$ twice unless $f(i)=i$ since $f(f(i)) = i$. Cyclically summing all these sequences imply that $p \mid a_1 + a_2 + \cdots a_p$ which is a contradiction. $\blacksquare$