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. Por ejemplo, 1/7 = 0,14285714285… 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.
En el teorema de Extended Midy, si dividimos la porción repetida de a/p en m dígitos, entonces su suma es un múltiplo de 10 m -1.
Supongamos que a = 1 y p = 17,
a/p = 1/17 = 0,0588235294117647…
Entonces, 0588235294117647 es la parte repetida de la expansión decimal de 1/17. Su parte repetida tiene 16 dígitos y se puede dividir en m dígitos donde m puede ser 2, 4, 8.
Si consideramos m = 4 entonces 0588235294117647 se puede dividir en 16/4 = 4 números y si sumamos estos 4 números entonces el resultado debe ser un múltiplo de 10 4 – 1 = 9999, es decir,
0588 + 2352 + 9411 + 7647 = 19998 = 2*9999
C++
// C++ program to demonstrate extended
// 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. */
unordered_map<int, int> mp;
// 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 Extended Midy's theorem
void ExtendedMidys(string str, int n, int m)
{
if (!isPrime(n)) {
cout << "Denominator is not prime, "
<< "thus Extended Midy's "
<< "theorem is not applicable";
return;
}
int l = str.length();
int part1 = 0, part2 = 0;
if (l % 2 == 0 && l % m == 0) {
// Dividing repeated part into m parts
int part[m] = { 0 }, sum = 0, res = 0;
for (int i = 0; i < l; i++) {
int var = i / m;
part[var] = part[var] * 10 + (str[i] - '0');
}
// Computing sum of parts.
for (int i = 0; i < m; i++) {
sum = sum + part[i];
cout << part[i] << " ";
}
// Checking for Extended Midy
cout << endl;
res = pow(10, m) - 1;
if (sum % res == 0)
cout << "Extended Midy's theorem holds!";
else
cout << "Extended Midy's theorem"
<< " doesn't hold!";
}
else if (l % 2 != 0) {
cout << "The repeating decimal is"
<< " of odd length thus Extended "
<< "Midy's theorem is not applicable";
}
else if (l % m != 0) {
cout << "The repeating decimal can "
<< "not be divided into m digits";
}
}
// Driver code
int main()
{
int numr = 1, denr = 17, m = 4;
string res = fractionToDecimal(numr, denr);
if (res == "-1")
cout << "The fraction does not"
<< " have repeating decimal";
else {
cout << "Repeating decimal = " << res << endl;
ExtendedMidys(res, denr, m);
}
return 0;
}
Java
// Java program to demonstrate extended
// 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 Extended Midy's theorem
static void ExtendedMidys(String str, int n, int m)
{
if (!isPrime(n))
{
System.out.print("Denominator is not prime, " +
"thus Extended Midy's theorem " +
"is not applicable");
return;
}
int l = str.length();
int part1 = 0, part2 = 0;
if (l % 2 == 0 && l % m == 0)
{
// Dividing repeated part into m parts
int []part = new int[m];
int sum = 0, res = 0;
for(int i = 0; i < l; i++)
{
int var = i / m;
part[var] = part[var] * 10 +
(str.charAt(i) - '0');
}
// Computing sum of parts.
for(int i = 0; i < m; i++)
{
sum = sum + part[i];
System.out.print(part[i] + " ");
}
// Checking for Extended Midy
System.out.println();
res = (int)Math.pow(10, m) - 1;
if (sum % res == 0)
System.out.print("Extended Midy's " +
"theorem holds!");
else
System.out.print("Extended Midy's " +
"theorem doesn't hold!");
}
else if (l % 2 != 0)
{
System.out.print("The repeating decimal is of " +
"odd length thus Extended Midy's " +
"theorem is not applicable");
}
else if (l % m != 0)
{
System.out.print("The repeating decimal can " +
"not be divided into m digits");
}
}
// Driver code
public static void main(String []args)
{
int numr = 1, denr = 17, m = 4;
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);
ExtendedMidys(res, denr, m);
}
}
}
// This code is contributed by rutvik_56
C#
// C# program to demonstrate extended
// 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 Extended Midy's theorem
static void ExtendedMidys(string str, int n, int m)
{
if (!isPrime(n))
{
Console.Write("Denominator is not prime, " +
"thus Extended Midy's theorem " +
"is not applicable");
return;
}
int l = str.Length;
if (l % 2 == 0 && l % m == 0)
{
// Dividing repeated part into m parts
int []part = new int[m];
int sum = 0, res = 0;
for(int i = 0; i < l; i++)
{
int var = i / m;
part[var] = part[var] * 10 +
(str[i] - '0');
}
// Computing sum of parts.
for(int i = 0; i < m; i++)
{
sum = sum + part[i];
Console.Write(part[i] + " ");
}
// Checking for Extended Midy
Console.WriteLine();
res = (int)Math.Pow(10, m) - 1;
if (sum % res == 0)
Console.Write("Extended Midy's " +
"theorem holds!");
else
Console.Write("Extended Midy's " +
"theorem doesn't hold!");
}
else if (l % 2 != 0)
{
Console.Write("The repeating decimal is of " +
"odd length thus Extended Midy's " +
"theorem is not applicable");
}
else if (l % m != 0)
{
Console.Write("The repeating decimal can " +
"not be divided into m digits");
}
}
// Driver code
public static void Main(string []args)
{
int numr = 1, denr = 17, m = 4;
string res = fractionToDecimal(numr, denr);
if (res == "-1")
Console.Write("The fraction does not " +
"have repeating decimal");
else
{
Console.WriteLine("Repeating decimal = " + res);
ExtendedMidys(res, denr, m);
}
}
}
// This code is contributed by pratham76.
Producción:
Repeating decimal = 0588235294117647 588 2352 9411 7647 Extended Midy's theorem holds!
Publicación traducida automáticamente
Artículo escrito por shivani.mittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA