# Double, XOR and do it again

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 , 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
• Related OEIS: A048274 which is the sequence a(n) = g(n) – Giuseppe Jun 6 '18 at 13:29

# Java 8, 685753 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.

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
• n->{for(int i=0;i<n;)i-=(i*2^i)==n?n=i:-1;return n;} (52 bytes). Sorry ^^' – Olivier Grégoire Jun 6 '18 at 7:55
• @OlivierGrégoire Even smarter, thanks! – Kevin Cruijssen Jun 6 '18 at 8:01
• for(int i=0;n>i-=i+i^i^n?-1:n=i;);? – Titus Jun 7 '18 at 1:52
• @Titus I'm afraid that's not going to work in Java (although I have used that approach in my iterative JavaScript answer). In Java i+i^i^n? is not a boolean, so it won't even compile. In addition, n>i-=... will need parenthesis (n>(i-=...)), and n=i isn't allowed in the else-clause of the ternary-if, only in the if-clause (this last one I don't know why, but that's what it is in Java unfortunately). – Kevin Cruijssen Jun 7 '18 at 6:42
• @KevinCruijssen "and n=i isn't allowed in the else-clause of the ternary-if". Because Java would parse it as (i-=(i*2^i)!=n?-1:n)=i which is illegal. – Olivier Grégoire Jun 7 '18 at 15:05

# Python 2, 54 53 bytes

f=lambda n:next((f(i)for i in range(n)if n==i^i*2),n)

Try it online!

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

• This was the approach I tried to use although I came up with a 50-byte version: f=n=>(g=n=>n<2?0/!n:n%2+2*g(n/2^n%2))(n)?f(g(n)):n. Sadly the boring approach is 12 bytes shorter. – Neil Jun 6 '18 at 9:46

# Pyth, 13 12 10 bytes

Saved 1 byte thanks to @MrXcoder, and 2 more bytes following their suggestion

fqQ.W<HQxy

Try it online

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?
• You can drop the trailing T for 12 bytes. – Mr. Xcoder Jun 6 '18 at 10:56

# R, 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!

Thanks a lot Giuseppe (-8) due to your tweaks, so simple yet very effective

• as opposed to a previous answer of yours, because this function is recursive, you do need the f= since the function needs to be bound to f to work properly. That being said, nice work, and take a +1 from me! – Giuseppe Jun 6 '18 at 15:09
• you can also do some re-jiggering of your logic and get this to 65 bytes – Giuseppe Jun 6 '18 at 15:11

# JavaScript, 38 36 bytes

f=(n,x=n)=>x?x^x+x^n?f(n,--x):f(x):n

Try it online - Starts throwing overflow errors somewhere between 9999 & 57308.

# Jelly, 8 7 bytes

Use ⁺¿ to return the last non-zero element (thanks Dennis for -1 byte)

^Ḥ)i$⁺¿ Try it online! Brute force wins again :( • ^Ḥ)i$⁺¿ saves a byte. – Dennis Jun 6 '18 at 14:44
• And it's 2x slower. – user202729 Jun 7 '18 at 17:12

# C (gcc), 575655 51 bytes

• Saved a byte thanks to ceilingcat; !=-.
• Saved a byte five bytes thanks to 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!

• +1 for X(O,R) – JayCe Jun 7 '18 at 0:18
• @ceilingcat Good suggestion, thanks. – Jonathan Frech Jun 20 '18 at 12:21
• for(R=1;R;O=R?R:O) saves a byte. – user77406 Jun 25 '18 at 10:24
• R=O; at the end seems to be unnecessary, saving you another 4 bytes. – user77406 Jun 25 '18 at 10:38
• @Rogem Seems to be, thanks. – Jonathan Frech Jun 25 '18 at 10:46

# 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!

Example with input of 85-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
• If you make a the loop counter instead of d, then you can replace the ld d,0 instructions by xor a both times, which saves two bytes. – Misha Lavrov Oct 6 '18 at 0:25

# Java (JDK 10), 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!

# JavaScript (Node.js), 4845 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.

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.
-3 bytes thanks to @Arnauld.

Try it online.

• You can do i-=i*2^i^n?-1:n=i (but unfortunately not in Java). – Arnauld Jun 6 '18 at 8:01
• @Arnauld Figured something was possible for the boolean in Java to just 1 in JS. Thanks! – Kevin Cruijssen Jun 6 '18 at 8:05
• 38 bytes written recursively (doesn't work for larger inputs): f=(n,i=0)=>i<n?i*2^i^n?f(n,i+1):f(i):n – Neil Jun 6 '18 at 9:43

# Ruby, 39 bytes

f=->x,y=x{y<1?x:x==y^y*2?f[y]:f[x,y-1]}

Try it online!

As expected for the recursive version, complains about "stack level too deep" on the latter test cases.

# Jelly, 11 9 bytes

BÄḂṛḄß$Ṫ? 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 (). # Forth (gforth), 71 bytes : f 0 begin 2dup dup 2* xor = if nip 0 else 1+ then 2dup < until drop ; 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 # Perl 6, 44 bytes {({first {($^a+^2*$a)==$_},^$_}...^!*).tail} Try it ## 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
}

# Prolog (SWI), 44 bytes

A-R:-between(1,A,B),A is B xor(B*2),B-R;R=A.

Try it online!

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

## 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!

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.

# JavaScript (Node.js), 40 bytes

f=n=>g(n)%2?n:f(g(n)/2)
g=x=>x&&x^g(x/2)

Try it online!

Thanks Shaggy for -1 bytes.

Port of my Jelly answer.

Finally there is a language where this approach is shorter (oops). (I tried Python and Java, it doesn't work)

Can anyone explain why I can use /2 instead of >>1?

• x/2 works because of arithmetic underflow. Any IEEE 754 number will eventually be evaluated as 0 when divided by 2 enough times. (And the decimal part is simply ignored when XOR'd, so this does not affect the result.) – Arnauld Jun 6 '18 at 8:59
• 40 bytes – Shaggy Jun 25 '18 at 10:57
• @Shaggy Surprised that it works. I know it works for Python and Lua etc., but not Javascript. – user202729 Jun 25 '18 at 15:36
• The false returned on the last iteration is implicitly cast to 0 by the bitwise XOR operator. – Shaggy Jun 25 '18 at 15:38
• @Shaggy In fact, no false is involved. JS && behaves almost identically to Python/Lua and. – user202729 Jun 25 '18 at 15:41

# K (ngn/k), 32 26 bytes

{$[*|a:2!+\2\x;x;2/-1_a]}/ 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

# 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;}

• int n(int j){for(int i=0;j>i-=i*2^i^j?-1:j=i;);return j;} Do these 57 bytes work? – Titus Jun 7 '18 at 1:49

# Wolfram Language (Mathematica), 58 bytes

Min[{#}//.x_:>Select[Range@#,MemberQ[x,#|BitXor[#,2#]]&]]&

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.