Is there an explicit function mapping $2^n+2^m$ to $(n,m)$?
$begingroup$
We know that the number $2^n+2^m$ is unique for $n,minmathbb{N}$. Is there any explicit way of writing a function $sigma:mathbb{N}tomathbb{N}^2$ such that
$$
sigma(2^n+2^m)=(n,m),
$$
for all $n,minmathbb{N}$?
Remark (edit): Here, $(n,m)$ is to be interpreted as the unordered pair ${n,m}$, since I'm only interested in the pair. More specifically, I want to find functions $sigma,f$ and $g$ such that
$$
sigma(k)=(g(k),f(k)),
$$
where $k=2^{g(k)}+2^{f(k)}$, $forall k inmathbb{N}$.
elementary-number-theory functions
$endgroup$
add a comment |
$begingroup$
We know that the number $2^n+2^m$ is unique for $n,minmathbb{N}$. Is there any explicit way of writing a function $sigma:mathbb{N}tomathbb{N}^2$ such that
$$
sigma(2^n+2^m)=(n,m),
$$
for all $n,minmathbb{N}$?
Remark (edit): Here, $(n,m)$ is to be interpreted as the unordered pair ${n,m}$, since I'm only interested in the pair. More specifically, I want to find functions $sigma,f$ and $g$ such that
$$
sigma(k)=(g(k),f(k)),
$$
where $k=2^{g(k)}+2^{f(k)}$, $forall k inmathbb{N}$.
elementary-number-theory functions
$endgroup$
4
$begingroup$
Such a function can't be well defined, otherwise you would have $sigma(2^n+2^m) = (n,m)=(m,n)$. But in $mathbb{N}^2$, you don't identify $(n,m)$ and $(m,n)$... The image of $sigma$ should be the set of parts of $mathbb{N}$ with two elements.
$endgroup$
– TheSilverDoe
7 hours ago
$begingroup$
You're right! I'm more interested in the unordered pair. How may I change my question to be more accurate w.r.t. this?
$endgroup$
– sam wolfe
7 hours ago
$begingroup$
You can write $sigma(2^n + 2^m) = (n,m) text{ or } (m,n)$ maybe.
$endgroup$
– TheSilverDoe
7 hours ago
$begingroup$
You could write $sigma(2^n+2^m)={n,m}$. But I'm not sure I understand what your goal is. What you have there is already an eminently explicit and understandable definition of your function -- you may just need to specify explicitly what $sigma$ does to numbers not of the form $2^n+2^m$. Unless you have extremely specific and concrete requirements to meet, any attempt to make it look "more symbolic" will just succeed in making the definition harder to understand. For which purpose would you want that?
$endgroup$
– Henning Makholm
7 hours ago
$begingroup$
I want a way of recovering the unique integers pair via an explicitly constructible bijection. Please check the edit I made
$endgroup$
– sam wolfe
7 hours ago
add a comment |
$begingroup$
We know that the number $2^n+2^m$ is unique for $n,minmathbb{N}$. Is there any explicit way of writing a function $sigma:mathbb{N}tomathbb{N}^2$ such that
$$
sigma(2^n+2^m)=(n,m),
$$
for all $n,minmathbb{N}$?
Remark (edit): Here, $(n,m)$ is to be interpreted as the unordered pair ${n,m}$, since I'm only interested in the pair. More specifically, I want to find functions $sigma,f$ and $g$ such that
$$
sigma(k)=(g(k),f(k)),
$$
where $k=2^{g(k)}+2^{f(k)}$, $forall k inmathbb{N}$.
elementary-number-theory functions
$endgroup$
We know that the number $2^n+2^m$ is unique for $n,minmathbb{N}$. Is there any explicit way of writing a function $sigma:mathbb{N}tomathbb{N}^2$ such that
$$
sigma(2^n+2^m)=(n,m),
$$
for all $n,minmathbb{N}$?
Remark (edit): Here, $(n,m)$ is to be interpreted as the unordered pair ${n,m}$, since I'm only interested in the pair. More specifically, I want to find functions $sigma,f$ and $g$ such that
$$
sigma(k)=(g(k),f(k)),
$$
where $k=2^{g(k)}+2^{f(k)}$, $forall k inmathbb{N}$.
elementary-number-theory functions
elementary-number-theory functions
edited 5 hours ago
Asaf Karagila♦
306k33438769
306k33438769
asked 7 hours ago
sam wolfesam wolfe
793525
793525
4
$begingroup$
Such a function can't be well defined, otherwise you would have $sigma(2^n+2^m) = (n,m)=(m,n)$. But in $mathbb{N}^2$, you don't identify $(n,m)$ and $(m,n)$... The image of $sigma$ should be the set of parts of $mathbb{N}$ with two elements.
$endgroup$
– TheSilverDoe
7 hours ago
$begingroup$
You're right! I'm more interested in the unordered pair. How may I change my question to be more accurate w.r.t. this?
$endgroup$
– sam wolfe
7 hours ago
$begingroup$
You can write $sigma(2^n + 2^m) = (n,m) text{ or } (m,n)$ maybe.
$endgroup$
– TheSilverDoe
7 hours ago
$begingroup$
You could write $sigma(2^n+2^m)={n,m}$. But I'm not sure I understand what your goal is. What you have there is already an eminently explicit and understandable definition of your function -- you may just need to specify explicitly what $sigma$ does to numbers not of the form $2^n+2^m$. Unless you have extremely specific and concrete requirements to meet, any attempt to make it look "more symbolic" will just succeed in making the definition harder to understand. For which purpose would you want that?
$endgroup$
– Henning Makholm
7 hours ago
$begingroup$
I want a way of recovering the unique integers pair via an explicitly constructible bijection. Please check the edit I made
$endgroup$
– sam wolfe
7 hours ago
add a comment |
4
$begingroup$
Such a function can't be well defined, otherwise you would have $sigma(2^n+2^m) = (n,m)=(m,n)$. But in $mathbb{N}^2$, you don't identify $(n,m)$ and $(m,n)$... The image of $sigma$ should be the set of parts of $mathbb{N}$ with two elements.
$endgroup$
– TheSilverDoe
7 hours ago
$begingroup$
You're right! I'm more interested in the unordered pair. How may I change my question to be more accurate w.r.t. this?
$endgroup$
– sam wolfe
7 hours ago
$begingroup$
You can write $sigma(2^n + 2^m) = (n,m) text{ or } (m,n)$ maybe.
$endgroup$
– TheSilverDoe
7 hours ago
$begingroup$
You could write $sigma(2^n+2^m)={n,m}$. But I'm not sure I understand what your goal is. What you have there is already an eminently explicit and understandable definition of your function -- you may just need to specify explicitly what $sigma$ does to numbers not of the form $2^n+2^m$. Unless you have extremely specific and concrete requirements to meet, any attempt to make it look "more symbolic" will just succeed in making the definition harder to understand. For which purpose would you want that?
$endgroup$
– Henning Makholm
7 hours ago
$begingroup$
I want a way of recovering the unique integers pair via an explicitly constructible bijection. Please check the edit I made
$endgroup$
– sam wolfe
7 hours ago
4
4
$begingroup$
Such a function can't be well defined, otherwise you would have $sigma(2^n+2^m) = (n,m)=(m,n)$. But in $mathbb{N}^2$, you don't identify $(n,m)$ and $(m,n)$... The image of $sigma$ should be the set of parts of $mathbb{N}$ with two elements.
$endgroup$
– TheSilverDoe
7 hours ago
$begingroup$
Such a function can't be well defined, otherwise you would have $sigma(2^n+2^m) = (n,m)=(m,n)$. But in $mathbb{N}^2$, you don't identify $(n,m)$ and $(m,n)$... The image of $sigma$ should be the set of parts of $mathbb{N}$ with two elements.
$endgroup$
– TheSilverDoe
7 hours ago
$begingroup$
You're right! I'm more interested in the unordered pair. How may I change my question to be more accurate w.r.t. this?
$endgroup$
– sam wolfe
7 hours ago
$begingroup$
You're right! I'm more interested in the unordered pair. How may I change my question to be more accurate w.r.t. this?
$endgroup$
– sam wolfe
7 hours ago
$begingroup$
You can write $sigma(2^n + 2^m) = (n,m) text{ or } (m,n)$ maybe.
$endgroup$
– TheSilverDoe
7 hours ago
$begingroup$
You can write $sigma(2^n + 2^m) = (n,m) text{ or } (m,n)$ maybe.
$endgroup$
– TheSilverDoe
7 hours ago
$begingroup$
You could write $sigma(2^n+2^m)={n,m}$. But I'm not sure I understand what your goal is. What you have there is already an eminently explicit and understandable definition of your function -- you may just need to specify explicitly what $sigma$ does to numbers not of the form $2^n+2^m$. Unless you have extremely specific and concrete requirements to meet, any attempt to make it look "more symbolic" will just succeed in making the definition harder to understand. For which purpose would you want that?
$endgroup$
– Henning Makholm
7 hours ago
$begingroup$
You could write $sigma(2^n+2^m)={n,m}$. But I'm not sure I understand what your goal is. What you have there is already an eminently explicit and understandable definition of your function -- you may just need to specify explicitly what $sigma$ does to numbers not of the form $2^n+2^m$. Unless you have extremely specific and concrete requirements to meet, any attempt to make it look "more symbolic" will just succeed in making the definition harder to understand. For which purpose would you want that?
$endgroup$
– Henning Makholm
7 hours ago
$begingroup$
I want a way of recovering the unique integers pair via an explicitly constructible bijection. Please check the edit I made
$endgroup$
– sam wolfe
7 hours ago
$begingroup$
I want a way of recovering the unique integers pair via an explicitly constructible bijection. Please check the edit I made
$endgroup$
– sam wolfe
7 hours ago
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
What do you think of
$$forall k in mathbb{N}, quad sigma(k)=left( lfloor log_2(k) rfloor, lfloor log_2 left( k-2^{lfloor log_2(k) rfloor} right)rfloor right)$$
This is well defined except when $k$ is a power of $2$.
In the other case where $k=2^p$, choose $sigma(k)=(p-1,p-1)$.
$endgroup$
2
$begingroup$
(+1) Looks like you had the idea first. It's hacky but it works.
$endgroup$
– 6005
7 hours ago
$begingroup$
I was a bit confused about the $lfloor log_2(k) rfloor$ choice, but I now understand that this actually picks the highest power between $n$ and $m$, thus the problem with $k=2^p$. Thank you!
$endgroup$
– sam wolfe
7 hours ago
$begingroup$
@samwolfe you got it ;)
$endgroup$
– TheSilverDoe
7 hours ago
add a comment |
$begingroup$
We have to relax your requirement a bit due to the comment by TheSilverDoe. So we require that for all $boldsymbol{m ge n ge 0}$, $sigma(2^m + 2^n) = (m, n)$.
Then this is possible. First define
$$
tau(x) := lceil log_2(x) rceil - 1,
$$
for example, $tau(2) = 0$, $tau(3) = tau(4) = 1$, $tau(5) = 2$, etc.
Then, define
$$
sigma(x) := Big(tau(x), tau left( 1 + x - 2^{tau(x)} right) Big).
$$
How it works:
$tau(x)$ is the exponent in the largest power of $2$ smaller than $x$; that is, if $2^k < x le 2^{k+1}$, then $tau(x) = k$.
For any $m ge n ge 0$, we know that $2^m < 2^m + 2^n le 2^{m+1}$. Therefore, $tau(2^m + 2^n) = m$.
So for $x = 2^m + 2^n$, we get $tau(x) = m$. Then, $1 + x - 2^{tau(x)} = 1 + (2^m + 2^n) - 2^n = 2^m + 1$, and the largest power of $2$ smaller than $2^m + 1$ is $2^m$. Thus,
$$tau(1 + x - 2^{tau(x)}) = n,$$
so
$$
sigma(x) = (m,n).
$$
Remark:
It seems likely that there will be no way to get a function $sigma$ that does not use floor functions or similar tricks. Some evidence for this is that there is no function on real numbers that satisfies $sigma(2^x + 2^y) = (x,y)$.
$endgroup$
$begingroup$
Yes, I understood my question was initially not so well posed. Thanks for the edit and the explanation, helped me to better understand TheSilverDoe's answer.
$endgroup$
– sam wolfe
6 hours ago
add a comment |
$begingroup$
If you just want to define your functions, and you're writing for an audience of human readers, I would strongly recommend writing simply:
Define the functions $f$ and $g$ such that for all $ale b$ it holds that
$$f(2^a+2^b)=a qquad g(2^a+2^b)=b $$
and for any number $n$ that is not of the form $2^a+2^b$, we have $f(n)=g(n)=0$.
These conditions obviously define $f$ and $g$ uniquely.
This is much easier to understand, and will give the reader a much clearer intuition about what on earth you're doing, than to try to avoid using English words. (Deliberately attempting to avoid English words in definition almost leads to bad mathematical exposition).
If you're writing not for a human audience, then what you should write depends crucially on what the non-human audience will understand.
In particular, if you're trying to program a computer to implement appropriate $f$ and $g$ for you, you should not be looking for algebraic expressions at all. Rather, exploit the fact that there are operations that work for this built right into modern CPUs. On x86/x64 processors they're implemented by the BSF
and BSR
instructions. Some programming languages expose them fairly directly, such as Long.numberOfLeadingZeros(n)
and Long.numberOfTrailingZeros(n)
in Java -- you need just a bit of trivial arithmetic to convert the result of the former of these to the representation you want.
$endgroup$
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%2f3145419%2fis-there-an-explicit-function-mapping-2n2m-to-n-m%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
What do you think of
$$forall k in mathbb{N}, quad sigma(k)=left( lfloor log_2(k) rfloor, lfloor log_2 left( k-2^{lfloor log_2(k) rfloor} right)rfloor right)$$
This is well defined except when $k$ is a power of $2$.
In the other case where $k=2^p$, choose $sigma(k)=(p-1,p-1)$.
$endgroup$
2
$begingroup$
(+1) Looks like you had the idea first. It's hacky but it works.
$endgroup$
– 6005
7 hours ago
$begingroup$
I was a bit confused about the $lfloor log_2(k) rfloor$ choice, but I now understand that this actually picks the highest power between $n$ and $m$, thus the problem with $k=2^p$. Thank you!
$endgroup$
– sam wolfe
7 hours ago
$begingroup$
@samwolfe you got it ;)
$endgroup$
– TheSilverDoe
7 hours ago
add a comment |
$begingroup$
What do you think of
$$forall k in mathbb{N}, quad sigma(k)=left( lfloor log_2(k) rfloor, lfloor log_2 left( k-2^{lfloor log_2(k) rfloor} right)rfloor right)$$
This is well defined except when $k$ is a power of $2$.
In the other case where $k=2^p$, choose $sigma(k)=(p-1,p-1)$.
$endgroup$
2
$begingroup$
(+1) Looks like you had the idea first. It's hacky but it works.
$endgroup$
– 6005
7 hours ago
$begingroup$
I was a bit confused about the $lfloor log_2(k) rfloor$ choice, but I now understand that this actually picks the highest power between $n$ and $m$, thus the problem with $k=2^p$. Thank you!
$endgroup$
– sam wolfe
7 hours ago
$begingroup$
@samwolfe you got it ;)
$endgroup$
– TheSilverDoe
7 hours ago
add a comment |
$begingroup$
What do you think of
$$forall k in mathbb{N}, quad sigma(k)=left( lfloor log_2(k) rfloor, lfloor log_2 left( k-2^{lfloor log_2(k) rfloor} right)rfloor right)$$
This is well defined except when $k$ is a power of $2$.
In the other case where $k=2^p$, choose $sigma(k)=(p-1,p-1)$.
$endgroup$
What do you think of
$$forall k in mathbb{N}, quad sigma(k)=left( lfloor log_2(k) rfloor, lfloor log_2 left( k-2^{lfloor log_2(k) rfloor} right)rfloor right)$$
This is well defined except when $k$ is a power of $2$.
In the other case where $k=2^p$, choose $sigma(k)=(p-1,p-1)$.
edited 7 hours ago
answered 7 hours ago
TheSilverDoeTheSilverDoe
3,794112
3,794112
2
$begingroup$
(+1) Looks like you had the idea first. It's hacky but it works.
$endgroup$
– 6005
7 hours ago
$begingroup$
I was a bit confused about the $lfloor log_2(k) rfloor$ choice, but I now understand that this actually picks the highest power between $n$ and $m$, thus the problem with $k=2^p$. Thank you!
$endgroup$
– sam wolfe
7 hours ago
$begingroup$
@samwolfe you got it ;)
$endgroup$
– TheSilverDoe
7 hours ago
add a comment |
2
$begingroup$
(+1) Looks like you had the idea first. It's hacky but it works.
$endgroup$
– 6005
7 hours ago
$begingroup$
I was a bit confused about the $lfloor log_2(k) rfloor$ choice, but I now understand that this actually picks the highest power between $n$ and $m$, thus the problem with $k=2^p$. Thank you!
$endgroup$
– sam wolfe
7 hours ago
$begingroup$
@samwolfe you got it ;)
$endgroup$
– TheSilverDoe
7 hours ago
2
2
$begingroup$
(+1) Looks like you had the idea first. It's hacky but it works.
$endgroup$
– 6005
7 hours ago
$begingroup$
(+1) Looks like you had the idea first. It's hacky but it works.
$endgroup$
– 6005
7 hours ago
$begingroup$
I was a bit confused about the $lfloor log_2(k) rfloor$ choice, but I now understand that this actually picks the highest power between $n$ and $m$, thus the problem with $k=2^p$. Thank you!
$endgroup$
– sam wolfe
7 hours ago
$begingroup$
I was a bit confused about the $lfloor log_2(k) rfloor$ choice, but I now understand that this actually picks the highest power between $n$ and $m$, thus the problem with $k=2^p$. Thank you!
$endgroup$
– sam wolfe
7 hours ago
$begingroup$
@samwolfe you got it ;)
$endgroup$
– TheSilverDoe
7 hours ago
$begingroup$
@samwolfe you got it ;)
$endgroup$
– TheSilverDoe
7 hours ago
add a comment |
$begingroup$
We have to relax your requirement a bit due to the comment by TheSilverDoe. So we require that for all $boldsymbol{m ge n ge 0}$, $sigma(2^m + 2^n) = (m, n)$.
Then this is possible. First define
$$
tau(x) := lceil log_2(x) rceil - 1,
$$
for example, $tau(2) = 0$, $tau(3) = tau(4) = 1$, $tau(5) = 2$, etc.
Then, define
$$
sigma(x) := Big(tau(x), tau left( 1 + x - 2^{tau(x)} right) Big).
$$
How it works:
$tau(x)$ is the exponent in the largest power of $2$ smaller than $x$; that is, if $2^k < x le 2^{k+1}$, then $tau(x) = k$.
For any $m ge n ge 0$, we know that $2^m < 2^m + 2^n le 2^{m+1}$. Therefore, $tau(2^m + 2^n) = m$.
So for $x = 2^m + 2^n$, we get $tau(x) = m$. Then, $1 + x - 2^{tau(x)} = 1 + (2^m + 2^n) - 2^n = 2^m + 1$, and the largest power of $2$ smaller than $2^m + 1$ is $2^m$. Thus,
$$tau(1 + x - 2^{tau(x)}) = n,$$
so
$$
sigma(x) = (m,n).
$$
Remark:
It seems likely that there will be no way to get a function $sigma$ that does not use floor functions or similar tricks. Some evidence for this is that there is no function on real numbers that satisfies $sigma(2^x + 2^y) = (x,y)$.
$endgroup$
$begingroup$
Yes, I understood my question was initially not so well posed. Thanks for the edit and the explanation, helped me to better understand TheSilverDoe's answer.
$endgroup$
– sam wolfe
6 hours ago
add a comment |
$begingroup$
We have to relax your requirement a bit due to the comment by TheSilverDoe. So we require that for all $boldsymbol{m ge n ge 0}$, $sigma(2^m + 2^n) = (m, n)$.
Then this is possible. First define
$$
tau(x) := lceil log_2(x) rceil - 1,
$$
for example, $tau(2) = 0$, $tau(3) = tau(4) = 1$, $tau(5) = 2$, etc.
Then, define
$$
sigma(x) := Big(tau(x), tau left( 1 + x - 2^{tau(x)} right) Big).
$$
How it works:
$tau(x)$ is the exponent in the largest power of $2$ smaller than $x$; that is, if $2^k < x le 2^{k+1}$, then $tau(x) = k$.
For any $m ge n ge 0$, we know that $2^m < 2^m + 2^n le 2^{m+1}$. Therefore, $tau(2^m + 2^n) = m$.
So for $x = 2^m + 2^n$, we get $tau(x) = m$. Then, $1 + x - 2^{tau(x)} = 1 + (2^m + 2^n) - 2^n = 2^m + 1$, and the largest power of $2$ smaller than $2^m + 1$ is $2^m$. Thus,
$$tau(1 + x - 2^{tau(x)}) = n,$$
so
$$
sigma(x) = (m,n).
$$
Remark:
It seems likely that there will be no way to get a function $sigma$ that does not use floor functions or similar tricks. Some evidence for this is that there is no function on real numbers that satisfies $sigma(2^x + 2^y) = (x,y)$.
$endgroup$
$begingroup$
Yes, I understood my question was initially not so well posed. Thanks for the edit and the explanation, helped me to better understand TheSilverDoe's answer.
$endgroup$
– sam wolfe
6 hours ago
add a comment |
$begingroup$
We have to relax your requirement a bit due to the comment by TheSilverDoe. So we require that for all $boldsymbol{m ge n ge 0}$, $sigma(2^m + 2^n) = (m, n)$.
Then this is possible. First define
$$
tau(x) := lceil log_2(x) rceil - 1,
$$
for example, $tau(2) = 0$, $tau(3) = tau(4) = 1$, $tau(5) = 2$, etc.
Then, define
$$
sigma(x) := Big(tau(x), tau left( 1 + x - 2^{tau(x)} right) Big).
$$
How it works:
$tau(x)$ is the exponent in the largest power of $2$ smaller than $x$; that is, if $2^k < x le 2^{k+1}$, then $tau(x) = k$.
For any $m ge n ge 0$, we know that $2^m < 2^m + 2^n le 2^{m+1}$. Therefore, $tau(2^m + 2^n) = m$.
So for $x = 2^m + 2^n$, we get $tau(x) = m$. Then, $1 + x - 2^{tau(x)} = 1 + (2^m + 2^n) - 2^n = 2^m + 1$, and the largest power of $2$ smaller than $2^m + 1$ is $2^m$. Thus,
$$tau(1 + x - 2^{tau(x)}) = n,$$
so
$$
sigma(x) = (m,n).
$$
Remark:
It seems likely that there will be no way to get a function $sigma$ that does not use floor functions or similar tricks. Some evidence for this is that there is no function on real numbers that satisfies $sigma(2^x + 2^y) = (x,y)$.
$endgroup$
We have to relax your requirement a bit due to the comment by TheSilverDoe. So we require that for all $boldsymbol{m ge n ge 0}$, $sigma(2^m + 2^n) = (m, n)$.
Then this is possible. First define
$$
tau(x) := lceil log_2(x) rceil - 1,
$$
for example, $tau(2) = 0$, $tau(3) = tau(4) = 1$, $tau(5) = 2$, etc.
Then, define
$$
sigma(x) := Big(tau(x), tau left( 1 + x - 2^{tau(x)} right) Big).
$$
How it works:
$tau(x)$ is the exponent in the largest power of $2$ smaller than $x$; that is, if $2^k < x le 2^{k+1}$, then $tau(x) = k$.
For any $m ge n ge 0$, we know that $2^m < 2^m + 2^n le 2^{m+1}$. Therefore, $tau(2^m + 2^n) = m$.
So for $x = 2^m + 2^n$, we get $tau(x) = m$. Then, $1 + x - 2^{tau(x)} = 1 + (2^m + 2^n) - 2^n = 2^m + 1$, and the largest power of $2$ smaller than $2^m + 1$ is $2^m$. Thus,
$$tau(1 + x - 2^{tau(x)}) = n,$$
so
$$
sigma(x) = (m,n).
$$
Remark:
It seems likely that there will be no way to get a function $sigma$ that does not use floor functions or similar tricks. Some evidence for this is that there is no function on real numbers that satisfies $sigma(2^x + 2^y) = (x,y)$.
answered 7 hours ago
60056005
36.7k751126
36.7k751126
$begingroup$
Yes, I understood my question was initially not so well posed. Thanks for the edit and the explanation, helped me to better understand TheSilverDoe's answer.
$endgroup$
– sam wolfe
6 hours ago
add a comment |
$begingroup$
Yes, I understood my question was initially not so well posed. Thanks for the edit and the explanation, helped me to better understand TheSilverDoe's answer.
$endgroup$
– sam wolfe
6 hours ago
$begingroup$
Yes, I understood my question was initially not so well posed. Thanks for the edit and the explanation, helped me to better understand TheSilverDoe's answer.
$endgroup$
– sam wolfe
6 hours ago
$begingroup$
Yes, I understood my question was initially not so well posed. Thanks for the edit and the explanation, helped me to better understand TheSilverDoe's answer.
$endgroup$
– sam wolfe
6 hours ago
add a comment |
$begingroup$
If you just want to define your functions, and you're writing for an audience of human readers, I would strongly recommend writing simply:
Define the functions $f$ and $g$ such that for all $ale b$ it holds that
$$f(2^a+2^b)=a qquad g(2^a+2^b)=b $$
and for any number $n$ that is not of the form $2^a+2^b$, we have $f(n)=g(n)=0$.
These conditions obviously define $f$ and $g$ uniquely.
This is much easier to understand, and will give the reader a much clearer intuition about what on earth you're doing, than to try to avoid using English words. (Deliberately attempting to avoid English words in definition almost leads to bad mathematical exposition).
If you're writing not for a human audience, then what you should write depends crucially on what the non-human audience will understand.
In particular, if you're trying to program a computer to implement appropriate $f$ and $g$ for you, you should not be looking for algebraic expressions at all. Rather, exploit the fact that there are operations that work for this built right into modern CPUs. On x86/x64 processors they're implemented by the BSF
and BSR
instructions. Some programming languages expose them fairly directly, such as Long.numberOfLeadingZeros(n)
and Long.numberOfTrailingZeros(n)
in Java -- you need just a bit of trivial arithmetic to convert the result of the former of these to the representation you want.
$endgroup$
add a comment |
$begingroup$
If you just want to define your functions, and you're writing for an audience of human readers, I would strongly recommend writing simply:
Define the functions $f$ and $g$ such that for all $ale b$ it holds that
$$f(2^a+2^b)=a qquad g(2^a+2^b)=b $$
and for any number $n$ that is not of the form $2^a+2^b$, we have $f(n)=g(n)=0$.
These conditions obviously define $f$ and $g$ uniquely.
This is much easier to understand, and will give the reader a much clearer intuition about what on earth you're doing, than to try to avoid using English words. (Deliberately attempting to avoid English words in definition almost leads to bad mathematical exposition).
If you're writing not for a human audience, then what you should write depends crucially on what the non-human audience will understand.
In particular, if you're trying to program a computer to implement appropriate $f$ and $g$ for you, you should not be looking for algebraic expressions at all. Rather, exploit the fact that there are operations that work for this built right into modern CPUs. On x86/x64 processors they're implemented by the BSF
and BSR
instructions. Some programming languages expose them fairly directly, such as Long.numberOfLeadingZeros(n)
and Long.numberOfTrailingZeros(n)
in Java -- you need just a bit of trivial arithmetic to convert the result of the former of these to the representation you want.
$endgroup$
add a comment |
$begingroup$
If you just want to define your functions, and you're writing for an audience of human readers, I would strongly recommend writing simply:
Define the functions $f$ and $g$ such that for all $ale b$ it holds that
$$f(2^a+2^b)=a qquad g(2^a+2^b)=b $$
and for any number $n$ that is not of the form $2^a+2^b$, we have $f(n)=g(n)=0$.
These conditions obviously define $f$ and $g$ uniquely.
This is much easier to understand, and will give the reader a much clearer intuition about what on earth you're doing, than to try to avoid using English words. (Deliberately attempting to avoid English words in definition almost leads to bad mathematical exposition).
If you're writing not for a human audience, then what you should write depends crucially on what the non-human audience will understand.
In particular, if you're trying to program a computer to implement appropriate $f$ and $g$ for you, you should not be looking for algebraic expressions at all. Rather, exploit the fact that there are operations that work for this built right into modern CPUs. On x86/x64 processors they're implemented by the BSF
and BSR
instructions. Some programming languages expose them fairly directly, such as Long.numberOfLeadingZeros(n)
and Long.numberOfTrailingZeros(n)
in Java -- you need just a bit of trivial arithmetic to convert the result of the former of these to the representation you want.
$endgroup$
If you just want to define your functions, and you're writing for an audience of human readers, I would strongly recommend writing simply:
Define the functions $f$ and $g$ such that for all $ale b$ it holds that
$$f(2^a+2^b)=a qquad g(2^a+2^b)=b $$
and for any number $n$ that is not of the form $2^a+2^b$, we have $f(n)=g(n)=0$.
These conditions obviously define $f$ and $g$ uniquely.
This is much easier to understand, and will give the reader a much clearer intuition about what on earth you're doing, than to try to avoid using English words. (Deliberately attempting to avoid English words in definition almost leads to bad mathematical exposition).
If you're writing not for a human audience, then what you should write depends crucially on what the non-human audience will understand.
In particular, if you're trying to program a computer to implement appropriate $f$ and $g$ for you, you should not be looking for algebraic expressions at all. Rather, exploit the fact that there are operations that work for this built right into modern CPUs. On x86/x64 processors they're implemented by the BSF
and BSR
instructions. Some programming languages expose them fairly directly, such as Long.numberOfLeadingZeros(n)
and Long.numberOfTrailingZeros(n)
in Java -- you need just a bit of trivial arithmetic to convert the result of the former of these to the representation you want.
answered 7 hours ago
Henning MakholmHenning Makholm
242k17308549
242k17308549
add a comment |
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%2f3145419%2fis-there-an-explicit-function-mapping-2n2m-to-n-m%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
4
$begingroup$
Such a function can't be well defined, otherwise you would have $sigma(2^n+2^m) = (n,m)=(m,n)$. But in $mathbb{N}^2$, you don't identify $(n,m)$ and $(m,n)$... The image of $sigma$ should be the set of parts of $mathbb{N}$ with two elements.
$endgroup$
– TheSilverDoe
7 hours ago
$begingroup$
You're right! I'm more interested in the unordered pair. How may I change my question to be more accurate w.r.t. this?
$endgroup$
– sam wolfe
7 hours ago
$begingroup$
You can write $sigma(2^n + 2^m) = (n,m) text{ or } (m,n)$ maybe.
$endgroup$
– TheSilverDoe
7 hours ago
$begingroup$
You could write $sigma(2^n+2^m)={n,m}$. But I'm not sure I understand what your goal is. What you have there is already an eminently explicit and understandable definition of your function -- you may just need to specify explicitly what $sigma$ does to numbers not of the form $2^n+2^m$. Unless you have extremely specific and concrete requirements to meet, any attempt to make it look "more symbolic" will just succeed in making the definition harder to understand. For which purpose would you want that?
$endgroup$
– Henning Makholm
7 hours ago
$begingroup$
I want a way of recovering the unique integers pair via an explicitly constructible bijection. Please check the edit I made
$endgroup$
– sam wolfe
7 hours ago