2
$\begingroup$

I know that 1 times 3 to any power is odd number. And 0 or 2 times 3 to any power is even. So, the occurrences of 1s determine if the base 3 expansion of n is odd or even and 1 has to appear odd number of times because 2(2n+1) = 2k which is even. But I am having hard time translating these to mathematical statements as I am very new to mathematics.

$\endgroup$
  • 2
    $\begingroup$ To be honest, I understand your argument perfectly even if you did not use any mathematical notation. I believe using mathematical notation would do more harm than good - would make the argument less clear. $\endgroup$ – Stinking Bishop Nov 15 at 10:20
  • $\begingroup$ To be honest I don't understand your reference to $2n+1$. $\endgroup$ – Yves Daoust Nov 15 at 10:30
  • $\begingroup$ @Yves odd values can pair up is basically what it means, this can actually be used to restate Collatz.$$C(n_3)=\begin{cases}n_31_3\quad\text{if $n_3$ has an odd number of 1s}\\{n_3\over 2}\quad\text{if $n_3$ has an even number of 1s}\end{cases}$$ $\endgroup$ – Roddy MacPhee Nov 15 at 12:26
  • $\begingroup$ @RoddyMacPhee: good to know, but the $2n+1$ in the OP has nothing to do there AFAIK. $\endgroup$ – Yves Daoust Nov 15 at 13:10
  • $\begingroup$ @YvesDaoust yes it does as $2(2n+1)$ is a digit sum of the odd digits. $\endgroup$ – Roddy MacPhee Nov 15 at 13:14
4
$\begingroup$

With $d_k$ denoting the $k^{th}$ digit of $n$ from the right,

$$n=\sum_{k=0}^m d_k3^k$$ $$=\sum_{k=0,\\d_k=0}^m d_k3^k+\sum_{k=0,\\d_k=1}^m d_k3^k+\sum_{k=0,\\d_k=2}^m d_k3^k$$ $$=\sum_{k=0,\\d_k=1}^m 3^k+2\sum_{k=0,\\d_k=2}^m 3^k$$ $$\equiv\sum_{k=0,\\d_k=1}^m 1 \bmod 2$$ because $3^k\equiv 1\bmod2$.

Hence the number of ones must be odd.


In common language:

All even digits (zero or two) bring an even contribution, and all odd digits (one) an odd contribution (some power of three). The global parity is the parity of the number of odd contributions.

$\endgroup$
3
$\begingroup$

Don't mistake the lack of formulas for a lack of mathematics. Your proof is more than mathematical enough the way it is.

That being said, it could be clearer, even without any formulas. Just a little trim will help (as Yves notes above, the 2n+1 thing is a bit unclear). Something like this is maybe just as good:

1 times 3 to any power is odd number. And 0 or 2 times 3 to any power is even. So, the occurrences of 1s determine if the base 3 expansion of n is odd or even.

If you really want to explain more, I would encourage you to explain why 0 or 1 or 2 times a power of 3 is relevant, by referencing the fact that that's what the base 3 expansion of a number is. Also, it could help to frame this proof, so that we all know what's being proven and that it has been proven as we read it:

Take some number $n$ written in base $3$. The digits (trits) of $n$ denote how $n$ is written as a sum of powers of $3$, some multiplied by $0$, some by $1$ and the rest by $2$. $1$ times any power of $3$ is an odd number. And $0$ or $2$ times any power of $3$ is even. So, the occurrences of $1$s is what determines if $n$ is odd or even.

$\endgroup$
0
$\begingroup$

It follows by casting out twos - the radix $3$ analog of casting out nines in radix $10,\,$ viz.

$\!\!\!\begin{align}\bmod 2\!:\,\ \color{#0a0}{3}\equiv \color{#c00}{\bf 1}\, \ \Rightarrow\!\!\!\! &\ \ \ \ \ \ \overbrace{d_0 + d_1 \ \color{#0a0}{3}\, +\, d_2\, \color{#0a0}{3}^2 + d_3\,\color{#0a0}{3}^3+\,\cdots }^{\!\!\!\textstyle\text{integer in radix $\color{#0a0}{\,3\,}$ with digits $\,d_i$}} \\[.3em] &\equiv\, d_0+d_1\,\color{#c00}{\bf 1}\ +d_2\,\color{#c00}{\bf 1}^2\! + d_3\,\color{#c00}{\bf 1}^3 +\,\cdots \\[.3em] &\equiv\, d_0 + d_1\ +\ d_2\ +\ d_3\ +\, \cdots\, \equiv\, \text{ digit sum}\\[.3em] &\equiv\ \text{number of } \textit{odd }\text{ digits $\,d_i = 1,\, $ by even digits $\equiv 0$} \end{align}$

where we employed the Congruence Sum & Product Rules (or Polynomial Rule)

$\endgroup$

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.