3

For a natural number $n$, the digital root of $n$ is the value obtained by an iterative process of summing digits. The digital root of $n$ is denoted by $d(n)$.

Examples; $d(142)=7$, $d(123785)=8$

In $2013$, I attended a hard mathematical tournament. In this tournament, no one answered this question, and I am curious to know the key of solving it. Any help will be appreciated.

If $d(n)=n-9\left \lfloor \frac{n-1}{9} \right \rfloor$, find the value of $d(\underset{\text{The number of }2 \text{'s is }2013}{\underbrace{2^{2^{2^{.^{.^{.^{2}}}}}}}})$.

Hussain-Alqatari
  • 5,065
  • 2
  • 13
  • 39
  • At a (very brief) first glance I would try using modular arithmetic, maybe reducing this big old number mod 9 or something. The floor function here is interesting because those always emerge naturally in division algorithms. What have you tried? – Jack Crawford Jul 04 '19 at 23:08
  • 1
    Are you sure that it was asking for the digital root? Because $d(n)=n-9\left \lfloor \frac{n-1}{9} \right \rfloor$ is not the same as the digital root. Consider $n = 19$. – Varun Vejalla Jul 04 '19 at 23:44
  • We need to find the value of "two to the power two to the power two to... (many times, a finite number)" modulo $9$. Two is prime to $9$. Euler. So we need to know the value of "two to the power two to... (many times, a finite number)" modulo $6=\phi(9)$. The above number is divisible by $2$. So we need (Chinese R.T.) the value of "two to the power two to... (many times, a finite number)" modulo $3$, the other factor of $6$. We can go on with Euler / Fermat, but note that $2=-1$ modulo $3$, and we have an even power. Putting all together we get the answer... – dan_fulea Jul 04 '19 at 23:52
  • 3
    @automaticallyGenerated: yes, it is the same. $d(19)=19-9\lfloor \frac{19-1}9\rfloor=19-9\cdot 2=1$, which is the same as $1+9=10,1+0=1$ – Ross Millikan Jul 04 '19 at 23:53
  • Whoops, I didn't realize that $10 \ge 10$ – Varun Vejalla Jul 04 '19 at 23:56
  • Related: What is the sum of sum of digits of $4444^{4444^{4444}}$ – Simply Beautiful Art Aug 09 '19 at 14:06

1 Answers1

7

I have found a suspiciously simple answer to this problem, so I would appreciate it if you could check my work. Let us define $\textrm{tow}(2, k)$ to indicate a power tower of $2$s of height $k$. We know that $2^6 \equiv 1 \mod 9$. Thus, $\textrm{tow}(2, 2013) \equiv 2^{a}\mod 9$, where $a \equiv \textrm{tow}(2, 2012) \mod 6$. However, note that $2^{2k} \equiv 4 \mod 6$ when $k>0$. $\textrm{tow}(2, 2012)$ is obviously even, so it follows that $\textrm{tow}(2, 2013) \equiv 2^{4}\equiv 7\mod 9$. Using the formula for $d(n)$ that you provided, we see that our final answer is indeed just $7$.

Sohom Paul
  • 754
  • it really is just applying Euler's totient theorem twice. with a bit of nuance once you want to go back down the chain. –  Jul 05 '19 at 00:53