Advertisement
Kaelygon

counterexample attempt

Nov 11th, 2024 (edited)
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.94 KB | None | 0 0
  1. import math
  2. from sympy import isprime
  3.  
  4. # Find all Pythagorean triples (a^2 + b^2 = P^2)
  5. def find_pythagorean_triples(P):
  6.     PSquare = P*P
  7.     triples = []
  8.     for a in range( 1, math.isqrt(PSquare // 2) ): # P^2=2*a^2 -> a=sqrt(P^2/2)
  9.         bSquare = PSquare - a*a # b^2 = P^2-a^2
  10.         b = math.isqrt(bSquare) # b = sqrt(P^2-a^2)
  11.         if b*b == bSquare: #check if integer
  12.             triples.append((a, b))
  13.     return triples
  14.  
  15.  
  16. # Find all representations as a sum of two squares (P = c^2 + d^2)
  17. def find_sums_of_two_squares(P,triples):
  18.     for c in range( 1, math.isqrt(P // 2) ):
  19.         d_squared = P - c*c
  20.         d = math.isqrt(d_squared)
  21.         if d.is_integer():
  22.             cd2 = 2 * c * d
  23.             for a, b in triples:
  24.                 if cd2 == a or cd2 == b: #return first valid solution 2*c*d=(a or b)
  25.                     return c, d, cd2
  26.     return None, None, None
  27.  
  28. # Main function to find counterexamples
  29. def find_counterexample(checkRange):
  30.     no_div_4_composites = []
  31.     no_div_4_primes = []
  32.     cd2_invalid_primes = []
  33.     cd2_invalid_composites = []
  34.  
  35.     for P in range(checkRange[0],checkRange[1]):
  36.         # Get all Pythagorean triples
  37.         triples = find_pythagorean_triples(P)
  38.         if not triples:
  39.             continue  # Skip if no triples exist
  40.  
  41.         # Get all sum of two squares
  42.         c, d, cd2 = find_sums_of_two_squares(P, triples)
  43.         if not c:
  44.             continue  # Skip if no sum-of-squares representation exists
  45.  
  46.         # Categorize based on validity and primality
  47.         if cd2 % 4 != 0:
  48.             if isprime(P):
  49.                 no_div_4_primes.append(P)
  50.             else:
  51.                 no_div_4_composites.append(P)
  52.         elif not cd2:
  53.             if isprime(P):
  54.                 cd2_invalid_primes.append(P)
  55.             else:
  56.                 cd2_invalid_composites.append(P)
  57.  
  58.     return no_div_4_primes, no_div_4_composites, cd2_invalid_primes, cd2_invalid_composites
  59.  
  60. # Example usage
  61. checkRange = 1,100
  62. no_div_4_primes, no_div_4_composites, cd2_invalid_primes, cd2_invalid_composites = find_counterexample(checkRange)
  63.  
  64. # Print results
  65. print("Numbers which neither Pythagorean side is divisible by 4")
  66. if no_div_4_primes:
  67.     print(f"Primes: {no_div_4_primes[:10]}")
  68. if no_div_4_composites:
  69.     print(f"Composites: {no_div_4_composites[:10]}")
  70.  
  71. print("\nNumbers which neither Pythagorean side is 2*c*d")
  72. if cd2_invalid_primes:
  73.     print(f"Primes: {cd2_invalid_primes[:10]}")
  74. if cd2_invalid_composites:
  75.     print(f"Composites: {cd2_invalid_composites[:10]}")
  76.  
  77. if (no_div_4_primes or no_div_4_composites) and \
  78.    (cd2_invalid_primes or cd2_invalid_composites):
  79.     # Combine all lists and sort them
  80.     all_invalid = sorted(no_div_4_primes + no_div_4_composites + cd2_invalid_primes + cd2_invalid_composites)
  81.  
  82.     # Print combined list
  83.     print("\nNumbers which break either rule")
  84.     if all_invalid:
  85.         print(f"Combined lists: {all_invalid[:10]}")
  86.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement