On randomly permuting digits in a large random number
$begingroup$
Suppose you're given a natural number with $N$ digits, randomly chosen except that none of the digits are $0$. Now shuffle its digits to obtain a new $N$-digit number. What is the probability (as $Nrightarrowinfty$, say) that the new number and the old one are relatively prime?
recreational-mathematics greatest-common-divisor natural-numbers
asked Dec 15 '18 at 5:40
mjqxxxxmjqxxxx
31.6k24086
$endgroup$
add a comment |
$begingroup$
Suppose you're given a natural number with $N$ digits, randomly chosen except that none of the digits are $0$. Now shuffle its digits to obtain a new $N$-digit number. What is the probability (as $Nrightarrowinfty$, say) that the new number and the old one are relatively prime?
recreational-mathematics greatest-common-divisor natural-numbers
asked Dec 15 '18 at 5:40
mjqxxxxmjqxxxx
31.6k24086
$endgroup$
1
$begingroup$
why no 0's as digits?
$endgroup$
– mathworker21
Dec 15 '18 at 5:48
$begingroup$
also, when you say "to obtain a new $N$-digit number" are you excluding permutations that result in the same number being obtained? if so, that makes the problem much uglier
$endgroup$
– mathworker21
Dec 15 '18 at 5:52
$begingroup$
@mathworker21: the chance the permutation matches is $frac 1{N!}$, which is tiny and goes to $0$ as $N to infty$. I presume the prohibition on zeros is to make sure neither permutation has leading zeros. I don't think that really matters.
$endgroup$
– Ross Millikan
Dec 15 '18 at 6:01
$begingroup$
@RossMillikan the $frac{1}{N!}$ can be added many times...
$endgroup$
– mathworker21
Dec 15 '18 at 6:03
$begingroup$
The restriction on zeroes is to avoid worrying about leading zeroes. I think the question would not be substantially harder or easier if zeroes were allowed. And the "new" part doesn't matter; the probability of getting the same number back certainly goes to zero as $Nrightarrowinfty$.
$endgroup$
– mjqxxxx
Dec 15 '18 at 7:06
add a comment |
$begingroup$
Suppose you're given a natural number with $N$ digits, randomly chosen except that none of the digits are $0$. Now shuffle its digits to obtain a new $N$-digit number. What is the probability (as $Nrightarrowinfty$, say) that the new number and the old one are relatively prime?
recreational-mathematics greatest-common-divisor natural-numbers
asked Dec 15 '18 at 5:40
mjqxxxxmjqxxxx
31.6k24086
$endgroup$
Suppose you're given a natural number with $N$ digits, randomly chosen except that none of the digits are $0$. Now shuffle its digits to obtain a new $N$-digit number. What is the probability (as $Nrightarrowinfty$, say) that the new number and the old one are relatively prime?
recreational-mathematics greatest-common-divisor natural-numbers
recreational-mathematics greatest-common-divisor natural-numbers
asked Dec 15 '18 at 5:40
mjqxxxxmjqxxxx
31.6k24086
asked Dec 15 '18 at 5:40
mjqxxxxmjqxxxx
31.6k24086
asked Dec 15 '18 at 5:40
mjqxxxxmjqxxxx
31.6k24086
asked Dec 15 '18 at 5:40
mjqxxxxmjqxxxx
31.6k24086
asked Dec 15 '18 at 5:40
mjqxxxxmjqxxxx
31.6k24086
31.6k24086
1
$begingroup$
why no 0's as digits?
$endgroup$
– mathworker21
Dec 15 '18 at 5:48
$begingroup$
also, when you say "to obtain a new $N$-digit number" are you excluding permutations that result in the same number being obtained? if so, that makes the problem much uglier
$endgroup$
– mathworker21
Dec 15 '18 at 5:52
$begingroup$
@mathworker21: the chance the permutation matches is $frac 1{N!}$, which is tiny and goes to $0$ as $N to infty$. I presume the prohibition on zeros is to make sure neither permutation has leading zeros. I don't think that really matters.
$endgroup$
– Ross Millikan
Dec 15 '18 at 6:01
$begingroup$
@RossMillikan the $frac{1}{N!}$ can be added many times...
$endgroup$
– mathworker21
Dec 15 '18 at 6:03
$begingroup$
The restriction on zeroes is to avoid worrying about leading zeroes. I think the question would not be substantially harder or easier if zeroes were allowed. And the "new" part doesn't matter; the probability of getting the same number back certainly goes to zero as $Nrightarrowinfty$.
$endgroup$
– mjqxxxx
Dec 15 '18 at 7:06
add a comment |
1
$begingroup$
why no 0's as digits?
$endgroup$
– mathworker21
Dec 15 '18 at 5:48
$begingroup$
also, when you say "to obtain a new $N$-digit number" are you excluding permutations that result in the same number being obtained? if so, that makes the problem much uglier
$endgroup$
– mathworker21
Dec 15 '18 at 5:52
$begingroup$
@mathworker21: the chance the permutation matches is $frac 1{N!}$, which is tiny and goes to $0$ as $N to infty$. I presume the prohibition on zeros is to make sure neither permutation has leading zeros. I don't think that really matters.
$endgroup$
– Ross Millikan
Dec 15 '18 at 6:01
$begingroup$
@RossMillikan the $frac{1}{N!}$ can be added many times...
$endgroup$
– mathworker21
Dec 15 '18 at 6:03
$begingroup$
The restriction on zeroes is to avoid worrying about leading zeroes. I think the question would not be substantially harder or easier if zeroes were allowed. And the "new" part doesn't matter; the probability of getting the same number back certainly goes to zero as $Nrightarrowinfty$.
$endgroup$
– mjqxxxx
Dec 15 '18 at 7:06
1
1
$begingroup$
why no 0's as digits?
$endgroup$
– mathworker21
Dec 15 '18 at 5:48
$begingroup$
why no 0's as digits?
$endgroup$
– mathworker21
Dec 15 '18 at 5:48
$begingroup$
also, when you say "to obtain a new $N$-digit number" are you excluding permutations that result in the same number being obtained? if so, that makes the problem much uglier
$endgroup$
– mathworker21
Dec 15 '18 at 5:52
$begingroup$
also, when you say "to obtain a new $N$-digit number" are you excluding permutations that result in the same number being obtained? if so, that makes the problem much uglier
$endgroup$
– mathworker21
Dec 15 '18 at 5:52
$begingroup$
@mathworker21: the chance the permutation matches is $frac 1{N!}$, which is tiny and goes to $0$ as $N to infty$. I presume the prohibition on zeros is to make sure neither permutation has leading zeros. I don't think that really matters.
$endgroup$
– Ross Millikan
Dec 15 '18 at 6:01
$begingroup$
@mathworker21: the chance the permutation matches is $frac 1{N!}$, which is tiny and goes to $0$ as $N to infty$. I presume the prohibition on zeros is to make sure neither permutation has leading zeros. I don't think that really matters.
$endgroup$
– Ross Millikan
Dec 15 '18 at 6:01
$begingroup$
@RossMillikan the $frac{1}{N!}$ can be added many times...
$endgroup$
– mathworker21
Dec 15 '18 at 6:03
$begingroup$
@RossMillikan the $frac{1}{N!}$ can be added many times...
$endgroup$
– mathworker21
Dec 15 '18 at 6:03
$begingroup$
The restriction on zeroes is to avoid worrying about leading zeroes. I think the question would not be substantially harder or easier if zeroes were allowed. And the "new" part doesn't matter; the probability of getting the same number back certainly goes to zero as $Nrightarrowinfty$.
$endgroup$
– mjqxxxx
Dec 15 '18 at 7:06
$begingroup$
The restriction on zeroes is to avoid worrying about leading zeroes. I think the question would not be substantially harder or easier if zeroes were allowed. And the "new" part doesn't matter; the probability of getting the same number back certainly goes to zero as $Nrightarrowinfty$.
$endgroup$
– mjqxxxx
Dec 15 '18 at 7:06
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
We know that the chance two numbers are coprime is $frac 6{pi^2}$ as shown in this question.
The exclusion of $0$ changes the chances that the numbers are divisible by $2$ and $5$. With all digits included the chance one number is divisible by $2$ is $frac 12$ and the chance both are is $frac 14$. Now the chance a number is even is $frac 49$ and the chance both are is $frac {16}{81}$. Similarly the chance both are multiples of $5$ is now $frac 1{81}$ instead of $frac 1{25}$.
The scrambling of the digits introduces an important correlation because if one of them has a factor $3$ so does the other. The chance two numbers both have a factor $3$ is $frac 19$ so in our case the factor $frac 89$ that they do not both have a factor $3$ is replaced by a factor $frac 23$.
The probability that they are not both multiples of any of $2,3,5$ now is $(1-frac {16}{81})(1-frac 13)(1-frac 1{81})=frac {10400}{19683}$ instead of $(1-frac 14)(1-frac 19)(1-frac 1{25})=frac {16}{25}.$ We would expect the probability they are coprime to be $frac 6{pi^2}cdot frac {25}{16} cdot frac {10400}{19683}approx 0.502$ per Alpha.
I can't prove that there are no changes for the probability for other primes, but one way to motivate it for primes with rather less than $N$ digits is to think about each digit contributing the the remainder on division by the prime. It adds in one of nine remainders that are reasonably scattered through the residues.
answered Dec 15 '18 at 5:59
Ross MillikanRoss Millikan
297k23198371
$endgroup$
$begingroup$
This is a comment, not an answer.
$endgroup$
– mathworker21
Dec 15 '18 at 6:00
1
$begingroup$
@mathworker21: No... it is a (partial) answer... not a comment.
$endgroup$
– David G. Stork
Dec 15 '18 at 6:19
$begingroup$
@DavidG.Stork No. The question asked what is the probability. Ross said what we would expect the probability to be. That is a comment, not an answer.
$endgroup$
– mathworker21
Dec 15 '18 at 6:23
$begingroup$
I like the direction of this answer -- correct the independent-numbers probability to account for invariants -- but I don't think it's exactly right, because simulation seems to give a slightly higher probability.
$endgroup$
– mjqxxxx
Dec 15 '18 at 7:11
1
$begingroup$
@antkam: yes, every prime divides a number of the form $10^k-1$ but that does not mean a correction is needed. For $11$, for example, there are $81$ different pairs of digits available when $0$s are excluded. There are $9$ pairs with sum $10 bmod 11$ and $7$ pairs with each other remainder. As you couple those with other pairs the differences wash out quickly, so if $N$ is large the numbers will be equally distributed. All we need is that very close to $frac 1{11}$ have divisor $11$. The same logic works for any prime much smaller than $N$ digits.
$endgroup$
– Ross Millikan
Dec 17 '18 at 22:59
|
show 4 more comments
Your Answer
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%2f3040209%2fon-randomly-permuting-digits-in-a-large-random-number%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
We know that the chance two numbers are coprime is $frac 6{pi^2}$ as shown in this question.
The exclusion of $0$ changes the chances that the numbers are divisible by $2$ and $5$. With all digits included the chance one number is divisible by $2$ is $frac 12$ and the chance both are is $frac 14$. Now the chance a number is even is $frac 49$ and the chance both are is $frac {16}{81}$. Similarly the chance both are multiples of $5$ is now $frac 1{81}$ instead of $frac 1{25}$.
The scrambling of the digits introduces an important correlation because if one of them has a factor $3$ so does the other. The chance two numbers both have a factor $3$ is $frac 19$ so in our case the factor $frac 89$ that they do not both have a factor $3$ is replaced by a factor $frac 23$.
The probability that they are not both multiples of any of $2,3,5$ now is $(1-frac {16}{81})(1-frac 13)(1-frac 1{81})=frac {10400}{19683}$ instead of $(1-frac 14)(1-frac 19)(1-frac 1{25})=frac {16}{25}.$ We would expect the probability they are coprime to be $frac 6{pi^2}cdot frac {25}{16} cdot frac {10400}{19683}approx 0.502$ per Alpha.
I can't prove that there are no changes for the probability for other primes, but one way to motivate it for primes with rather less than $N$ digits is to think about each digit contributing the the remainder on division by the prime. It adds in one of nine remainders that are reasonably scattered through the residues.
answered Dec 15 '18 at 5:59
Ross MillikanRoss Millikan
297k23198371
$endgroup$
$begingroup$
This is a comment, not an answer.
$endgroup$
– mathworker21
Dec 15 '18 at 6:00
1
$begingroup$
@mathworker21: No... it is a (partial) answer... not a comment.
$endgroup$
– David G. Stork
Dec 15 '18 at 6:19
$begingroup$
@DavidG.Stork No. The question asked what is the probability. Ross said what we would expect the probability to be. That is a comment, not an answer.
$endgroup$
– mathworker21
Dec 15 '18 at 6:23
$begingroup$
I like the direction of this answer -- correct the independent-numbers probability to account for invariants -- but I don't think it's exactly right, because simulation seems to give a slightly higher probability.
$endgroup$
– mjqxxxx
Dec 15 '18 at 7:11
1
$begingroup$
@antkam: yes, every prime divides a number of the form $10^k-1$ but that does not mean a correction is needed. For $11$, for example, there are $81$ different pairs of digits available when $0$s are excluded. There are $9$ pairs with sum $10 bmod 11$ and $7$ pairs with each other remainder. As you couple those with other pairs the differences wash out quickly, so if $N$ is large the numbers will be equally distributed. All we need is that very close to $frac 1{11}$ have divisor $11$. The same logic works for any prime much smaller than $N$ digits.
$endgroup$
– Ross Millikan
Dec 17 '18 at 22:59
|
show 4 more comments
$begingroup$
We know that the chance two numbers are coprime is $frac 6{pi^2}$ as shown in this question.
The exclusion of $0$ changes the chances that the numbers are divisible by $2$ and $5$. With all digits included the chance one number is divisible by $2$ is $frac 12$ and the chance both are is $frac 14$. Now the chance a number is even is $frac 49$ and the chance both are is $frac {16}{81}$. Similarly the chance both are multiples of $5$ is now $frac 1{81}$ instead of $frac 1{25}$.
The scrambling of the digits introduces an important correlation because if one of them has a factor $3$ so does the other. The chance two numbers both have a factor $3$ is $frac 19$ so in our case the factor $frac 89$ that they do not both have a factor $3$ is replaced by a factor $frac 23$.
The probability that they are not both multiples of any of $2,3,5$ now is $(1-frac {16}{81})(1-frac 13)(1-frac 1{81})=frac {10400}{19683}$ instead of $(1-frac 14)(1-frac 19)(1-frac 1{25})=frac {16}{25}.$ We would expect the probability they are coprime to be $frac 6{pi^2}cdot frac {25}{16} cdot frac {10400}{19683}approx 0.502$ per Alpha.
I can't prove that there are no changes for the probability for other primes, but one way to motivate it for primes with rather less than $N$ digits is to think about each digit contributing the the remainder on division by the prime. It adds in one of nine remainders that are reasonably scattered through the residues.
answered Dec 15 '18 at 5:59
Ross MillikanRoss Millikan
297k23198371
$endgroup$
$begingroup$
This is a comment, not an answer.
$endgroup$
– mathworker21
Dec 15 '18 at 6:00
1
$begingroup$
@mathworker21: No... it is a (partial) answer... not a comment.
$endgroup$
– David G. Stork
Dec 15 '18 at 6:19
$begingroup$
@DavidG.Stork No. The question asked what is the probability. Ross said what we would expect the probability to be. That is a comment, not an answer.
$endgroup$
– mathworker21
Dec 15 '18 at 6:23
$begingroup$
I like the direction of this answer -- correct the independent-numbers probability to account for invariants -- but I don't think it's exactly right, because simulation seems to give a slightly higher probability.
$endgroup$
– mjqxxxx
Dec 15 '18 at 7:11
1
$begingroup$
@antkam: yes, every prime divides a number of the form $10^k-1$ but that does not mean a correction is needed. For $11$, for example, there are $81$ different pairs of digits available when $0$s are excluded. There are $9$ pairs with sum $10 bmod 11$ and $7$ pairs with each other remainder. As you couple those with other pairs the differences wash out quickly, so if $N$ is large the numbers will be equally distributed. All we need is that very close to $frac 1{11}$ have divisor $11$. The same logic works for any prime much smaller than $N$ digits.
$endgroup$
– Ross Millikan
Dec 17 '18 at 22:59
|
show 4 more comments
$begingroup$
We know that the chance two numbers are coprime is $frac 6{pi^2}$ as shown in this question.
The exclusion of $0$ changes the chances that the numbers are divisible by $2$ and $5$. With all digits included the chance one number is divisible by $2$ is $frac 12$ and the chance both are is $frac 14$. Now the chance a number is even is $frac 49$ and the chance both are is $frac {16}{81}$. Similarly the chance both are multiples of $5$ is now $frac 1{81}$ instead of $frac 1{25}$.
The scrambling of the digits introduces an important correlation because if one of them has a factor $3$ so does the other. The chance two numbers both have a factor $3$ is $frac 19$ so in our case the factor $frac 89$ that they do not both have a factor $3$ is replaced by a factor $frac 23$.
The probability that they are not both multiples of any of $2,3,5$ now is $(1-frac {16}{81})(1-frac 13)(1-frac 1{81})=frac {10400}{19683}$ instead of $(1-frac 14)(1-frac 19)(1-frac 1{25})=frac {16}{25}.$ We would expect the probability they are coprime to be $frac 6{pi^2}cdot frac {25}{16} cdot frac {10400}{19683}approx 0.502$ per Alpha.
I can't prove that there are no changes for the probability for other primes, but one way to motivate it for primes with rather less than $N$ digits is to think about each digit contributing the the remainder on division by the prime. It adds in one of nine remainders that are reasonably scattered through the residues.
answered Dec 15 '18 at 5:59
Ross MillikanRoss Millikan
297k23198371
$endgroup$
We know that the chance two numbers are coprime is $frac 6{pi^2}$ as shown in this question.
The exclusion of $0$ changes the chances that the numbers are divisible by $2$ and $5$. With all digits included the chance one number is divisible by $2$ is $frac 12$ and the chance both are is $frac 14$. Now the chance a number is even is $frac 49$ and the chance both are is $frac {16}{81}$. Similarly the chance both are multiples of $5$ is now $frac 1{81}$ instead of $frac 1{25}$.
The scrambling of the digits introduces an important correlation because if one of them has a factor $3$ so does the other. The chance two numbers both have a factor $3$ is $frac 19$ so in our case the factor $frac 89$ that they do not both have a factor $3$ is replaced by a factor $frac 23$.
The probability that they are not both multiples of any of $2,3,5$ now is $(1-frac {16}{81})(1-frac 13)(1-frac 1{81})=frac {10400}{19683}$ instead of $(1-frac 14)(1-frac 19)(1-frac 1{25})=frac {16}{25}.$ We would expect the probability they are coprime to be $frac 6{pi^2}cdot frac {25}{16} cdot frac {10400}{19683}approx 0.502$ per Alpha.
I can't prove that there are no changes for the probability for other primes, but one way to motivate it for primes with rather less than $N$ digits is to think about each digit contributing the the remainder on division by the prime. It adds in one of nine remainders that are reasonably scattered through the residues.
answered Dec 15 '18 at 5:59
Ross MillikanRoss Millikan
297k23198371
edited Dec 16 '18 at 1:06
answered Dec 15 '18 at 5:59
Ross MillikanRoss Millikan
297k23198371
answered Dec 15 '18 at 5:59
Ross MillikanRoss Millikan
297k23198371
answered Dec 15 '18 at 5:59
Ross MillikanRoss Millikan
297k23198371
297k23198371
$begingroup$
This is a comment, not an answer.
$endgroup$
– mathworker21
Dec 15 '18 at 6:00
1
$begingroup$
@mathworker21: No... it is a (partial) answer... not a comment.
$endgroup$
– David G. Stork
Dec 15 '18 at 6:19
$begingroup$
@DavidG.Stork No. The question asked what is the probability. Ross said what we would expect the probability to be. That is a comment, not an answer.
$endgroup$
– mathworker21
Dec 15 '18 at 6:23
$begingroup$
I like the direction of this answer -- correct the independent-numbers probability to account for invariants -- but I don't think it's exactly right, because simulation seems to give a slightly higher probability.
$endgroup$
– mjqxxxx
Dec 15 '18 at 7:11
1
$begingroup$
@antkam: yes, every prime divides a number of the form $10^k-1$ but that does not mean a correction is needed. For $11$, for example, there are $81$ different pairs of digits available when $0$s are excluded. There are $9$ pairs with sum $10 bmod 11$ and $7$ pairs with each other remainder. As you couple those with other pairs the differences wash out quickly, so if $N$ is large the numbers will be equally distributed. All we need is that very close to $frac 1{11}$ have divisor $11$. The same logic works for any prime much smaller than $N$ digits.
$endgroup$
– Ross Millikan
Dec 17 '18 at 22:59
|
show 4 more comments
$begingroup$
This is a comment, not an answer.
$endgroup$
– mathworker21
Dec 15 '18 at 6:00
1
$begingroup$
@mathworker21: No... it is a (partial) answer... not a comment.
$endgroup$
– David G. Stork
Dec 15 '18 at 6:19
$begingroup$
@DavidG.Stork No. The question asked what is the probability. Ross said what we would expect the probability to be. That is a comment, not an answer.
$endgroup$
– mathworker21
Dec 15 '18 at 6:23
$begingroup$
I like the direction of this answer -- correct the independent-numbers probability to account for invariants -- but I don't think it's exactly right, because simulation seems to give a slightly higher probability.
$endgroup$
– mjqxxxx
Dec 15 '18 at 7:11
1
$begingroup$
@antkam: yes, every prime divides a number of the form $10^k-1$ but that does not mean a correction is needed. For $11$, for example, there are $81$ different pairs of digits available when $0$s are excluded. There are $9$ pairs with sum $10 bmod 11$ and $7$ pairs with each other remainder. As you couple those with other pairs the differences wash out quickly, so if $N$ is large the numbers will be equally distributed. All we need is that very close to $frac 1{11}$ have divisor $11$. The same logic works for any prime much smaller than $N$ digits.
$endgroup$
– Ross Millikan
Dec 17 '18 at 22:59
$begingroup$
This is a comment, not an answer.
$endgroup$
– mathworker21
Dec 15 '18 at 6:00
$begingroup$
This is a comment, not an answer.
$endgroup$
– mathworker21
Dec 15 '18 at 6:00
1
1
$begingroup$
@mathworker21: No... it is a (partial) answer... not a comment.
$endgroup$
– David G. Stork
Dec 15 '18 at 6:19
$begingroup$
@mathworker21: No... it is a (partial) answer... not a comment.
$endgroup$
– David G. Stork
Dec 15 '18 at 6:19
$begingroup$
@DavidG.Stork No. The question asked what is the probability. Ross said what we would expect the probability to be. That is a comment, not an answer.
$endgroup$
– mathworker21
Dec 15 '18 at 6:23
$begingroup$
@DavidG.Stork No. The question asked what is the probability. Ross said what we would expect the probability to be. That is a comment, not an answer.
$endgroup$
– mathworker21
Dec 15 '18 at 6:23
$begingroup$
I like the direction of this answer -- correct the independent-numbers probability to account for invariants -- but I don't think it's exactly right, because simulation seems to give a slightly higher probability.
$endgroup$
– mjqxxxx
Dec 15 '18 at 7:11
$begingroup$
I like the direction of this answer -- correct the independent-numbers probability to account for invariants -- but I don't think it's exactly right, because simulation seems to give a slightly higher probability.
$endgroup$
– mjqxxxx
Dec 15 '18 at 7:11
1
1
$begingroup$
@antkam: yes, every prime divides a number of the form $10^k-1$ but that does not mean a correction is needed. For $11$, for example, there are $81$ different pairs of digits available when $0$s are excluded. There are $9$ pairs with sum $10 bmod 11$ and $7$ pairs with each other remainder. As you couple those with other pairs the differences wash out quickly, so if $N$ is large the numbers will be equally distributed. All we need is that very close to $frac 1{11}$ have divisor $11$. The same logic works for any prime much smaller than $N$ digits.
$endgroup$
– Ross Millikan
Dec 17 '18 at 22:59
$begingroup$
@antkam: yes, every prime divides a number of the form $10^k-1$ but that does not mean a correction is needed. For $11$, for example, there are $81$ different pairs of digits available when $0$s are excluded. There are $9$ pairs with sum $10 bmod 11$ and $7$ pairs with each other remainder. As you couple those with other pairs the differences wash out quickly, so if $N$ is large the numbers will be equally distributed. All we need is that very close to $frac 1{11}$ have divisor $11$. The same logic works for any prime much smaller than $N$ digits.
$endgroup$
– Ross Millikan
Dec 17 '18 at 22:59
|
show 4 more comments
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%2f3040209%2fon-randomly-permuting-digits-in-a-large-random-number%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
1
$begingroup$
why no 0's as digits?
$endgroup$
– mathworker21
Dec 15 '18 at 5:48
$begingroup$
also, when you say "to obtain a new $N$-digit number" are you excluding permutations that result in the same number being obtained? if so, that makes the problem much uglier
$endgroup$
– mathworker21
Dec 15 '18 at 5:52
$begingroup$
@mathworker21: the chance the permutation matches is $frac 1{N!}$, which is tiny and goes to $0$ as $N to infty$. I presume the prohibition on zeros is to make sure neither permutation has leading zeros. I don't think that really matters.
$endgroup$
– Ross Millikan
Dec 15 '18 at 6:01
$begingroup$
@RossMillikan the $frac{1}{N!}$ can be added many times...
$endgroup$
– mathworker21
Dec 15 '18 at 6:03
$begingroup$
The restriction on zeroes is to avoid worrying about leading zeroes. I think the question would not be substantially harder or easier if zeroes were allowed. And the "new" part doesn't matter; the probability of getting the same number back certainly goes to zero as $Nrightarrowinfty$.
$endgroup$
– mjqxxxx
Dec 15 '18 at 7:06