Is there an explicit function mapping $2^n+2^m$ to $(n,m)$?Function for unique hash codeDetermine an explicit expression for $f$.A functional equation over integersHow to scale a ratio to a limited range?Equal functions with non-equal definitionsIs there a mathematical function which flips 1 and 2?Is there any explicit bijective mapping from $mathbbZ$ to $mathbbQ^+$?Is the Cantor Pairing function guaranteed to generate a unique real number for all real numbers?Dichotomy of function mapping and its inverse.Term for functions that map functions to other functions

Am I not good enough for you?

Fourth person (in Slavey language)

Do I really need to have a scientific explanation for my premise?

CSS animation in LWC not working

infinitive telling the purpose

Could a cubesat propel itself to Mars?

What are the best books to study Neural Networks from a purely mathematical perspective?

What are some noteworthy "mic-drop" moments in math?

Is this animal really missing?

Latest web browser compatible with Windows 98

How do I express some one as a black person?

Is "history" a male-biased word ("his+story")?

Solving "Resistance between two nodes on a grid" problem in Mathematica

The return of String.intern() explained

Probability of rolling two dices

How strictly should I take "Candidates must be local"?

Why does the negative sign arise in this thermodynamic relation?

Grey hair or white hair

Replacing Windows 7 security updates with anti-virus?

MTG: Can I kill an opponent in response to lethal activated abilities, and not take the damage?

Rejected in 4th interview round citing insufficient years of experience

Constexpr variable captured inside lambda loses its constexpr-ness

Could a cubesat be self propelled to the moon from LEO?

Is having access to past exams cheating and, if yes, could it be proven just by a good grade?



Is there an explicit function mapping $2^n+2^m$ to $(n,m)$?


Function for unique hash codeDetermine an explicit expression for $f$.A functional equation over integersHow to scale a ratio to a limited range?Equal functions with non-equal definitionsIs there a mathematical function which flips 1 and 2?Is there any explicit bijective mapping from $mathbbZ$ to $mathbbQ^+$?Is the Cantor Pairing function guaranteed to generate a unique real number for all real numbers?Dichotomy of function mapping and its inverse.Term for functions that map functions to other functions













4












$begingroup$


We know that the number $2^n+2^m$ is unique for $n,minmathbbN$. Is there any explicit way of writing a function $sigma:mathbbNtomathbbN^2$ such that
$$
sigma(2^n+2^m)=(n,m),
$$

for all $n,minmathbbN$?



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 inmathbbN$.










share|cite|improve this question











$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 $mathbbN^2$, you don't identify $(n,m)$ and $(m,n)$... The image of $sigma$ should be the set of parts of $mathbbN$ with two elements.
    $endgroup$
    – TheSilverDoe
    18 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
    18 hours ago











  • $begingroup$
    You can write $sigma(2^n + 2^m) = (n,m) text or (m,n)$ maybe.
    $endgroup$
    – TheSilverDoe
    17 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
    17 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
    17 hours ago
















4












$begingroup$


We know that the number $2^n+2^m$ is unique for $n,minmathbbN$. Is there any explicit way of writing a function $sigma:mathbbNtomathbbN^2$ such that
$$
sigma(2^n+2^m)=(n,m),
$$

for all $n,minmathbbN$?



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 inmathbbN$.










share|cite|improve this question











$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 $mathbbN^2$, you don't identify $(n,m)$ and $(m,n)$... The image of $sigma$ should be the set of parts of $mathbbN$ with two elements.
    $endgroup$
    – TheSilverDoe
    18 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
    18 hours ago











  • $begingroup$
    You can write $sigma(2^n + 2^m) = (n,m) text or (m,n)$ maybe.
    $endgroup$
    – TheSilverDoe
    17 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
    17 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
    17 hours ago














4












4








4


0



$begingroup$


We know that the number $2^n+2^m$ is unique for $n,minmathbbN$. Is there any explicit way of writing a function $sigma:mathbbNtomathbbN^2$ such that
$$
sigma(2^n+2^m)=(n,m),
$$

