How to identify "Capicua" numbers that have 5 digits?

Asked

Viewed 4,394 times

35

According to this definition of Priberam.pt, a Picua number is:

Number also read from right to left or vice versa and to which good luck is attributed.

Following this reasoning, Picua would be 12521, 37073, 10001, etc...

How to find out between 5-digit numbers, those that are Picua only using mathematical calculations, removing numbers that have all 5 identical digits like 55555, 33333, 00000, etc?

P.S.: No matter the language, only the logic to develop a way to solve it.

  • has to be by mathematical method?

  • 1

    @Guilhermelautert yes, I believe that there are libs that do this, but I believe that then I would have no challenge :p

  • 1

    I can point out unorthodox indirect methods that make unnecessary use of Features of a language?

  • 1

    @Jeffersonquesado to get involved a little of the mathematics in logic, of course yes :)

  • @Articuno I’m not sure I understand the question, do you want to find out if a given number is Capicua or generate all the numbers Capicua? Or something else?

  • 1

    @Piovezan is to find out if a number that has 5 digits is Picua. This is the essence of the question, although many answers have not limited to only 5 (which has made them even more interesting).

Show 1 more comment

8 answers

30

Let us initially consider a positive 5-digit integer value that can be written as abcde. From the definition, we have that this value will be considered a Capicua if, and only if, abcde is equal to edcba. Thus, we have the first condition that defines our whole:

  • b, c and d belong to the set of natural numbers, such that 0 ≤ b, c, d ≤ 9;
  • a and e belong to the set of non-zero natural numbers, such that 0 < a, e ≤ 9;

Note that the digits a and e cannot be 0, as this would set a 4-digit number, since in mathematics the left zero is ignored.

So, considering the polynomial form of the numbers on the decimal basis, we can write:

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

Being the natural numbers, this expression is valid only if, and only if,, a - e = 0 and b - d = 0; that is, if a = e and b = d, as would already be expected. So we can imagine a function:

inserir a descrição da imagem aqui

Being x the number abcde. The function f(x) will return 0 for any Picua number, but not only them. In fact, it will return 0 to any value it satisfies a - e = -(b - d), as 65365, since 6 - 5 = -(5 - 6). Such problem can be circumvented if we consider the value module:

inserir a descrição da imagem aqui

So it will remain zero for the numbers capicuas and non-zero for any other value. However, numbers with repeated digits would be considered equally, as they continue to satisfy this condition. To then identify the numbers with repeated digits, we can imagine a value:

inserir a descrição da imagem aqui

Collaboration of Jefferson Quesado.

Where w will be 0 for all capicuas of repeated digits and 1 for any other Capicua. We can then imagine a function g(x) in such a way that:

inserir a descrição da imagem aqui

Return 1 for the Capicuas not repeated and any other value for other numbers, including Capicuas repeated. In this case, g(x) will be the very value of w, then:

inserir a descrição da imagem aqui

So we can calculate the values of a, b, c, d and e with:

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

We can then generalize to a function that gets the nth digit of a number:

inserir a descrição da imagem aqui

Javascript

I will implement in Javascript to take advantage that is executable by snippet of the site.

const digit = n => x => (x % Math.pow(10, n) - x % Math.pow(10, n-1)) / Math.pow(10, n-1);

const a = digit(5);
const b = digit(4);
const c = digit(3);
const d = digit(2);
const e = digit(1);

const g = x => Math.ceil(
    Math.abs(
        (a(x)+1000)/(b(x)+1000) + (b(x)+1000)/(c(x)+1000) + (c(x)+1000)/(d(x)+1000) + (d(x)+1000)/(e(x)+1000) - 4
    )
);

const f = x => Math.abs(a(x) - e(x)) + Math.abs(b(x) - d(x)) + g(x);

let capicuas = 0;

