20
\$\begingroup\$

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

22 Answers 22

5
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ n->{for(int i=0;i<n;)i-=(i*2^i)==n?n=i:-1;return n;} (52 bytes). Sorry ^^' \$\endgroup\$ – Olivier Grégoire Jun 6 '18 at 7:55
  • \$\begingroup\$ @OlivierGrégoire Even smarter, thanks! \$\endgroup\$ – Kevin Cruijssen Jun 6 '18 at 8:01
  • \$\begingroup\$ for(int i=0;n>i-=i+i^i^n?-1:n=i;);? \$\endgroup\$ – Titus Jun 7 '18 at 1:52
  • \$\begingroup\$ @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). \$\endgroup\$ – Kevin Cruijssen Jun 7 '18 at 6:42
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Olivier Grégoire Jun 7 '18 at 15:05
4
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Neil Jun 6 '18 at 9:46
3
\$\begingroup\$

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

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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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! \$\endgroup\$ – Giuseppe Jun 6 '18 at 15:09
  • 2
    \$\begingroup\$ you can also do some re-jiggering of your logic and get this to 65 bytes \$\endgroup\$ – Giuseppe Jun 6 '18 at 15:11
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ ^Ḥ)i$⁺¿ saves a byte. \$\endgroup\$ – Dennis Jun 6 '18 at 14:44
  • \$\begingroup\$ And it's 2x slower. \$\endgroup\$ – user202729 Jun 7 '18 at 17:12
2
\$\begingroup\$

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!

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

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Misha Lavrov Oct 6 '18 at 0:25
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You can do i-=i*2^i^n?-1:n=i (but unfortunately not in Java). \$\endgroup\$ – Arnauld Jun 6 '18 at 8:01
  • \$\begingroup\$ @Arnauld Figured something was possible for the boolean in Java to just 1 in JS. Thanks! \$\endgroup\$ – Kevin Cruijssen Jun 6 '18 at 8:05
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – Neil Jun 6 '18 at 9:43
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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 ().
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
}
\$\endgroup\$
1
\$\begingroup\$

Prolog (SWI), 44 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ 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.) \$\endgroup\$ – Arnauld Jun 6 '18 at 8:59
  • \$\begingroup\$ 40 bytes \$\endgroup\$ – Shaggy Jun 25 '18 at 10:57
  • \$\begingroup\$ @Shaggy Surprised that it works. I know it works for Python and Lua etc., but not Javascript. \$\endgroup\$ – user202729 Jun 25 '18 at 15:36
  • \$\begingroup\$ The false returned on the last iteration is implicitly cast to 0 by the bitwise XOR operator. \$\endgroup\$ – Shaggy Jun 25 '18 at 15:38
  • \$\begingroup\$ @Shaggy In fact, no false is involved. JS && behaves almost identically to Python/Lua and. \$\endgroup\$ – user202729 Jun 25 '18 at 15:41
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.