20
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, 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
3
Related OEIS: A048274 which is the sequence
– Giuseppe – 2018-06-06T13:29:26.443a(n) = g(n)