for all $n,minmathbbN$?



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 inmathbbN$.










share|cite|improve this question











$endgroup$




We know that the number $2^n+2^m$ is unique for $n,minmathbbN$. Is there any explicit way of writing a function $sigma:mathbbNtomathbbN^2$ such that
$$
sigma(2^n+2^m)=(n,m),
$$

for all $n,minmathbbN$?



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 inmathbbN$.







elementary-number-theory functions






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 15 hours ago









Asaf Karagila

306k33438769




306k33438769










asked 18 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 $mathbbN^2$, you don't identify $(n,m)$ and $(m,n)$... The image of $sigma$ should be the set of parts of $mathbbN$ with two elements.
    $endgroup$
    – TheSilverDoe
    18 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
    18 hours ago











  • $begingroup$
    You can write $sigma(2^n + 2^m) = (n,m) text or (m,n)$ maybe.
    $endgroup$
    – TheSilverDoe
    17 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
    17 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
    17 hours ago













  • 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 $mathbbN^2$, you don't identify $(n,m)$ and $(m,n)$... The image of $sigma$ should be the set of parts of $mathbbN$ with two elements.
    $endgroup$
    – TheSilverDoe
    18 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
    18 hours ago











  • $begingroup$
    You can write $sigma(2^n + 2^m) = (n,m) text or (m,n)$ maybe.
    $endgroup$
    – TheSilverDoe
    17 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
    17 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
    17 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 $mathbbN^2$, you don't identify $(n,m)$ and $(m,n)$... The image of $sigma$ should be the set of parts of $mathbbN$ with two elements.
$endgroup$
– TheSilverDoe
18 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 $mathbbN^2$, you don't identify $(n,m)$ and $(m,n)$... The image of $sigma$ should be the set of parts of $mathbbN$ with two elements.
$endgroup$
– TheSilverDoe
18 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
18 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
18 hours ago













$begingroup$
You can write $sigma(2^n + 2^m) = (n,m) text or (m,n)$ maybe.
$endgroup$
– TheSilverDoe
17 hours ago




$begingroup$
You can write $sigma(2^n + 2^m) = (n,m) text or (m,n)$ maybe.
$endgroup$
– TheSilverDoe
17 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
17 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
17 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
17 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
17 hours ago











3 Answers
3






active

oldest

votes


















5












$begingroup$

What do you think of
$$forall k in mathbbN, 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)$.






share|cite|improve this answer











$endgroup$








  • 2




    $begingroup$
    (+1) Looks like you had the idea first. It's hacky but it works.
    $endgroup$
    – 6005
    17 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
    17 hours ago










  • $begingroup$
    @samwolfe you got it ;)
    $endgroup$
    – TheSilverDoe
    17 hours ago


















3












$begingroup$

We have to relax your requirement a bit due to the comment by TheSilverDoe. So we require that for all $boldsymbolm 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)$.






share|cite|improve this answer









$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
    17 hours ago


















2












$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.






share|cite|improve this answer









