De acuerdo con el teorema de Midy , si el período de un decimal periódico para 
, donde p es primo y es una fracción reducida , tiene un número par de dígitos, entonces dividir la porción periódica por la mitad y sumar da una string de 9s.
Ejemplos:
a = 1 y p = 7
1/7 = 0.14285714285.
Entonces 1/7 es un decimal periódico con 142857 repetido. Ahora, según el teorema, tiene un número par de dígitos repetidos, es decir, 142857. Además, si lo dividimos en dos mitades, obtenemos 142 y 857. Por lo tanto, al sumar estos dos, obtenemos 999, que es una string de 9 y coincide con nuestro teorema.
a = 2 y p = 11
2/11 = 0.18181818181..
Aquí, el decimal periódico es 18. Ahora, esto es par en número, por lo tanto, 1+8 = 9, lo que nuevamente muestra la validez del teorema de Midy.
Dados el numerador y el denominador, la tarea es encontrar si el número de punto flotante resultante sigue el teorema de Midy o no.
Enfoque:
simulemos el proceso de conversión de fracción a decimal. Miremos la parte donde ya hemos descubierto la parte entera que es piso (numerador/denominador). Ahora nos queda (resto = numerador% denominador) / denominador.
Si recuerdas el proceso de conversión a decimal, en cada paso hacemos lo siguiente:
- Multiplica el resto por 10.
- Agregar resto/denominador al resultado.
- Resto = resto % denominador.
En cualquier momento, si el resto se convierte en 0, hemos terminado.
Sin embargo, cuando hay una secuencia recurrente, el resto nunca se convierte en 0. Por ejemplo, si miras 1/3, el resto nunca se convierte en 0.
A continuación hay una observación importante:
si comenzamos con el resto ‘rem’ y si el resto se repite en cualquier momento, los dígitos entre las dos apariciones de ‘rem’ se siguen repitiendo.
Entonces, la idea es almacenar los restos vistos en un mapa. Cada vez que se repite un resto, devolvemos la secuencia anterior a la siguiente aparición.
A continuación se muestra la implementación del teorema de Midy:
C++
// C++ implementation as a
// proof of the Midy's theorem
#include <bits/stdc++.h>
using namespace std;
// Returns repeating sequence of a fraction.
// If repeating sequence doesn't exits,
// then returns -1
string fractionToDecimal(int numerator, int denominator)
{
string res;
/* Create a map to store already seen remainders
remainder is used as key and its position in
result is stored as value. Note that we need
position for cases like 1/6. In this case,
the recurring sequence doesn't start from first
remainder. */
map<int, int> mp;
mp.clear();
// Find first remainder
int rem = numerator % denominator;
// Keep finding remainder until either remainder
// becomes 0 or repeats
while ((rem != 0) && (mp.find(rem) == mp.end()))
{
// Store this remainder
mp[rem] = res.length();
// Multiply remainder with 10
rem = rem * 10;
// Append rem / denr to result
int res_part = rem / denominator;
res += to_string(res_part);
// Update remainder
rem = rem % denominator;
}
return (rem == 0) ? "-1" : res.substr(mp[rem]);
}
// Checks whether a number is prime or not
bool isPrime(int n)
{
for (int i = 2; i <= n / 2; i++)
if (n % i == 0)
return false;
return true;
}
// If all conditions are met,
// it proves Midy's theorem
void Midys(string str, int n)
{
int l = str.length();
int part1 = 0, part2 = 0;
if (!isPrime(n))
{
cout << "Denominator is not prime, "
<< "thus Midy's theorem is not applicable";
}
else if (l % 2 == 0)
{
for (int i = 0; i < l / 2; i++)
{
part1 = part1 * 10 + (str[i] - '0');
part2 = part2 * 10 + (str[l / 2 + i] - '0');
}
cout << part1 << " + " << part2 << " = "
<< (part1 + part2) << endl;
cout << "Midy's theorem holds!";
}
else
{
cout << "The repeating decimal is of odd length "
<< "thus Midy's theorem is not applicable";
}
}
// Driver code
int main()
{
int numr = 2, denr = 11;
string res = fractionToDecimal(numr, denr);
if (res == "-1")
cout << "The fraction does not have repeating decimal";
else {
cout << "Repeating decimal = " << res << endl;
Midys(res, denr);
}
return 0;
}
Java
// Java implementation as a
// proof of the Midy's theorem
import java.util.*;
class GFG{
// Returns repeating sequence of a fraction.
// If repeating sequence doesn't exits,
// then returns -1
static String fractionToDecimal(int numerator,
int denominator)
{
String res = "";
/* Create a map to store already seen remainders
remainder is used as key and its position in
result is stored as value. Note that we need
position for cases like 1/6. In this case,
the recurring sequence doesn't start from first
remainder. */
HashMap<Integer, Integer> mp = new HashMap<>();
// Find first remainder
int rem = numerator % denominator;
// Keep finding remainder until either remainder
// becomes 0 or repeats
while ((rem != 0) && !mp.containsKey(rem))
{
// Store this remainder
mp.put(rem, res.length());
// Multiply remainder with 10
rem = rem * 10;
// Append rem / denr to result
int res_part = rem / denominator;
res += res_part + "";
// Update remainder
rem = rem % denominator;
}
return (rem == 0) ? "-1" : res.substring(mp.get(rem));
}
// Checks whether a number is prime or not
static boolean isPrime(int n)
{
for(int i = 2; i <= n / 2; i++)
if (n % i == 0)
return false;
return true;
}
// If all conditions are met,
// it proves Midy's theorem
static void Midys(String str, int n)
{
int l = str.length();
int part1 = 0, part2 = 0;
if (!isPrime(n))
{
System.out.print("Denominator is not prime, " +
"thus Midy's theorem is not " +
"applicable");
}
else if (l % 2 == 0)
{
for(int i = 0; i < l / 2; i++)
{
part1 = part1 * 10 + (str.charAt(i) - '0');
part2 = part2 * 10 + (str.charAt(l / 2 + i) - '0');
}
System.out.println(part1 + " + " + part2 +
" = " + (part1 + part2));
System.out.print("Midy's theorem holds!");
}
else
{
System.out.print("The repeating decimal is " +
"of odd length thus Midy's "+
"theorem is not applicable");
}
}
// Driver code
public static void main(String []args)
{
int numr = 2, denr = 11;
String res = fractionToDecimal(numr, denr);
if (res == "-1")
System.out.print("The fraction does not " +
"have repeating decimal");
else
{
System.out.println("Repeating decimal = " + res);
Midys(res, denr);
}
}
}
// This code is contributed by rutvik_56
Python3
# Python3 implementation as a
# proof of the Midy's theorem
# Returns repeating sequence of a fraction.
# If repeating sequence doesn't exits,
# then returns -1
def fractionToDecimal(numerator, denominator):
res = ""
''' Create a map to store already seen remainders
remainder is used as key and its position in
result is stored as value. Note that we need
position for cases like 1/6. In this case,
the recurring sequence doesn't start from first
remainder. '''
mp = dict()
# Find first remainder
rem = numerator % denominator
# Keep finding remainder until either remainder
# becomes 0 or repeats
while ((rem != 0) and (rem not in mp)):
# Store this remainder
mp[rem] = len(res)
# Multiply remainder with 10
rem = rem * 10
# Append rem / denr to result
res_part = (rem // denominator)
res += str(res_part)
# Update remainder
rem = rem % denominator
return ["-1", res[mp[rem]:]][rem != 0]
# Checks whether a number is prime or not
def isPrime(n):
for i in range(2, 1 + n // 2):
if (n % i == 0):
return False
return True
# If all conditions are met,
# it proves Midy's theorem
def Midys(str, n):
l = len(str)
part1 = 0
part2 = 0
if (not isPrime(n)):
print("Denominator is not prime, thus Midy's theorem is not applicable")
elif (l % 2 == 0):
for i in range(l // 2):
part1 = part1 * 10 + int(str[i])
part2 = part2 * 10 + int(str[(l // 2) + i])
print(part1, "+", part2, "=", (part1 + part2))
print("Midy's theorem holds!")
else:
print(
"The repeating decimal is of odd length thus Midy's theorem is not applicable")
# Driver code
numr = 2
denr = 11
res = fractionToDecimal(numr, denr)
if (res == "-1"):
print("The fraction does not have repeating decimal")
else:
print("Repeating decimal =", res)
Midys(res, denr)
# This code is contributed by phasing17.
C#
// C# implementation as a
// proof of the Midy's theorem
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Returns repeating sequence of a fraction.
// If repeating sequence doesn't exits,
// then returns -1
static String fractionToDecimal(int numerator,
int denominator)
{
String res = "";
/* Create a map to store already seen remainders
remainder is used as key and its position in
result is stored as value. Note that we need
position for cases like 1/6. In this case,
the recurring sequence doesn't start from first
remainder. */
Dictionary<int,int> mp = new Dictionary<int,int>();
// Find first remainder
int rem = numerator % denominator;
// Keep finding remainder until either remainder
// becomes 0 or repeats
while ((rem != 0) && !mp.ContainsKey(rem))
{
// Store this remainder
mp[rem]= res.Length;
// Multiply remainder with 10
rem = rem * 10;
// Append rem / denr to result
int res_part = rem / denominator;
res += res_part + "";
// Update remainder
rem = rem % denominator;
}
return (rem == 0) ? "-1" : res.Substring(mp[rem]);
}
// Checks whether a number is prime or not
static bool isPrime(int n)
{
for(int i = 2; i <= n / 2; i++)
if (n % i == 0)
return false;
return true;
}
// If all conditions are met,
// it proves Midy's theorem
static void Midys(String str, int n)
{
int l = str.Length;
int part1 = 0, part2 = 0;
if (!isPrime(n))
{
Console.Write("Denominator is not prime, " +
"thus Midy's theorem is not " +
"applicable");
}
else if (l % 2 == 0)
{
for(int i = 0; i < l / 2; i++)
{
part1 = part1 * 10 + (str[i] - '0');
part2 = part2 * 10 + (str[l / 2 + i] - '0');
}
Console.WriteLine(part1 + " + " + part2 +
" = " + (part1 + part2));
Console.Write("Midy's theorem holds!");
}
else
{
Console.Write("The repeating decimal is " +
"of odd length thus Midy's "+
"theorem is not applicable");
}
}
// Driver code
public static void Main(string []args)
{
int numr = 2, denr = 11;
string res = fractionToDecimal(numr, denr);
if (res == "-1")
Console.Write("The fraction does not " +
"have repeating decimal");
else
{
Console.WriteLine("Repeating decimal = " + res);
Midys(res, denr);
}
}
}
// This code is contributed by pratham76.
Javascript
// JavaScript implementation as a
// proof of the Midy's theorem
// Returns repeating sequence of a fraction.
// If repeating sequence doesn't exits,
// then returns -1
function fractionToDecimal(numerator, denominator)
{
let res = "";
/* Create a map to store already seen remainders
remainder is used as key and its position in
result is stored as value. Note that we need
position for cases like 1/6. In this case,
the recurring sequence doesn't start from first
remainder. */
let mp = {};
// Find first remainder
let rem = numerator % denominator;
// Keep finding remainder until either remainder
// becomes 0 or repeats
while ((rem != 0) && (!mp.hasOwnProperty(rem)))
{
// Store this remainder
mp[rem] = res.length;
// Multiply remainder with 10
rem = rem * 10;
// Append rem / denr to result
let res_part = Math.floor(rem / denominator);
res += (res_part.toString());
// Update remainder
rem = rem % denominator;
}
return (rem == 0) ? "-1" : res.substr(mp[rem]);
}
// Checks whether a number is prime or not
function isPrime(n)
{
for (var i = 2; i <= n / 2; i++)
if (n % i == 0)
return false;
return true;
}
// If all conditions are met,
// it proves Midy's theorem
function Midys(str, n)
{
var l = str.length;
var part1 = 0, part2 = 0;
if (!isPrime(n))
{
console.log("Denominator is not prime, thus Midy's theorem is not applicable");
}
else if (l % 2 == 0)
{
for (var i = 0; i < l / 2; i++)
{
part1 = part1 * 10 + parseInt(str[i]);
part2 = part2 * 10 + parseInt(str[Math.floor(l / 2) + i]);
}
console.log(part1 + " + " + part2 + " = " + (part1 + part2));
console.log("Midy's theorem holds!");
}
else
{
console.log("The repeating decimal is of odd length thus Midy's theorem is not applicable");
}
}
// Driver code
let numr = 2;
let denr = 11;
let res = fractionToDecimal(numr, denr);
if (res == "-1")
console.log("The fraction does not have repeating decimal");
else
{
console.log("Repeating decimal = " + res);
Midys(res, denr);
}
// This code is contributed by phasing17.
Producción :
Repeating decimal = 18 1 + 8 = 9 Midy's theorem holds!
Puede encontrar más información sobre el teorema de Midy en
http://www.kurims.kyoto-u.ac.jp/EMIS/journals/INTEGERS/papers/h2/h2.pdf
http://digitalcommons.unl.edu/cgi/viewcontent .cgi?article=1047&context=mathfacpub