Natural numbers with unique digit sum and product

decimal-expansiondiophantine equationselementary-number-theory

This question is inspired by this poorly received question.

For a given base $b$, every natural number has a unique representation in that base, and a corresponding digit sum and digit product. If a natural number $n$ is uniquely determined by its digit sum and digit product in base $b$, call that number $b$-good.

Question: For every natural number $b\geq2$, what are the $b$-good numbers?

Equivalently, given a natural number $b\geq2$, for which natural numbers $n$ are there no other natural numbers $m$ such that $n$ and $m$ have the same digit sum and the same digit product in base $b$?

Here are some examples and some non-examples in base $10$:

  • The numbers $2146$ and $382$ both have digit sum $13$ and digit product $48$. So neither is uniquely determined by its digit sum and digit product in base $10$, and so neither is $10$-good.
  • The number $3$ is uniquely determined by its digit sum $3$ and digit product $3$, in any base $b>3$, so $3$ is $b$-good for every $b>3$.
  • The number $4$ has the same digit sum and product as the number $22$, in any base $b>4$. So $4$ is not $b$-good for any sensible $b$.

My progress so far:

  • The $2$-good numbers are precisely the natural numbers of the form $n=2^m-1$.
  • For $b>2$, the number $2$ is always $b$-good.
  • If a natural number $n$ is $b$-good for some $b>2$, then $n$ is a repdigit in base $b$, meaning that the base-$b$ representation of $n$ consists of a single digit $d$ repeated some number of times. Moreover $d\neq2,4$ unless $n=2$.

None of the above is difficult to prove, I believe, but I can include proofs if desired.

Best Answer

For the case where we allow permutations of the digits, as OP indicates, we should focus on the repdigits.

Let $ a_d$ be the repdigit with digit $a$ written $d$ times.

Obvious Lemma: If $a_d$ is not good, then neither is $a_{d+1}$.

Obvious Lemma: If $a_d$ is not good, there is some combination of non-$a$ digits whose product is $a^k$ and whose sum is $ka$.

Corollary: $1_d$ is always good.

Corollary: If $a$ is composite, $a_d$ is always not good.
Hint: Think about 6.

Corollary: If $a$ is a prime $ \geq \sqrt{b}$, then $a_d$ is always good.
Hint: There is no digit $(a^2)$.

Claim: If $a$ is a prime and $ 3 \leq a < \sqrt{b}$, then $a_d$ is always good.

Proof: Suppose not. Let $D$ be the smallest $d$ such that $a_d$ is not good.
Let $a_D$ pair with $n$, which consists of $ k_i $ digits of the form $(a^i)$, for $i \geq 0 $. We have

  • $ k_1 = 0 $ (otherwise it contradicts the minimality of $D$)
  • $ \sum_{i\geq 2} k_i > 0 $ (since $n$ must contain a digit of the form $a^i$ for $ i \geq 2$).
  • $\sum k_i a^i = aD$ (digit sum)
  • $\prod a^{ik_i} = a^D \Rightarrow \sum ik_i = D $. (digit product, consider exponent)
  • Furthermore, since $ik_i = 0 $ for $ i = 0, 1$, hence $\sum_{i\geq 2 } i k_i = D$.

Then, we then have the following contradiction:

$\begin{array} {l l } aD & = \sum k_i a^i & \text{Digit sum} \\ & \geq \sum_{i \geq 2} k_i a^i & \text{Exclude } i = 0, 1 \\ & > \sum_{i\geq 2} k_i ai & \text{Uses 1)} a^i > ai \text{ for } a \geq 3, i \geq 2 \text{ and } \\ & & 2) \sum_{i\geq 2} k_i > 0 \text{ to establish strict inequality}\\ & = a \sum_{i\geq 2} k_i i & \text{Factor out } a \\ & = aD & \text{Digit Product result} \end{array} $

Hence, there is no such $D$, so $a_d$ is always good.

Corollary: If $ b > 4$, then $2_d$ is not good iff $d\geq 2$.
Hint: The previous proof breaks down because the inequality $a^i > ai$ doesn't hold for $ a = 2, i = 2$.

Corollary: If $ b \leq 4$, then $2_d$ is always good.
Hint: There is no digit $(2^2)$.

Incomplete musings for the more general case where we exclude permutations of the digit and restrict to $b \geq 4$ for the interesting case):

Each number can be expressed as $1_{i_1} 2 {i_2} \ldots (b-1)_{i_{b-1} } $, where the sub index $i_j$ indicates how many times the digit $j$ appears.

Obvious lemma: If $1_{i_1} 2 {i_2} \ldots (b-1)_{i_{b-1} } $ is not good, then neither is $1_{j_1} 2 {j_2} \ldots (b-1)_{j_{b-1} } $ where $j_k \geq i_k$.

So, we only need to focus on categorizing good numbers which comprises of

  • composite numbers are not allowed
  • 1 as many times as we want
  • primes $ a \geq \sqrt{b}$ as many times as we want -> These will never affect the result.
  • primes $ 3 \leq a > \sqrt{b}$ as many times as we want
  • 2 at most once

Some (but not all) additional constraints are:

  1. If the 2 smallest distinct primes are $ p, q < \sqrt{b}$, then $i_1 < pq - p - a $.
  2. If for prime $ 3 \leq a < \sqrt{b}$ we have $i_a \geq 2$, then $ i_1 < a(a-2)$
Related Question