for (let x = 10000; x < 100000; x++) {
    
    // Verifica se é capicua:
    if (f(x) === 1) {
        
        capicuas++;
        
        // Confirma se realmente é invertendo a string:
        if (x.toString() != x.toString().split('').reverse().join('')) {
            console.log(`Não é capicua, mas foi considerado: ${x}.`)
        }
        
    } else {
        
        // O número é capicua, mas foi desconsiderado pela função:
        if (x.toString() == x.toString().split('').reverse().join('')) {
            console.log(`É capicua, mas não foi considerado: ${x}.`)
        }
        
    }
}

console.log(`Foram encontrados ${capicuas} números capicuas de 5 dígitos.`);

  • At intermission 10000-100000 were found 891 capicuas numbers, its function is returning 810, possibly the problem already mentioned above. But I really liked the answer =]

  • 3

    @Rovannlinhalis problem solved.

  • 2

    This answer should be printed and framed in gold

25

Basically it is necessary to reverse the number and check if it is equal to the original input.

This implementation works for numbers with any number of digits.

Implementation in C#:

using static System.Console;

public class Program
{
    public static void Main()
    {
        int num;
        int original = num = 51315;     
        int rev = 0;

        while (num > 0)
        {
            int dig = num % 10; //Captura cada dígito

            rev = rev * 10 + dig; 
            // (^) Adiciona o dígito na variável 'rev'.
            // Como usamos a base 10, tudo o que já existe 
            // em rev precisa ser mulplicado por 10

            num = num / 10;
            // Controla o loop
        }

        WriteLine(original == rev ? "É capícua" : "Não é capícua");
    }
}

See working on . NET Fiddle | Code on Github for future reference

16

To be Picua, just separate all digits and compare the digit d_a with its complement d_(5-a+1). Note that the middle digit is ignored because it is equal to itself.

Consider // the entire split operation, as described by the Python language. Consider lines that start with # as comments.

Tip from @Andersoncarloswoss, initially I had not defined that I was using entire division

d1 = n // 10000
r1 = n % 10000

d2 = r1 // 1000
r2 = r1 % 1000

d3 = r2 // 100
r3 = r2 % 100

d4 = r3 // 10
r4 = r3 % 10

d5 = r4

# garantia de capicua:
d1 == d5 and d2 == d3

# garantia de que tem algum dígito distinto:
not (d1 == d2 and d2 == d3 and d3 == d4 and d4 == d5)

# portanto, para ser capicua com algum dígito distinto
return d1 == d5 and d2 == d3 and not (d1 == d2 and d2 == d3 and d3 == d4 and d4 == d5)

12

I can define a word as being a set of tuples formed by character/position. Thus, the word banana would have the following mathematical representation:

{
  ('b',0),
  ('a',1),
  ('n',2),
  ('a',3),
  ('n',4),
  ('a',5)
}

I can change the definition a little bit so that each letter is mapped to a set of positions; so, banana would look like this:

{
  ('b',{0}),
  ('a',{1,3,5}),
  ('n',{2,4})
}

Something interesting about this definition is that if my letter is not in the word, I can associate it with the empty set:

{
  ('a',{1,3,5}),
  ('b',{0}),
  ('c',{}),
  ('d',{}),
  ('e',{}),
  ('f',{}),
  ('g',{}),
  ('h',{}),
  ('i',{}),
  ('j',{}),
  ('k',{}),
  ('l',{}),
  ('m',{}),
  ('n',{2,4}),
  ('o',{}),
  ('p',{}),
  ('q',{}),
  ('r',{}),
  ('s',{}),
  ('t',{}),
  ('u',{}),
  ('v',{}),
  ('w',{}),
  ('x',{}),
  ('y',{}),
  ('z',{})
}

This type of data structure, from a key map to a set of elements, is called multimope. In general, multimapa has two operations: insert value and redeem set.

So, in the multimap of banana (hereafter referred to as mm_banana), we can add s in position 6:

mm_banana.put('s', 6)

// conteúdo de mm_banana modificado sem conjuntos vazios:

{
  ('a',{1,3,5}),
  ('b',{0}),
  ('n',{2,4}),
  ('s',{6})
}

If we add 's',6, 'e',7 and 's',8 to mm_banana, would look like this:

