Double, XOR and do it again

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 g^k(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 g²(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, 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 1

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.

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 2

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!

Answer 3

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 4

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?

Answer 5

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

Answer 6

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.

Answer 7

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 :(

Answer 8

C (gcc), 57 56 55 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!

Answer 9

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

Answer 10

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.

---

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.

Answer 11

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 (ṛ).

Answer 12

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

Answer 13

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!

Answer 14

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?

Answer 15

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.

Answer 16

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

Answer 17

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
}

Answer 18

Prolog (SWI), 44 bytes

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

Try it online!

Answer 19

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.

Answer 20

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.

Answer 21

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 22

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.