Every number is congruent to some sum of consecutive primes

96 Views Asked by At

Is it true that for every $n\ge 2$,

There exists a consecutive subsequence of first $n-1$ primes, whose sum is a multiple of $n$ ?

Let $p_n$ be the $n$-th prime. Such subsequence sum is $S(i,j)=(p_i+p_{i+1}+\dots+p_j)$.

Notice that $S(i,j) = (s_j - s_{i-1})$ where $s_n$ is the sum of first $n$ primes, for some $i\le j\lt n$.

We want to prove that for every $n$ there exist $i\le j\lt n$ such that $(s_j-s_{i-1})\equiv 0\pmod{n}$.

This is clearly true if $n=p_k$ is a prime number because we have $S(k,k)=p_k=n$.

But can we prove this for all composite numbers $n$ ?

I've verified that it holds for all numbers $n$ up to $10^4$.

For example,

It is true for $n=4$ because in $(2,3,5)$ we have $(3+5)=8\equiv 0 \pmod{4}$.

It is true for $n=6$ because in $(2,3,5,7,11)$ we find $(5+7)=12\equiv 0 \pmod{6}$.

It is true for $n=49$ because in $(2,3,\dots,223)$ we find $(13+17+19)=49\equiv 0 \pmod{49}$.


Let $\alpha(n)$ be the length of shortest subsequence such that its sum $S(i,j)\equiv 0 \pmod{n}$.

For example $\alpha(49)=3$. We know that if $n$ is prime, then $\alpha(n)=1$.

It appears that large $\alpha(n)$ values are very rare. All numbers $n\le 10^4$ have $\alpha(n)\le 6$, except:

n s.t. a(n)=7  : 289, 335, 1639, 1945, 2095, 5865, 6401, 6789, 7483, 9019, 9407

n s.t. a(n)=8  : 91, 1102, 1852, 1936, 1978, 2632, 2877, 2978, 3043, 3278, 5755, 7513 

n s.t. a(n)=9  : 3249, 3765, 6319, 6757

n s.t. a(n)=10 : 2732, 6351

A counter-example would occur if $\alpha(n)\gt n-1$ was needed.

That seems unlikely, since $\max\{\alpha(n): n\le 10^4\}=10\lt 10^4$ so far.

Is there a constant upper limit to $\alpha(n)$, or can it be arbitrarily large ?

enter image description here



P.S. If you manage to prove the statement in this question, then this implies that there is no $n$ that can satisfy Properties of the remainders from division into primes, so feel free to then also answer that question. (Assuming it is still unsolved.)

1

There are 1 best solutions below

1
On

Let $T_n$ be the sum of the first $n$ primes, with $T_0 = 0$. Consider $T_0, \ldots, T_{n-1}$ mod $n$. These are $n$ values in $\{0, \ldots, n-1\}$. If they are not all distinct, say $T_i \equiv T_j \mod n$ with $i < j$, then $\sum_{k=i+1}^j p_k$ is a sum of consecutive primes that is divisible by $n$. With $n$ terms and $n$ possible values, it is just possible that they could be all different: $T_0, T_1, \ldots, T_{n-1}$ mod $n$ could be a permutation of $0,1,\ldots, n-1$. But this is extremely unlikely.

I can show that your statement is true if $n$ is even. Note that half of the $n$ values $0, 1, \ldots, n-1$ are odd and half are even. Now since the first prime ($2$) is even and all others are odd, $T_0$ and $T_k$ for all odd $k$ are even, while $T_k$ for even $k \ge 2$ are odd. Thus there are too many even values to be all distinct mod $n$.