mm_banana.put('s', 6)
mm_banana.put('e', 7)
mm_banana.put('s', 8)

// conteúdo de mm_banana modificado sem conjuntos vazios:

{
  ('a',{1,3,5}),
  ('b',{0}),
  ('e',{7}),
  ('n',{2,4}),
  ('s',{6,8})
}

The decimal representation of a number is a word multimope (as described above), the key alphabet being the decimal digits.

To, from any number x, obtain its decimal representation, we make successive divisions and store the rest. For the sake of simplicity, let’s consider writing the word decimal in little-endian, where the least significant comes first. Thus, the number 0x10 has its representation in decimal word little-endian 61. The following Python code below demonstrates this:

def representacao_base(x, base):
  digit_pos = 0
  while (x > 0):
    digito = x % base
    print("digito %d, posição %d" % (digito, digit_pos));
    x //= base
    digitPos += 1

representacao_base(0x10, 10)

See working on ideone.

Did you notice that I wrote generally for any basis? It is, the advantage of this is that we can verify if a number is Picua on any further basis. Then, 12 would be represented as 0011 on base 2 using little-endian. The endianism does not influence the decision of the number to be Capicua or not, just as writing a contrary word does not influence the fact whether or not it is palíndrome.

To detect that a number is Picua, we use the above algorithm to dismember it and put each digit as the key of the multimapa, each position as the value being inserted into the multimapa. In Java, I achieved this in the following way:

public class Multimapa {
    Set<Integer>[] pos;
    int size;
    int base;

    private void initPos(int base) {
        pos = new HashSet[base];

        for (int i = 0; i < base; i++) {
            pos[i] = new HashSet<>();
        }
    }

    public Multimapa(int n, int base) {
        this.base = base;
        initPos(base);

        if (n == 0) {
            pos[0].add(0);
            size = 1;
            return;
        }
        if (n < 0) {
            n = -n;
        }
        int digitPos = 0;
        while (n > 0) {
            int digit = n % base;
            pos[digit].add(digitPos);

            n /= base;
            digitPos++;
        }
        size = digitPos;
    }
}

Note that since the key is a digit, and a digit in turn is an integer, the multimope is provided by the attribute pos; pos[7] will get the positions in little-endian that digit 7 occupies in the base passed. Detail: the key is an integer and the value is a set (set in English means ensemble in Portuguese, in the mathematical context) of integers.

Thus, to demonstrate that the class Multimapa behaves like the multimope data structure described above, I need to show that it supports the same insertion and rescue operations.

The rescue operation is simple. Given a digit d, pos[d] redeems the matching set. To add the position p to the digit d, just do pos[d].add(p). Note that this is an idempotent operation, so pos[d].add(p); has the same effect as pos[d].add(p); pos[d].add(p); pos[d].add(p);.

Remember the word representation with multimope using empty set for the non-existence of that letter in the word? We are using the same concept here, to facilitate the rescue and addition operations without requiring further negotiations or offending the definition.

To determine whether the number is repeated, we can verify that it has more than one nonzero digit. To do this, simply iterate on the digits and check the size of the sets. If there is only one digit of non-zero size, then the number is repeated. To detect if it is not repeated, just do the logical inversion. Since there is no number option without digit, then the minimum of digits with at least one position in the number is 1. Therefore, the negation of being number with a single digit is having the count > 1.

private static boolean ehNaoRepetido(Multimapa mm) {
    int nDigitosDistintos = 0;

    for (int i = 0; i < mm.base; i++) {
        nDigitosDistintos += mm.pos[i].size() > 0? 1: 0;
    }

    return nDigitosDistintos > 1;
}

To check if a number is Picua in the defined base, we need to ensure that every digit in the position p has another digit in the specular position p'. A special case is the number of the intermediate position with odd-sized numbers: it is its own to speculate, so it can be ignored.

The relationship between p, p' and the size size of the number is:

p + p' = size - 1

      ||
      \/

p' = size - 1 - p

The intermediate position t, which will be ignored, is calculated thus:

