[Question]
  [
We define the function **g** as **g(n) = n XOR (n \* 2)** for any integer **n > 0**.
Given **x > 0**, find the smallest integer **y > 0** such that **gk(y) = x** for some **k > 0**.
## Example
```
x = 549
549 = 483 XOR (483 * 2)     (as binary: 1000100101 = 111100011 XOR 1111000110)
483 = 161 XOR (161 * 2)     (as binary:  111100011 =  10100001 XOR  101000010)
```
Which means that **g2(161) = 549**. We can't go any further, as there is no **n** such that **g(n) = 161**. So, the expected output for **x = 549** is **y = 161**.
## Rules
* You are not supposed to support invalid entries. A pair **(y, k)** is guaranteed to exist for the input value **x**.
* This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest answer in bytes wins!
## Test cases
```
     3 -->     1
     5 -->     1
     6 -->     2
     9 -->     7
    10 -->     2
    23 -->    13
    85 -->     1
   549 -->   161
   960 -->    64
  1023 -->   341
  1155 -->   213
  1542 -->     2
  9999 -->  2819
 57308 --> 19124
 57311 -->   223
983055 -->     1
```
  
[Answer]
# Java 8, ~~68~~ ~~57~~ ~~53~~ 52 bytes
```
n->{for(int i=0;i<n;)i-=(i*2^i)==n?n=i:-1;return n;}
```
-5 bytes thanks to *@OlivierGrégoire*.
[Try it online.](https://tio.run/##XZFPb4JAEMXvfoqJJ6iBsCAWXbf9BPXisX@SLWIzioOBwaQhfHa6bjmw7mGSN5n3y8vbk77p4HQ4D3mpmwbeNFIHMANA4qI@6ryAXWekXUDu3Sf50mz6mRkNa8YcdkCgYKDgpTtWtT1CFUnckvQxUB4@xV/oK0WvpHATCFkX3NYEJPtB3jnX9rs0nBF3q/AAFxPF23ON9PP@Cdr/T8FFw15iA4winYrVVKynQkRTFTuIzGGkS8e4XkUux/UKkTpukS5jx26eQ39OouxhIYTjyJJoZE47tqXYA1vv2Mf@t@HiElYth1dTFZfk4WK@@eD5gkLzXf7I6Yc/)
**Explanation:**
```
n->{                 // Method with integer as both parameter and return-type
  for(int i=0;i<n;)  //  Loop `i` in the range (1,n)
    i-=(i*2^i)==n?   //   If `i*2` XOR-ed with `i` equals `n`
        n=i          //    Set `n` to `i`, and set `i` to 0 to reset the loop
       :             //   Else:
        -1;          //    Increase `i` by 1 to go to the next iteration
  return n;}         //  Return `n` after the entire loop
```
[Answer]
# [Python 2](https://docs.python.org/2/), ~~54~~ 53 bytes
```
f=lambda n:next((f(i)for i in range(n)if n==i^i*2),n)
```
[Try it online!](https://tio.run/##FY3NCsIwEITvPsUeE5lDfrq1KfRJRKFiowu6LaWH@vQxncPAfHwwy297zxpKycNn/D6eI2mv074Zk43YPK8kJErrqK/JqJVMOgxyl3OwUFsOQatwjWC0SPAOIaJjcJOQWldB3d4zw3MTkGrAl@i6o71H6qJjvvUnWlbRjXJ9KX8 "Python 2 – Try It Online")
[Answer]
# JavaScript, 53 bytes
```
f=x=>(i=0,y=(G=x=>x&&(i^=x&1)+2*G(x>>1))(x),i?x:f(y))
```
`G` is `g^-1`, which set `i` to `0` if success, set `i` to `1` if failed.
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), ~~13 12~~ 10 bytes
*Saved 1 byte thanks to @MrXcoder, and 2 more bytes following their suggestion*
```
fqQ.W<HQxy
```
[Try it online](https://pyth.herokuapp.com/?code=fqQ.W%3CHQxy&input=1023&debug=0)
Explanation:
```
fqQ.W<HQxyZZT   Implicit: Q=eval(input()), trailing ZZT inferred
f               Return the first T in [1,2,3...] where the following is truthy
   .W       T     Functional while - loop until condition is true, starting value T
     <HQ            Condition: continue while iteration value (H) less than input
        xyZZ        Body: xor iteration value (Z) with double (y) iteration value (Z)
 qQ               Is the result of the above equal to input?
```
[Answer]
# [R](https://www.r-project.org/), ~~73~~ 65 bytes
```
f=function(x){for(i in 1:x)if(x==bitwXor(i,i*2)){i=f(i);break};i}
```
[Try it online!](https://tio.run/##RY3dCoMwDEbvfYpcNqMDq6tzP77H7oZKC2GuG7Yyh/jsLh0bBr4EDod8/bLYyg6uDfRwYsTJPnpBQA7UcUSyYqyqhsLrErGkTYY4UWUF4anpTX2bTzQvwfhwbWtvPJy30IocJGhOwTlwVCohyyWUEerdgWmRRhyhUlrz1ruMMQ8b@zwtv0cpZmWeao1Jb/zQhW/D4DryQXT189m9xdouwSImrr4bL346Rn81/l@WDw "R – Try It Online")
Thanks a lot [Giuseppe](https://codegolf.stackexchange.com/users/67312/giuseppe) (-8) due to your tweaks, so simple yet very effective
[Answer]
# JavaScript, ~~38~~ 36 bytes
```
f=(n,x=n)=>x?x^x+x^n?f(n,--x):f(x):n
```
[Try it online](https://tio.run/##VY3LCoMwFER/xUUXCd4Eo6Y0hehHdNlWEnwUxd6ISgmUfnuaLjuLgTlnMZN92a1dx2Vn6Lo@hEETBK@R6srXvvGpb7AeImPM0/NAYmFoHW5u7vnsHuRagIQjKBAZ5AWcJMhSgTpmEcQthJQgZJmDirnzp12I15U5vP3H8MV2l92uOylpahLGqsSkUf1u/i3lkxvR3NDQ8AU) - Starts throwing overflow errors somewhere between `9999` & `57308`.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~8~~ 7 bytes
Use `⁺¿` to return the last non-zero element (thanks Dennis for -1 byte)
```
^Ḥ)i$⁺¿
```
[Try it online!](https://tio.run/##y0rNyan8/z/u4Y4lmpkqjxp3Hdr//3D7o6Y1//9HG@uY6pjpWOoYGugYGetYmOqYmljqWJoZAAWAfENDU1MdQ1MTIx1LINAxNTc2sACRhoY6lhbGBqamsQA "Jelly – Try It Online")
Brute force wins again :(
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~57~~ ~~56~~ ~~55~~ 51 bytes
* Saved a byte thanks to [ceilingcat](https://codegolf.stackexchange.com/users/52904/ceilingcat); `!=` ~ `-`.
* Saved ~~a byte~~ five bytes thanks to [Rogem](https://codegolf.stackexchange.com/users/77406/rogem); making use of the ternary expression and gcc quirks.
```
X(O,R){for(R=1;R;O=R?R:O)for(R=O;--R&&(R^2*R)-O;);}
```
[Try it online!](https://tio.run/##Zc7daoMwFMDx6/UpgsOSMyJ4orGmIfgIQuiFF2MgfozA5orurvTZnUu2lHW5OeHH4Z90yWvXrWtDa2bgMn7M1GhURtXaVOZYg5daJYnZ76l54U8GklqBuq6P/TDaaSAnatkM59lOnyONGhoXPRCtSSx6ois3aLzA8xQxyxpqgc1uaD1X0bldlqGPjtHY2rftAmr33tqJwmX3cKLk@2TMDYQg4p8UXvhNpJdDEEzvd7gvYxakvC@L3HWwCCIL3ynyH8HUd7L8dwdRuA4PZRQ5//u63M4mvETpRRyytGQEJfI8CKLrcN@RZZaK2w@v6xc "C (gcc) – Try It Online")
[Answer]
# [Z80Golf](https://github.com/lynn/z80golf), 22 bytes
```
00000000: 1600 1803 4216 007a b830 097a 82aa b828  ....B..z.0.z...(
00000010: f314 18f3 78c9                           ....x.
```
Port of @KevinCruijssen's Java answer
[Example with input of 9-Try it online!](https://tio.run/##jcwxCsMwEATAPq/YMpVZSUY6p8xPZBmlMbgLQZ9XVrEfkIWDPbibZnwde@2dVx5g5IKycQVZIgLLpmZEii6qOQPD7IHpF2reozxvp@BkuEjd59X0Li1l88hj9VYD3CyjhmTDaBKa3u/D@FyGl1EW/Jep9y8 "Z80Golf – Try It Online")
[Example with input of 85-Try it online!](https://tio.run/##jY7BboMwEETP8BVz7CFCawjOJlIP7S0fkA8wdt1UcqAKpmr5eTK0fEBHsna8mnnaWeV9SHFZZNMJYtsWPkgHEW/RiA90KjhYY@mMQpp9DVSXihK@r9W8ln8EQ4axwrzrlHU50mkNt35rjQ3MnozYHJSMaiZhZv1pZXxvjJoMf8T/VC3Luf@c8rO25cs4vt269IM43BGn3uePoYd3KcH1AcOUGTyVY3Z3jiIFdDvWit9ELAsXAk@@bgvlKfRXl/ID "Z80Golf – Try It Online")
Assembly:
```
;d=loop counter
;b=input and output
f:
	ld d,0
	jr loop
	begin:
	ld b,d
	ld d,0
	loop:
		ld a,d
		cp b
		jr nc,end	; if d==b end
		ld a,d
		add d		; mul by 2
		xor d
		cp b
		jr z,begin	; if (d*2)^d==b set b to d
		inc d
		jr loop
	end:
	ld a,b
	ret
```
Assembly example for calling the function and printing the result:
```
ld b,9 ; input to the function, in this case 9
call f
add 30h ; ASCII char '0'
call 8000h ; putchar
halt
```
[Answer]
# [Java (JDK 10)](http://jdk.java.net/), 78 bytes
```
int g(int n){return f(n)%2<1?g(f(n)/2):n;}int f(int x){return 1>x?0:x^f(x/2);}
```
[Try it online!](https://tio.run/##XZFfa4MwFMXf@ykuhUJCmUu0dlbH@gn21Mf9gaxVSWvTYq6dQ/zsLhFZk@UhyQnn/ALnHsVNPBwPp2FfCa3hVUjVDVIhlMTuinZ1jk2toCCKLsJnvi2JvT6GNFVZbz3F6Gz/nPyl3bK0/SxIa1xZP2SzGcC1@arkHjQKNMftIg9wNp@RHdZSlW8fIGhnbACYayQRze4idsXaFRtXcOaq0EMkHiNeecHNmvkcP8t57KV5vAq9uFke/Sliyb8Hzr1EErGJ2dtu3FJGgy1UTn3sfjTm5@DSYHA1VWGlCMjlPH3H@RJU/j3OjNDADIzCxOyHXw "Java (JDK 10) – Try It Online")
[Answer]
# JavaScript (Node.js), ~~48~~ ~~45~~ 38 bytes
```
f=(n,i=0)=>i<n?i*2^i^n?f(n,i+1):f(i):n
```
-7 bytes thanks to @Neil creating a recursive version of my iterative version below. Doesn't work for large test cases.
[Try it online.](https://tio.run/##TczBDoIwDIDhO09BOG2iZgWGgA5exJAQBDJDOiOLrz/BZMWe/i1f@@w@3dK/9cue0DwG50bF8KiV4KrWN2z0IWl1i824/cbAq5FpXqGzw2JDFaKqe4OLmYfzbCaGcVTdbRSvmvNrEGyKpWv9QvrIfZQ@QPhKiBfkZUawzMW@s1sASRpklhBfh65cUlH8PQBIFanY9t0X)
---
Iterative **45 bytes** version that works for all test cases:
```
n=>{for(i=0;i<n;)i-=i*2^i^n?-1:n=i;return n;}
```
[Port of my Java answer.](https://codegolf.stackexchange.com/a/166272/52210)  
-3 bytes thanks to *@Arnauld*.
[Try it online.](https://tio.run/##TczRDoIgGIbhc6/CeYQ5G6iYStSNNDdn0GjupyF10rp20jYwjt5/ez7uw2uYR6MeNgd9FU5yB/z0ltogxTFTR2CpyrnaFb3q4ZyTDrhiRtingRjYx1kx25jHy2jUMOtJ7Cd9Q5Al3cUmmUSQpiyKVoXKpX5BfdQ@Wh8E@yoCb4KnVYBtjbfNZgmhQRNaFYEvL/xyKHHzdxASVFPide@@)
[Answer]
# [Ruby](https://www.ruby-lang.org/), 39 bytes
```
f=->x,y=x{y<1?x:x==y^y*2?f[y]:f[x,y-1]}
```
[Try it online!](https://tio.run/##ZZBNCsIwEEb3OUXAnTTSyZ9JMe1BQgUVg0vRFhJaz17TqDTY2czwZnh8zKM/h2lyhtS@CMYP4QCNr7wx4Ri2tHE2tJWzcUegfU0Wx2K42BBSzyMGlJpYI5kh@kE6Q/uEoFxd0UwPLCG10gu@uEAmpGXmkhzN8szF@HwFIBYXTXoQnP6F0LF@iCrQCIs9K9UXgQbKEwJYXJQhrVgZ9TiL2u6up8ttGLvx3ndP7GwXn/gG "Ruby – Try It Online")
As expected for the recursive version, complains about "stack level too deep" on the latter test cases.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~11~~ 9 bytes
```
BÄḂṛḄß$Ṫ?
```
[Try it online!](https://tio.run/##y0rNyan8/9/pcMvDHU0Pd85@uKPl8HyVhztX2f8/3P6oac3//9HGOqY6ZjqWOoYGOkbGOhamOqYmljqWZgZAASDf0NDUVMfQ1MRIxxIIdEzNjQ0sQKShoY6lhbGBqWksAA "Jelly – Try It Online")
Tips: Use recursive function instead of loops.
---
Very fast, unfortunately loses to the brute force approach.
Note that:
* For *x > 0*, *f(x) > x*.
* *popcount(f(x))* is even, where *popcount(n)* is the number of bits set in *n*.
* If *n* has even popcount, then there exists *x* such that *f(x) = n*.
* Let *B(x)* be the binary representation of *x*, and *Ṗ(l)* be the list *l* with last element removed. Then *B(x)* is the accumulated XOR of *Ṗ(B(f(x)))*.
So, we repeatedly:
* Compute its binary representation (`B`)
* then take the accumulated XOR (use `^\` or `ÄḂ`, they have the same effect).
* Check if (`?`) the tail (last element) (`Ṫ`) of the accumulated XOR is nonzero (odd popcount)
	+ If so, convert the binary list back to decimal and recurse.
	+ If not, returns the input (`ṛ`).
[Answer]
# [Forth (gforth)](http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/), 71 bytes
```
: f 0 begin 2dup dup 2* xor = if nip 0 else 1+ then 2dup < until drop ;
```
[Try it online!](https://tio.run/##LYzhDoIwDIT/8xQXfmpG2NyIiPowygZLyLaMkfj22KJNvja9u9bFXGYxOR77foNDi5edfIAatwRGnfCJGQ94h@ATBeyyWsgzymz/uTu2UPyCMceEgf78TjWajKYGhHjW9Nvw/s4YqgtSZYiO6AnZUlOsXlk2msW@aw/r0KU07EijFVtUSPsX "Forth (gforth) – Try It Online")
### Explanation
```
0                 \ add an index variable to the top of the stack
begin             \ start an indefinite loop
  2dup            \ duplicate the top two stack items (n and i)
  dup 2* xor =    \ calculate i xor 2i and check if equal to n
  if nip 0        \ if equal, drop n (making i the new n) and use 0 as the new i
  else 1+         \ otherwise just increment i by 1
  then            \ end the if-statement
  2dup <          \ duplicate the top two stack items and check if n < i
until             \ if previous statement is true, end the loop
drop              \ drop i, leaving n on top of the stack
```
[Answer]
# [Perl 6](https://perl6.org), 44 bytes
```
{({first {($^a+^2*$a)==$_},^$_}...^!*).tail}
```
[Try it](https://tio.run/##XY5daoQwFEbfs4pbkKKjkzHROKZi6SL6WCxWMyD4hzqlRVxRd9GN2SSjMvU@JHDyfeemFV0ZzNdewGeAswih6hsesyYXEM@jOV6Krh9gNI0ktRN6MFIrjo33yUnkgTFOHg4WHtKinGbZexmEDMdQFrXocZW2TzDavz84a6oP8/SW2yfLAVlESO17leEItWVag62bEbo03SI5PoNpGkXdXgfHEF@tyAaRq3Yu@syCEQEUPah/Lin1tuaWWISmGdR4cJQ@NQTpi@1BsAF6A3wDZw2Iu0vQTUo8DcKdlPmrgwQa8GBzBD5Sys3h@SpBCFsdVEsJ8@m/tVzODdCQcATs7LmhBoQT6mtAyOqgHuKh57K7j/0B "Perl 6 – Try It Online")
## Expanded:
```
{  # bare block lambda with implicit parameter $_
  (
    # generate a sequence
    # no need to seed the sequence with $_, as the following block will
    # default to using the outer $_
    # $_, 
    { # parameter $_
      first
        {  # block with placeholder parameter $a
          ( $^a +^ 2 * $a ) # double (numeric) xor
          == $_             # is it equal to the previous value
        },
        ^$_  # Range up to and excluding the previous value ( 0..^$_ )
    }
    ...^  # keep doing that until: (and throw away last value)
    !*    # it doesn't return a trueish value
  ).tail  # return the last generated value
}
```
[Answer]
# [Prolog (SWI)](http://www.swi-prolog.org), 44 bytes
```
A-R:-between(1,A,B),A is B xor(B*2),B-R;R=A.
```
[Try it online!](https://tio.run/##bY5BCsMgEEX3PYXLWJzgaExNSwl6BI9QkCKEWEzA3t527/zlW7z3PyVv@Q1HTa05CHd4xbPGuA8onPBcOJYO5tk3l8FfFRcewiM83dhW0BAEqyWdcduHwMfLCqZHc4@WHqHsmSICliiYiRAus6QqlBPREFY0kyK0/xEPblpaEiMSDqtlV2w/ "Prolog (SWI) – Try It Online")
[Answer]
# PHP, 49 bytes
Based on Kevin Cruijssen's answers.
```
for($x=$argn;$x>$i-=$i*2^$i^$x?-1:$x=$i;);echo$x;
```
Run as pipe with `-nr` or [try it online](http://sandbox.onlinephpfunctions.com/code/2c3a9d770bce01dc8b29b8a2efee8420a062ab60).
[Answer]
## F#, 92 bytes
```
let rec o i=
 let r=Seq.tryFind(fun x->x^^^x*2=i){1..i-1}
 if r.IsNone then i else o r.Value
```
[Try it online!](https://tio.run/##LZBBS8NAEIXv@RWPQsEK2WaTpqbE5KYgiAhCL7WBkE7qQNzUzUYi6m@Pk9q5DPMxvHlv6s6vWkvj2JCDpQotOPNwnrIX@lDOft2zOVzVvcHg50NRFMN1mPHiWyvFvv71wDWseuieWkNwb2TAoKYjkbJqWzY9jbvbOyNCzy0bl@@9Sf29ZIPSHj9xOcfm1LsOGXZRijjFOsUmhQ5ShAISIfFKwGYdTHRiWsdCdbwKBUvJxk0UJOemtbAkCuJ47@GRO6fYkcV/DPi5mBvwk@NkxVJtMJvzq5vzDMPi4sRDgOVSfuJ6K04llXF0FA0a2KFqDzT@AQ)
Recursively checks through the numbers from 1 to `i-1`. If there's a match, check for a smaller for that number. If there's no match, return the input number.
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 40 bytes
```
f=n=>g(n)%2?n:f(g(n)/2)
g=x=>x&&x^g(x/2)
```
[Try it online!](https://tio.run/##TczRCoMgGIbh864igoUS29SyVcN2I2MQzWIjdCwZ3r3TgX/z6FWez@fwGdbx/XiZvdJ36dwklOhnpPCOXVQ3oZBHhpNZWNHbPLe3GVn/4IxcTSpSr0etVr3Iw6I9LrLuarJi8jN8TpKgUOnrFzxGHaONQUksBrwBzyuAbU22zWYp5aAprxhwf@CXU0mavwuloJqShL37Ag "JavaScript (Node.js) – Try It Online")
Thanks Shaggy for -1 bytes.
Port of my [Jelly answer](https://codegolf.stackexchange.com/a/166281/69850).
Finally there is a language where this approach is ~~shorter~~ ([oops](https://codegolf.stackexchange.com/a/166285/69850)). (I tried Python and [Java](https://codegolf.stackexchange.com/a/166283), it doesn't work)
Can anyone explain why I can use `/2` instead of `>>1`?
[Answer]
# [K (ngn/k)](https://gitlab.com/n9n/k), ~~32~~ 26 bytes
```
{$[*|a:2!+\2\x;x;2/-1_a]}/
```
[Try it online!](https://tio.run/##FYvdCoJAFITve4oTBGkh7jn7467nUVLSGyMMA/FCKXv17ezAwDDfzFhMjynGof6cbpdvX9Px2lCz8spUFnjv272MS4Lbb64HWLl7j5x1Q/98yWbjOW/3w1KeMw3IVuyAOEDFqCSQtJp96q0JgA45OAXOCBamDTKitUCyQmsofUVAHgPbSisPGJBMyohApDl4reSBefwD "K (ngn/k) – Try It Online")
`{` `}` is a function with argument `x`
`/` applies it until convergence
`$[` `;` `;` `]` if-then-else
`2\x` binary digits of `x` (this is specific to ngn/k)
`+\` partial sums
`2!` mod 2
`a:` assign to `a`
`*|` last - reverse (`|`) and get first (`*`)
if the above is 1, `x` will be returned
otherwise:
`-1_a` drop the last element of `a`
`2/` decode binary
[Answer]
# C, 62 bytes
Based on Kevin Cruijssen's Java:
`int n(int j){for(int i=0;i<j;)i-=(i*2^i)==j?j=i:-1;return j;}`
To test:
```
#include <stdio.h>
int n(int j);
#define p(i) printf("%6d --> %5d\n", i, n(i))
int main(void)
{
    p(3);
    p(5);
    p(6);
    p(9);
    p(10);
    p(23);
    p(85);
    p(549);
    p(960);
    p(1023);
    p(1155);
    p(1542);
    p(9999);
    p(57308);
    p(57311);
    p(983055);
}
```
When run, the test program outputs:
```
     3 -->     1
     5 -->     1
     6 -->     2
     9 -->     7
    10 -->     2
    23 -->    13
    85 -->     1
   549 -->   161
   960 -->    64
  1023 -->   341
  1155 -->   213
  1542 -->     2
  9999 -->  2819
 57308 --> 19124
 57311 -->   223
983055 -->     1
```
# C, 54 bytes
Only works with C89 or K&R C:
`n(j){for(i=0;i<j;)i-=(i*2^i)==j?j=i:-1;return j;}`
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 58 bytes
```
Min[{#}//.x_:>Select[Range@#,MemberQ[x,#|BitXor[#,2#]]&]]&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78H1CUmVcS/d83My@6WrlWX1@vIt7KLjg1JzW5JDooMS891UFZxzc1Nym1KDC6Qke5ximzJCK/KFpZx0g5NlYNiP7rOyhUG@somOoomOkoWOooGBroKBgBBSyAIqYmQAFLMwOQqJFxbex/AA "Wolfram Language (Mathematica) – Try It Online")
Starts with a list containing just the input. Iteratively replaces the list by all integers that are either already in it, or map into it by the double-and-xor operation. Then `//.` says to do this until reaching a fixed point. The answer is the least element of the result.
]