Mixing
Formula for smallest multiple of given number, whose every digit is 1
$begingroup$
Introduction
I've been solving a problem, which says which number is the smallest multiple of $x$ which only has digits with value 1.
For example: $minOnes(3) = 3 -> 111$;
$minOnes(7) = 6 -> 111111$
$minOnes(11) = 2 -> 11$;
$minOnes(2601) = 2448$.
I have been playing with numbers, and have reached to a formula. If $x$ is our number to solve.
Formula
$minOnes(x) = minOnes( mcm(minOnes(divisors[x])) * ( divisor[x]$ ^ ($times$_$appeared$-$1$) for each $divisor$ in $divisors$) )
divisors are all the divisors of $x$. For example, 21 has 3 and 7 as divisors.times_appeared is the number of times the divisor divides $x$. For example, 3 divides 3 times 27.
mcm(..) is the minimum common multiple of the minOnes() of its divisors.
Example
$63 = 3 times 3 times 7$
$minOnes(3) = 3$; $ minOnes(7) = 6$;
$minOnes(63) = mcm(6, 3)times 3^1 times 7^0 = 6times 3 = 18$
Counter-example
Well... I have tried this formula to lot of numbers, and everything went correct. Except one: 3249 = $(3^2)(19^2)$. $minOnes(3249) = 342$, but with my formula, $minOnes(3249) = 1026 = (342)(3)$. There are maybe more numbers that don't follow this rule, but this surprises me because the formula works with almost each number.
I wanted to let it be known, if someone knows the answer or hasinterest in this :)
Note: numbers with divisors 2 and 5 are excluyed (they get a digit with 0).
Edit
I have tried with more numbers, and indeed there are more numbers which do not follow the rule. They are a few, and obey some pattern:
$171 = 3^2 times 19$;
$513 = 3^3 times 19$; $981 = 3^2 times 109$;
$1197 = 3^2 times 7 times 19$;
$1421 = 7^2 times 29$;
$1467 = 3^2 times 163$;
$1539= 3^4 times 19$;
$1629 = 3^2 times 181$;
$1791 = 3^2 times 199$;
$... 1881$ $2107$ $2223$ $2763$ $2783$ $2907$ $2943$ $3249$ $3411$ $3479$ $3573$
So strange...
contest-math
edited May 2 '16 at 7:59
Did
249k23226466
asked May 1 '16 at 16:30
Santiago GilSantiago Gil
1306
$endgroup$
add a comment |
$begingroup$
Introduction
I've been solving a problem, which says which number is the smallest multiple of $x$ which only has digits with value 1.
For example: $minOnes(3) = 3 -> 111$;
$minOnes(7) = 6 -> 111111$
$minOnes(11) = 2 -> 11$;
$minOnes(2601) = 2448$.
I have been playing with numbers, and have reached to a formula. If $x$ is our number to solve.
Formula
$minOnes(x) = minOnes( mcm(minOnes(divisors[x])) * ( divisor[x]$ ^ ($times$_$appeared$-$1$) for each $divisor$ in $divisors$) )
divisors are all the divisors of $x$. For example, 21 has 3 and 7 as divisors.times_appeared is the number of times the divisor divides $x$. For example, 3 divides 3 times 27.
mcm(..) is the minimum common multiple of the minOnes() of its divisors.
Example
$63 = 3 times 3 times 7$
$minOnes(3) = 3$; $ minOnes(7) = 6$;
$minOnes(63) = mcm(6, 3)times 3^1 times 7^0 = 6times 3 = 18$
Counter-example
Well... I have tried this formula to lot of numbers, and everything went correct. Except one: 3249 = $(3^2)(19^2)$. $minOnes(3249) = 342$, but with my formula, $minOnes(3249) = 1026 = (342)(3)$. There are maybe more numbers that don't follow this rule, but this surprises me because the formula works with almost each number.
I wanted to let it be known, if someone knows the answer or hasinterest in this :)
Note: numbers with divisors 2 and 5 are excluyed (they get a digit with 0).
Edit
I have tried with more numbers, and indeed there are more numbers which do not follow the rule. They are a few, and obey some pattern:
$171 = 3^2 times 19$;
$513 = 3^3 times 19$; $981 = 3^2 times 109$;
$1197 = 3^2 times 7 times 19$;
$1421 = 7^2 times 29$;
$1467 = 3^2 times 163$;
$1539= 3^4 times 19$;
$1629 = 3^2 times 181$;
$1791 = 3^2 times 199$;
$... 1881$ $2107$ $2223$ $2763$ $2783$ $2907$ $2943$ $3249$ $3411$ $3479$ $3573$
So strange...
contest-math
edited May 2 '16 at 7:59
Did
249k23226466
asked May 1 '16 at 16:30
Santiago GilSantiago Gil
1306
$endgroup$
add a comment |
$begingroup$
Introduction
I've been solving a problem, which says which number is the smallest multiple of $x$ which only has digits with value 1.
For example: $minOnes(3) = 3 -> 111$;
$minOnes(7) = 6 -> 111111$
$minOnes(11) = 2 -> 11$;
$minOnes(2601) = 2448$.
I have been playing with numbers, and have reached to a formula. If $x$ is our number to solve.
Formula
$minOnes(x) = minOnes( mcm(minOnes(divisors[x])) * ( divisor[x]$ ^ ($times$_$appeared$-$1$) for each $divisor$ in $divisors$) )
divisors are all the divisors of $x$. For example, 21 has 3 and 7 as divisors.times_appeared is the number of times the divisor divides $x$. For example, 3 divides 3 times 27.
mcm(..) is the minimum common multiple of the minOnes() of its divisors.
Example
$63 = 3 times 3 times 7$
$minOnes(3) = 3$; $ minOnes(7) = 6$;
$minOnes(63) = mcm(6, 3)times 3^1 times 7^0 = 6times 3 = 18$
Counter-example
Well... I have tried this formula to lot of numbers, and everything went correct. Except one: 3249 = $(3^2)(19^2)$. $minOnes(3249) = 342$, but with my formula, $minOnes(3249) = 1026 = (342)(3)$. There are maybe more numbers that don't follow this rule, but this surprises me because the formula works with almost each number.
I wanted to let it be known, if someone knows the answer or hasinterest in this :)
Note: numbers with divisors 2 and 5 are excluyed (they get a digit with 0).
Edit
I have tried with more numbers, and indeed there are more numbers which do not follow the rule. They are a few, and obey some pattern:
$171 = 3^2 times 19$;
$513 = 3^3 times 19$; $981 = 3^2 times 109$;
$1197 = 3^2 times 7 times 19$;
$1421 = 7^2 times 29$;
$1467 = 3^2 times 163$;
$1539= 3^4 times 19$;
$1629 = 3^2 times 181$;
$1791 = 3^2 times 199$;
$... 1881$ $2107$ $2223$ $2763$ $2783$ $2907$ $2943$ $3249$ $3411$ $3479$ $3573$
So strange...
contest-math
edited May 2 '16 at 7:59
Did
249k23226466
asked May 1 '16 at 16:30
Santiago GilSantiago Gil
1306
$endgroup$
Introduction
I've been solving a problem, which says which number is the smallest multiple of $x$ which only has digits with value 1.
For example: $minOnes(3) = 3 -> 111$;
$minOnes(7) = 6 -> 111111$
$minOnes(11) = 2 -> 11$;
$minOnes(2601) = 2448$.
I have been playing with numbers, and have reached to a formula. If $x$ is our number to solve.
Formula
$minOnes(x) = minOnes( mcm(minOnes(divisors[x])) * ( divisor[x]$ ^ ($times$_$appeared$-$1$) for each $divisor$ in $divisors$) )
divisors are all the divisors of $x$. For example, 21 has 3 and 7 as divisors.times_appeared is the number of times the divisor divides $x$. For example, 3 divides 3 times 27.
mcm(..) is the minimum common multiple of the minOnes() of its divisors.
Example
$63 = 3 times 3 times 7$
$minOnes(3) = 3$; $ minOnes(7) = 6$;
$minOnes(63) = mcm(6, 3)times 3^1 times 7^0 = 6times 3 = 18$
Counter-example
Well... I have tried this formula to lot of numbers, and everything went correct. Except one: 3249 = $(3^2)(19^2)$. $minOnes(3249) = 342$, but with my formula, $minOnes(3249) = 1026 = (342)(3)$. There are maybe more numbers that don't follow this rule, but this surprises me because the formula works with almost each number.
I wanted to let it be known, if someone knows the answer or hasinterest in this :)
Note: numbers with divisors 2 and 5 are excluyed (they get a digit with 0).
Edit
I have tried with more numbers, and indeed there are more numbers which do not follow the rule. They are a few, and obey some pattern:
$171 = 3^2 times 19$;
$513 = 3^3 times 19$; $981 = 3^2 times 109$;
$1197 = 3^2 times 7 times 19$;
$1421 = 7^2 times 29$;
$1467 = 3^2 times 163$;
$1539= 3^4 times 19$;
$1629 = 3^2 times 181$;
$1791 = 3^2 times 199$;
$... 1881$ $2107$ $2223$ $2763$ $2783$ $2907$ $2943$ $3249$ $3411$ $3479$ $3573$
So strange...
contest-math
contest-math
edited May 2 '16 at 7:59
Did
249k23226466
asked May 1 '16 at 16:30
Santiago GilSantiago Gil
1306
edited May 2 '16 at 7:59
Did
249k23226466
asked May 1 '16 at 16:30
Santiago GilSantiago Gil
1306
edited May 2 '16 at 7:59
Did
249k23226466
edited May 2 '16 at 7:59
Did
249k23226466
edited May 2 '16 at 7:59
Did
249k23226466
249k23226466
asked May 1 '16 at 16:30
Santiago GilSantiago Gil
1306
asked May 1 '16 at 16:30
Santiago GilSantiago Gil
1306
asked May 1 '16 at 16:30
Santiago GilSantiago Gil
1306
1306
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
As dez pointed such a number exists if and only if $gcd(n,10)=1$.$newcommand{ord}{operatorname{ord}}$
Case 1 $3 nmid x$. Then
$$x |111...1 Leftrightarrow x|999...9 Leftrightarrow 10^n equiv 1 pmod(x) Leftrightarrow ord_x(10)|n$$
Therefore, the smallest $n$ is
$$n=ord_x(10)$$
that is the order of $10$ modulo $n$.
Case 2 $3 mid x$. Then
$$x |111...1 Leftrightarrow 9x|999...9 Leftrightarrow 10^n equiv 1 pmod(9x) Leftrightarrow ord_{9x}(10)|n$$
Therefore, the smallest $n$ is
$$n=ord_{9x}(10)$$
Note that one can use Case 2 to cover case 1 too, but the order of 10 is easier to calculate $pmod{x}$ instead of $pmod{9x}$.
How to actually calculate
By Euler theorem, $ ord_{9x}(10)|phi(9x)$, thus you need to find the smallest divisor of $phi(9x)$ such that $10^d equiv 1 pmod{9x}$. (and similarly for case 1).
If you are familiar with the Chinese reminder theorem, you can use the prime factorization of $9x$ as dezdichado suggested.
P.S. interesting fact: It is easy to prove that for $gcd(k,10)=1$ we have: $ord_{k}(10)$ is equal to the lenght of the period in $frac{1}{k}$.
Added To calculate, here is how one should proceed:
If $k=p_1^{alpha_1}cdot...cdot p_n^{alpha_n}$
then by the Chinese Remainder Theorem
$$ord_k(10)= LCM[ ord{p_1^{alpha_1}}(10),ord{p_2^{alpha_2}}(10),.., ord{p_n^{alpha_n}}(10)$$
This means that you only need to figure $ord{p_j^{alpha_j}}(10)$.
The question boils down to how to calculate $ord_{p^alpha}(10)$. This can be done recursively:
$$ord_p(10)|p-1$$
by Fermat Little Theorem. Also
$$ord_{p^alpha}(10)| ord_{p^(alpha+1)}(10) | p^alpha(p-1)$$
which reduces somewhat the calculation of the order modulo $p-1$.
Therefore, if $d= ord_{p^alpha}(10)$ you need to find the smallest $k$ which divides $frac{p^alpha(p-1)}{ord_{p^alpha}(10)}$ such that
$$p^{alpha+1}|10^{kd}-1$$
Note that if $p^{alpha+1}|10^{d}-1$, you are done, otherwise the problem is equivalent to finding the smallest such $k$ so that
$$p| 1+10^d+10^{2d}+..+10^{(k-1)d}$$
edited Jan 29 at 7:41
Martin Sleziak
44.9k10122277
answered May 1 '16 at 18:16
N. S.N. S.
105k7114210
$endgroup$
$begingroup$
What abour if my $x$ has big values, for example, $2^{31}$. Is it a good algorithm to start from $d=1$ to infinf, applying in each iteration that condition?
$endgroup$
– Santiago Gil
May 1 '16 at 21:13
$begingroup$
The algorithm is really slow for numbers such as $x = 7730183 = 509 * 15187$ Im sure there has to be an optimization based on the factors of the $x$.
$endgroup$
– Santiago Gil
May 2 '16 at 10:53
$begingroup$
@SantiGil Check the addon, it is based on the factors of $x$ which are powers of primes, that's all you need.
$endgroup$
– N. S.
May 2 '16 at 13:30
add a comment |
$begingroup$
Your question is equivalent to asking what is the smallest $n$ such that $10^n-1$ is divisible by given number $x$. Such a number exists if and only if $gcd(10,x) = 1$. So what you need to do is solve the problem for $2^n-1$ and $5^n-1$, and take their least common multiple.
You only need to consider the prime power divisors of $n$, not all the divisors of $n$. In other words, if $n = p_1^{a_1}...p_k^{a_k}$, then only consider each $p_i^{a_i}$ in your formula.
answered May 1 '16 at 16:55
dezdichadodezdichado
6,4691929
$endgroup$
$begingroup$
I don't get it. If minOnes(3) = 3, your $n$ would be 3. But with n = 2 < 3, $ 10^2$ - 1 = 99 is divisible by 3, so I think is not the same question.
$endgroup$
– Santiago Gil
May 1 '16 at 17:15
add a comment |
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1766947%2fformula-for-smallest-multiple-of-given-number-whose-every-digit-is-1%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As dez pointed such a number exists if and only if $gcd(n,10)=1$.$newcommand{ord}{operatorname{ord}}$
Case 1 $3 nmid x$. Then
$$x |111...1 Leftrightarrow x|999...9 Leftrightarrow 10^n equiv 1 pmod(x) Leftrightarrow ord_x(10)|n$$
Therefore, the smallest $n$ is
$$n=ord_x(10)$$
that is the order of $10$ modulo $n$.
Case 2 $3 mid x$. Then
$$x |111...1 Leftrightarrow 9x|999...9 Leftrightarrow 10^n equiv 1 pmod(9x) Leftrightarrow ord_{9x}(10)|n$$
Therefore, the smallest $n$ is
$$n=ord_{9x}(10)$$
Note that one can use Case 2 to cover case 1 too, but the order of 10 is easier to calculate $pmod{x}$ instead of $pmod{9x}$.
How to actually calculate
By Euler theorem, $ ord_{9x}(10)|phi(9x)$, thus you need to find the smallest divisor of $phi(9x)$ such that $10^d equiv 1 pmod{9x}$. (and similarly for case 1).
If you are familiar with the Chinese reminder theorem, you can use the prime factorization of $9x$ as dezdichado suggested.
P.S. interesting fact: It is easy to prove that for $gcd(k,10)=1$ we have: $ord_{k}(10)$ is equal to the lenght of the period in $frac{1}{k}$.
Added To calculate, here is how one should proceed:
If $k=p_1^{alpha_1}cdot...cdot p_n^{alpha_n}$
then by the Chinese Remainder Theorem
$$ord_k(10)= LCM[ ord{p_1^{alpha_1}}(10),ord{p_2^{alpha_2}}(10),.., ord{p_n^{alpha_n}}(10)$$
This means that you only need to figure $ord{p_j^{alpha_j}}(10)$.
The question boils down to how to calculate $ord_{p^alpha}(10)$. This can be done recursively:
$$ord_p(10)|p-1$$
by Fermat Little Theorem. Also
$$ord_{p^alpha}(10)| ord_{p^(alpha+1)}(10) | p^alpha(p-1)$$
which reduces somewhat the calculation of the order modulo $p-1$.
Therefore, if $d= ord_{p^alpha}(10)$ you need to find the smallest $k$ which divides $frac{p^alpha(p-1)}{ord_{p^alpha}(10)}$ such that
$$p^{alpha+1}|10^{kd}-1$$
Note that if $p^{alpha+1}|10^{d}-1$, you are done, otherwise the problem is equivalent to finding the smallest such $k$ so that
$$p| 1+10^d+10^{2d}+..+10^{(k-1)d}$$
edited Jan 29 at 7:41
Martin Sleziak
44.9k10122277
answered May 1 '16 at 18:16
N. S.N. S.
105k7114210
$endgroup$
$begingroup$
What abour if my $x$ has big values, for example, $2^{31}$. Is it a good algorithm to start from $d=1$ to infinf, applying in each iteration that condition?
$endgroup$
– Santiago Gil
May 1 '16 at 21:13
$begingroup$
The algorithm is really slow for numbers such as $x = 7730183 = 509 * 15187$ Im sure there has to be an optimization based on the factors of the $x$.
$endgroup$
– Santiago Gil
May 2 '16 at 10:53
$begingroup$
@SantiGil Check the addon, it is based on the factors of $x$ which are powers of primes, that's all you need.
$endgroup$
– N. S.
May 2 '16 at 13:30
add a comment |
$begingroup$
As dez pointed such a number exists if and only if $gcd(n,10)=1$.$newcommand{ord}{operatorname{ord}}$
Case 1 $3 nmid x$. Then
$$x |111...1 Leftrightarrow x|999...9 Leftrightarrow 10^n equiv 1 pmod(x) Leftrightarrow ord_x(10)|n$$
Therefore, the smallest $n$ is
$$n=ord_x(10)$$
that is the order of $10$ modulo $n$.
Case 2 $3 mid x$. Then
$$x |111...1 Leftrightarrow 9x|999...9 Leftrightarrow 10^n equiv 1 pmod(9x) Leftrightarrow ord_{9x}(10)|n$$
Therefore, the smallest $n$ is
$$n=ord_{9x}(10)$$
Note that one can use Case 2 to cover case 1 too, but the order of 10 is easier to calculate $pmod{x}$ instead of $pmod{9x}$.
How to actually calculate
By Euler theorem, $ ord_{9x}(10)|phi(9x)$, thus you need to find the smallest divisor of $phi(9x)$ such that $10^d equiv 1 pmod{9x}$. (and similarly for case 1).
If you are familiar with the Chinese reminder theorem, you can use the prime factorization of $9x$ as dezdichado suggested.
P.S. interesting fact: It is easy to prove that for $gcd(k,10)=1$ we have: $ord_{k}(10)$ is equal to the lenght of the period in $frac{1}{k}$.
Added To calculate, here is how one should proceed:
If $k=p_1^{alpha_1}cdot...cdot p_n^{alpha_n}$
then by the Chinese Remainder Theorem
$$ord_k(10)= LCM[ ord{p_1^{alpha_1}}(10),ord{p_2^{alpha_2}}(10),.., ord{p_n^{alpha_n}}(10)$$
This means that you only need to figure $ord{p_j^{alpha_j}}(10)$.
The question boils down to how to calculate $ord_{p^alpha}(10)$. This can be done recursively:
$$ord_p(10)|p-1$$
by Fermat Little Theorem. Also
$$ord_{p^alpha}(10)| ord_{p^(alpha+1)}(10) | p^alpha(p-1)$$
which reduces somewhat the calculation of the order modulo $p-1$.
Therefore, if $d= ord_{p^alpha}(10)$ you need to find the smallest $k$ which divides $frac{p^alpha(p-1)}{ord_{p^alpha}(10)}$ such that
$$p^{alpha+1}|10^{kd}-1$$
Note that if $p^{alpha+1}|10^{d}-1$, you are done, otherwise the problem is equivalent to finding the smallest such $k$ so that
$$p| 1+10^d+10^{2d}+..+10^{(k-1)d}$$
edited Jan 29 at 7:41
Martin Sleziak
44.9k10122277
answered May 1 '16 at 18:16
N. S.N. S.
105k7114210
$endgroup$
$begingroup$
What abour if my $x$ has big values, for example, $2^{31}$. Is it a good algorithm to start from $d=1$ to infinf, applying in each iteration that condition?
$endgroup$
– Santiago Gil
May 1 '16 at 21:13
$begingroup$
The algorithm is really slow for numbers such as $x = 7730183 = 509 * 15187$ Im sure there has to be an optimization based on the factors of the $x$.
$endgroup$
– Santiago Gil
May 2 '16 at 10:53
$begingroup$
@SantiGil Check the addon, it is based on the factors of $x$ which are powers of primes, that's all you need.
$endgroup$
– N. S.
May 2 '16 at 13:30
add a comment |
$begingroup$
As dez pointed such a number exists if and only if $gcd(n,10)=1$.$newcommand{ord}{operatorname{ord}}$
Case 1 $3 nmid x$. Then
$$x |111...1 Leftrightarrow x|999...9 Leftrightarrow 10^n equiv 1 pmod(x) Leftrightarrow ord_x(10)|n$$
Therefore, the smallest $n$ is
$$n=ord_x(10)$$
that is the order of $10$ modulo $n$.
Case 2 $3 mid x$. Then
$$x |111...1 Leftrightarrow 9x|999...9 Leftrightarrow 10^n equiv 1 pmod(9x) Leftrightarrow ord_{9x}(10)|n$$
Therefore, the smallest $n$ is
$$n=ord_{9x}(10)$$
Note that one can use Case 2 to cover case 1 too, but the order of 10 is easier to calculate $pmod{x}$ instead of $pmod{9x}$.
How to actually calculate
By Euler theorem, $ ord_{9x}(10)|phi(9x)$, thus you need to find the smallest divisor of $phi(9x)$ such that $10^d equiv 1 pmod{9x}$. (and similarly for case 1).
If you are familiar with the Chinese reminder theorem, you can use the prime factorization of $9x$ as dezdichado suggested.
P.S. interesting fact: It is easy to prove that for $gcd(k,10)=1$ we have: $ord_{k}(10)$ is equal to the lenght of the period in $frac{1}{k}$.
Added To calculate, here is how one should proceed:
If $k=p_1^{alpha_1}cdot...cdot p_n^{alpha_n}$
then by the Chinese Remainder Theorem
$$ord_k(10)= LCM[ ord{p_1^{alpha_1}}(10),ord{p_2^{alpha_2}}(10),.., ord{p_n^{alpha_n}}(10)$$
This means that you only need to figure $ord{p_j^{alpha_j}}(10)$.
The question boils down to how to calculate $ord_{p^alpha}(10)$. This can be done recursively:
$$ord_p(10)|p-1$$
by Fermat Little Theorem. Also
$$ord_{p^alpha}(10)| ord_{p^(alpha+1)}(10) | p^alpha(p-1)$$
which reduces somewhat the calculation of the order modulo $p-1$.
Therefore, if $d= ord_{p^alpha}(10)$ you need to find the smallest $k$ which divides $frac{p^alpha(p-1)}{ord_{p^alpha}(10)}$ such that
$$p^{alpha+1}|10^{kd}-1$$
Note that if $p^{alpha+1}|10^{d}-1$, you are done, otherwise the problem is equivalent to finding the smallest such $k$ so that
$$p| 1+10^d+10^{2d}+..+10^{(k-1)d}$$
edited Jan 29 at 7:41
Martin Sleziak
44.9k10122277
answered May 1 '16 at 18:16
N. S.N. S.
105k7114210
$endgroup$
As dez pointed such a number exists if and only if $gcd(n,10)=1$.$newcommand{ord}{operatorname{ord}}$
Case 1 $3 nmid x$. Then
$$x |111...1 Leftrightarrow x|999...9 Leftrightarrow 10^n equiv 1 pmod(x) Leftrightarrow ord_x(10)|n$$
Therefore, the smallest $n$ is
$$n=ord_x(10)$$
that is the order of $10$ modulo $n$.
Case 2 $3 mid x$. Then
$$x |111...1 Leftrightarrow 9x|999...9 Leftrightarrow 10^n equiv 1 pmod(9x) Leftrightarrow ord_{9x}(10)|n$$
Therefore, the smallest $n$ is
$$n=ord_{9x}(10)$$
Note that one can use Case 2 to cover case 1 too, but the order of 10 is easier to calculate $pmod{x}$ instead of $pmod{9x}$.
How to actually calculate
By Euler theorem, $ ord_{9x}(10)|phi(9x)$, thus you need to find the smallest divisor of $phi(9x)$ such that $10^d equiv 1 pmod{9x}$. (and similarly for case 1).
If you are familiar with the Chinese reminder theorem, you can use the prime factorization of $9x$ as dezdichado suggested.
P.S. interesting fact: It is easy to prove that for $gcd(k,10)=1$ we have: $ord_{k}(10)$ is equal to the lenght of the period in $frac{1}{k}$.
Added To calculate, here is how one should proceed:
If $k=p_1^{alpha_1}cdot...cdot p_n^{alpha_n}$
then by the Chinese Remainder Theorem
$$ord_k(10)= LCM[ ord{p_1^{alpha_1}}(10),ord{p_2^{alpha_2}}(10),.., ord{p_n^{alpha_n}}(10)$$
This means that you only need to figure $ord{p_j^{alpha_j}}(10)$.
The question boils down to how to calculate $ord_{p^alpha}(10)$. This can be done recursively:
$$ord_p(10)|p-1$$
by Fermat Little Theorem. Also
$$ord_{p^alpha}(10)| ord_{p^(alpha+1)}(10) | p^alpha(p-1)$$
which reduces somewhat the calculation of the order modulo $p-1$.
Therefore, if $d= ord_{p^alpha}(10)$ you need to find the smallest $k$ which divides $frac{p^alpha(p-1)}{ord_{p^alpha}(10)}$ such that
$$p^{alpha+1}|10^{kd}-1$$
Note that if $p^{alpha+1}|10^{d}-1$, you are done, otherwise the problem is equivalent to finding the smallest such $k$ so that
$$p| 1+10^d+10^{2d}+..+10^{(k-1)d}$$
edited Jan 29 at 7:41
Martin Sleziak
44.9k10122277
answered May 1 '16 at 18:16
N. S.N. S.
105k7114210
edited Jan 29 at 7:41
Martin Sleziak
44.9k10122277
edited Jan 29 at 7:41
Martin Sleziak
44.9k10122277
edited Jan 29 at 7:41
Martin Sleziak
44.9k10122277
44.9k10122277
answered May 1 '16 at 18:16
N. S.N. S.
105k7114210
answered May 1 '16 at 18:16
N. S.N. S.
105k7114210
answered May 1 '16 at 18:16
N. S.N. S.
105k7114210
105k7114210
$begingroup$
What abour if my $x$ has big values, for example, $2^{31}$. Is it a good algorithm to start from $d=1$ to infinf, applying in each iteration that condition?
$endgroup$
– Santiago Gil
May 1 '16 at 21:13
$begingroup$
The algorithm is really slow for numbers such as $x = 7730183 = 509 * 15187$ Im sure there has to be an optimization based on the factors of the $x$.
$endgroup$
– Santiago Gil
May 2 '16 at 10:53
$begingroup$
@SantiGil Check the addon, it is based on the factors of $x$ which are powers of primes, that's all you need.
$endgroup$
– N. S.
May 2 '16 at 13:30
add a comment |
$begingroup$
What abour if my $x$ has big values, for example, $2^{31}$. Is it a good algorithm to start from $d=1$ to infinf, applying in each iteration that condition?
$endgroup$
– Santiago Gil
May 1 '16 at 21:13
$begingroup$
The algorithm is really slow for numbers such as $x = 7730183 = 509 * 15187$ Im sure there has to be an optimization based on the factors of the $x$.
$endgroup$
– Santiago Gil
May 2 '16 at 10:53
$begingroup$
@SantiGil Check the addon, it is based on the factors of $x$ which are powers of primes, that's all you need.
$endgroup$
– N. S.
May 2 '16 at 13:30
$begingroup$
What abour if my $x$ has big values, for example, $2^{31}$. Is it a good algorithm to start from $d=1$ to infinf, applying in each iteration that condition?
$endgroup$
– Santiago Gil
May 1 '16 at 21:13
$begingroup$
What abour if my $x$ has big values, for example, $2^{31}$. Is it a good algorithm to start from $d=1$ to infinf, applying in each iteration that condition?
$endgroup$
– Santiago Gil
May 1 '16 at 21:13
$begingroup$
The algorithm is really slow for numbers such as $x = 7730183 = 509 * 15187$ Im sure there has to be an optimization based on the factors of the $x$.
$endgroup$
– Santiago Gil
May 2 '16 at 10:53
$begingroup$
The algorithm is really slow for numbers such as $x = 7730183 = 509 * 15187$ Im sure there has to be an optimization based on the factors of the $x$.
$endgroup$
– Santiago Gil
May 2 '16 at 10:53
$begingroup$
@SantiGil Check the addon, it is based on the factors of $x$ which are powers of primes, that's all you need.
$endgroup$
– N. S.
May 2 '16 at 13:30
$begingroup$
@SantiGil Check the addon, it is based on the factors of $x$ which are powers of primes, that's all you need.
$endgroup$
– N. S.
May 2 '16 at 13:30
add a comment |
$begingroup$
Your question is equivalent to asking what is the smallest $n$ such that $10^n-1$ is divisible by given number $x$. Such a number exists if and only if $gcd(10,x) = 1$. So what you need to do is solve the problem for $2^n-1$ and $5^n-1$, and take their least common multiple.
You only need to consider the prime power divisors of $n$, not all the divisors of $n$. In other words, if $n = p_1^{a_1}...p_k^{a_k}$, then only consider each $p_i^{a_i}$ in your formula.
answered May 1 '16 at 16:55
dezdichadodezdichado
6,4691929
$endgroup$
$begingroup$
I don't get it. If minOnes(3) = 3, your $n$ would be 3. But with n = 2 < 3, $ 10^2$ - 1 = 99 is divisible by 3, so I think is not the same question.
$endgroup$
– Santiago Gil
May 1 '16 at 17:15
add a comment |
$begingroup$
Your question is equivalent to asking what is the smallest $n$ such that $10^n-1$ is divisible by given number $x$. Such a number exists if and only if $gcd(10,x) = 1$. So what you need to do is solve the problem for $2^n-1$ and $5^n-1$, and take their least common multiple.
You only need to consider the prime power divisors of $n$, not all the divisors of $n$. In other words, if $n = p_1^{a_1}...p_k^{a_k}$, then only consider each $p_i^{a_i}$ in your formula.
answered May 1 '16 at 16:55
dezdichadodezdichado
6,4691929
$endgroup$
$begingroup$
I don't get it. If minOnes(3) = 3, your $n$ would be 3. But with n = 2 < 3, $ 10^2$ - 1 = 99 is divisible by 3, so I think is not the same question.
$endgroup$
– Santiago Gil
May 1 '16 at 17:15
add a comment |
$begingroup$
Your question is equivalent to asking what is the smallest $n$ such that $10^n-1$ is divisible by given number $x$. Such a number exists if and only if $gcd(10,x) = 1$. So what you need to do is solve the problem for $2^n-1$ and $5^n-1$, and take their least common multiple.
You only need to consider the prime power divisors of $n$, not all the divisors of $n$. In other words, if $n = p_1^{a_1}...p_k^{a_k}$, then only consider each $p_i^{a_i}$ in your formula.
answered May 1 '16 at 16:55
dezdichadodezdichado
6,4691929
$endgroup$
Your question is equivalent to asking what is the smallest $n$ such that $10^n-1$ is divisible by given number $x$. Such a number exists if and only if $gcd(10,x) = 1$. So what you need to do is solve the problem for $2^n-1$ and $5^n-1$, and take their least common multiple.
You only need to consider the prime power divisors of $n$, not all the divisors of $n$. In other words, if $n = p_1^{a_1}...p_k^{a_k}$, then only consider each $p_i^{a_i}$ in your formula.
answered May 1 '16 at 16:55
dezdichadodezdichado
6,4691929
edited May 1 '16 at 17:31
answered May 1 '16 at 16:55
dezdichadodezdichado
6,4691929
answered May 1 '16 at 16:55
dezdichadodezdichado
6,4691929
answered May 1 '16 at 16:55
dezdichadodezdichado
6,4691929
6,4691929
$begingroup$
I don't get it. If minOnes(3) = 3, your $n$ would be 3. But with n = 2 < 3, $ 10^2$ - 1 = 99 is divisible by 3, so I think is not the same question.
$endgroup$
– Santiago Gil
May 1 '16 at 17:15
add a comment |
$begingroup$
I don't get it. If minOnes(3) = 3, your $n$ would be 3. But with n = 2 < 3, $ 10^2$ - 1 = 99 is divisible by 3, so I think is not the same question.
$endgroup$
– Santiago Gil
May 1 '16 at 17:15
$begingroup$
I don't get it. If minOnes(3) = 3, your $n$ would be 3. But with n = 2 < 3, $ 10^2$ - 1 = 99 is divisible by 3, so I think is not the same question.
$endgroup$
– Santiago Gil
May 1 '16 at 17:15
$begingroup$
I don't get it. If minOnes(3) = 3, your $n$ would be 3. But with n = 2 < 3, $ 10^2$ - 1 = 99 is divisible by 3, so I think is not the same question.
$endgroup$
– Santiago Gil
May 1 '16 at 17:15
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1766947%2fformula-for-smallest-multiple-of-given-number-whose-every-digit-is-1%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