t = size % 2 == 1? size/2: -1;

As there are only filled positions from 0, placing -1 will ensure that t will always be ignored for numbers of an even size of digits.

Therefore, the following verification deals with this:

private static boolean ehCapicua(Multimapa mm) {
    int somaSimetrica = mm.size - 1;
    int posIgnorada = mm.size % 2 == 1? mm.size/2: -1;

    for (int d = 0; d < mm.base; d++) {
        for (Integer p: mm.pos[d]) {
            // só tenta verificar se tem o complemento se e somente se não é ignorado
            if (p != posIgnorada) {
                int posComplemento = somaSimetrica - p;

                // se não existe o dígito na posição complementar, então não é capicua
                if (!mm.pos[d].contains(posComplemento)) {
                    return false;
                }
            }
        }
    }
    return true;
}

Follow the complete code used to verify if a number is Picua not repeated in the given bases:

package capicua;

import java.util.HashSet;
import java.util.Set;

public class Multimapa {

    Set<Integer>[] pos;
    int size;
    int base;

    private void initPos(int base) {
        pos = new HashSet[base];

        for (int i = 0; i < base; i++) {
            pos[i] = new HashSet<>();
        }
    }

    public Multimapa(int n, int base) {
        this.base = base;
        initPos(base);

        if (n == 0) {
            pos[0].add(0);
            size = 1;
            return;
        }
        if (n < 0) {
            n = -n;
        }
        int digitPos = 0;
        while (n > 0) {
            int digit = n % base;
            pos[digit].add(digitPos);

            n /= base;
            digitPos++;
        }
        size = digitPos;
    }

    public static void main(String... args) {
        int qntNumerosInteressantes = 0;
        for (int i = 0; i < 99999999; i++) {
            if (julga(i, 10)) {
                System.out.println(i + " é capicua não repetido na base " + 10);
                qntNumerosInteressantes++;
            }
        }

        System.out.println("quantidade de números capicua e não repetidos nas base 10: " + qntNumerosInteressantes);

        qntNumerosInteressantes = 0;
        for (int i = 0; i < 99999999; i++) {
            if (julga(i, 16)) {
                System.out.println(i + " é capicua não repetido na base " + 16);
                qntNumerosInteressantes++;
            }
        }

        System.out.println("quantidade de números capicua e não repetidos nas base 16: " + qntNumerosInteressantes);

        meta_julga(0xffeff, 10); // 1048319
        meta_julga(121, 10);
        meta_julga(1221, 10);
        meta_julga(12721, 10);
        meta_julga(12721, 16); // 31b1
        meta_julga(0xffeff, 16);
        meta_julga(0xffdead, 16);
        meta_julga(0101, 8);
        meta_julga(0171, 8);
        meta_julga(01267621, 8);
        meta_julga(01267421, 8);

        meta_julga(5, 2); // 101
        meta_julga(6, 2); // 110
        meta_julga(7, 2); // 111
        meta_julga(4, 2); // 10
        meta_julga(16, 3); // 121
        meta_julga(10, 3); // 101
        meta_julga(12, 3); // 110
    }

    private static void meta_julga(int n, int base) {
        if (julga(n, base)) {
            System.out.println(n + " é capicua não repetido na base " + base);
        } else {
            System.out.println(n + " não é capicua não repetido na base " + base);
        }
    }

    // retorna verdade se todos os dígitos do número passado forem idênticos
    //
    // algoritmo de detecção: se, por acaso, existirem pelo menos dois dígitos com 1 ou mais posições, então é não repetido.
    // caso seja tudo zero exceto por um único dígito, então é repetido
    private static boolean ehNaoRepetido(Multimapa mm) {
        int nDigitosDistintos = 0;

        for (int i = 0; i < mm.base; i++) {
            nDigitosDistintos += mm.pos[i].size() > 0? 1: 0;
        }

        return nDigitosDistintos > 1;
    }

