2

What is the smallest positive integer N such that the integer formed by reversing the digits of N is triple N? (Does such an integer even exist? If not, then for what multiplier for $N$ will such an integer exist?)

Here are my thoughts so far: (where $n$ is the number of digits of $N$) $$N=\sum\limits_{i=0}^{n}{d_i 10^i}$$ $$3N=\sum\limits_{i=0}^{n}{d_i 10^{n-i}}$$ therefore $$3\sum\limits_{i=0}^{n}{d_i 10^i}=\sum\limits_{i=0}^{n}{d_i 10^{n-i}}$$ so $$\sum\limits_{i=0}^{n}{d_i(10^{n-i}-3\times10^i)}=0$$ $$d_0(10^n-3)+d_n(1-3\times10^n)+\sum\limits_{i=1}^{n-1}{d_i(10^{n-i}-3\times10^i)}=0$$ $$d_0(10^n-3)+d_n(1-3\times10^n)+10\sum\limits_{i=1}^{n-1}{d_i(10^{n-i-1}-3\times10^{i-1})}=0$$ Then using congruence relations, $$d_0(10^n-3)+d_n(1-3\times10^n)+10\sum\limits_{i=1}^{n-1}{d_i(10^{n-i-1}-3\times10^{i-1})}\equiv 0\pmod{10}$$ $$d_0(10^n-3)+d_n(1-3\times10^n)\equiv 0\pmod{10}$$ However, this doesn't seem like the right way to go; even if I can get many congruence relations I would still have to brute-force many different N values to confirm the congruence relations. So how can I solve the puzzle without brute-forcing it?

feralin
  • 1,693

2 Answers2

2

There is no such $N$ (besides $0$).

Now, say $N$'s first digit is $a$ and its last digit is $b$. Since $N$ and $3N$ have the same number of digits, $a$ can only be $1, 2$, or $3$. If $a=3$, then $b=9$ is the only choice, but this is impossible since then $3N$ would end in $7$, not $3$. $a=1$ also doesn't work, since then $b$ would have to be $3, 4,$ or $5$, and none of those triple to $1 \mod 10$. Similarly, $a=2$ doesn't work, since then $b$ must be $6, 7,$ or $8$, none of which triple to a number ending in $2$.

As an extension, you can show by the same reasoning that it still doesn't work if you change $3$ to any positive integer greater than $1$, except possibly $4$ (where $N$ must start with $2$ and end with $8$) and $9$ (where $N$ must start with $1$ and end with $9$). It obviously won't work if the multiplier is greater than $9$ since then the number of digits will change.

Nishant
  • 9,155
2

Question

Let $n \in \mathbb{N}_0$. Is there a $N = \sum_{i=0} d_i \cdot 10^i \in \mathbb{N}$ such that $$3N = \sum_{i=0}^{p := \lfloor \log(N) \rfloor} d_{p-i} \cdot 10^i$$

Answer

The answer was already given by Nishant, but I would like to add some thoughts.

Pre-Calculation

\begin{align} n \cdot N &= \sum_{i=0}^{p := \lfloor N \rfloor + 1} d_{p-i} \cdot 10^i\\ \Leftrightarrow n \cdot \sum_{i=0} d_i \cdot 10^i &= \sum_{i=0} d_{p-i} \cdot 10^i\\ \Leftrightarrow 0 &= \sum_{i=0} d_{p-i} \cdot 10^i - n \cdot \sum_{i=0} d_i \cdot 10^i\\ &= \sum_{i=0} \underbrace{(d_{p-i} - n \cdot d_i)}_{\in [-n \cdot 9, 9]} \cdot 10^i \end{align}

Restriction 1

Now you can easily see that the first digit $d_0$ and the last digit $d_p$ have to fulfill the following equation:

$$n \cdot d_p - d_0 \equiv 0 \mod 10$$

Testscript

#!/usr/bin/env python


def digit_reverse(N):
    return int(str(N)[::-1])


def test(N, n):
    """ Test if a = (N digit-reversed) fulfils n*N = a """
    return n*N == digit_reverse(N)


def search_smallest(n):
    # Obiously, it works for 0...
    N = 1
    while not test(N, n):
        N += 1
    return N

if __name__ == '__main__':
    from argparse import ArgumentParser

    parser = ArgumentParser()

    # Add more options if you like
    parser.add_argument("-n", "--multiplier", dest="n",
                        default="9", type=int)
    args = parser.parse_args()
    print(search_smallest(args.n))

Answer

n = 1

Obviously $1, 2, 3, 4, 5, 6, 7, 8, 9$ work. Also, every palindrome works.

A generating formula done with Python is:

def getPalindrome():
    """
        Generator for palindromes.
        Generates palindromes, starting with 0.
        A palindrome is a number which reads the same in both
        directions.
    """
    yield 0
    for digits in count(1):
        first = 10 ** ((digits - 1) // 2)
        for s in map(str, range(first, 10 * first)):
            yield int(s + s[-(digits % 2)-1::-1])

n = 2

Because of restriction one, you know that the first digit $d_0$ cannot be

  • uneven (1, 3, 5, 7, 9)
  • 0

So we know: $d_0 \in [2, 4, 6, 8]$ and $d_p = 2 \cdot d_0 \mod 10$

If we only take digits up to 4, we don't get a carry digit. So we would all the time only compare the digits. As one side gets multiplied with 2, the only number that can fulfill that would be 0.

So we know: We need at least once a digit from $[5, 6, 7, 8, 9]$.

n = 4

  • 2178
  • 21978
  • 219978
  • 2199978
  • 21782178
  • 21999978

Infinitely more more:

\begin{align} d_p &= 2\\ d_{p-1} &= 1\\ d_{i} &= 9 \forall i \in 2, \dots, p-2\\ d_{1} &= 7\\ d_{0} &= 8 \end{align}

The $9$s cancel themselves and it works for the other 4 digits, too.

n = 9

  • 1089
  • 10989
  • 109989
  • 1099989
  • 10891089
  • 10999989

Infinitely more:

\begin{align} d_p &= 1\\ d_{p-1} &= 0\\ d_{i} &= 9 \forall i \in 2, \dots, p-2\\ d_{1} &= 8\\ d_{0} &= 89 \end{align}

$n \geq 10$

Not possible. How should you get a digit more by reversing the digits?

Follow-up question

For 4 and 8: Are there infinitely many numbers that don't follow the described patterns?

Martin Thoma
  • 9,821