Can I make general formula for this problem
$begingroup$
I want to find how many pairs of numbers satisfy this condition on $[1,n]$.
For given $n$ , how many pairs $(a,b)$ are there such that $gcd(a,b) = 2^t , t > 0 $ for some whole number $t$.
All pairs $(a,b)$ should be bounded by $1leq a < b leq n $ .
Now I know that if $2|a land2|b implies 2|gcd(a,b)$ and this excludes all odd numbers .
But the space is too big to count for very large $n$.
Can I make general formula for $forall n $ ?
$a,b,n,t$ are whole numbers.
number-theory greatest-common-divisor
asked Jan 2 at 0:04
NoodleNoodle
717
$endgroup$
add a comment |
$begingroup$
I want to find how many pairs of numbers satisfy this condition on $[1,n]$.
For given $n$ , how many pairs $(a,b)$ are there such that $gcd(a,b) = 2^t , t > 0 $ for some whole number $t$.
All pairs $(a,b)$ should be bounded by $1leq a < b leq n $ .
Now I know that if $2|a land2|b implies 2|gcd(a,b)$ and this excludes all odd numbers .
But the space is too big to count for very large $n$.
Can I make general formula for $forall n $ ?
$a,b,n,t$ are whole numbers.
number-theory greatest-common-divisor
asked Jan 2 at 0:04
NoodleNoodle
717
$endgroup$
$begingroup$
Is an asymptotic answer sufficient? It's not too hard to figure out that, if $f(n)$ is the number of such pairs, then $lim_{nrightarrowinfty}frac{f(n)}{n^2}$ is positive and finite (and it's not even so hard to compute this constant). I don't see how one would get an exact answer for all $n$ though without considerable computation.
$endgroup$
– Milo Brandt
Jan 2 at 0:10
$begingroup$
that is the main problem here, for $n = 10^{6} $ , with brute force it takes about 3-4 hours to compute them , if its not possible for a general formula to be made maybe decreasing the search space will help but this of course requires more properties for such pairs
$endgroup$
– Noodle
Jan 2 at 0:15
add a comment |
$begingroup$
I want to find how many pairs of numbers satisfy this condition on $[1,n]$.
For given $n$ , how many pairs $(a,b)$ are there such that $gcd(a,b) = 2^t , t > 0 $ for some whole number $t$.
All pairs $(a,b)$ should be bounded by $1leq a < b leq n $ .
Now I know that if $2|a land2|b implies 2|gcd(a,b)$ and this excludes all odd numbers .
But the space is too big to count for very large $n$.
Can I make general formula for $forall n $ ?
$a,b,n,t$ are whole numbers.
number-theory greatest-common-divisor
asked Jan 2 at 0:04
NoodleNoodle
717
$endgroup$
I want to find how many pairs of numbers satisfy this condition on $[1,n]$.
For given $n$ , how many pairs $(a,b)$ are there such that $gcd(a,b) = 2^t , t > 0 $ for some whole number $t$.
All pairs $(a,b)$ should be bounded by $1leq a < b leq n $ .
Now I know that if $2|a land2|b implies 2|gcd(a,b)$ and this excludes all odd numbers .
But the space is too big to count for very large $n$.
Can I make general formula for $forall n $ ?
$a,b,n,t$ are whole numbers.
number-theory greatest-common-divisor
number-theory greatest-common-divisor
asked Jan 2 at 0:04
NoodleNoodle
717
asked Jan 2 at 0:04
NoodleNoodle
717
asked Jan 2 at 0:04
NoodleNoodle
717
asked Jan 2 at 0:04
NoodleNoodle
717
asked Jan 2 at 0:04
NoodleNoodle
717
717
$begingroup$
Is an asymptotic answer sufficient? It's not too hard to figure out that, if $f(n)$ is the number of such pairs, then $lim_{nrightarrowinfty}frac{f(n)}{n^2}$ is positive and finite (and it's not even so hard to compute this constant). I don't see how one would get an exact answer for all $n$ though without considerable computation.
$endgroup$
– Milo Brandt
Jan 2 at 0:10
$begingroup$
that is the main problem here, for $n = 10^{6} $ , with brute force it takes about 3-4 hours to compute them , if its not possible for a general formula to be made maybe decreasing the search space will help but this of course requires more properties for such pairs
$endgroup$
– Noodle
Jan 2 at 0:15
add a comment |
$begingroup$
Is an asymptotic answer sufficient? It's not too hard to figure out that, if $f(n)$ is the number of such pairs, then $lim_{nrightarrowinfty}frac{f(n)}{n^2}$ is positive and finite (and it's not even so hard to compute this constant). I don't see how one would get an exact answer for all $n$ though without considerable computation.
$endgroup$
– Milo Brandt
Jan 2 at 0:10
$begingroup$
that is the main problem here, for $n = 10^{6} $ , with brute force it takes about 3-4 hours to compute them , if its not possible for a general formula to be made maybe decreasing the search space will help but this of course requires more properties for such pairs
$endgroup$
– Noodle
Jan 2 at 0:15
$begingroup$
Is an asymptotic answer sufficient? It's not too hard to figure out that, if $f(n)$ is the number of such pairs, then $lim_{nrightarrowinfty}frac{f(n)}{n^2}$ is positive and finite (and it's not even so hard to compute this constant). I don't see how one would get an exact answer for all $n$ though without considerable computation.
$endgroup$
– Milo Brandt
Jan 2 at 0:10
$begingroup$
Is an asymptotic answer sufficient? It's not too hard to figure out that, if $f(n)$ is the number of such pairs, then $lim_{nrightarrowinfty}frac{f(n)}{n^2}$ is positive and finite (and it's not even so hard to compute this constant). I don't see how one would get an exact answer for all $n$ though without considerable computation.
$endgroup$
– Milo Brandt
Jan 2 at 0:10
$begingroup$
that is the main problem here, for $n = 10^{6} $ , with brute force it takes about 3-4 hours to compute them , if its not possible for a general formula to be made maybe decreasing the search space will help but this of course requires more properties for such pairs
$endgroup$
– Noodle
Jan 2 at 0:15
$begingroup$
that is the main problem here, for $n = 10^{6} $ , with brute force it takes about 3-4 hours to compute them , if its not possible for a general formula to be made maybe decreasing the search space will help but this of course requires more properties for such pairs
$endgroup$
– Noodle
Jan 2 at 0:15
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let $psi(n)=#{(x,y) : 1 leqslant x,y leqslant n, gcd(x, y) = 1}$. Then, for $1 leqslant d leqslant n$,
$$#{(x,y) : 1 leqslant x,y leqslant n, gcd(x, y) = d} = psibig(lfloor n/d rfloorbig),$$
and the union of these sets is just ${(x,y) : 1 leqslant x,y leqslant n}$. This gives
$$color{blue}{sum_{d=1}^{n}psibig(lfloor n/d rfloorbig)=n^2} implies psi(n)=sum_{d=1}^{n}mu(d)lfloor n/d rfloor^2$$
(by the "second" Möbius inversion formula). This leads to a solution of your problem:
$$2^t leqslant n implies #{(a, b) : 1 leqslant a < b leqslant n, gcd(a, b) = 2^t } = frac{psi(lfloor 2^{-t} n rfloor) - 1}{2}.$$
There's an algorithm which computes $psi(n)$ in $mathcal{O}(n^{1+epsilon})$ time and $mathcal{O}(n^{1/2+epsilon})$ space (without computing any values of $mu$). The idea is to use the "blue" formula above recursively (or rather iteratively), noting that there are just $mathcal{O}(sqrt{n})$ different values of $lfloor n/d rfloor$ for $1 leqslant d leqslant n$, which allows to simplify the sum; namely, for any $1 leqslant k leqslant n$,
$$n^2=sum_{d=1}^{n}psileft(leftlfloorfrac{n}{d}rightrfloorright)=sum_{d=1}^{lfloor n/(k+1) rfloor}psileft(leftlfloorfrac{n}{d}rightrfloorright)+sum_{d=1}^{k}psi(d)left(leftlfloorfrac{n}{d}rightrfloor-leftlfloorfrac{n}{d+1}rightrfloorright),$$
and we may put $k=lfloorsqrt{n}rfloor$ here. This recurrence for $psi(n)$ gives the algorithm.
answered Jan 2 at 0:30
metamorphymetamorphy
3,6821621
$endgroup$
$begingroup$
I was just going to ask how do you compute $ psi (n) $ , it will help lots if you can or provide some info
$endgroup$
– Noodle
Jan 2 at 0:38
$begingroup$
How does one compute $mu (d)$
$endgroup$
– Noodle
Jan 2 at 0:45
$begingroup$
The formula for $psi$ with $mu$ is still of use (to show that $displaystylelim_{ntoinfty}frac{psi(n)}{n^2} = frac{6}{pi^2}$ - see comments to the OP).
$endgroup$
– metamorphy
Jan 2 at 1:45
$begingroup$
Does $$psi (n) = n prod_{p|n}(1+frac{1}{p})$$ here ?
$endgroup$
– Noodle
Jan 2 at 2:15
$begingroup$
No, there's no such simple formula here.
$endgroup$
– metamorphy
Jan 2 at 2:21
|
show 2 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%2f3059011%2fcan-i-make-general-formula-for-this-problem%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$
Let $psi(n)=#{(x,y) : 1 leqslant x,y leqslant n, gcd(x, y) = 1}$. Then, for $1 leqslant d leqslant n$,
$$#{(x,y) : 1 leqslant x,y leqslant n, gcd(x, y) = d} = psibig(lfloor n/d rfloorbig),$$
and the union of these sets is just ${(x,y) : 1 leqslant x,y leqslant n}$. This gives
$$color{blue}{sum_{d=1}^{n}psibig(lfloor n/d rfloorbig)=n^2} implies psi(n)=sum_{d=1}^{n}mu(d)lfloor n/d rfloor^2$$
(by the "second" Möbius inversion formula). This leads to a solution of your problem:
$$2^t leqslant n implies #{(a, b) : 1 leqslant a < b leqslant n, gcd(a, b) = 2^t } = frac{psi(lfloor 2^{-t} n rfloor) - 1}{2}.$$
There's an algorithm which computes $psi(n)$ in $mathcal{O}(n^{1+epsilon})$ time and $mathcal{O}(n^{1/2+epsilon})$ space (without computing any values of $mu$). The idea is to use the "blue" formula above recursively (or rather iteratively), noting that there are just $mathcal{O}(sqrt{n})$ different values of $lfloor n/d rfloor$ for $1 leqslant d leqslant n$, which allows to simplify the sum; namely, for any $1 leqslant k leqslant n$,
$$n^2=sum_{d=1}^{n}psileft(leftlfloorfrac{n}{d}rightrfloorright)=sum_{d=1}^{lfloor n/(k+1) rfloor}psileft(leftlfloorfrac{n}{d}rightrfloorright)+sum_{d=1}^{k}psi(d)left(leftlfloorfrac{n}{d}rightrfloor-leftlfloorfrac{n}{d+1}rightrfloorright),$$
and we may put $k=lfloorsqrt{n}rfloor$ here. This recurrence for $psi(n)$ gives the algorithm.
answered Jan 2 at 0:30
metamorphymetamorphy
3,6821621
$endgroup$
$begingroup$
I was just going to ask how do you compute $ psi (n) $ , it will help lots if you can or provide some info
$endgroup$
– Noodle
Jan 2 at 0:38
$begingroup$
How does one compute $mu (d)$
$endgroup$
– Noodle
Jan 2 at 0:45
$begingroup$
The formula for $psi$ with $mu$ is still of use (to show that $displaystylelim_{ntoinfty}frac{psi(n)}{n^2} = frac{6}{pi^2}$ - see comments to the OP).
$endgroup$
– metamorphy
Jan 2 at 1:45
$begingroup$
Does $$psi (n) = n prod_{p|n}(1+frac{1}{p})$$ here ?
$endgroup$
– Noodle
Jan 2 at 2:15
$begingroup$
No, there's no such simple formula here.
$endgroup$
– metamorphy
Jan 2 at 2:21
|
show 2 more comments
$begingroup$
Let $psi(n)=#{(x,y) : 1 leqslant x,y leqslant n, gcd(x, y) = 1}$. Then, for $1 leqslant d leqslant n$,
$$#{(x,y) : 1 leqslant x,y leqslant n, gcd(x, y) = d} = psibig(lfloor n/d rfloorbig),$$
and the union of these sets is just ${(x,y) : 1 leqslant x,y leqslant n}$. This gives
$$color{blue}{sum_{d=1}^{n}psibig(lfloor n/d rfloorbig)=n^2} implies psi(n)=sum_{d=1}^{n}mu(d)lfloor n/d rfloor^2$$
(by the "second" Möbius inversion formula). This leads to a solution of your problem:
$$2^t leqslant n implies #{(a, b) : 1 leqslant a < b leqslant n, gcd(a, b) = 2^t } = frac{psi(lfloor 2^{-t} n rfloor) - 1}{2}.$$
There's an algorithm which computes $psi(n)$ in $mathcal{O}(n^{1+epsilon})$ time and $mathcal{O}(n^{1/2+epsilon})$ space (without computing any values of $mu$). The idea is to use the "blue" formula above recursively (or rather iteratively), noting that there are just $mathcal{O}(sqrt{n})$ different values of $lfloor n/d rfloor$ for $1 leqslant d leqslant n$, which allows to simplify the sum; namely, for any $1 leqslant k leqslant n$,
$$n^2=sum_{d=1}^{n}psileft(leftlfloorfrac{n}{d}rightrfloorright)=sum_{d=1}^{lfloor n/(k+1) rfloor}psileft(leftlfloorfrac{n}{d}rightrfloorright)+sum_{d=1}^{k}psi(d)left(leftlfloorfrac{n}{d}rightrfloor-leftlfloorfrac{n}{d+1}rightrfloorright),$$
and we may put $k=lfloorsqrt{n}rfloor$ here. This recurrence for $psi(n)$ gives the algorithm.
answered Jan 2 at 0:30
metamorphymetamorphy
3,6821621
$endgroup$
$begingroup$
I was just going to ask how do you compute $ psi (n) $ , it will help lots if you can or provide some info
$endgroup$
– Noodle
Jan 2 at 0:38
$begingroup$
How does one compute $mu (d)$
$endgroup$
– Noodle
Jan 2 at 0:45
$begingroup$
The formula for $psi$ with $mu$ is still of use (to show that $displaystylelim_{ntoinfty}frac{psi(n)}{n^2} = frac{6}{pi^2}$ - see comments to the OP).
$endgroup$
– metamorphy
Jan 2 at 1:45
$begingroup$
Does $$psi (n) = n prod_{p|n}(1+frac{1}{p})$$ here ?
$endgroup$
– Noodle
Jan 2 at 2:15
$begingroup$
No, there's no such simple formula here.
$endgroup$
– metamorphy
Jan 2 at 2:21
|
show 2 more comments
$begingroup$
Let $psi(n)=#{(x,y) : 1 leqslant x,y leqslant n, gcd(x, y) = 1}$. Then, for $1 leqslant d leqslant n$,
$$#{(x,y) : 1 leqslant x,y leqslant n, gcd(x, y) = d} = psibig(lfloor n/d rfloorbig),$$
and the union of these sets is just ${(x,y) : 1 leqslant x,y leqslant n}$. This gives
$$color{blue}{sum_{d=1}^{n}psibig(lfloor n/d rfloorbig)=n^2} implies psi(n)=sum_{d=1}^{n}mu(d)lfloor n/d rfloor^2$$
(by the "second" Möbius inversion formula). This leads to a solution of your problem:
$$2^t leqslant n implies #{(a, b) : 1 leqslant a < b leqslant n, gcd(a, b) = 2^t } = frac{psi(lfloor 2^{-t} n rfloor) - 1}{2}.$$
There's an algorithm which computes $psi(n)$ in $mathcal{O}(n^{1+epsilon})$ time and $mathcal{O}(n^{1/2+epsilon})$ space (without computing any values of $mu$). The idea is to use the "blue" formula above recursively (or rather iteratively), noting that there are just $mathcal{O}(sqrt{n})$ different values of $lfloor n/d rfloor$ for $1 leqslant d leqslant n$, which allows to simplify the sum; namely, for any $1 leqslant k leqslant n$,
$$n^2=sum_{d=1}^{n}psileft(leftlfloorfrac{n}{d}rightrfloorright)=sum_{d=1}^{lfloor n/(k+1) rfloor}psileft(leftlfloorfrac{n}{d}rightrfloorright)+sum_{d=1}^{k}psi(d)left(leftlfloorfrac{n}{d}rightrfloor-leftlfloorfrac{n}{d+1}rightrfloorright),$$
and we may put $k=lfloorsqrt{n}rfloor$ here. This recurrence for $psi(n)$ gives the algorithm.
answered Jan 2 at 0:30
metamorphymetamorphy
3,6821621
$endgroup$
Let $psi(n)=#{(x,y) : 1 leqslant x,y leqslant n, gcd(x, y) = 1}$. Then, for $1 leqslant d leqslant n$,
$$#{(x,y) : 1 leqslant x,y leqslant n, gcd(x, y) = d} = psibig(lfloor n/d rfloorbig),$$
and the union of these sets is just ${(x,y) : 1 leqslant x,y leqslant n}$. This gives
$$color{blue}{sum_{d=1}^{n}psibig(lfloor n/d rfloorbig)=n^2} implies psi(n)=sum_{d=1}^{n}mu(d)lfloor n/d rfloor^2$$
(by the "second" Möbius inversion formula). This leads to a solution of your problem:
$$2^t leqslant n implies #{(a, b) : 1 leqslant a < b leqslant n, gcd(a, b) = 2^t } = frac{psi(lfloor 2^{-t} n rfloor) - 1}{2}.$$
There's an algorithm which computes $psi(n)$ in $mathcal{O}(n^{1+epsilon})$ time and $mathcal{O}(n^{1/2+epsilon})$ space (without computing any values of $mu$). The idea is to use the "blue" formula above recursively (or rather iteratively), noting that there are just $mathcal{O}(sqrt{n})$ different values of $lfloor n/d rfloor$ for $1 leqslant d leqslant n$, which allows to simplify the sum; namely, for any $1 leqslant k leqslant n$,
$$n^2=sum_{d=1}^{n}psileft(leftlfloorfrac{n}{d}rightrfloorright)=sum_{d=1}^{lfloor n/(k+1) rfloor}psileft(leftlfloorfrac{n}{d}rightrfloorright)+sum_{d=1}^{k}psi(d)left(leftlfloorfrac{n}{d}rightrfloor-leftlfloorfrac{n}{d+1}rightrfloorright),$$
and we may put $k=lfloorsqrt{n}rfloor$ here. This recurrence for $psi(n)$ gives the algorithm.
answered Jan 2 at 0:30
metamorphymetamorphy
3,6821621
edited Jan 2 at 3:19
answered Jan 2 at 0:30
metamorphymetamorphy
3,6821621
answered Jan 2 at 0:30
metamorphymetamorphy
3,6821621
answered Jan 2 at 0:30
metamorphymetamorphy
3,6821621
3,6821621
$begingroup$
I was just going to ask how do you compute $ psi (n) $ , it will help lots if you can or provide some info
$endgroup$
– Noodle
Jan 2 at 0:38
$begingroup$
How does one compute $mu (d)$
$endgroup$
– Noodle
Jan 2 at 0:45
$begingroup$
The formula for $psi$ with $mu$ is still of use (to show that $displaystylelim_{ntoinfty}frac{psi(n)}{n^2} = frac{6}{pi^2}$ - see comments to the OP).
$endgroup$
– metamorphy
Jan 2 at 1:45
$begingroup$
Does $$psi (n) = n prod_{p|n}(1+frac{1}{p})$$ here ?
$endgroup$
– Noodle
Jan 2 at 2:15
$begingroup$
No, there's no such simple formula here.
$endgroup$
– metamorphy
Jan 2 at 2:21
|
show 2 more comments
$begingroup$
I was just going to ask how do you compute $ psi (n) $ , it will help lots if you can or provide some info
$endgroup$
– Noodle
Jan 2 at 0:38
$begingroup$
How does one compute $mu (d)$
$endgroup$
– Noodle
Jan 2 at 0:45
$begingroup$
The formula for $psi$ with $mu$ is still of use (to show that $displaystylelim_{ntoinfty}frac{psi(n)}{n^2} = frac{6}{pi^2}$ - see comments to the OP).
$endgroup$
– metamorphy
Jan 2 at 1:45
$begingroup$
Does $$psi (n) = n prod_{p|n}(1+frac{1}{p})$$ here ?
$endgroup$
– Noodle
Jan 2 at 2:15
$begingroup$
No, there's no such simple formula here.
$endgroup$
– metamorphy
Jan 2 at 2:21
$begingroup$
I was just going to ask how do you compute $ psi (n) $ , it will help lots if you can or provide some info
$endgroup$
– Noodle
Jan 2 at 0:38
$begingroup$
I was just going to ask how do you compute $ psi (n) $ , it will help lots if you can or provide some info
$endgroup$
– Noodle
Jan 2 at 0:38
$begingroup$
How does one compute $mu (d)$
$endgroup$
– Noodle
Jan 2 at 0:45
$begingroup$
How does one compute $mu (d)$
$endgroup$
– Noodle
Jan 2 at 0:45
$begingroup$
The formula for $psi$ with $mu$ is still of use (to show that $displaystylelim_{ntoinfty}frac{psi(n)}{n^2} = frac{6}{pi^2}$ - see comments to the OP).
$endgroup$
– metamorphy
Jan 2 at 1:45
$begingroup$
The formula for $psi$ with $mu$ is still of use (to show that $displaystylelim_{ntoinfty}frac{psi(n)}{n^2} = frac{6}{pi^2}$ - see comments to the OP).
$endgroup$
– metamorphy
Jan 2 at 1:45
$begingroup$
Does $$psi (n) = n prod_{p|n}(1+frac{1}{p})$$ here ?
$endgroup$
– Noodle
Jan 2 at 2:15
$begingroup$
Does $$psi (n) = n prod_{p|n}(1+frac{1}{p})$$ here ?
$endgroup$
– Noodle
Jan 2 at 2:15
$begingroup$
No, there's no such simple formula here.
$endgroup$
– metamorphy
Jan 2 at 2:21
$begingroup$
No, there's no such simple formula here.
$endgroup$
– metamorphy
Jan 2 at 2:21
|
show 2 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%2f3059011%2fcan-i-make-general-formula-for-this-problem%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$
Is an asymptotic answer sufficient? It's not too hard to figure out that, if $f(n)$ is the number of such pairs, then $lim_{nrightarrowinfty}frac{f(n)}{n^2}$ is positive and finite (and it's not even so hard to compute this constant). I don't see how one would get an exact answer for all $n$ though without considerable computation.
$endgroup$
– Milo Brandt
Jan 2 at 0:10
$begingroup$
that is the main problem here, for $n = 10^{6} $ , with brute force it takes about 3-4 hours to compute them , if its not possible for a general formula to be made maybe decreasing the search space will help but this of course requires more properties for such pairs
$endgroup$
– Noodle
Jan 2 at 0:15