ossifrage

Find x,y,N s.t. x³ - y³ - 2xy - N = 0

Mar 8th, 2022 (edited)
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.26 KB | None | 0 0
  1. # Find natural numbers x, y, N that satisfy x³ - y³ - 2xy - N = 0
  2. # See https://www.youtube.com/watch?v=2Zov0KXPswk for more
  3.  
  4. def f(n):
  5.     # Find all x,y ∈ ℕ s.t. x³ - y³ - 2xy - N = 0
  6.     # Limits:
  7.     # y < x because y³ + 2xy + N = x³, and x,y,N are all non-negative
  8.     # x < N + 1, 0therwise there can be no y that satisfies this relation
  9.     #   Rationale: if x,y = N+1,N,
  10.     #   then x³ - y³ - 2xy - N = (N+1)³ - N³ - 2N(N+1) - N = (N+1)² > 0
  11.     #   any smaller value of y will also give a result greater than zero
  12.     #   so there is no value of y for which x³ - y³ - 2xy - N = 0
  13.     result = []
  14.     for x in range(1,n+1):
  15.         x_cubed_minus_n = x**3 - n
  16.         # Find corresponding y by binary search (if it exists)
  17.         ymin, ymax = 0, x-1
  18.         while ymin <= ymax:
  19.             y = (ymin + ymax) // 2
  20.             z = x_cubed_minus_n - y**3 - 2*x*y
  21.             if z == 0:
  22.                 result.append((x,y))
  23.                 break
  24.             elif z > 0:
  25.                 ymin = y + 1
  26.             else:
  27.                 ymax = y - 1
  28.     return result
  29.  
  30.  
  31. for n in range(1000):
  32.     result = f(n)
  33.     # If there are one or more solutions for this value of n,
  34.     # print them out
  35.     if len(result) > 0:
  36.         print(n,result)
  37.  
Add Comment
Please, Sign In to add comment