    // retorna verdadeiro caso seja capicua
    //
    // algoritmo: verifica cada dígito; se for de tamanho `t` ímpar, então o dígito da posição `floor(t/2)` deve ser ignorado
    // para um dígito `d` na posição `p` não ignorado, é necessário existir um outro dígito `d` na posição complementar `p'`, tal que `p + p' = t - 1`
    private static boolean ehCapicua(Multimapa mm) {
        int somaSimetrica = mm.size - 1;
        int posIgnorada = mm.size % 2 == 1? mm.size/2: -1;

        for (int d = 0; d < mm.base; d++) {
            for (Integer p: mm.pos[d]) {
                // só tenta verificar se tem o complemento se e somente se não é ignorado
                if (p != posIgnorada) {
                    int posComplemento = somaSimetrica - p;

                    // se não existe o dígito na posição complementar, então não é capicua
                    if (!mm.pos[d].contains(posComplemento)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    private static boolean julga(int n, int base) {
        Multimapa mm = new Multimapa(n, base);

        if (ehNaoRepetido(mm)) {
            if (ehCapicua(mm)) {
                return true;
            }
        }

        return false;
    }
}

See working on ideone.

9

It is possible to obtain an estimate of how many digits there are in a number using the logarithm in base 10:

  • (log10 1 = 0)
  • (log10 10 = 1)
  • (log10 100 = 2)
  • (log10 1000 = 3)

The logarithm is a strictly increasing function. So, if we round down its value, we have this:

  • From 1 to 9: Result is 0.
  • From 10 to 99: Result is 1.
  • From 100 to 999: Result is 2.
  • From 1000 to 9999: Result is 3.
  • ...

If we add 1 to this value, we have the number of digits in the base 10 of a number. This formula can be generalized to other bases by changing the basis of the logarithm to the corresponding base. With this, we can assemble this function:

function digitos(numero) {
    return numero === 0 ? 1 : Math.floor(Math.log10(numero)) + 1;
}

It is possible to determine whether a number has all the repeated digits based on thereupon. However I took a slightly different approach:

  • A number ending at zero that is not zero itself is never a repetition of digits.

  • Any number consisting of a repetition of digits, when multiplied by 9, will have all the resulting digits except perhaps the first and last as a sequence of nines. This has to do with the fact that in the table of 9, all multiples of 9 between 9 and 90 when they have their digits summed, produces 9 as a result. As a consequence, by multiplying a number that is a repetition by 9, these digits will sum in all positions except the first and last, producing several nines in the middle of the number.

  • Be it r the number which is a repetition of digits and is k=9r. If r end with 1 (let’s call this last digit d), the last digit of k (let’s call it m)) will be 9. If it ends with 2, it will be 8 ((9 x 2 = 18)). If it ends with 3, it’ll be 7 ((9 x 3 = 27)). That is to say, (m = 10 - d), and therefore (m + d = 10). Soon, as we do k + m, we will have 10 as a result in the last digit and we will launch a sequence of "go-ones" in all nines having then a number g such that g = b x 10^p, 1 <= b <= 9, b e N and p e N.

  • If r starts with 1, then k begins with 9. If r starts with 2, then k begins with 1. If r starts with 3, then k starts with 2... This can be seen in the table of 9. By adding 1 to the first digit of k, if you have a number whose first digit is the first digit of r. This means that after the entire "go-ones" sequence of the above item, we have b = d. Soon, as we do g/d, if and only if the result is a power of 10, it is because r is a repetition of digits. We can check if it is a power of 10 if the logarithm in base 10 is integer.

Putting it all together:

function repetido(numero) {
    if (numero === 0) return true;
    var d = numero % 10;
    if (d === 0) return false;
    var g = numero * 9 + d; 
    var n = Math.log10(g / d);
    return n === Math.floor(n);
}

A number can be checked if it is palindromic by separating digits using exponentiation, module and rounding (no strings) and checked in pairs from outside to inside.

Putting it all together:

function palindromo(numero) {
    var numDigitos = digitos(numero);
    for (var i = 0; i < numDigitos / 2; i++) {
        var a = Math.floor(numero / Math.pow(10, i)) % 10;
        var b = Math.floor(numero / Math.pow(10, numDigitos - i - 1)) % 10;
        if (a !== b) return false;
    }
    return true;
}

Finally, a capicuia number is a palindrome that is not a repetition:

function capicua(numero) {
    return !repetido(numero) && palindromo(numero);
}

Below is the code that checks if a number is capicuia (for any number of digits). It also has a test that checks whether the implementation is correct for all numbers from 0 to 99999. The test was made to show only the numbers that went wrong (and the way it is does not show any, it works for everyone). After that, it shows some examples for testing.

function digitos(numero) {
    return numero === 0 ? 1 : Math.floor(Math.log10(numero)) + 1;
}

function repetido(numero) {
    if (numero === 0) return true;
    var d = numero % 10;
    if (d === 0) return false;
    var g = numero * 9 + d; 
    var n = Math.log10(g / d);
    return n === Math.floor(n);
}

function palindromo(numero) {
    var numDigitos = digitos(numero);
    for (var i = 0; i < numDigitos / 2; i++) {
        var a = Math.floor(numero / Math.pow(10, i)) % 10;
        var b = Math.floor(numero / Math.pow(10, numDigitos - i - 1)) % 10;
        if (a !== b) return false;
    }
    return true;
}

function capicua(numero) {
    return !repetido(numero) && palindromo(numero);
}

function testeNumero(numero) {

    var numeroStr = "" + numero;
    var numDigitos = numeroStr.length;

    var palindromoStr = numeroStr.split("").reverse().join("") === numeroStr;

    var repetidoStr = true;
    for (var i = 1; i < numDigitos; i++) {
        if (numeroStr.charAt(i) !== numeroStr.charAt(0)) {
            repetidoStr = false;
            break;
        }
    }

    if (digitos(numero) !== numDigitos) {
        document.write("Falhou digitos com " + numero + ".<br>");
    }

    if (palindromo(numero) !== palindromoStr) {
        document.write("Falhou palindromo com " + numero + ".<br>");
    }

    if (repetido(numero) !== repetidoStr) {
        document.write("Falhou repetido com " + numero + ".<br>");
    }

    if (capicua(numero) !== (!repetidoStr && palindromoStr)) {
        document.write("Falhou capicua com " + numero + ".<br>");
    }
}

function teste() {
   document.write("Começando...<br>");
   for (var i = 0; i < 100000; i++) {
        testeNumero(i);
   }
   document.write("Teste concluído.<br>");
}

teste();
document.write("53035 é capicua? " + (capicua(53035) ? "Sim" : "Não") + "<br>");
document.write("53035 é repetido? " + (repetido(53035) ? "Sim" : "Não") + "<br>");
document.write("53567 é capicua? " + (capicua(53567) ? "Sim" : "Não") + "<br>");
document.write("8765678 é capicua? " + (capicua(8765678) ? "Sim" : "Não") + "<br>");
document.write("369 é capicua? " + (capicua(369) ? "Sim" : "Não") + "<br>");
document.write("363 é capicua? " + (capicua(363) ? "Sim" : "Não") + "<br>");
document.write("55555 é capicua? " + (capicua(55555) ? "Sim" : "Não") + "<br>");
document.write("55555 é repetido? " + (repetido(55555) ? "Sim" : "Não") + "<br>");
document.write("55455 é repetido? " + (repetido(55455) ? "Sim" : "Não") + "<br>");

I tried to find a formula that would check whether it is palindromic not only without using strings, but also without using loops and recursion. In the meantime, I couldn’t, and I had to settle for a bow tie. In this attempt, the best I could prove is that every palindromic number with an even number of digits is a multiple of 11 (but not every multiple of 11 is palindromic).

5

I did some examples in C#, but converting the number to string:

First:

public static bool Capicua(int x) //0.046s
{
    string s = x.ToString();
    int l = s.Length/2;


    for (int i =0; i<= l; i++)
    {
        if (s[i] != s[s.Length-1-i])
        {
            return false;
        }
    }

    return true;

}

According to:

public static bool Capicua2(int x) //0.063s
{
    string s = x.ToString();
    return s == Reverse(s);
}

public static string Reverse(string s )
{
    char[] charArray = s.ToCharArray();
    Array.Reverse( charArray );
    return new string( charArray );
}

Auxiliary method to remove numbers where all digits are equal:

public static bool TodosIguais(int x)
{
    string s = x.ToString();
    char c = s[0];
    for (int i =1; i< s.Length;i++)
    {
        if (s[i] != c)
        {
            return false;
        }
    }

    return true;

}

Running the application:

public static void Main()
{
    int encontrados = 0;
    for (int i =10000; i <= 90000; i++)
    {
        //if (!TodosIguais(i) && Capicua(i))
        //if (!TodosIguais(i) && Capicua2(i))
        if (CapicuaLINQ(i))
        {
            Console.WriteLine("Capicua: "+ i);
            encontrados++;
        }
    }
    Console.WriteLine("Encontrados: "+ encontrados);
}

Upshot:

Capicua: 10001
Capicua: 10101
Capicua: 10201
Capicua: 10301
Capicua: 10401
Capicua: 10501
Capicua: 10601
...
Capicua: 89698
Capicua: 89798
Capicua: 89898
Capicua: 89998
Encontrados: 792

However, the code posted by LINQ as response, does not make the conversion to string, which is better, being faster the execution time. I just made the change so I didn’t take the numbers that all the digits are the same:

///LINQ
public static bool CapicuaLINQ(int x) //0.019s
{
    int num;
    int original = num = x;     
    int rev = 0;
    int digAnt =  num % 10;
    bool todosIguais = true;

    while (num > 0)
    {
        int dig = num % 10; //Captura cada dígito

        if (dig != digAnt)
        {
            todosIguais = false;
        }

        rev = rev * 10 + dig; 
        // (^) Adiciona o dígito na variável 'rev'.
        // Como usamos a base 10, tudo o que já existe 
        // em rev precisa ser mulplicado por 10

        num = num / 10;
        // Controla o loop
    }

    return original == rev && !todosIguais;

}

I put in the . Netfiddle: https://dotnetfiddle.net/IWXftW

  • 2

    Yes, I was hoping for an answer turning into xD string As inefficient as I think it is an alternative that needed to be contained here

  • 1

    Missing capicuas started by 9, such as 92529.

  • 1

    @Victorstafusa the for only goes as far as 90000, just raise his limit =]

4

One logic I found was the following, separating 3 pieces of information from the 5-digit number, which I call x:

  1. Take the first 2 digits (I’ll call left2).
  2. Take the last 2 digits and reverse their order (I’ll call right2_reverse).
  3. Just take the first digit (I’ll call x1).

The middle number (the third) is derisory and does not enter the question.

With this 3 information, just apply the comparison:

The left2 is equal to right2_reverse?

If YES, so it is Capicua.

But you don’t want numbers where all the digits are equal, like 00000, 11111 etc...

Just split the number x by its first digit x1 (after all are equal). If the result is different from 11.111, then it is Capicua without having all the same digits.

Whenever any number where all digits are equal is divided by 1 digit of that number, the result will be a sequence of 1 with the same number of digits:

Ex. 99.999 / 9 = 11.111

The problem is the number 00,000, which if divided by 0 gives error, due to the mathematical rule where "no number can be divided by zero".

In this case, just check whether the absolute value of the number x is zero. If it is, just ignore.

Examples:

Be the number x = 37073

left2 = 37
right2_reverse = 37

They’re the same, so it’s Picua.


Be the number x = 37075

left2 = 37
right2_reverse = 57

They’re different, so nay is Picua.

I made a Javascript code for verification:

digitos = 5;

for(x=0;x<=99999;x++){
	if( x.toString().length < digitos ){
		while(x.toString().length < digitos){
			x = "0"+x;
		}
	}
	left2 = x.toString().substring(0,2);
	right2_1 = x.toString().substring(x.toString().length-2,x.toString().length-1);
	right2_2 = x.toString().substring(x.toString().length-1,x.toString().length);
	right2_reverse = right2_2+right2_1;
	
	x1 = parseFloat(x.toString().substring(0,1));

	if(left2 == right2_reverse && x/x1 != 11111 && Math.abs(x) != 0){
		capicua = " capicua!";
	}else{
		capicua = "";
	}
	$("#teste").append(x+capicua+"<br />");
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="teste">
</div>

Another programmatic way would be to divide the number x for its mirrored value, if the result is 1, then Capicua.

  • Important note for the reader: as the number has five digits, x1 is guaranteed to be distinct from zero, so the split will always be valid

  • 1

    It is worth noting that the number 00,000, mathematically, does not have 5 digits, as it will only be 0. So the problem of dividing by 0 does not exist, in fact. The same goes for the numbers you add the 0 to the left. In the mathematical domain, this is not necessary, because a value like 05650 is not Capicua because it is actually 5650 (4 digits).

  • @Andersoncarloswoss Vc is right. But in this case the number is more a string than number itself. It’s like the lottery, where there are numbers with zero on the left, like, 05,381.

  • 1

    I understand your point, I just don’t agree to analyze the number as string in a problem we are dealing with in the mathematical domain. In programming, it would be as if xbe the type int, then do x = 01 ends up being the same as x = 1.

  • @Andersoncarloswoss But the term "palindromes" applies to words, not numbers. It’s okay that it can be applied to numbers, but in this case, the number becomes a word: two hundred and twelve is a palindrome, when writing 212.

  • That is why the question asks for "capicuas", which is the equivalent of palindrome for numbers, but do not get me wrong, I just thought it necessary to comment on this detail. This does not necessarily imply that your answer is wrong and needs correction :D

  • @Andersoncarloswoss There is a small difference between one term and another. Capicua is applied to digits, while palindrome is to words.

  • Anyway, I could understand rsrs.

  • @Andersoncarloswoss Thanks for the editing, it was perfect.

  • 2

    @Andersoncarloswoss 01 is not 1 in ES3 huahuehaeuh

Show 5 more comments

4

Already now a solution batuteira (I only know how to make of these ): generate them instead of recognizing them.

The general idea is: a 5 digit chart has the following structure abcde in which:

  • ab is the inverse of de that is to say de = b*10+a (or ab%10*10 + int(ab/10))

    inv(ac)= mod(ab,10)×10 + int(ab/10)
    
  • so the set of 5 digit capicuas is

    { ab×1000 + c×100 + inv(ab) |  ab ∈ 10..99, c ∈ 0..9 }
    
  • to check if a number is Picua: "yes" se ele ∈ conjunto

To create a concrete program, for example Using Perl, we can write:

perl -E 'say for map {$a=$_; 
                      map {$a*1000+$_*100 +$a%10*10+int($a/10)} 
                          0..9
                     } 
                     10..99 '

to generate the 5 digit capicuas;

To recognize them: BEGIN{calculates set} for each line: tell if it belongs

perl -nlE '
  BEGIN{ $p{$_}=1 
         for map {$a=$_;map {$a*1000+$_*100+$a%10*10+int($a/10)} 0..9} 11..99} 
  say "yes" if $p{$_}'
  • 2

    But the question is "how to identify" is only of numbers with 5 digits. And as I do not know the language, the explanation of logic here is essential.

  • I liked the idea of generating, but I’m with @Articuno : that for me is something arcane and magical! If it were even possible to put the exit in ideone you would be helping me to understand Perl

  • 1

    Speaking of generating number, you gave me an idea of how to respond in Prolog...

  • @Jeffersonquesado, I put together an explanation with sets in understanding. They think they understand?

  • I understand your good will, but the purpose of the question is to identify numbers capicuas, not generate them.

  • Article: I know (so to say that it is cheating) identify(x) = x set generated.

Show 1 more comment

Browser other questions tagged

You are not signed in. Login or sign up in order to post.