0
$\begingroup$

We denote by $C$ the set of integers of Cantor, that is to say the natural integers whose writing in base 3 does not admit any number 1.

Calculate $\sum \limits_{a\in C,a<3^{2017}} a^{103} \mod (2^{89}-1)$.

Source : les dattes à Dattier

$\endgroup$
  • 2
    $\begingroup$ For anyone who wonders: $2^{89}-1$ is prime. $\endgroup$ – ThomasR Jan 25 '17 at 22:22
5
$\begingroup$

So it's 98191387587393867840363579. You should have pretty good intuition.

Edit: explanation.

  1. Well, lets imagine the following situation: given an integer $A$ and integers $B[1], B[2], ..., B[k]$, we want to calculate following sum: $\sum_{c=1}^{k} (A+B[k])^p$ for some p.

  2. Lets look at the polynomial formula: $(a + b)^n$ = $\sum_{i, j, i + j = n} (\frac{n!}{i!j!}a^ib^j)$. Applying this to $A$ and $B[1], .., B[k]$ we get $$ S = \sum_{c=1}^{k} (A+B[k])^p = \sum_{i, j, i + j = p}\frac{p!}{i!j!}(A^i \sum_{c = 1}^{k}B[c]^j).$$ Thus knowing only the sum of the $j^{th}$ powers of each $B$ for all $0 \le j \le p$ we can calculate $S$.

  3. Ok, now lets calculate following: $dp[i][j]$ = sum of $j^{th}$ powers of all Cantor numbers $B[k] < 3^{i}$, or $dp[2017][103]$ is what we are looking for.

  4. To do this, one first can notice that following from point 2, $$dp[m][n] = dp[m - 1][n] + \sum_{i, j, i + j = n}\frac{n!}{i!j!}(2\cdot 3^{m-1})^i \cdot dp[m-1][j].$$ The proof is left as an exercise to the reader.

  5. Everything should be calculated mod $2^{89}-1$, starting with $dp[][]$ filled with zeroes and going into the ranges $1 \le i \le 2017$ and $0 \le j \le 103$.

This approach took about 5 minutes in Wolfram Mathematica 7.0 to finish and works in $O(2017 \cdot 104 \cdot 104 \cdot O(\text{long arithmetics}))$.

I used this code. Sorry if it's not great, I'm more used to C++.

Sorry for my English, I'm not a native speaker. If you have any questions left feel free to ask.

$\endgroup$
  • 2
    $\begingroup$ A little explanation definitely wouldn't hurt. $\endgroup$ – Ivan Neretin Jan 26 '17 at 21:18
  • $\begingroup$ My dear GaBuZoMeu, can you explain or give your algorithm ? $\endgroup$ – Dattier Jan 26 '17 at 21:47
  • 1
    $\begingroup$ Explained, answer edited $\endgroup$ – i.trofimow Jan 27 '17 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.