Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Find natural numbers x, y, N that satisfy x³ - y³ - 2xy - N = 0
- # See https://www.youtube.com/watch?v=2Zov0KXPswk for more
- def f(n):
- # Find all x,y ∈ ℕ s.t. x³ - y³ - 2xy - N = 0
- # Limits:
- # y < x because y³ + 2xy + N = x³, and x,y,N are all non-negative
- # x < N + 1, 0therwise there can be no y that satisfies this relation
- # Rationale: if x,y = N+1,N,
- # then x³ - y³ - 2xy - N = (N+1)³ - N³ - 2N(N+1) - N = (N+1)² > 0
- # any smaller value of y will also give a result greater than zero
- # so there is no value of y for which x³ - y³ - 2xy - N = 0
- result = []
- for x in range(1,n+1):
- x_cubed_minus_n = x**3 - n
- # Find corresponding y by binary search (if it exists)
- ymin, ymax = 0, x-1
- while ymin <= ymax:
- y = (ymin + ymax) // 2
- z = x_cubed_minus_n - y**3 - 2*x*y
- if z == 0:
- result.append((x,y))
- break
- elif z > 0:
- ymin = y + 1
- else:
- ymax = y - 1
- return result
- for n in range(1000):
- result = f(n)
- # If there are one or more solutions for this value of n,
- # print them out
- if len(result) > 0:
- print(n,result)
Add Comment
Please, Sign In to add comment