Determine which integers $n > 1$ have the property that there exists an infinite sequence $a_1, a_2, a_3, \ldots$ of nonzero integers such that the equality \[a_k+2a_{2k}+\ldots+na_{nk}=0\]holds for every positive integer $k$.
Problem
Source: 2012 USAMO problem #3
Tags: function, modular arithmetic, floor function, AMC, USA(J)MO, USAMO
dinoboy
25.04.2012 01:04
A construction for odd numbers, I haven't found much about even numbers though. I've heard from a friend the answer is all $n \ge 3$.
Let $f$ be a function from the natural numbers to the integers and let $p_1,p_2,...,p_g$ be the prime divisors of $n$. Let $a_k = f(\prod_{i=1}^g p_i^{v_{p_i}(k)})$ for each $k$. I claim a function $f$ satisfies the problem condition for odd $n$.
It is just easy algebra to show this is equivalent to $\sum_{d|n, d \neq 1} \frac{\phi(d)}{2}f(an/d) = -f(an)$ for each positive integer $a$, hence if we have for all $m < k$ $f$ is defined to be an integer then $f(k)$ is also an integer. Let $f(m) = 1$ for each positive integer $m$ such that $n \nmid m$. Then remark that $f(m) \equiv 1 \pmod{(n+1)/2}$ for each positive integer $m$, hence as a result we have a working sequence $a_k$ for odd $n$ that is nonzero everywhere.
Mod edit: Hidden.
pythag011
25.04.2012 01:11
I had read much of the research around the Erdos discrepancy problem (http://michaelnielsen.org/polymath1/index.php?title=The_Erd%C5%91s_discrepancy_problem) And once you've seen those methods this problem is very straightforward; simply make $a_i$ be completely multiplicative, then take two fairly large primes and bezout and you're done. Amusingly I sent out the EDP link to most of the TSTST group some time ago but I doubt very many people read it. EDIT: apparently Linus Hamilton read the link and instantly made the connection, lol
ftong
25.04.2012 01:17
pythag011 wrote: And once you've seen those methods this problem is very straightforward; simply make $a_i$ be completely multiplicative, then take two fairly large primes and bezout and you're done. I hadn't seen this problem before but I think I used the same method. Bertrand's postulate gives us two primes so we can make $a_1, a_2, \hdots, a_n$ multiplicative and also satisfy $a_1 + 2a_2 + \cdots + na_n = 0$. Then extend it to an infinite multiplicative sequence by setting $a_p = 1$ whenever $p$ is a prime bigger than $n$.
pythag011
25.04.2012 01:21
Apparently mitchell read my link as well~
pr0likethis
25.04.2012 01:23
so does this mean it was all n>1?
geoishard
25.04.2012 01:24
well no n=2 fails lol @pythag011 I didn't read it but I did that
Ihatepie
25.04.2012 01:27
It seems like this was the easy part of the problem, but how many points do you guys think I'd get for constructing an answer for the odd numbers and wrongly stating that n=2 worked? (because I included rational numbers in the sequence for n=2 for some strange reason) I'm hoping for 1 but it seems like 0 is more likely.
GeorgiaTechMan
25.04.2012 01:30
I solved this one but I used the theorem that there is a prime between x and 2x for all positive x. I forgot the name, so I just called it a famous theorem. There goes my chance for a perfect 7 on question 3....
v_Enhance
25.04.2012 01:39
pythag011 wrote: And once you've seen those methods this problem is very straightforward; simply make $a_i$ be completely multiplicative, then take two fairly large primes and bezout and you're done. This is exactly what I did, except I haven't seen these ideas. u_u. Anyways, here is a sketch of what I put on the test. The details were not pretty.
For $n=2$ everything fails because $a_{2^k} = \frac{a_1}{2^k}$, which is impossible.
We'll prove stuff for $n \ge 18$; I listed the other cases by hand. Note that by Bertrand's Postulate it's possible to select primes $p$ and $q$ such that
\[ \lfloor \frac{\lfloor n/2 \rfloor - 1}{2} \rfloor + 1 \le p \le \lfloor n/2 \rfloor - 1 \]
\[ \lfloor n/2 \rfloor \le q \le n \]
Notice $p \neq q$, $q \ge 7$ and $p \ge 4$. Now we'll select $a_i$ such that $a_{ij} = a_i a_j$, and the equality holds for $k=1$; then we'll be done. To do this we only need to select the values of $a_i$ at primes.
Nuke everything by setting $a_i = 1$ for primes $i$ other than $p$ and $q$. Suppose $2p$ is the largest multiple of $p$ in $\{1,2,\cdots,n\}$. Then we just need
\[ pa_p + 2p a_2a_p + q a_q + (1+2+\cdots+n)-(p+2p+q) = 0 \]
Or (for $p \neq 2$) \[ 3p a_p + q a_q = \text{blah} \]
Since $(3p,q) = 1$, by Bezout, there's nonzero integers $x,y$ with $3px + qy = 1$; then the conclusion's obvious. Proceed similarly for $3p$ and the rare $4p$ being the largest multiplies.
GeorgiaTechMan wrote: prime between x and 2x for all positive x Bertrand's Postulate And in fact there's one between $x$ and $2x-2$ for $x \ge 4$. ... So anyways, USAMO2 >> USAMO3? What is this...
lab
25.04.2012 02:06
Isn't Bertrand's Postulate not allowed on USAMO? (according to Romanian AMSP instructors anyway) Since there's no way anyone here really knows how to prove it that is.
pythag011
25.04.2012 02:07
lab wrote: Isn't Bertrand's Postulate not allowed on USAMO? (according to Romanian AMSP instructors anyway) Since there's no way anyone here really knows how to prove it that is. It's not very hard to prove, just a bit annoying...
Zhero
25.04.2012 02:21
Err also in general any well-known named result, like Bertrand's postulate, is citable on an Olympiad. It's just that certain such results (like Dirichlet's theorem) may draw the ire of graders. But Bertrand's postulate is not really that high-tech.
Yongyi781
25.04.2012 04:02
Here's an ugly solution that I came up with. It is an algorithmic construction. I am still not 100% sure of its validity, so if anyone could check it, that would be great!.
The answer is all $n\geq 3$. Of course, $n=2$ doesn't work by infinite descent.
The algorithmic construction for $n\geq 3$ is as follows:
For each $k=1,2,3,\dots$ such that $n\nmid k$, do the following:
(a) For $m=1,2,\dots,n-2$, if $a_{km}$ is already defined, do nothing, otherwise set $a_{km}=1$ (this is arbitrary).
(b) Then put in $a_{k(n-1)}$ an integer such that $a_{k(n-1)}\equiv a_k+2a_{2k}+\dots+(n-2)a_{(n-2)k}\pmod n$. In this way, we can put
(c) $a_{kn}=\frac{-a_k-2a_{2k}-\dots-(n-1)a_{(n-1)k}}{n}$, and by (b), this is an integer and $a_k+2a_{2k}+\dots+na_{nk}=0$.
Also call part (c) of this operation a $k$-run.
Now for each $p=1,2,3,\dots$, we still need to modify the sequence so that $a_{n^pk}+2a_{2n^pk}+\dots+(n-1)a_{(n-1)n^pk}$ is divisible by $n$ for each $k$ with $n\nmid k$. We can do this as follows:
For $p=1,2,3,\dots$, and for each $k=1,2,3,\dots$ such that $n\nmid k$, let $x_{k,p}$ be the remainder when $a_{n^pk}+2a_{2n^pk}+\dots+(n-1)a_{(n-1)n^pk}$ is divided by $n$. Then do the following:
- Add $n^px_{k,p}$ to $a_{(n-1)^{p+1}k}$.
- Perform a $(n-1)^{p+1}k$-run. This will add $n^{p-1}x_{k,p}$ to $a_{(n-1)^pnk}$ (modulo $n^p$).
- Perform a $(n-1)^pnk$-run. This will add $n^{p-2}x_{k,p}$ to $a_{(n-1)^{p-1}n^2k}$.
... and so on, ... until
- Perform a $(n-1)^2n^{p-1}k$-run. This will add $x_{k,p}$ to $a_{(n-1)n^pk}$.
- We can now put an integer for $a_{n^{p+1}k}$.
Now changing some of the numbers may change other numbers, but these other numbers are separate from this process and we will only need to correct for this by changing the last number in any such modified sequence. So although this is an infinite process, we are guaranteed that for each $\ell$, at some finite point, $a_\ell$ stops changing. So this infinite sequence exists.
Edit: It's very likely I typoed somewhere, so if you are thinking, "Hey shouldn't that sign be flipped?" you're probably right.
resurrection
25.04.2012 05:00
oh the fml of not doing math and forgetting bertrand's postulate when i needed it most
superpi83
25.04.2012 05:08
How may points would this be worth?
2 doesn't work because $a_k+2a_{2k}=0$ implies $a_{2k}=-\frac{1}{2}a_k$. Then if $a_1$ has $m$ factors of 2, $a_{2^{m+1}}$ will not be an integer.
To prove that all odd primes work: Let $p$ be an odd prime. Then for $n=p$, an infinite sequence that satisfies the problem's criteria is $a_i=\left(-\frac{p-1}{2}\right)^{v_p(i)}$ for all $i$. This is because we have $a_k=a_{2k}=\dots=a_{(p-1)k}$ and $a_{pk}=\left(-\frac{p-1}{2}\right)a_k$, so $a_k+2a_{2k}+\dots+(p-1)a_{(p-1)k}+pa_{pk}=(1+2+\dots+(p-1))a_k-p\left(\frac{p-1}{2}\right)a_k$ $=\frac{p(p-1)}{2}\cdot a_k-\frac{p(p-1)}{2}\cdot a_k=0$ for all $k$.
Lawrence Wu
25.04.2012 05:14
superpi83 wrote: How may points would this be worth?
2 doesn't work because $a_k+2a_{2k}=0$ implies $a_{2k}=-\frac{1}{2}a_k$. Then if $a_1$ has $m$ factors of 2, $a_{2^{m+1}}$ will not be an integer.
To prove that all odd primes work: Let $p$ be an odd prime. Then for $n=p$, an infinite sequence that satisfies the problem's criteria is $a_i=\left(-\frac{p-1}{2}\right)^{v_p(i)}$ for all $i$. This is because we have $a_k=a_{2k}=\dots=a_{(p-1)k}$ and $a_{pk}=\left(-\frac{p-1}{2}\right)a_k$, so $a_k+2a_{2k}+\dots+(p-1)a_{(p-1)k}+pa_{pk}=(1+2+\dots+(p-1))a_k-p\left(\frac{p-1}{2}\right)a_k$ $=\frac{p(p-1)}{2}\cdot a_k-\frac{p(p-1)}{2}\cdot a_k=0$ for all $k$.
I got that construction in about a minute, then gave up on the problem, and walked out expecting 0 points for it. I don't think the graders are particularly interested in the simplest cases, they're probably interested in the multiplicative sequence thing that I failed to see.
tenniskidperson3
25.04.2012 17:22
Seems like everyone's solutions are "unsure" or "not rigorous", so I'll post mine (exactly the same as pythag011's idea)
First let's state Bertrand's postulate: For any real $x>1$, there is a prime in the half-open interval $[x, 2x)$.
Let's do some easy cases first. $n=2$ is impossible, of course. If $n=4$: Let $i=2^k3^lm$ where $m$ is divisible by neither $2$ nor $3$. Then $a_i=2^k(-7)^l$ works: $a_i+2a_{2i}+3a_{3i}+4a_{4i}=a_i(1+2\cdot2+3\cdot(-7)+4\cdot4)=0$.
So otherwise we assume $n\neq4$ and $n>2$. We find two distinct primes $p_1$ and $p_2$ so that $\sqrt{n}<p_1\leq n$ and $\frac{n}{2}<p_2<n$. For $n=3$ we can choose $p_1=3$ and $p_2=2$. For $n=5$ we can choose $p_1=5$ and $p_2=3$; for $n=6$ through $n=8$ we can choose $p_1=3$ and $p_2=5$; from $n=9$ through $n=13$ we can choose $p_1=5$ and $p_2=7$, and from $n=14$ to $n=24$ we can choose $p_1=5$ and $p_2=13$.
Beyond this, if $n$ is even, then take $x=\frac{n+1}{2}$ in Bertrand's postulate. This shows that there is a prime in the interval $\left[\frac{n+1}{2}, n+1\right)$ or (equivalently) the interval $\left[\frac{n+1}{2}, n\right]$. But $n$ is even so it can't be prime. Thus there is a prime in the interval $\left[\frac{n+1}{2}, n-1\right]$, call it $p_2$ because $\frac{n}{2}<\frac{n+1}{2}\leq p_2\leq n-1<n$. If $n$ is odd, we choose instead $x=\frac{n}{2}$. There is thus a prime in the interval $\left[\frac{n}{2}, n\right)$. But $\frac{n}{2}$ is not an integer, so we shrink the interval to $\left[\frac{n+1}{2}, n-1\right]$. Then let this prime be $p_2$; it works for the same reasons.
Then there is a prime again in the interval $\left[\frac{p_2}{2}, p_2\right)$, call it $p_1$. But $p_1\geq\frac{p_2}{2}>\frac{n}{4}>\frac{\sqrt{n}\sqrt{16}}{4}=\sqrt{n}$. And clearly $p_1<p_2<n$.
So now, for all $n\neq4$ we've found two primes $p_1$ and $p_2$ with $\frac{n}{2}<p_2<n$ and $\sqrt{n}<p_1\leq n$. So now for every other prime besides $p_1$ and $p_2$, we define $a_{p_k}=p_2$. But there is some $x, y$ (by Bezout's theorem) so that $1+xp_1=yp_2$; let $a_{p_1}=x$. Then for all $m$ not divisible by $p_2$, if $m=p_1^{e_1}p_3^{e_3}p_4^{e_4}\ldots$ then let $a_m=a_{p_1}^{e_1}a_{p_3}^{e_3}a_{p_4}^{e_4}\ldots$; in other words, make it totally multiplicative. Finally let $a_1=1$.
Then all numbers less than or equal to $n$ that are not $1$, $p_1$ or $p_2$ have a prime factor that is not $p_1$ or $p_2$ (because $p_1$ and $p_2$ are greater than $\sqrt{n}$), and so all numbers $i$ that are not $p_1$ or $p_2$ have $p_2|a_i$.
So then the number $\frac{-a_1-2a_2-3a_3-\ldots-(p_2-1)a_{p_2-1}-(p_2+1)a_{p_2+1}-\ldots-na_n}{p_2}$ is just $\frac{-1-p_1a_{p_1}}{p_2}-m=\frac{-1-xp_1}{p_2}-m=-y-m$ for some integer $m$. We let $-y-m$ be $a_{p_2}$, so that $a_1+2a_2+\ldots+na_n=0$.
Thus $a_k+2a_{2k}+3a_{3k}+\ldots+na_{nk}=a_k(a_1+2a_2+3a_3+\ldots+na_n)=0$ because we made it totally multiplicative, so we can pull the factor of $a_k$ out whatever $k$ may be. Thus we're done.
mage24365
26.04.2012 15:50
The answer is the set of all integers that are at least 3.
For composite n where there are two primes p_1 and p_2 such that n/2<p_1<p_2<n, here's your construction:
Pick maximal integers j_1 and j_2 such that ((p_1)^(j_1))((p_2)^(j_2)) divides i.
Pick a minimal positive integer s such that (n(n+1)/2)+(s-1)(p_1) is 0 mod p_2. (You know it exists since p_1 and p_2 are relatively prime.)
Pick an integer t such that (n(n+1)/2)+(s-1)(p_1)+(t-1)(p_2)=0. (It exists because of how we defined s. It also must be negative.)
Then a_i=(s^(j_1))(t^(j_2)).
For n=4:
a_i=(-1)^(j_1+j_2), where (2^j_1)(3^j_2) divides i.
For n=6:
a_i=(2^j_1)(-5)^j_2, where (3^j_1)(5^j_2) divides i.
For n=10:
a_i=(2^j_1)(-9)^j_2, where (5^j_1)(7^j_2) divides i.
v_Enhance
28.01.2017 02:33
About five years later, here is a completed version of the solution I alluded to in 2012.
Answer: all $n > 2$.
For $n = 2$, we have $a_k + 2a_{2k} = 0$, which is clearly not possible, since it implies $a_{2^k} = \frac{a_1}{2^k}$ for all $k$.
For $n \ge 3$ we will construct a completely multiplicative sequence (meaning $a_{ij} = a_i a_j$ for all $i$ and $j$). Thus $(a_i)$ is determined by its value on primes, and satisfies the condition as long as $a_1 + 2a_2 + \dots + na_n = 0$. The idea is to take two large primes and use Bezout's theorem, but the details require significant care.
We start by solving the case where $n \ge 9$. In that case, by Bertrand postulate there exists primes $p$ and $q$ such that \[ \left\lceil n/2 \right\rceil < q < 2\left\lceil n/2 \right\rceil. \quad\text{and}\quad \frac{1}{2}(q-1) < p < q-1 \]Clearly $p \neq q$, and $q \ge 7$, so $p > 3$. Also, $p < q < n$ but $2q > n$, and $4p \ge 4\left( \frac{1}{2}(q+1) \right) > n$. We now stipulate that $a_r = 1$ for any prime $r \neq p,q$ (in particular including $r=2$ and $r=3$). There are now three cases, identical in substance.
If $p, 2p, 3p \in [1,n]$ then we would like to choose nonzero $a_p$ and $a_q$ such that \[ 6p \cdot a_p + q \cdot a_q = 6p + q - \frac{1}{2} n (n+1) \]which is possible by B\'ezout lemma, since $\gcd(6p,q) = 1$.
Else if $p, 2p \in [1,n]$ then we would like to choose nonzero $a_p$ and $a_q$ such that \[ 3p \cdot a_p + q \cdot a_q = 3p + q - \frac{1}{2} n (n+1) \]which is possible by B\'ezout lemma, since $\gcd(3p, q) = 1$.
Else if $p \in [1,n]$ then we would like to choose nonzero $a_p$ and $a_q$ such that \[ p \cdot a_p + q \cdot a_q = p + q - \frac{1}{2} n (n+1) \]which is possible by B\'ezout lemma, since $\gcd(p, q) = 1$. (This case is actually possible in a few edge cases, for example when $n=9$, $q=7$, $p=5$.)
It remains to resolve the cases where $3 \le n \le 8$. We enumerate these cases manually:
For $n = 3$, let $a_n = (-1)^{\nu_3(n)}$.
For $n = 4$, let $a_n = (-1)^{\nu_2(n) + \nu_3(n)}$.
For $n = 5$, let $a_n = (-2)^{\nu_5(n)}$.
For $n = 6$, let $a_n = 5^{\nu_2(n)} \cdot 3^{\nu_3(n)} \cdot (-42)^{\nu_5(n)}$.
For $n = 7$, let $a_n = (-3)^{\nu_7(n)}$.
For $n = 8$, we can choose $(p,q) = (5,7)$ in the prior construction.
This completes the constructions for all $n > 2$.
Idio-logy
12.06.2020 04:59
$n=2$ does not hold since $a_1=2^ka_{2^k}$ for any positive integer $k$. We will construct a valid sequence for any $n\ge 3$. In addition, we will make the sequence completely multiplicative. First, we list explicit constructions for small cases $n\le 8$: For $n=3,5,7$, let $a_k = (-\frac{n-1}{2})^{v_n(k)}$. For $n=4$, let $a_k=2^{v_2(k)}(-7)^{v_3(k)}$. For $n=6$, let $a_k=(-3)^{v_3(k)}4^{v_5(k)}$. For $n=8$, let $a_k=(-2)^{v_5(k)+v_7(k)}$. All of them satisfy $a_1+2a_2+\dots +na_n=0$, so they are valid since they are completely multiplicative. For $n\ge 9$, we choose two distinct primes $p<q$ using Bertrand's postulate: - If $n=4m$, let $2m<q<4m$ and $m<p<2m$. - If $n=4m+1$, let $2m+1<q<4m+2$ and $m+1<p<2m+2$. - If $n=4m+2$, let $2m+1<q<4m+2$ and $m+1<p<2m+2$. - If $n=4m+3$, let $2m+2<q<4m+4$ and $m+1<p<2m+2$. In all four cases, $4\le p<q\le n$, $2q>n$, and $4p>n$. Since it suffices to choose values at primes, we let $a_r=1$ for all primes $r$ except $p$ and $q$. The only condition left is \[a_1+2a_2+\dots +na_n=0,\]which is linear in $a_p$ and $a_q$ by our choices of $p$ and $q$. Since $q>6$ and $p>3$, $q$ is coprime with $(1+2+3)p$, so we are done by Bezout.
SnowPanda
19.06.2020 03:04
The answer is $n > 2.$ For $n = 2,$ we have $a_k + 2a_{2k} = 0$ for all positive integers $k,$ so $a_{2k} = -\frac{1}{2}a_k.$ This means $$a_{2^m} = \left(-\frac{1}{2}\right)^m a_1$$for all nonnegative integers $m.$ But for large enough $m$ this means $a_{2^m}$ is not an integer, so $n = 2$ does not work.
Now we show all $n > 2$ work.
Claim: For all $n \geq 3,$ let $p_1, p_2, \ldots, p_r$ be the set of primes less than or equal to $n,$ in increasing order. Then we can choose nonzero integers $c_1, c_2, \ldots, c_r$ such that $$\sum_{m = 1}^n m \cdot \left(\prod_{i = 1}^r c_i^{v_{p_i}(m)}\right) = 0.$$
Proof: First we show this is true for all $n \geq 16.$
By Bertrand's Postulate (which states that for all $n > 1,$ there is a prime $p$ with $n < p < 2n$), there is a prime in the interval $\left(\lceil{\frac{n}{4}}\rceil, 2\lceil{\frac{n}{4}}\rceil\right)$, and a prime in the interval $\left(\lceil{\frac{n}{2}}\rceil, 2\lceil{\frac{n}{2}}\rceil\right)$. Also, there is no integer in both intervals - this would require $2\lceil{\frac{n}{4}}\rceil \geq \lceil{\frac{n}{2}}\rceil + 2$ (because the integer $k$ would need to satisfy $k \geq 2\lceil{\frac{n}{4}}\rceil + 1$ and $k \leq \lceil{\frac{n}{2}}\rceil - 1$), and this never happens (we can check this is false for $n = 0, 1, 2, 3,$ so by writing $n = 4a + b$ with $b \in \{0, 1, 2, 3\},$ it is false for all $n$). This means the two primes are distinct. So then $p_r > \frac{n}{2}$ and $p_{r - 1} > \frac{n}{4}.$
Now set $c_i = 1$ for $1 \leq i \leq r - 2,$ and let $S$ be the sum over all $m$ not divisible by $p_r$ or $p_{r - 1}$ (of the given quantity). Since $n \geq 16,$ then $p_{r - 1}^2, p_{r - 1}p_r,$ and $p_r^2$ are greater than $n,$ so each $m$ is divisible by at most one of them, and is never divisible by their squares (for $1 \leq m \leq n$). Since $2p_r > n,$ the only term containing $p_r$ is $m = p_r,$ which contributes $p_r \cdot c_r$ to the sum. Since $4p_{r - 1} > n,$ the set of terms containing $p_{r - 1}$ is one of $\{p_{r - 1}\}, \{p_{r - 1}, 2p_{r - 1}\},$ or $\{p_{r - 1}, 2p_{r - 1}, 3p_{r - 1}\},$ so its contribution to the sum is $p_{r - 1}\cdot c_{r - 1}\cdot k,$ where $k \in \{1, 3, 6\}.$ So then the entire sum is $$S + c_r\cdot p_r + c_{r - 1}\cdot kp_{r - 1},$$where $k \in \{1, 3, 6\},$ and we need to choose $c_r, c_{r - 1}$ so that this sum is $0.$ But $p_r$ and $kp_{r - 1}$ are relatively prime (because $p_r \neq 2, 3$), so we can choose $c_r$ and $c_{r - 1}$ which make $c_r\cdot p_r + c_{r - 1}\cdot kp_{r - 1}$ to be any integer, which means we can make it $-S.$ Also, if $(c_r, c_{r - 1})$ works, then $(c_r - kp_{r - 1}, c_{r - 1} + p_r)$ also works, so we can repeatedly do this until $c_r$ is negative and $c_{r - 1}$ is positive. Then neither is $0,$ so we are done.
Now we show this is true for $3 \leq n \leq 15.$
For $n = 3,$ we can choose $c_1 = 1$ (corresponding to $p_1 = 2$) and $c_2 = -1$ (corresponding to $p_2 = 3$), as $1\cdot 1 + 2\cdot 1 + 3 \cdot (-1) = 0.$
For $n = 4,$ we can choose $c_1 = c_2 = -1$ (corresponding to $p_1 = 2, p_2 = 3$), as $1 \cdot 1 + 2\cdot (-1) + 3\cdot (-1) + 4\cdot 1 = 0.$
For $n = 5,$ we can choose $c_1 = c_2 = 1$ (corresponding to $p_1 = 2, p_2 = 3$) and $c_3 = -2$ (corresponding to $p_3 = 5$), as $1\cdot 1 + 2\cdot 1 + 3\cdot 1 + 4\cdot 1 + 5\cdot (-2) = 0.$
For $n = 6,$ we can choose $c_1 = 1$ (for $p_1 = 2$), $c_2 = 2$ (for $p_2 = 3$), and $c_3 = -5$ (for $p_3 = 5$), as $1\cdot 1 + 2\cdot 1 + 3\cdot 2 + 4\cdot 1 + 5\cdot (-5) + 6\cdot 2 = 0.$
For $7 \leq n \leq 15,$ we can check that $p_r > p_{r - 1} \geq \frac{n}{2}.$ Then the same argument applies - we can let $c_i = 1$ for $1 \leq i \leq r - 2,$ and let $S$ be the sum of the given expression over all $m$ not divisible by $p_{r - 1}$ or $p_r.$ Then since $n > 4,$ all of $p_{r - 1}^2, p_{r-1}p_r,$ and $p_r^2$ are greater than $n.$ Then the sum is $$S + c_r\cdot p_r + c_{r - 1}\cdot kp_{r - 1},$$where $k \in \{1, 3\}.$ Since $p_r \neq 3,$ then $p_r$ and $kp_{r - 1}$ are relatively prime, so by the same reasoning as before, it is possible to choose nonzero $c_r, c_{r - 1}$ so that this sum is $0.$
So then it is possible to choose such $c_i$ for all $n \geq 3.$
Now we show that taking $a_k = \prod_{i = 1}^r c_i^{v_{p_i}(k)}$ for all positive integers $k$ satisfies the problem. We have $v_p(mn) = v_p(m) + v_p(n),$ so then
\begin{align*}
\sum_{m = 1}^n ma_{mk} &= \sum_{m = 1}^n m\prod_{i = 1}^r c_i^{v_{p_i}(mk)} \\
&= \prod_{i = 1}^r c_i^{v_{p_i}(k)} \cdot \left(\sum_{m = 1}^n m\prod_{i = 1}^r c_i^{v_{p_i}(m)} \right)\\
&= 0,
\end{align*}by our choice of the $c_i.$ So then there exist such $a_i$ for all $n > 2.$
GeronimoStilton
22.06.2020 17:33
We claim that $n$ works iff $n\ge 2$. First, we show that $n=2$ does not satisfy this property. Suppose otherwise; consider some such sequence of $a_i$. Claim: For all $k \ge 1$, $a_1=(-2)^ka_{2^k}$. Solution: Induct on $k$. For the base case, remark that $a_1=-2a_2$ because $a_1+2a_2=0$. For the induction step, note that $a_1 =(-2)^ka_{2^k} = (-2)^k \cdot (-2a_{2^{k+1}}) = (-2)^{k+1}a_{2^{k+1}}$. $\fbox{}$ Remark that this implies that $2^k\mid a_1$ for all $k\ge 1$, absurd because $a_1\ne 0$. Now, we show that all $n\ne 2$ satisfy this property. For convenience, write $a_i=f(i)$. We will find multiplicative $f$ satisfying \[f(1)+2f(2)+\cdots + nf(n)=0,\]which will clearly suffice by multiplicativity. The idea is the following. When $n/4 \ge 2$, we can choose some primes \[\left\lfloor\frac{n}{4}\right\rfloor < q < 2\left\lfloor\frac{n}{4}\right\rfloor \le \left\lceil\frac{n}{2}\right\rceil\]and \[\left\lfloor\frac{n}{2}\right\rfloor < p < 2\left\lfloor\frac{n}{2}\right\rfloor \le n\]by Bertrand's Postulate. As long as $n/4 \ge \sqrt{n}$ (that is, $n \ge 16$), we can then fix $f(i)=1$ for all $i\perp pq$ then choose values of $p,q$ so \[0=\sum_{i=1}^n if(i) = \sum_{1\le i \le n, i\perp pq}i + pf(p)+xqf(q)\]by Bézout (where $x\in \{3,6\} = \{1+2,1+2+3\}$). Thus, it suffices to deal with the cases $n\le 15$. We then bash. For $n=3$, take $(f(1),f(2),f(3)) = (1,1,-1)$. For $n=4$, take $(f(1),f(2),f(3),f(4)) = (1,-1,-1,1)$. For $n=5$, take $(f(1),f(2),f(3),f(4),f(5)) = (1,1,1,1,-2)$. For $n=6$, take $(f(1),f(2),f(3),f(4),f(5),f(6)) = (1,-1,1,1,0,1)$. For $n=7$, we can use a similar Bézout argument with $p=7,q=5$ to generate a solution. For $8\le n \le 10$, take $(p,q)=(7,5)$ to generate a solution with Bézout. For $11\le n\le 15$, take $(p,q) = (11,7)$ to generate a solution with Bézout.
amuthup
24.08.2020 02:54
The answer is all $n>2.$ $\textbf{Claim: }$ $n=2$ doesn't work. $\emph{Proof: }$ Suppose there exists an infinite sequence of nonzero integers $a_1,a_2,\dots$ such that $$a_1+2a_2=0,$$$$a_2+2a_4=0,$$$$a_3+3a_6=0,$$$$\vdots$$This implies that $a_1=(-2)^{i}a_{2^i}$ for all $i,$ which is impossible as $a_1\ne 0.$ $\blacksquare$ $\textbf{Claim: }$ $n=6,7,8,10,11,12,13,14,15$ and all $n\ge 16$ work. $\emph{Proof: }$ Let $p_1,p_2,\dots,p_m$ be the set of primes less than or equal to $n.$ Note that for all values of $n$ specified in the claim, there exists a prime in the interval $\left(\sqrt{n},\frac{n}{2}\right]$ (check manually for $n=6,7,8,10,11,12,13,14,15$ and choose a prime between $n/2$ and $n/4$ for $n\ge 16$). Let this prime be $p_a.$ By Bertrand's Postulate, there exists a prime (say $p_b$) between $\left\lceil\frac{n}{2}\right\rceil$ and $n.$ Let $x_{p_a}$ be a positive integer such that $x_{p_a}\equiv -\frac{1}{p_a}\pmod{p_b}$ and let $x_{p_i}=p_b$ if $i\ne a,b.$ We will deal with $x_{p_b}$ later. Consider the sequence defined by $$a_k=\prod_{i=1}^{m}x_{p_i}^{\nu_{p_i}(k)}.$$We have $$\frac{1}{a_k}(a_{k}+2a_{2k}+\dots + na_{nk}=\sum_{i=1}^{n}\left(i\prod_{p\mid i}x_p\right),$$where primes are counted with multiplicity. Observe that every term on the RHS except $p_{a}x_{p_a}$ and $1$ is divisible by $p_b.$ But $1+p_{a}x_{p_a}$ is divisible by $p_a,$ so the sum of the terms on the RHS is divisible by $p_b.$ Thus, there is some value of $x_{p_b}$ such that $p_{b}x_{p_b}$ is equal to negative the sum of the other terms on the RHS, which results in a sum of zero. $\blacksquare$ $\textbf{Claim: }$ $n=3,4,5,9$ work. $\emph{Proof: }$ For $n=3,$ take the sequence $a_k=(-2)^{\nu_2(k)}.$ For $n=4,$ take the sequence $a_k=(-1)^{\nu_2(k)+\nu_3(k)}.$ For $n=5,$ take the sequence $(-4)^{\nu_3(k)}.$ For $n=9,$ take the sequence $(-8)^{\nu_5(k)}.$ $\blacksquare$
i3435
13.03.2022 21:46
The answer is $n>2$. $n=1$ doesn't work because $a_1$ must equal $0$. $n=2$ doesn't work because $a_1+2a_2=0$, so $v_2(a_2)=v_2(a_1)-1$, and similarly $v_2(a_{2^k})=v_2(a_1)-k$, so for large enough $k$, $v_2(a_{2^k})<0$. Let $p,q$ be the two largest primes below $n$. $p>\frac{n}{2}$ by Bertrand's postulate, and $q>\frac{n}{4}$ by another application of Bertrand's postulate. Thus for $n\ge 16$, $q>\sqrt{n}$. For $n=3,5\le n\le 15$, we can verify that $q>\sqrt{n}$. Thus for $n=3,n>5$, we can construct $a$ in the following way: $a_1=1$ $a_{\text{primes less than q}}=p$ $a_{\text{primes greater than q}}=1$ (it doesn't matter what their values are) $a_q=c$ such that $qc\equiv -1\mod p$, which is possible by Bezout $a_p=\frac{-1}{p}(a_1+2a_2+\cdots (p-1)a_{p-1}+(p+1)a_{p+1}+\cdots na_n)$ $a_{c_1c_2}=a_{c_1}a_{c_2}$ for any $c_1,c_2$ (the sequence is multiplicative) Because the sequence is multiplicative, we only have to verify that $a_1+2a_2+\dots na_n=0$. It suffices to show that $a_1+2a_2+\cdots (p-1)a_{p-1}+(p+1)a_{p+1}+\cdots na_n\equiv 0\mod p$. Because every prime less than $q$ has output of $p$, and $q^2>n$, it suffices to show that $a_1+qa_q\equiv 0\mod p$, but this is true by construction. Now the only case left is $n=4$, but the following works in that case. $a_1=1$ $a_{2}=a_3=-1$ $a_{\text{primes greater than q}}=1$ (again it doesn't matter what their values are) $a_{c_1c_2}=a_{c_1}a_{c_2}$ for any $c_1,c_2$ (the sequence is also multiplicative)
IAmTheHazard
31.08.2023 03:42
The answer is $n \neq 2$. Clearly $n=2$ fails, since by induction we should have $a_1=(-2)^ka_{2^k}$ for all $k$, which is absurd unless $a_1=0$. Now we provide a construction for the other $n$. First, impose the condition that $(a_i)$ is a completely multiplicative sequence, so it suffices to construct $a_1,\ldots,a_n$ (satisfying this multiplicativity condition) such that $a_1+2a_2+\cdots+na_n=0$. For $n=3$ take $(a_1,a_2,a_3)=(1,1,-1)$, and for $n=4$ take $(a_1,a_2,a_3,a_4)=(1,2,-7,4)$. Now assume $n \geq 5$; in this case I claim that there exist two primes $(p,q)$ with $n \geq p>n/2$ and $p>q>\sqrt{n}$. Indeed, If $5 \leq n \leq 6$ then take $(p,q)=(5,3)$. If $7 \leq n \leq 12$ then take $(p,q)=(7,5)$. If $n \geq 13$, then by Bertrand pick $p$ to be a prime in $(n/2,n)$ and $q$ to be a prime in $(n/4,n/2)$, which works since $\lceil n/4\rceil>\sqrt{n}$. Let $e=\lfloor n/q\rfloor<\sqrt{n}$. For $1 \leq i \leq n$, if $i \perp pq$ then set $a_i=1$. Then since $q^2>n$, for any $1 \leq i \leq e$ we have $a_{eq}=a_q$, and $$\sum_{i=1}^e eqa_{eq}=\frac{qe(e+1)a_q}{2}.$$Since we clearly have $e<p-1$, it follows that $\tfrac{qe(e+1)}{2} \perp p$, hence as $a_q$ varies the above expression can obtain any value modulo $p$; in particular, we should be able to pick $a_q$ such that $$p \mid \sum_{\substack{1 \leq i \leq n\\i \neq p}} ia_i,$$and we are then free to set $a_p$ to the correct value to make $a_1+2a_2+\cdots+na_n=0$. $\blacksquare$
HamstPan38825
05.01.2024 04:10
The answer is all $n \geq 3$. $n=2$ fails because the condition implies $a_i$ is even for every $i$, creating an infinite descent. For construction, let $\{a_i\}$ be a completely multiplicative sequence. In other words, we fix $a_1 = 1$ and $a_{ij}= a_i \cdot a_j$ for all $(i, j)$. Such a construction is obviously impossible by, say, expressing $n$ as a product of its prime factors. Then, it suffices to have $$a_k+2a_{2k}+\cdots+na_{nk} = a_k(a_1+2a_2+\cdots+na_n) = 0,$$which means we need only solve the $k=1$ case. Furthermore, for some $n = p_1^{k_1} p_2^{k_2} \cdots p_\ell^{k_\ell}$, we have $$a_1+2a_2+\cdots+na_n = \prod_{i=1}^\ell (a_1+2a_2+\cdots+p_ia_{p_i})^{k_i}$$so it suffices to show that we may force $a_1+2a_2+\cdots+p_ia_{p_i} = 0$ for any $p_i \mid n$. This is done for all $p_i \geq 3$ by fixing a prime $\frac{p_i}2 < q < p_i$ using Bertrand: we may pick all terms except for $a_q$ arbitrarily and then $a_q$ such that $a_1+2a_2+\cdots+(p_i-1)a_{p_i-1}$ is a multiple of $p_i$ as $\gcd(p, q) = 1$. This finishes the problem for all $n$ that isn't a power of two. If $n$ is a power of two, we cannot have $a_1 = 1$ and $a_1+2a_2 = 0$, so we instead force $a_1+2a_2+3a_3+4a_4 = 0$ by picking $a_2 \equiv -1 \pmod 3$ (yielding $a_1+2a_2+4a_4 \equiv 1-2+4 = 0 \pmod 3$) and then $a_3$ to satisfy the condition. This finishes the problem.
naonaoaz
09.03.2024 21:42
Notice that $n = 2$ fails since then \[a_1 = -2a_2 = 4a_4 = -8a_8 = \cdots\]Now we'll construct as sequence for all $n \ge 3$. Let the sequence be multiplicative, so $a_{ij} = a_ia_j$ for any $i,j \ge 1$. Thus it suffices to find $a_1,\ldots,a_n$ such that \[\sum_{i = 1}^n i \cdot a_i =0\]First assume that $n \ge 25$. A stronger version of Betrand's postulate implies there exists primes $p$ and $q$ such that \[\frac{5}{6}n < p < n \text{ and } \frac{5}{6}p < q < p \implies \frac{n}{2}<\frac{25}{36}n < q < p <n\]Thus, let all $a_i = 1$ for all $i \le n$ such that $i \neq p,q$. Since both $p,q > \frac{n}{2}$, after we do this, the sequence is still multiplicative. Now we need to find $a_p$ and $a_q$ with \[pa_p+qa_q = \text{some constant}\]Since $\gcd(p,q) = 1$, such $a_p$ and $a_q$ exist by Bezout's Lemma. For $n<25$, do the following: If $17 \le n < 25$, then take $p = 17$ and $q = 13$ and repeat the argument above. If $13 \le n < 17$, then take $p = 13$ and $q = 11$ and repeat the argument above. If $11 \le n < 13$, then take $p = 11$ and $q = 7$ and repeat the argument above. For $n = 10$, take $(1,-1,-1,1,7,1,4,-1,1,-7)$ as the first $10$ numbers. For $7 \le n \le 9$, then take $p = 7$ and $q = 5$ and repeat the argument above. For $n = 6$, take $(1,-1,6,1,3,-6)$ as the first $6$ numbers. For $n = 5$, take $(1,-1,4,1,-3)$ as the first $5$ numbers. For $n = 4$, take $(1,-1,-1,1)$ as the first $4$ numbers. For $n = 3$, take $(1,1,-1)$ as the first $3$ numbers.
Mathandski
07.05.2024 01:50
Similar two primes solution as above except without Bezout (I wrote this up at school today had to use Word)
Attachments:
Pitchu-25
06.06.2024 20:55
We claim that the answer is always positive except for $n=2$. First of all, it's clear that no such sequence exists for $n=2$ since $v_2(a_1)$ would need to be arbitrarly large, which is impossible for any non zero $a_1$. Next, we exhibit sequences that work for $n=3,4,\ldots,8$ : $\star$ For $n=p$ prime, take $a_k=\left(-\frac{p-1}{2}\right)^{v_p(k)}$. $\star$ For $n=4$, take $a_k=(-1)^{v_2(k)+v_3(k)}$, and for $n=8$ take $a_k=(-1)^{v_2(k)+v_3(k)+v_5(k)}$. $\star$ For $n=6$, take $a_k=(-3)^{v_3(k)}\times 4^{v_5(k)}$. Here is what we do for a general $n$. We want to construct a sequence of the form $a_k=\prod_{p}A_p^{v_p(k)}$, where the product ranges over all primes $p\le n$ (all $A_p$'s are constant). Then, for such a sequence to work, the $A_p's$ must be the root of some multivariable polynomial. For $n=9$, take $A_2=A_3=1$, then, since the only $5$ and $7$ terms that show up will be $5A_5+7A_7$, we can adjust by Bezout to get a working sequence. For $n\ge 10$, take a prime $n/2<q\le n$ and a prime $r$ with $n/4<r\le n/2$. We assign the value $1$ to all $A_p$'s with $p\ne q,r$. Then, the monomials containing $r$'s will be either $rA_r$, or $rA_r+2rA_r=3rA_r$, or $rA_r+2rA_r+3rA_r=6rA_r$. On the other hand, the only monomial containing $q$ will be $qA_q$. Since $q>n/2$, we have $q\ge 7$, so again we get two coprime bases and the result follows with Bezout. $\square$
ihategeo_1969
01.07.2024 14:21
We claim that \[\boxed{\text{$n$ works iff $n \geq 3$}}\]. It is obvious to see why $n=2$, does not work because of $\nu_2$ issues. We will prove the converse now. Lemma(Chebyshev's Estimate)There exists two distinct prime number in the range $\left(\frac{n}2,n\right]$ iff $n \neq 4$, $6$, $10$. Proof: Use the Prime Number Theorem and some manual computation. $\square$. So we will first prove the result holds for $n=4$, $6$, $10$. See that one can take $\bullet$ For $n=4$, take $a_k={(-1)}^{\nu_2(k)+\nu_3(k)}$. $\bullet$ For $n=6$, take $a_k={(-2)}^{\nu_2(k)} \cdot 2^{\nu_3(k)}$. $\bullet$ For $n=10$, take $a_k=2^{\nu_5(k)} \cdot {(-9)}^{\nu_7(k)}$. Now for the other $n$, let $\frac{n}2 <p \leq q \leq n$ and then look at the equation \[p(X-1)+q(Y-1)=-\frac{(n)(n+1)}2\]which obviously has solutions and see that \[a_k=X^{\nu_p(k)} \cdot Y^{\nu_q(k)} \text{ if $p \neq q$}\]\[a_k={(X+Y)}^{\nu_p(k)} \text{ if $p=q$}\]works fine.