Increasing the number of nonzero digits (from AOPS)
Clash Royale CLAN TAG#URR8PPP
up vote
8
down vote
favorite
I found this currently unsolved problem in the AOPS site (link):
Let $n$ be a positive integer with exactly $d$ non-zero digits. Show that there is a multiple of $n$ which has exactly $d+1$ non-zero digits.
It seems to be quite challenging and I have no idea how to solve it. Any hints how to proceed?
elementary-number-theory
asked Aug 8 at 18:37
Frank S
586
add a comment |Â
up vote
8
down vote
favorite
I found this currently unsolved problem in the AOPS site (link):
Let $n$ be a positive integer with exactly $d$ non-zero digits. Show that there is a multiple of $n$ which has exactly $d+1$ non-zero digits.
It seems to be quite challenging and I have no idea how to solve it. Any hints how to proceed?
elementary-number-theory
asked Aug 8 at 18:37
Frank S
586
Interesting problem! Could be out of reach.
– Peter
Aug 8 at 22:35
How many digits does $n$ have? Is it $d$ or more?
– user582949
Aug 10 at 18:45
@user582949 $n$ can have more than $d$ digits: $d$ are nonzero and the others are zero.
– Frank S
Aug 10 at 20:36
add a comment |Â
up vote
8
down vote
favorite
up vote
8
down vote
favorite
I found this currently unsolved problem in the AOPS site (link):
Let $n$ be a positive integer with exactly $d$ non-zero digits. Show that there is a multiple of $n$ which has exactly $d+1$ non-zero digits.
It seems to be quite challenging and I have no idea how to solve it. Any hints how to proceed?
elementary-number-theory
asked Aug 8 at 18:37
Frank S
586
I found this currently unsolved problem in the AOPS site (link):
Let $n$ be a positive integer with exactly $d$ non-zero digits. Show that there is a multiple of $n$ which has exactly $d+1$ non-zero digits.
It seems to be quite challenging and I have no idea how to solve it. Any hints how to proceed?
elementary-number-theory
asked Aug 8 at 18:37
Frank S
586
asked Aug 8 at 18:37
Frank S
586
asked Aug 8 at 18:37
Frank S
586
asked Aug 8 at 18:37
Frank S
586
586
Interesting problem! Could be out of reach.
– Peter
Aug 8 at 22:35
How many digits does $n$ have? Is it $d$ or more?
– user582949
Aug 10 at 18:45
@user582949 $n$ can have more than $d$ digits: $d$ are nonzero and the others are zero.
– Frank S
Aug 10 at 20:36
add a comment |Â
Interesting problem! Could be out of reach.
– Peter
Aug 8 at 22:35
How many digits does $n$ have? Is it $d$ or more?
– user582949
Aug 10 at 18:45
@user582949 $n$ can have more than $d$ digits: $d$ are nonzero and the others are zero.
– Frank S
Aug 10 at 20:36
Interesting problem! Could be out of reach.
– Peter
Aug 8 at 22:35
Interesting problem! Could be out of reach.
– Peter
Aug 8 at 22:35
How many digits does $n$ have? Is it $d$ or more?
– user582949
Aug 10 at 18:45
How many digits does $n$ have? Is it $d$ or more?
– user582949
Aug 10 at 18:45
@user582949 $n$ can have more than $d$ digits: $d$ are nonzero and the others are zero.
– Frank S
Aug 10 at 20:36
@user582949 $n$ can have more than $d$ digits: $d$ are nonzero and the others are zero.
– Frank S
Aug 10 at 20:36
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
5
down vote
You can combine three simple tricks to solve the problem:
Take a digit greater than $1$, and split it into two nonzero digits by adding $10^t-10^s$.
If each digit in your number $n$ is $0$ or $1$, replace $n$ by $2n$.
In order to get rid of the prime factors $2$ and $5$, multiply $n$ by a power of $10$.
If $n$ has a digit greater than $1$ then let $m=n$. Otherwise, if each digit of $n$ are $0$ or $1$ then let $m=2n$. Hence $m$ is a multiple of $n$, it has the same nonzero digits as $n$, and $m$ has at least one digit grater than $1$.
Let $m=sum_i=0^k-1 a_icdot 10^i$ where $a_0,ldots,a_k-1$ are the decimal digits of $m$ and let $g$ be an index with $a_gge2$.
Take two integers $t,s$ such that $s>g$, $t>s+k$ and $10^tequiv 10^spmodn$, and choose
$$
M = 10^s-gm + (10^t-10^s).
$$
The factor $10^s-g$ shifts the digit $a_g$ to the $s$th position.
The term $10^t-10^s$ replaces the digit $a_g$ by $a_g-1$ (which is nonzero), and adds a new leading digit $1$. Due to $t-s>k$, this leading $1$ is not added to the previous nonzero digits.
answered Aug 11 at 7:54
user141614
11.9k925
I have a few questions, but perhaps the most significant is this: Is there a guarantee that we can always choose such $s,t$ so that $10^sequiv 10^t pmod n$?
– Allawonder
Aug 15 at 19:11
@Allawonder By the pigeonhole principle, in the infinite sequence $10^n_n$ there are infinite couples $(10^s,10^t)$ with $snot=t$ such that $10^s$ and $10^t$ have the same remainder when divided by $n$.
– Robert Z
Aug 15 at 20:13
@RobertZ Thanks for your response, but I cannot say I understand your argument. Could you be more explicit as to how the pigeonhole principle does what we want? On the other hand the number $10^s-10^t$ is always of the form $underbrace999...99_s-t ,,,9'sunderbrace00...0_t,,, 0's.$ How does this help us out? I mean, apart from the fact that it is not obvious that every prime divides a number of this form, how does it help to increase the digit by just one in every case? I don't know if I'm making any sense.
– Allawonder
2 days ago
@Allawonder Note that $M = 10^t +10^s-gm -10^s$: $10^t$ increases the number of non-zero digits and $10^s-gm -10^s$ decreases by one the digit at $s$-position (which is at least $2$).
– Robert Z
yesterday
@RobertZ I think I'm beginning to get the gist now. I pay attention to notation, and the parentheses around $10^t-10^s$ may have misled me into thinking of it as $10^s(10^t-s-1).$
– Allawonder
yesterday
 |Â
