Teoría de Números (Datos Interesantes y Algoritmos)

Las preguntas basadas en varios conceptos de teoría de números y diferentes tipos de números se hacen con bastante frecuencia en los concursos de programación. En este artículo, discutimos algunos hechos y algoritmos famosos:

Datos interesantes :

1. Todos los números palindrómicos de 4 dígitos son divisibles por 11.
2. Si repetimos dos veces un número de tres dígitos, para formar un número de seis dígitos. El resultado será divisible por 7, 11 y 13, y dividir por los tres te dará tu número original de tres dígitos.
3. Un número de forma 2 ^N tiene exactamente N+1 divisores. Por ejemplo 4 tiene 3 divisores, 1, 2 y 4.
4. Para calcular la suma de factores de un número , podemos encontrar el número de factores primos y sus exponentes. Sean p ₁ , p ₂ , … p _k factores primos de n. Sean a ₁ , a ₂ , .. a _k potencias máximas de p ₁ , p ₂ , .. p _k respectivamente que dividen n, es decir, podemos escribir n como n = (p ₁ ^{a ₁} )*(p ₂ ^{a ₂} )* … (p _k ^{a _k} ) .

Sum of divisors = (1 + p1 + p12 ... p1a1) * 
                  (1 + p2 + p22 ... p2a2) *
                  .............................................
                  (1 + pk + pk2 ... pkak) 

We can notice that individual terms of above 
formula are Geometric Progressions (GP). We
can rewrite the formula as.

Sum of divisors = (p1a1+1 - 1)/(p1 -1) * 
                  (p2a2+1 - 1)/(p2 -1) *
                  ..................................
                  (pkak+1 - 1)/(pk -1)

1. Para un producto de N números, si tenemos que restar una constante K tal que el producto obtenga su valor máximo, luego restarlo de un valor más grande tal que el valor más grande-k sea mayor que 0. Si tenemos que restar una constante K tal que el producto obtenga su valor mínimo, luego restarlo del valor más pequeño donde el valor más pequeño-k debe ser mayor que 0
2. Conjetura de Goldbach: Todo número par mayor que 2 se puede expresar como la suma de 2 números primos.
3. Números perfectos o Números amistosos : Los números perfectos son aquellos números que son iguales a la suma de sus divisores propios. Ejemplo: 6 = 1 + 2 + 3
4. Números de Lychrel : Son aquellos números que no pueden formar un palíndromo cuando se invierten repetidamente y se suman a sí mismos. Por ejemplo, 47 no es un número Lychrel ya que 47 + 74 = 121
5. Conjetura de Lemoine : Cualquier entero impar mayor que 5 puede expresarse como la suma de un primo impar (todos los primos excepto 2 son impares) y un semiprimo par. Un número semiprimo es el producto de dos números primos. Esto se llama la conjetura de Lemoine.
6. Último teorema de Fermat : De acuerdo con el teorema, no hay tres enteros positivos a, b, c que satisfagan la ecuación,  para cualquier valor entero de n mayor que 2. Para n = 1 y n = 2, la ecuación tiene infinitas soluciones.

Algoritmos de teoría de números

MCD y MCM 

1. MCD y MCM
2. MCM de array
3. MCD de array
4. Algoritmos euclidianos básicos y extendidos

¡Artículos recientes sobre GCD y LCM! Factorización prima y divisores:

1. factores primos
2. Algoritmo Rho de Pollard para factorización prima
3. Encontrar todos los divisores de un número natural
4. Suma de todos los divisores propios de un número natural
5. Factorización prima usando Sieve O (log n) para consultas múltiples
6. Encuentra la cortesía de un número
7. Imprima números primos en un rango dado usando C++ STL
8. k-ésimo factor primo de un número dado
9. Números de Smith

¡Artículos recientes sobre factores primos! Números de Fibonacci:

1. Números de Fibonacci
2. Datos interesantes sobre los números de Fibonacci
3. ¿Cómo verificar si un número dado es el número de Fibonacci?
4. Teorema de Zeckendorf (Representación de Fibonacci no vecina)

