(정수론/파이썬) 친화수 (Amicable Pair)

# '친절한 수론 길라잡이'
# 연습문제 15.8 친화수 (amicable pair)
# m의 진약수의 합이 n이고 m의 진약수의 합이 n인 두 수 m, n을 친화수라 부른다.
# 예)  220의 진약수의 합: 284
#      284의 진약수의 합: 220
#
# a) 수 (m, n)이 친화수가 되기 위한 필요충분조건은 sigma(n)과 sigma(m)이 모두 n + m임을 증명하라.
# 오른쪽으로 가는 증명: (m, n)이 친화수면 => sigma(n) = sigma(m) = n + m
#   (m, n)이 친화수면, sigma(m) - m = n 이다(좌변은 전체 약수의 합에서 자신을 뺀 것이므로 m의 진약수의 합이다)
#   (m, n)이 친화수면, sigma(n) - n = m 이다(좌변은 전체 약수의 합에서 자신을 뺀 것이므로 n의 진약수의 합이다)
#   따라서 좌변의 -m과 -n을 오른쪽으로 넘기면, sigma(m) = n + m, sigma(n) = m + n 이 되어서 증명된다.
# 왼편으로 가는 증명: sigma(n) = sigma(m) = n + m 이면, (m, n)은 친화수
#   sigma(n) = n + m 이면 이항하여 sigma(n) - n = m이 되고, 좌변은 n의 전체 약수 합에서 자신을 뺀 것이므로 
#        진약수 합이 되고 그것이 m 이라고 하였으므로 친화수 조건 만족
#   sigma(m) = n + m 이면 이항하여 sigma(m) - m = n이 되고, 좌변은 m의 전체 약수 합에서 자신을 뺀 것이므로
#        진약수 합이 되고 그것이 n과 같다고 하였으므로 친화수 조건 만족
#  따라서 오른쪽으로 가는 증명, 왼편으로 가는 증명 모두 증명하였으므로 a) 명제 증명 끝.
# 
# b) 다음 수들이 친화수임을 증명하여라.
#
# 두 수가 친화수인지 검사하는 함수

from number_util import * 

def isAmicablePair(m, n):
  hap = m + n
  # m의 전체 약수 합이 m+n이고, n의 전체 약수 합이 n + m이면 m ,n은 친화수이다.
  return sigma_fun(m) == hap and sigma_fun(n) == hap

pairs = [(220, 284), (1184, 1210), (2620, 2924), (5020, 5564), (6232, 6368), 
           (10744, 10856), (12285, 14595)]

# 목록의 숫자 쌍이 친화수인지 검사하는 코드.
for m, n in pairs:
  if isAmicablePair(m, n):
    print(f"{m}과 {n}은 amicable pair입니다.")
print()
# 함수를 사용하지 않고 친화수를 검사하는 코드. 함수를 풀어헤친 코드
for m, n in pairs:
  hap = m + n
  if sigma_fun(m) == hap and sigma_fun(n) == hap: # isAmicablePair 함수 내용을 그대로 쓰고 있다
    print(f"{m}과 {n}은 amicable pair입니다.")

print("\n")
# 연습문제 15.8.d
# 타비트 벤 코라의 공식에 e=2를 대입하면 친화수 (220, 284)를 얻는다. 이 방법을 이용하여
# 두 번째 친화수를 찾아보자. 컴퓨터로 소인수분해를 할 수 있다면, 이 공식을 이용하여 더 많은
# 친화수를 찾아보자.

for e in range(2, 20):  # range 값을 넓혀 좀더 검사해볼 수 있다.
  p = 3*(2**(e-1)) - 1
  q = 2*p + 1
  r = (p + 1)*(q + 1) - 1

  # p, q, r 이 모두 홀수인 소수라면 친화수를 구할 수 있다.
  if p % 2 != 0 and isPrime(p) and q % 2 != 0 and isPrime(q) and r % 2 != 0 and isPrime(r):
    m = (2**e)*p*q
    n = (2**e)*r
  
    print(f"e : {e}, amicable_pair = ({m}, {n})")
  else:
    print(f"e : {e}에서 친화수를 구할 수 없습니다.")

220과 284은 amicable pair입니다.
1184과 1210은 amicable pair입니다.
2620과 2924은 amicable pair입니다.
5020과 5564은 amicable pair입니다.
6232과 6368은 amicable pair입니다.
10744과 10856은 amicable pair입니다.
12285과 14595은 amicable pair입니다.

220과 284은 amicable pair입니다.
1184과 1210은 amicable pair입니다.
2620과 2924은 amicable pair입니다.
5020과 5564은 amicable pair입니다.
6232과 6368은 amicable pair입니다.
10744과 10856은 amicable pair입니다.
12285과 14595은 amicable pair입니다.


e : 2, amicable_pair = (220, 284)
e : 3에서 친화수를 구할 수 없습니다.
e : 4, amicable_pair = (17296, 18416)
e : 5에서 친화수를 구할 수 없습니다.
e : 6에서 친화수를 구할 수 없습니다.
e : 7, amicable_pair = (9363584, 9437056)
e : 8에서 친화수를 구할 수 없습니다.
e : 9에서 친화수를 구할 수 없습니다.
e : 10에서 친화수를 구할 수 없습니다.
e : 11에서 친화수를 구할 수 없습니다.
e : 12에서 친화수를 구할 수 없습니다.
e : 13에서 친화수를 구할 수 없습니다.
e : 14에서 친화수를 구할 수 없습니다.
e : 15에서 친화수를 구할 수 없습니다.
e : 16에서 친화수를 구할 수 없습니다.
e : 17에서 친화수를 구할 수 없습니다.
e : 18에서 친화수를 구할 수 없습니다.
e : 19에서 친화수를 구할 수 없습니다.