show 2 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
You can combine three simple tricks to solve the problem:
Take a digit greater than $1$, and split it into two nonzero digits by adding $10^t-10^s$.
If each digit in your number $n$ is $0$ or $1$, replace $n$ by $2n$.
In order to get rid of the prime factors $2$ and $5$, multiply $n$ by a power of $10$.
If $n$ has a digit greater than $1$ then let $m=n$. Otherwise, if each digit of $n$ are $0$ or $1$ then let $m=2n$. Hence $m$ is a multiple of $n$, it has the same nonzero digits as $n$, and $m$ has at least one digit grater than $1$.
Let $m=sum_i=0^k-1 a_icdot 10^i$ where $a_0,ldots,a_k-1$ are the decimal digits of $m$ and let $g$ be an index with $a_gge2$.
Take two integers $t,s$ such that $s>g$, $t>s+k$ and $10^tequiv 10^spmodn$, and choose
$$
M = 10^s-gm + (10^t-10^s).
$$
The factor $10^s-g$ shifts the digit $a_g$ to the $s$th position.
The term $10^t-10^s$ replaces the digit $a_g$ by $a_g-1$ (which is nonzero), and adds a new leading digit $1$. Due to $t-s>k$, this leading $1$ is not added to the previous nonzero digits.
answered Aug 11 at 7:54
user141614
11.9k925
I have a few questions, but perhaps the most significant is this: Is there a guarantee that we can always choose such $s,t$ so that $10^sequiv 10^t pmod n$?
– Allawonder
Aug 15 at 19:11
@Allawonder By the pigeonhole principle, in the infinite sequence $10^n_n$ there are infinite couples $(10^s,10^t)$ with $snot=t$ such that $10^s$ and $10^t$ have the same remainder when divided by $n$.
– Robert Z
Aug 15 at 20:13
@RobertZ Thanks for your response, but I cannot say I understand your argument. Could you be more explicit as to how the pigeonhole principle does what we want? On the other hand the number $10^s-10^t$ is always of the form $underbrace999...99_s-t ,,,9'sunderbrace00...0_t,,, 0's.$ How does this help us out? I mean, apart from the fact that it is not obvious that every prime divides a number of this form, how does it help to increase the digit by just one in every case? I don't know if I'm making any sense.
– Allawonder
2 days ago
@Allawonder Note that $M = 10^t +10^s-gm -10^s$: $10^t$ increases the number of non-zero digits and $10^s-gm -10^s$ decreases by one the digit at $s$-position (which is at least $2$).
– Robert Z
yesterday
@RobertZ I think I'm beginning to get the gist now. I pay attention to notation, and the parentheses around $10^t-10^s$ may have misled me into thinking of it as $10^s(10^t-s-1).$
– Allawonder
yesterday
 |Â