¡Artículos recientes sobre los números de Fibonacci! Números catalanes:

1. números catalanes
2. Aplicaciones de los Números Catalanes

¡Artículos recientes sobre los números catalanes! Aritmética modular :

1. Exponenciación Modular (Potencia en Aritmética Modular)
2. Inverso multiplicativo modular
3. División Modular
4. orden multiplicativo
5. Buscar raíz cuadrada en Módulo p | Conjunto 1 (Cuando p está en forma de 4*i + 3)
6. Buscar raíz cuadrada en Módulo p | Conjunto 2 (algoritmo Shanks Tonelli)
7. Criterio de Euler (Comprobar si existe raíz cuadrada bajo módulo p)
8. Multiplica números enteros grandes por debajo de módulo grande
9. Encuentra la suma del módulo K del primer N número natural
10. ¿Cómo calcular mod de un número grande?
11. Clase BigInteger en Java
12. Módulo 10^9+7 (1000000007)
13. ¿Cómo evitar el desbordamiento en la multiplicación modular?
14. Algoritmo RSA en Criptografía
15. Encuentra (a^b)%m donde ‘a’ es muy grande
16. Encuentra el poder del poder bajo mod de un número primo

¡Artículos recientes sobre aritmética modular! Función de Euler Totient:

1. Función totiente de Euler
2. Función Totient de Euler optimizada para evaluaciones múltiples
3. Función Totient de Euler para todos los números menores o iguales que n
4. Raíz primitiva de un número primo n módulo n

Cálculos nCr:

1. Coeficiente Binomial
2. Calcule nCr % p | Set 1 (Introducción y Solución de Programación Dinámica)
3. Calcule nCr % p | Conjunto 2 (Teorema de Lucas)
4. Calcule nCr % p | Conjunto 3 (usando el pequeño teorema de Fermat)

Teorema chino del resto: 

1. Serie 1 (Introducción)
2. Conjunto 2 (Implementación basada en módulo inverso)
3. Comprobación de redundancia cíclica y división Modulo-2
4. Uso del teorema chino del resto para combinar ecuaciones modulares

Factoriales :

1. Factorial
2. La fórmula de Legendre (Dados p y n, ¡encuentra la x más grande tal que p^x divide a n!)
3. Suma de divisores del factorial de un número
4. Contar divisores de factorial
5. Calcula n! bajo módulo p
   1. Teorema de Wilson
   2. Prueba de primalidad | Conjunto 1 (Introducción y Método Escolar)
   3. Prueba de primalidad | Juego 2 (Método Fermat)
   4. Prueba de primalidad | Conjunto 3 (Miller-Rabin)
   5. Prueba de primalidad | Conjunto 4 (Solovay-Strassen)
   6. Hecho 22 | (2^x + 1 y primo)
   7. Lema de Euclides
   8. Tamiz de Eratóstenes
   9. Tamiz segmentado
   10. Tamiz de Atkin
   11. Tamiz de Sundaram para imprimir todos los números primos menores que n
   12. Tamiz de Eratóstenes en complejidad de tiempo 0(n)
   13. Comprobar si un número grande es divisible por 3 o no
   14. Comprobar si un número grande es divisible por 11 o no
   15. Para comprobar la divisibilidad de cualquier número grande por 999
   16. Números de Carmichael
   17. Generadores de grupo cíclico finito bajo adición
   18. Mida un litro usando dos recipientes y suministro de agua infinito
   19. Programa para encontrar el último dígito del enésimo número de Fibonacci
   20. MCD de dos números cuando uno de ellos puede ser muy grande
   21. Encuentra el último dígito de a^b para números grandes
   22. Resto con 7 para números grandes
   23. Cuente todos los subconjuntos que tengan una suma divisible por k
   24. Dividir un número en dos partes divisibles
   25. Número de substrings divisibles por 6 en una string de enteros
   26. ‘Problemas de práctica’ sobre aritmética modular
   27. ‘Problemas de práctica’ sobre teoría de números
   28. Haz una pregunta sobre teoría de números
   29. Padován , OESIS