Digit manipulation number conversion

Question

I have 4 digit number from 0000 to 1440. I want to generate an equivalent four digit number. That means I can reverse the number from the equivalent number. Basic requirement is the equivalent number must be completely different from the original one. Is there a good equation to do this? For example, each digit can be replaced by 10 - digit. Thus, 1440 becomes 9660, and 1254 becomes 9756.

Thanks.

Answer 1

You can use a Linear Congruential Generator with a period of 10000. This is a pseudo-random number generator that cycles through each number in the range of 0-9999 once and only once. To generate your number, just take the original number and calculate the next number in the LCG sequence.

An LCG generates random numbers using the following formula:

X_n+1 = ((X_n * a) + c) mod m

To generate 4-digit numbers m should be 10000 (range of 0-9999).

To guarantee no repeats (a "full period") you have to select values for a and c using the following criteria:

c and m are relatively prime

a - 1 is divisible by all prime factors of m

a - 1 is a multiple of 4 if m is a multiple of 4.

The prime factors of 10000 are 2 and 5, and it's also divisible by 4, so any multiple of 20 + 1 will work as a suitable value of a. For c just choose a reasonably large prime number.

e.g: m = 10000, a = 4781, c = 7621

To go the other way, you need to make the function reversible. See this answer for an explanation of the math behind that.

Here's a simple implementation:

#define M (10000)
#define A (4781)
#define C (7621)

int extendedEuclidY(int a, int b);

int extendedEuclidX(int a, int b)
{
    return (b==0) ? 1 : extendedEuclidY(b, a-b*(a/b));
}

int extendedEuclidY(int a, int b)
{
    return (b==0) ? 0 : extendedEuclidX(b, a-b*(a/b)) - (a/b) * extendedEuclidY(b, a-b*(a/b));
}

int forward(int x)
{
   return ((x*A)+C)%M;
}

int backward(int x)
{
   return ((extendedEuclidX(A, M)*(x-C)%M)+M)%M;
}

int main()
{
    int x;
    for(x=0; x<1440; x++)
    {
        printf("%d <-> %d\n", backward(forward(x)), forward(x));
    }
    
    return 0;
}

I've adapted the extendedEuclid functions from the linked answer.

forward(x) finds your equivalent number, backward(x) gets the original back.