show 2 more comments
up vote
5
down vote
You can combine three simple tricks to solve the problem:
Take a digit greater than $1$, and split it into two nonzero digits by adding $10^t-10^s$.
If each digit in your number $n$ is $0$ or $1$, replace $n$ by $2n$.
In order to get rid of the prime factors $2$ and $5$, multiply $n$ by a power of $10$.
If $n$ has a digit greater than $1$ then let $m=n$. Otherwise, if each digit of $n$ are $0$ or $1$ then let $m=2n$. Hence $m$ is a multiple of $n$, it has the same nonzero digits as $n$, and $m$ has at least one digit grater than $1$.
Let $m=sum_i=0^k-1 a_icdot 10^i$ where $a_0,ldots,a_k-1$ are the decimal digits of $m$ and let $g$ be an index with $a_gge2$.
Take two integers $t,s$ such that $s>g$, $t>s+k$ and $10^tequiv 10^spmodn$, and choose
$$
M = 10^s-gm + (10^t-10^s).
$$
The factor $10^s-g$ shifts the digit $a_g$ to the $s$th position.
The term $10^t-10^s$ replaces the digit $a_g$ by $a_g-1$ (which is nonzero), and adds a new leading digit $1$. Due to $t-s>k$, this leading $1$ is not added to the previous nonzero digits.
answered Aug 11 at 7:54
user141614
11.9k925
I have a few questions, but perhaps the most significant is this: Is there a guarantee that we can always choose such $s,t$ so that $10^sequiv 10^t pmod n$?
– Allawonder
Aug 15 at 19:11
@Allawonder By the pigeonhole principle, in the infinite sequence $10^n_n$ there are infinite couples $(10^s,10^t)$ with $snot=t$ such that $10^s$ and $10^t$ have the same remainder when divided by $n$.
– Robert Z
Aug 15 at 20:13
@RobertZ Thanks for your response, but I cannot say I understand your argument. Could you be more explicit as to how the pigeonhole principle does what we want? On the other hand the number $10^s-10^t$ is always of the form $underbrace999...99_s-t ,,,9'sunderbrace00...0_t,,, 0's.$ How does this help us out? I mean, apart from the fact that it is not obvious that every prime divides a number of this form, how does it help to increase the digit by just one in every case? I don't know if I'm making any sense.
– Allawonder
2 days ago
@Allawonder Note that $M = 10^t +10^s-gm -10^s$: $10^t$ increases the number of non-zero digits and $10^s-gm -10^s$ decreases by one the digit at $s$-position (which is at least $2$).
– Robert Z
yesterday
@RobertZ I think I'm beginning to get the gist now. I pay attention to notation, and the parentheses around $10^t-10^s$ may have misled me into thinking of it as $10^s(10^t-s-1).$
– Allawonder
yesterday
 |Â
