Doubt - Logic of numbers that change places

Your idea of dividing by powers of 10 to extract each digit from the number is essentially right; you do not need to save the numbers you found in an array to print only at the end: it's okay to have 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, as you might have guessed, compare if 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.

One trick that works for this particular case is to use Gödel numbering 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₈ × p₉ = 2 × 7 × 19 × 23 = 6118; and 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 the product of prime numbers (eg 120 = 2³ × 3 × 5). Since the multiplication operation is commutative, it 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 do not understand why this is true, shout at the comments.)

How will you implement this in code? You will, for both the original number and 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've finished running this block from if s to each digit, you can compare the two values of goedel - if they are equal, you can conclude that contador and contador * nTeste have the same% digits (albeit 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 microprocessor of processors, is that 23⁷ is less than 2³².)

Let x be a natural number and y another natural number that is anagram of x in base 10, / em> ≠ y .

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

  

m * x = y
  m = y / x

x is nonzero because if x is zero, y would also be zero, which would violate the 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 exists a rational number that multiplied by x results in y . > So the only numbers that do not become an anagram when multiplied by any other are those numbers that do not have anagrams, such as 11, 2222, 33, 5, 77, and so on. All others can change places when multiplied by something.