Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # This program find the solutions of diophantine equation
- # x^x-y^y=p, p prime number
- # The theory show that the number of solution is limited to 7 triples x y p
- # x must be prime, y is equal to x-1, p must be of opportune form
- # the primality test is implemented using miller rabin algorithm
- P=500
- import random
- def power(x, y, p):
- res = 1;
- x = x % p;
- while (y > 0):
- if (y & 1):
- res = (res * x) % p;
- y = y>>1; # y = y/2
- x = (x * x) % p;
- return res;
- def miillerTest(d, n):
- a = 2 + random.randint(1, n - 4);
- x = power(a, d, n);
- if (x == 1 or x == n - 1):
- return True;
- while (d != n - 1):
- x = (x * x) % n;
- d *= 2;
- if (x == 1):
- return False;
- if (x == n - 1):
- return True;
- return False;
- def isPrime( n, k):
- if (n <= 1 or n == 4):
- return False;
- if (n <= 3):
- return True;
- d = n - 1;
- while (d % 2 == 0):
- d //= 2;
- for i in range(k):
- if (miillerTest(d, n) == False):
- return False;
- return True;
- # Driver Code
- # Number of iterations
- k = 4;
- print("x y p")
- for x in range(2,P+1):
- if(isPrime(x, k)):
- if(isPrime(x**x-(x-1)**x, k)):
- print(x,x-1,x**x-(x-1)**x)
Advertisement
Add Comment
Please, Sign In to add comment