show 2 more comments
up vote
5
down vote
up vote
5
down vote
You can combine three simple tricks to solve the problem:
Take a digit greater than $1$, and split it into two nonzero digits by adding $10^t-10^s$.
If each digit in your number $n$ is $0$ or $1$, replace $n$ by $2n$.
In order to get rid of the prime factors $2$ and $5$, multiply $n$ by a power of $10$.
If $n$ has a digit greater than $1$ then let $m=n$. Otherwise, if each digit of $n$ are $0$ or $1$ then let $m=2n$. Hence $m$ is a multiple of $n$, it has the same nonzero digits as $n$, and $m$ has at least one digit grater than $1$.
Let $m=sum_i=0^k-1 a_icdot 10^i$ where $a_0,ldots,a_k-1$ are the decimal digits of $m$ and let $g$ be an index with $a_gge2$.
Take two integers $t,s$ such that $s>g$, $t>s+k$ and $10^tequiv 10^spmodn$, and choose
$$
M = 10^s-gm + (10^t-10^s).
$$
The factor $10^s-g$ shifts the digit $a_g$ to the $s$th position.
The term $10^t-10^s$ replaces the digit $a_g$ by $a_g-1$ (which is nonzero), and adds a new leading digit $1$. Due to $t-s>k$, this leading $1$ is not added to the previous nonzero digits.
answered Aug 11 at 7:54
user141614
11.9k925
You can combine three simple tricks to solve the problem:
Take a digit greater than $1$, and split it into two nonzero digits by adding $10^t-10^s$.
If each digit in your number $n$ is $0$ or $1$, replace $n$ by $2n$.
In order to get rid of the prime factors $2$ and $5$, multiply $n$ by a power of $10$.
If $n$ has a digit greater than $1$ then let $m=n$. Otherwise, if each digit of $n$ are $0$ or $1$ then let $m=2n$. Hence $m$ is a multiple of $n$, it has the same nonzero digits as $n$, and $m$ has at least one digit grater than $1$.
Let $m=sum_i=0^k-1 a_icdot 10^i$ where $a_0,ldots,a_k-1$ are the decimal digits of $m$ and let $g$ be an index with $a_gge2$.
Take two integers $t,s$ such that $s>g$, $t>s+k$ and $10^tequiv 10^spmodn$, and choose
$$
M = 10^s-gm + (10^t-10^s).
$$
The factor $10^s-g$ shifts the digit $a_g$ to the $s$th position.
The term $10^t-10^s$ replaces the digit $a_g$ by $a_g-1$ (which is nonzero), and adds a new leading digit $1$. Due to $t-s>k$, this leading $1$ is not added to the previous nonzero digits.
answered Aug 11 at 7:54
user141614
11.9k925
answered Aug 11 at 7:54
user141614
11.9k925
answered Aug 11 at 7:54
user141614
11.9k925
answered Aug 11 at 7:54
user141614
11.9k925
11.9k925
I have a few questions, but perhaps the most significant is this: Is there a guarantee that we can always choose such $s,t$ so that $10^sequiv 10^t pmod n$?
– Allawonder
Aug 15 at 19:11
@Allawonder By the pigeonhole principle, in the infinite sequence $10^n_n$ there are infinite couples $(10^s,10^t)$ with $snot=t$ such that $10^s$ and $10^t$ have the same remainder when divided by $n$.
– Robert Z
Aug 15 at 20:13
@RobertZ Thanks for your response, but I cannot say I understand your argument. Could you be more explicit as to how the pigeonhole principle does what we want? On the other hand the number $10^s-10^t$ is always of the form $underbrace999...99_s-t ,,,9'sunderbrace00...0_t,,, 0's.$ How does this help us out? I mean, apart from the fact that it is not obvious that every prime divides a number of this form, how does it help to increase the digit by just one in every case? I don't know if I'm making any sense.
– Allawonder
2 days ago
@Allawonder Note that $M = 10^t +10^s-gm -10^s$: $10^t$ increases the number of non-zero digits and $10^s-gm -10^s$ decreases by one the digit at $s$-position (which is at least $2$).
– Robert Z
yesterday
@RobertZ I think I'm beginning to get the gist now. I pay attention to notation, and the parentheses around $10^t-10^s$ may have misled me into thinking of it as $10^s(10^t-s-1).$
– Allawonder
yesterday
 |Â
