Doubt - Logic of numbers changing places

Question

I’m trying to put together a C algorithm to find integer numbers that change places by multiplying by another.

I haven’t found problems like this on the Internet, I don’t even know if there’s a way to do it with whole numbers. But a brief example with fractional numbers is: 12 * 1,75 = 21

For four-digit numbers; 1489, it should be 9148.

I wanted help from you not to receive a complete code, but rather a path/logic to follow to develop the code.

The way I’m thinking is the following:

a variable "counter = 1". a while body to find numbers that change places between 1 and 1 million. The multiplication numbers for tests are only 2, 3, 4, 5, 6, 7, 8 and 9. Instead of using counter++, use counter += nTeste;

Remarks

I’m new to programming. I can’t find the condition to use to know if the number has changed position or not. I haven’t studied array’s in C yet, so my code will only find a single number and display it. If I knew array’s, I could go storing all the numbers I find up to a million and then display them all. I tried to explain my doubt, but in case you don’t understand some part, just leave a note.

Thank you.

The following code is something very initial of how I’m trying to do;

#include <stdio.h>
#include <locale.h>

int main(int argc, char const *argv[]) {

    setlocale(LC_ALL, "");

    //Número inteiros.
    int u, d, c, m, md, mc, mi, contador;

    //Números de testes para multiplicação.
    int nTeste;


    /*int iU, iD, iC, iM, iMD, iMC, iMI, total;*/


    /*Variáveis para extrair os dígitos de cada posição.
    Ex: Para extrair "2" de "21"; "tempDecimal = 21 / d".*/
    u = 1;          //Unidades
    d = 10;         //Dezenas
    c = 100;        //Centenas
    m = 1000;       //Milhar
    md = 10000;     //Dezenas de milhar
    mc = 100000;    //Centenas de milhar
    mi = 1000000;   //Milhão


    while (nTeste >= 2 && nTeste <= 9) {
        printf("Digite um número para teste: [2 a 9]");
        scanf("%d", &nTeste);
    }

    while (contador <= mi) {

        if (contador <= u) {

        }

        if (contado > u && contador <= d) {

        }

        if (contado > d && contador <= c) {

        }

        if (contado > c && contador <= m) {

        }

        if (contado > m && contador <= md) {

        }

        if (contado > md && contador <= mc) {

        }

        if (contado > mc && contador <= mi) {

        }



    }

    return 0;
}

Answer 1

Your idea of dividing by power of 10 to extract each digit from the number is essentially right; you nay need to save the numbers you found in an array to print only at the end: no problem having a if (/* número é válido */) { printf("%d\n", contador); } in the middle of your while; so your program will print the cyclic numbers as they are found.

The part that would normally be done with arrays would be, as you might have imagined, to compare whether e.g. 1489 and 9148 have the same digits. With arrays, you can put each digit in the array, sort and compare the two arrays.

A trick that works for this particular case is to use numeration of Gödel to find these cases. Specifically, consider the "cousins"

p_0 = 1
p_1 = 2
p_2 = 3
p_3 = 5
p_4 = 7
p_5 = 11
p_6 = 13
p_7 = 17
p_8 = 19
p_9 = 23

You will represent the number 1489 by the product p p p = 2 7 19 23 = 6118; the number 9148 = p p p p = 23 2 7 19 = 6118. These products are the gödel number of the original number.

You must have learned at some point in your Elementary School, every integer (positive) has a unique factorization as a product of prime numbers (e.g. 120 = 2³ 3 5). Since the multiplication operation is commutative, this implies that two integers X and Y have the same Gödel number if and only if X and Y have the same digits (this is the key fact of the idea - if you don’t understand why this is true, shout in the comments).

How will you implement this in code? You will both for the original number, and for the number multiplied by nTeste, do something like

int goedel = 1;
int digito;

/* extrai um dígito do número, guarda em digito */

if (digito == 0) { goedel *= 1; }
if (digito == 1) { goedel *= 2; }
if (digito == 2) { goedel *= 3; }
if (digito == 3) { goedel *= 5; }
if (digito == 4) { goedel *= 7; }
if (digito == 5) { goedel *= 11; }
if (digito == 6) { goedel *= 13; }
if (digito == 7) { goedel *= 17; }
if (digito == 8) { goedel *= 19; }
if (digito == 9) { goedel *= 23; }

After you finish running that little bloc of ifs for each digit, you can compare the two values of goedel - if they are the same, you can conclude that contador and contador * nTeste have the same digits (although in different orders).

(An important fact for this idea to work, whose relevance you will not understand today, but whose relevance you will understand when you have studied more programming, and in particular microarchitecture of processors, is that 23 is less than 2³².)

Answer 2

Be it x a natural number and y another natural number which is an anagram of x base 10, being x ≠ y.

To find the multiplier m which multiplied by x results in y, we have to:

m * x = y
m = y / x

Since so much x how much y are natural and x is different from zero*, so y/x is a rational number.

(*) x is different from zero because if x were zero, y would also be zero, which would violate the condition x ≠ y.

The conclusion is that for ALL natural numbers x and y such that y is an anagram of x and x ≠ y, then there is a rational number that multiplied by x results in y.

Therefore, the only numbers that do not turn into an anagram when multiplied by some other, are those numbers that do not have anagrams, such as 11, 2222, 33, 5, 77, etc. Everyone else can change their place when multiplied by something.