Probability of $f(n) - varphi(n)$ to be an even number.
$begingroup$
Let $f(n)$ denotes the product of all the positive divisors of n, and $varphi(n)$ denotes the sum of all the positive divisors of $n$. If number $n$ is to be randomly selected from the first $100$ positive integers, what is the probability that $f(n) - varphi(n)$ is an even number?
So far, I know that $f(n)$ and $varphi(n)$ need to be either both odd or both even. If $n$ is odd, then $f(n)$ must also be odd; if $n$ is even, then $f(n)$ must also be even. However, I have difficulty calculating when $varphi(n)$ is odd or even. It appears to be completely random.
probability elementary-number-theory arithmetic-functions
$endgroup$
add a comment |
$begingroup$
Let $f(n)$ denotes the product of all the positive divisors of n, and $varphi(n)$ denotes the sum of all the positive divisors of $n$. If number $n$ is to be randomly selected from the first $100$ positive integers, what is the probability that $f(n) - varphi(n)$ is an even number?
So far, I know that $f(n)$ and $varphi(n)$ need to be either both odd or both even. If $n$ is odd, then $f(n)$ must also be odd; if $n$ is even, then $f(n)$ must also be even. However, I have difficulty calculating when $varphi(n)$ is odd or even. It appears to be completely random.
probability elementary-number-theory arithmetic-functions
$endgroup$
$begingroup$
Hello, and welcome to MSE. Although your title says you have no clue, please tell us what have your tried so far? Here is a hint that might help you: The probability would be the # of values of $n$ where $fleft(nright) - phileft(nright)$ is even divided by the total # of values being checked, this being $100$ in your case.
$endgroup$
– John Omielan
Jan 20 at 5:11
add a comment |
$begingroup$
Let $f(n)$ denotes the product of all the positive divisors of n, and $varphi(n)$ denotes the sum of all the positive divisors of $n$. If number $n$ is to be randomly selected from the first $100$ positive integers, what is the probability that $f(n) - varphi(n)$ is an even number?
So far, I know that $f(n)$ and $varphi(n)$ need to be either both odd or both even. If $n$ is odd, then $f(n)$ must also be odd; if $n$ is even, then $f(n)$ must also be even. However, I have difficulty calculating when $varphi(n)$ is odd or even. It appears to be completely random.
probability elementary-number-theory arithmetic-functions
$endgroup$
Let $f(n)$ denotes the product of all the positive divisors of n, and $varphi(n)$ denotes the sum of all the positive divisors of $n$. If number $n$ is to be randomly selected from the first $100$ positive integers, what is the probability that $f(n) - varphi(n)$ is an even number?
So far, I know that $f(n)$ and $varphi(n)$ need to be either both odd or both even. If $n$ is odd, then $f(n)$ must also be odd; if $n$ is even, then $f(n)$ must also be even. However, I have difficulty calculating when $varphi(n)$ is odd or even. It appears to be completely random.
probability elementary-number-theory arithmetic-functions
probability elementary-number-theory arithmetic-functions
edited Jan 20 at 6:22
Chris.
asked Jan 20 at 5:04
Chris.Chris.
132
132
$begingroup$
Hello, and welcome to MSE. Although your title says you have no clue, please tell us what have your tried so far? Here is a hint that might help you: The probability would be the # of values of $n$ where $fleft(nright) - phileft(nright)$ is even divided by the total # of values being checked, this being $100$ in your case.
$endgroup$
– John Omielan
Jan 20 at 5:11
add a comment |
$begingroup$
Hello, and welcome to MSE. Although your title says you have no clue, please tell us what have your tried so far? Here is a hint that might help you: The probability would be the # of values of $n$ where $fleft(nright) - phileft(nright)$ is even divided by the total # of values being checked, this being $100$ in your case.
$endgroup$
– John Omielan
Jan 20 at 5:11
$begingroup$
Hello, and welcome to MSE. Although your title says you have no clue, please tell us what have your tried so far? Here is a hint that might help you: The probability would be the # of values of $n$ where $fleft(nright) - phileft(nright)$ is even divided by the total # of values being checked, this being $100$ in your case.
$endgroup$
– John Omielan
Jan 20 at 5:11
$begingroup$
Hello, and welcome to MSE. Although your title says you have no clue, please tell us what have your tried so far? Here is a hint that might help you: The probability would be the # of values of $n$ where $fleft(nright) - phileft(nright)$ is even divided by the total # of values being checked, this being $100$ in your case.
$endgroup$
– John Omielan
Jan 20 at 5:11
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
$f(n)$ is odd whenever $n$ is odd and even whenever $n$ is even because when $n$ is even there is a factor $2$.
$varphi(n)$ is multiplicative-we have $varphi(nm)=varphi(n)varphi(m)$ whenever $n$ and $m$ are coprime. If $n=p^k$ for $k$ an odd prime, $varphi(p^k)$ is even when $k$ is odd, but $varphi(2^k)$ is always odd. This means that $varphi(n)$ is even when $n$ has at least one factor of an odd prime raised to an odd power and odd otherwise. For example, all multiples of $3$ that are not multiples of $9$ have an even sum of factors because we have all the factors without a factor $3$ and all the factors with a factor $3$, making $4$ times the sum of all the factors without a factor $3$.
For odd $n$ the only ones with $varphi(n)$ odd are $9,25,49$, so $47$ odd numbers have $f(n)-varphi(n) odd.
For even $n$ the only ones with $varphi(n)$ odd are $18,36,54,72,90,50,80$ so $7$ even numbers have $f(n)-varphi(n)$ odd.
The chance a number $n$ in the range $1$ to $100$ inclusive has $f(n)-varphi(n)$ even is $frac {51}{100}$
$endgroup$
$begingroup$
This is not right... Why is o(n) multiplicative? If you substitute 2 and 3 in, it is not right. o(2*3) ≠ o(2)*o(3)
$endgroup$
– Chris.
Jan 20 at 11:03
$begingroup$
@Chris: yes it is. $varphi(2)=1+2=3, varphi(3)=1+3=4, varphi=1+2+3+6=12=3cdot 4$
$endgroup$
– Ross Millikan
Jan 20 at 14:57
add a comment |
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%2f3080204%2fprobability-of-fn-varphin-to-be-an-even-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$
$f(n)$ is odd whenever $n$ is odd and even whenever $n$ is even because when $n$ is even there is a factor $2$.
$varphi(n)$ is multiplicative-we have $varphi(nm)=varphi(n)varphi(m)$ whenever $n$ and $m$ are coprime. If $n=p^k$ for $k$ an odd prime, $varphi(p^k)$ is even when $k$ is odd, but $varphi(2^k)$ is always odd. This means that $varphi(n)$ is even when $n$ has at least one factor of an odd prime raised to an odd power and odd otherwise. For example, all multiples of $3$ that are not multiples of $9$ have an even sum of factors because we have all the factors without a factor $3$ and all the factors with a factor $3$, making $4$ times the sum of all the factors without a factor $3$.
For odd $n$ the only ones with $varphi(n)$ odd are $9,25,49$, so $47$ odd numbers have $f(n)-varphi(n) odd.
For even $n$ the only ones with $varphi(n)$ odd are $18,36,54,72,90,50,80$ so $7$ even numbers have $f(n)-varphi(n)$ odd.
The chance a number $n$ in the range $1$ to $100$ inclusive has $f(n)-varphi(n)$ even is $frac {51}{100}$
$endgroup$
$begingroup$
This is not right... Why is o(n) multiplicative? If you substitute 2 and 3 in, it is not right. o(2*3) ≠ o(2)*o(3)
$endgroup$
– Chris.
Jan 20 at 11:03
$begingroup$
@Chris: yes it is. $varphi(2)=1+2=3, varphi(3)=1+3=4, varphi=1+2+3+6=12=3cdot 4$
$endgroup$
– Ross Millikan
Jan 20 at 14:57
add a comment |
$begingroup$
$f(n)$ is odd whenever $n$ is odd and even whenever $n$ is even because when $n$ is even there is a factor $2$.
$varphi(n)$ is multiplicative-we have $varphi(nm)=varphi(n)varphi(m)$ whenever $n$ and $m$ are coprime. If $n=p^k$ for $k$ an odd prime, $varphi(p^k)$ is even when $k$ is odd, but $varphi(2^k)$ is always odd. This means that $varphi(n)$ is even when $n$ has at least one factor of an odd prime raised to an odd power and odd otherwise. For example, all multiples of $3$ that are not multiples of $9$ have an even sum of factors because we have all the factors without a factor $3$ and all the factors with a factor $3$, making $4$ times the sum of all the factors without a factor $3$.
For odd $n$ the only ones with $varphi(n)$ odd are $9,25,49$, so $47$ odd numbers have $f(n)-varphi(n) odd.
For even $n$ the only ones with $varphi(n)$ odd are $18,36,54,72,90,50,80$ so $7$ even numbers have $f(n)-varphi(n)$ odd.
The chance a number $n$ in the range $1$ to $100$ inclusive has $f(n)-varphi(n)$ even is $frac {51}{100}$
$endgroup$
$begingroup$
This is not right... Why is o(n) multiplicative? If you substitute 2 and 3 in, it is not right. o(2*3) ≠ o(2)*o(3)
$endgroup$
– Chris.
Jan 20 at 11:03
$begingroup$
@Chris: yes it is. $varphi(2)=1+2=3, varphi(3)=1+3=4, varphi=1+2+3+6=12=3cdot 4$
$endgroup$
– Ross Millikan
Jan 20 at 14:57
add a comment |
$begingroup$
$f(n)$ is odd whenever $n$ is odd and even whenever $n$ is even because when $n$ is even there is a factor $2$.
$varphi(n)$ is multiplicative-we have $varphi(nm)=varphi(n)varphi(m)$ whenever $n$ and $m$ are coprime. If $n=p^k$ for $k$ an odd prime, $varphi(p^k)$ is even when $k$ is odd, but $varphi(2^k)$ is always odd. This means that $varphi(n)$ is even when $n$ has at least one factor of an odd prime raised to an odd power and odd otherwise. For example, all multiples of $3$ that are not multiples of $9$ have an even sum of factors because we have all the factors without a factor $3$ and all the factors with a factor $3$, making $4$ times the sum of all the factors without a factor $3$.
For odd $n$ the only ones with $varphi(n)$ odd are $9,25,49$, so $47$ odd numbers have $f(n)-varphi(n) odd.
For even $n$ the only ones with $varphi(n)$ odd are $18,36,54,72,90,50,80$ so $7$ even numbers have $f(n)-varphi(n)$ odd.
The chance a number $n$ in the range $1$ to $100$ inclusive has $f(n)-varphi(n)$ even is $frac {51}{100}$
$endgroup$
$f(n)$ is odd whenever $n$ is odd and even whenever $n$ is even because when $n$ is even there is a factor $2$.
$varphi(n)$ is multiplicative-we have $varphi(nm)=varphi(n)varphi(m)$ whenever $n$ and $m$ are coprime. If $n=p^k$ for $k$ an odd prime, $varphi(p^k)$ is even when $k$ is odd, but $varphi(2^k)$ is always odd. This means that $varphi(n)$ is even when $n$ has at least one factor of an odd prime raised to an odd power and odd otherwise. For example, all multiples of $3$ that are not multiples of $9$ have an even sum of factors because we have all the factors without a factor $3$ and all the factors with a factor $3$, making $4$ times the sum of all the factors without a factor $3$.
For odd $n$ the only ones with $varphi(n)$ odd are $9,25,49$, so $47$ odd numbers have $f(n)-varphi(n) odd.
For even $n$ the only ones with $varphi(n)$ odd are $18,36,54,72,90,50,80$ so $7$ even numbers have $f(n)-varphi(n)$ odd.
The chance a number $n$ in the range $1$ to $100$ inclusive has $f(n)-varphi(n)$ even is $frac {51}{100}$
edited Jan 20 at 14:59
answered Jan 20 at 5:32
Ross MillikanRoss Millikan
298k23198371
298k23198371
$begingroup$
This is not right... Why is o(n) multiplicative? If you substitute 2 and 3 in, it is not right. o(2*3) ≠ o(2)*o(3)
$endgroup$
– Chris.
Jan 20 at 11:03
$begingroup$
@Chris: yes it is. $varphi(2)=1+2=3, varphi(3)=1+3=4, varphi=1+2+3+6=12=3cdot 4$
$endgroup$
– Ross Millikan
Jan 20 at 14:57
add a comment |
$begingroup$
This is not right... Why is o(n) multiplicative? If you substitute 2 and 3 in, it is not right. o(2*3) ≠ o(2)*o(3)
$endgroup$
– Chris.
Jan 20 at 11:03
$begingroup$
@Chris: yes it is. $varphi(2)=1+2=3, varphi(3)=1+3=4, varphi=1+2+3+6=12=3cdot 4$
$endgroup$
– Ross Millikan
Jan 20 at 14:57
$begingroup$
This is not right... Why is o(n) multiplicative? If you substitute 2 and 3 in, it is not right. o(2*3) ≠ o(2)*o(3)
$endgroup$
– Chris.
Jan 20 at 11:03
$begingroup$
This is not right... Why is o(n) multiplicative? If you substitute 2 and 3 in, it is not right. o(2*3) ≠ o(2)*o(3)
$endgroup$
– Chris.
Jan 20 at 11:03
$begingroup$
@Chris: yes it is. $varphi(2)=1+2=3, varphi(3)=1+3=4, varphi=1+2+3+6=12=3cdot 4$
$endgroup$
– Ross Millikan
Jan 20 at 14:57
$begingroup$
@Chris: yes it is. $varphi(2)=1+2=3, varphi(3)=1+3=4, varphi=1+2+3+6=12=3cdot 4$
$endgroup$
– Ross Millikan
Jan 20 at 14:57
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%2f3080204%2fprobability-of-fn-varphin-to-be-an-even-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
$begingroup$
Hello, and welcome to MSE. Although your title says you have no clue, please tell us what have your tried so far? Here is a hint that might help you: The probability would be the # of values of $n$ where $fleft(nright) - phileft(nright)$ is even divided by the total # of values being checked, this being $100$ in your case.
$endgroup$
– John Omielan
Jan 20 at 5:11