show 2 more comments
I have a few questions, but perhaps the most significant is this: Is there a guarantee that we can always choose such $s,t$ so that $10^sequiv 10^t pmod n$?
– Allawonder
Aug 15 at 19:11
@Allawonder By the pigeonhole principle, in the infinite sequence $10^n_n$ there are infinite couples $(10^s,10^t)$ with $snot=t$ such that $10^s$ and $10^t$ have the same remainder when divided by $n$.
– Robert Z
Aug 15 at 20:13
@RobertZ Thanks for your response, but I cannot say I understand your argument. Could you be more explicit as to how the pigeonhole principle does what we want? On the other hand the number $10^s-10^t$ is always of the form $underbrace999...99_s-t ,,,9'sunderbrace00...0_t,,, 0's.$ How does this help us out? I mean, apart from the fact that it is not obvious that every prime divides a number of this form, how does it help to increase the digit by just one in every case? I don't know if I'm making any sense.
– Allawonder
2 days ago
@Allawonder Note that $M = 10^t +10^s-gm -10^s$: $10^t$ increases the number of non-zero digits and $10^s-gm -10^s$ decreases by one the digit at $s$-position (which is at least $2$).
– Robert Z
yesterday
@RobertZ I think I'm beginning to get the gist now. I pay attention to notation, and the parentheses around $10^t-10^s$ may have misled me into thinking of it as $10^s(10^t-s-1).$
– Allawonder
yesterday
I have a few questions, but perhaps the most significant is this: Is there a guarantee that we can always choose such $s,t$ so that $10^sequiv 10^t pmod n$?
– Allawonder
Aug 15 at 19:11
I have a few questions, but perhaps the most significant is this: Is there a guarantee that we can always choose such $s,t$ so that $10^sequiv 10^t pmod n$?
– Allawonder
Aug 15 at 19:11
@Allawonder By the pigeonhole principle, in the infinite sequence $10^n_n$ there are infinite couples $(10^s,10^t)$ with $snot=t$ such that $10^s$ and $10^t$ have the same remainder when divided by $n$.
– Robert Z
Aug 15 at 20:13
@Allawonder By the pigeonhole principle, in the infinite sequence $10^n_n$ there are infinite couples $(10^s,10^t)$ with $snot=t$ such that $10^s$ and $10^t$ have the same remainder when divided by $n$.
– Robert Z
Aug 15 at 20:13
@RobertZ Thanks for your response, but I cannot say I understand your argument. Could you be more explicit as to how the pigeonhole principle does what we want? On the other hand the number $10^s-10^t$ is always of the form $underbrace999...99_s-t ,,,9'sunderbrace00...0_t,,, 0's.$ How does this help us out? I mean, apart from the fact that it is not obvious that every prime divides a number of this form, how does it help to increase the digit by just one in every case? I don't know if I'm making any sense.
– Allawonder
2 days ago
@RobertZ Thanks for your response, but I cannot say I understand your argument. Could you be more explicit as to how the pigeonhole principle does what we want? On the other hand the number $10^s-10^t$ is always of the form $underbrace999...99_s-t ,,,9'sunderbrace00...0_t,,, 0's.$ How does this help us out? I mean, apart from the fact that it is not obvious that every prime divides a number of this form, how does it help to increase the digit by just one in every case? I don't know if I'm making any sense.
– Allawonder
2 days ago
@Allawonder Note that $M = 10^t +10^s-gm -10^s$: $10^t$ increases the number of non-zero digits and $10^s-gm -10^s$ decreases by one the digit at $s$-position (which is at least $2$).
– Robert Z
yesterday
@Allawonder Note that $M = 10^t +10^s-gm -10^s$: $10^t$ increases the number of non-zero digits and $10^s-gm -10^s$ decreases by one the digit at $s$-position (which is at least $2$).
– Robert Z
yesterday
@RobertZ I think I'm beginning to get the gist now. I pay attention to notation, and the parentheses around $10^t-10^s$ may have misled me into thinking of it as $10^s(10^t-s-1).$
– Allawonder
yesterday
@RobertZ I think I'm beginning to get the gist now. I pay attention to notation, and the parentheses around $10^t-10^s$ may have misled me into thinking of it as $10^s(10^t-s-1).$
– Allawonder
yesterday
 |Â
show 2 more comments
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2876425%2fincreasing-the-number-of-nonzero-digits-from-aops%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Interesting problem! Could be out of reach.
– Peter
Aug 8 at 22:35
How many digits does $n$ have? Is it $d$ or more?
– user582949
Aug 10 at 18:45
@user582949 $n$ can have more than $d$ digits: $d$ are nonzero and the others are zero.
– Frank S
Aug 10 at 20:36