$endgroup$












    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
    );



    );













    draft saved

    draft discarded


















    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









    5












    $begingroup$

    What do you think of
    $$forall k in mathbbN, 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)$.






    share|cite|improve this answer











    $endgroup$








    • 2




      $begingroup$
      (+1) Looks like you had the idea first. It's hacky but it works.
      $endgroup$
      – 6005
      17 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
      17 hours ago










    • $begingroup$
      @samwolfe you got it ;)
      $endgroup$
      – TheSilverDoe
      17 hours ago















    5












    $begingroup$

    What do you think of
    $$forall k in mathbbN, 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)$.






    share|cite|improve this answer











    $endgroup$








    • 2




      $begingroup$
      (+1) Looks like you had the idea first. It's hacky but it works.
      $endgroup$
      – 6005
      17 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
      17 hours ago










    • $begingroup$
      @samwolfe you got it ;)
      $endgroup$
      – TheSilverDoe
      17 hours ago













    5












    5








    5





    $begingroup$

    What do you think of
    $$forall k in mathbbN, 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)$.






    share|cite|improve this answer











    $endgroup$



    What do you think of
    $$forall k in mathbbN, 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)$.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited 17 hours ago

























    answered 18 hours ago









    TheSilverDoeTheSilverDoe

    3,804112




    3,804112







    • 2




      $begingroup$
      (+1) Looks like you had the idea first. It's hacky but it works.
      $endgroup$
      – 6005
      17 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
      17 hours ago










    • $begingroup$
      @samwolfe you got it ;)
      $endgroup$
      – TheSilverDoe
      17 hours ago












    • 2




      $begingroup$
      (+1) Looks like you had the idea first. It's hacky but it works.
      $endgroup$
      – 6005
      17 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
      17 hours ago










    • $begingroup$
      @samwolfe you got it ;)
      $endgroup$
      – TheSilverDoe
      17 hours ago







    2




    2




    $begingroup$
    (+1) Looks like you had the idea first. It's hacky but it works.
    $endgroup$
    – 6005
    17 hours ago




    $begingroup$
    (+1) Looks like you had the idea first. It's hacky but it works.
    $endgroup$
    – 6005
    17 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
    17 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
    17 hours ago












    $begingroup$
    @samwolfe you got it ;)
    $endgroup$
    – TheSilverDoe
    17 hours ago




    $begingroup$
    @samwolfe you got it ;)
    $endgroup$
    – TheSilverDoe
    17 hours ago











    3












    $begingroup$

    We have to relax your requirement a bit due to the comment by TheSilverDoe. So we require that for all $boldsymbolm 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)$.






    share|cite|improve this answer









    $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
      17 hours ago















    3












    $begingroup$

    We have to relax your requirement a bit due to the comment by TheSilverDoe. So we require that for all $boldsymbolm 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)$.






    share|cite|improve this answer









    $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
      17 hours ago













    3












    3








    3





    $begingroup$

    We have to relax your requirement a bit due to the comment by TheSilverDoe. So we require that for all $boldsymbolm 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)$.






    share|cite|improve this answer









    $endgroup$



    We have to relax your requirement a bit due to the comment by TheSilverDoe. So we require that for all $boldsymbolm 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)$.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered 17 hours ago









    60056005

    36.7k751127




    36.7k751127











    • $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
      17 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
      17 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
    17 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
    17 hours ago











    2












    $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.






    share|cite|improve this answer









    $endgroup$

















      2












      $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.






      share|cite|improve this answer









      $endgroup$















        2












        2








        2





        $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.






        share|cite|improve this answer









        $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.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 17 hours ago









        Henning MakholmHenning Makholm

        242k17308549




        242k17308549



























            draft saved

            draft discarded
















































            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.




            draft saved


            draft discarded














            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





















































            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







            -elementary-number-theory, functions

            Popular posts from this blog

            Frič See also Navigation menuinternal link

            Identify plant with long narrow paired leaves and reddish stems Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?What is this plant with long sharp leaves? Is it a weed?What is this 3ft high, stalky plant, with mid sized narrow leaves?What is this young shrub with opposite ovate, crenate leaves and reddish stems?What is this plant with large broad serrated leaves?Identify this upright branching weed with long leaves and reddish stemsPlease help me identify this bulbous plant with long, broad leaves and white flowersWhat is this small annual with narrow gray/green leaves and rust colored daisy-type flowers?What is this chilli plant?Does anyone know what type of chilli plant this is?Help identify this plant

            fontconfig warning: “/etc/fonts/fonts.conf”, line 100: unknown “element blank” The 2019 Stack Overflow Developer Survey Results Are In“tar: unrecognized option --warning” during 'apt-get install'How to fix Fontconfig errorHow do I figure out which font file is chosen for a system generic font alias?Why are some apt-get-installed fonts being ignored by fc-list, xfontsel, etc?Reload settings in /etc/fonts/conf.dTaking 30 seconds longer to boot after upgrade from jessie to stretchHow to match multiple font names with a single <match> element?Adding a custom font to fontconfigRemoving fonts from fontconfig <match> resultsBroken fonts after upgrading Firefox ESR to latest Firefox