Deriving a function based on a relation/characteristic

Question

Say I give you an integer set [1, N], which is the initial step, and define a notion of a step by this example:

given N=16

Step 0: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Step 1: (1)(2) (3)(4) (5)(6) (7)(8) (9)(10) (11)(12) (13)(14) (15)(16)
Step 2: (1)(3) (5)(7) (9)(11) (13)(15)
Step 3: (1)(5) (9)(13)
Step 4: (1)(9)

i.e. you see that in each step pairs consist of the first numbers of pairs of the previous step.

Can you give me a function $f$ which takes step number $n$ and a number $x \in [1, N]$, and tells me whether in step $n$ the number $x$ is stacked together in a pair such that $x$ is on the right of it, and if it is, then what is the number to the left of it.

For example,

$f(n=1, x=5) = false$

$f(n=2, x=5) = false$

$f(n=3, x=5) = true, 1$

$f(n=4, x=5) = false$.

Answer 1

I came up with this, which seems to work perfectly:

If $x-2^{n-1}-1$ mod $2^n$ equals $0$, then $x$ is on the right and $x-2^{n-1}$ is the number on its left.

Won't be giving any proof of it, but here is a program to test it.

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

bool f(int n, int x, int *left)
{
    // (1 << n) is 2^n
    int possible_left = x-(1 << n-1);
    if ((possible_left-1)%(1 << n) == 0) {
        *left = possible_left;
        return true;
    }
    return false;
}

int main()
{
    int *left;

    if (f(1, 5, left)) {
        printf("1: true, %d\n", *left);
    }
    if (f(2, 5, left)) {
        printf("2: true, %d\n", *left);
    }
    if (f(3, 5, left)) {
        printf("3: true, %d\n", *left);
    }
    if (f(4, 5, left)) {
        printf("4: true, %d\n", *left);
    }

    return 0;
}

Which prints

3: true, 1

And this, which essentially uses the same check and prints steps 1-4 for N=16

#include <stdio.h>

int main()
{
    int n = 1;
    int N = 16;
    int p;

    while ((p = 1 << n) <= N) {
        printf("Step %d: ", n);
        for (int x = 1; x <= N; x++) {
            if ((x-1)%p == 0) {
                printf("(%d)(%d), ", x, x+(1 << n-1));
            }
        }
        printf("\n");
        n++;
    }

    return 0;
}

Outputs

Step 1: (1)(2), (3)(4), (5)(6), (7)(8), (9)(10), (11)(12), (13)(14), (15)(16),
Step 2: (1)(3), (5)(7), (9)(11),
Step 3: (1)(5), (9)(13), 
Step 4: (1)(9),