0
$\begingroup$

Definition

Let $W$ be the function , defined as $W(a,b)=r$

given $a,b\in \mathbb{Z_+}$ and $a>1$

Take $m$ to be the integer s.t. $a^{m+1} \ge b > a^{m}$, i.e. $m = \lceil \log{b}/\log{a} \rceil - 1$.

Convert number $a^{m+1} - b$ in base $a$ and add its digits

$$a^{m+1} - b = (r_{l} r_{l-1} ... r_{1} r_{0})_{a}$$

Where $r=\sum_{i=0}^{l}r_{i}$.

Show that $W(10,9x+1)=9$

Iff $x=\{(\ \underbrace{ 1\ 1\cdots\ 1\ 1}_{\text{$n$ terms}}\ \ 0 \ \ \underbrace{ \alpha_t\ \alpha_{t-1} \cdots \alpha_1 \ \alpha_0}_{\text{$u$ terms, u=t+1}}) \mid\ n,u\ge 0\ and \ 9 \ge \alpha_j\ge \alpha_{j-1} \ge 1 \ for \ t\ge j \ge 1 \}$

Example

$x= \begin{align} 5 \\ 432 \\ 1108552 \\ 111110777322 \\110111 \\ 11103221 \\ 11110 \\ \vdots \end{align}$

Note: $x$ have at most only one '0' digit means $111...111$ not alowd

Python programming for calculate $W$ function

n1=5
n2=77
rem_array = []
while n2 != 1:
    mod = n2%n1
    if mod != 0:
      rem = n1-mod
      n2 = n2 + rem
      rem_array.append(round(rem))
      n2=n2/n1
    else:
        n2 = n2/n1
        rem_array.append(0)
print(rem_array[::-1])
print(sum(rem_array))

$\endgroup$
4
  • $\begingroup$ Are you sure? Can you explain how to calculate $W(10,10) = 9$ or $W(10, 100 ) = 9$, or $ W(10, 109) = 9$? $\endgroup$
    – Calvin Lin
    Dec 1 '19 at 20:33
  • $\begingroup$ @CalvinLin in $W(10,10) \implies x=1,W(10,100) \implies x=11,W(10,110) \implies x=12$ which not satisfied. $\endgroup$
    – Pruthviraj
    Dec 1 '19 at 20:56
  • $\begingroup$ Ah ic. I missed the "iff" condition as it wasn't indicated in the title. $\endgroup$
    – Calvin Lin
    Dec 2 '19 at 4:00
  • $\begingroup$ Another question about $W$ from this user, mathoverflow.net/questions/347796/… $\endgroup$ Dec 7 '19 at 5:28
1
$\begingroup$

First, some definitions of sets that are crucial to this problem.

  1. Let $ S(k)$ be the set of $k$ digit numbers with digit sum of 9.
  2. Let $X(k)$ be the set as given in the problem, namely$\{ x=(\ \underbrace{ 1\ 1\cdots\ 1\ 1}_{\text{$n$ terms}}\ \ 0 \ \ \underbrace{ \alpha_t\ \alpha_{t-1} \cdots \alpha_1 \ \alpha_0}_{\text{$k$ terms, k=t+1}}) \mid\ n,k\ge 0\ and \ 9 \ge \alpha_j\ge \alpha_{j-1} \ge 1 \ for \ t\ge j \ge 1 \} $
  3. Let $D(k)$ be the set of $k$ digit numbers whose digits are non-increasing, namely $ \{x=(\ \underbrace{ \alpha_t\ \alpha_{t-1} \cdots \alpha_1 \ \alpha_0}_{\text{$u$ terms, u=t+1}}) \mid\ u\ge 0\ and \ 9 \ge \alpha_j\ge \alpha_{j-1} \ge 1 \ for \ t\ge j \ge 1 \}$.
    These are the tail end of the set $X$.

Lemma: For $k\geq 2$, given $s_k \in S(k)$, $10^k - s_k - 1 = 9 d_{k-1}$ iff $d_{k-1} \in D(k-1)$.

Proof: Given $d_{k-1} \in D(k-1)$

$9 d_{k-1} = (10-1) d_{k-1} = \underbrace{ (\alpha_t -1 )\ (9 -\alpha_{t-1}+\alpha_{t-1}) \cdots (9 - \alpha_1+\alpha_0) \ (10 - \alpha_0})$.
Observe that each place value is nonnegative, so this is indeed the base 10 representation (possibly ignoring leading 0's).

$10^k -1 - 9d_{k-1} = \underbrace{ (10-\alpha_t )\ (\alpha_{t}-\alpha_{t-1}) \cdots ( \alpha_1-\alpha_0) \ (\alpha_0} - 1)$ The sum of the digits is $10-\alpha_t +\alpha_{t}-\alpha_{t-1} + \ldots + \alpha_0 -1 = 9$.

For the converse, just reverse these steps.


Corollary: Given $s_k \in S(k)$, $10^{k+n} - s_k - 1 = 9 x_{k-1}$ iff $x_{k-1} \in X(k-1)$.

Proof: $ \frac{ 10^{k+n} - 10^k } { 9} = 10^k \frac{ {\underbrace {9\ 9 \ 9 }_\text{$n$ terms}}} {9} = \underbrace {1\ 1 \ 1 }_\text{$n$ terms} \times 10^k$ as desired.

Corollary $W(10, 9x+1) = 9 $ iff $ x \in X(k)$ for some $k$.

Proof: This is a restatement of the previous corollary.

$\endgroup$
5
  • $\begingroup$ Please elaborate set $S(k)$ with example $\endgroup$
    – Pruthviraj
    Dec 2 '19 at 11:13
  • $\begingroup$ @Pruthviraj What part of "$k$ digit numbers with digit sum of 9" needs elaborating on? What are you confused by? Can you state some examples of what you are thinking is in / not in this set? $\endgroup$
    – Calvin Lin
    Dec 2 '19 at 16:11
  • $\begingroup$ I apologize, i just got a bit confused.now I'm clear. I will give you responce in few hours. $\endgroup$
    – Pruthviraj
    Dec 2 '19 at 16:45
  • $\begingroup$ In lemma proof, why $1\le \alpha_0 <9$, why not $1\le \alpha_0 \le 9$ $\endgroup$
    – Pruthviraj
    Dec 2 '19 at 18:17
  • $\begingroup$ Edited/Removed. That wasn't required. $\endgroup$
    – Calvin Lin
    Dec 2 '19 at 23:38

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.