# '친절한 수론 길라잡이'
# 연습문제 15.9 사교수 (socialbe numbers)
# s(n) : 전체 약수에서 자신을 제외한 진약수의 합을 말한다.
# s(n) = n : 완전수
# s(n) = m, s(m) = n : 친화수 amicable pair
# s(n1) = n2, s(n2) = n3,... s(n(t-1)) = nt, s(nt) = s(n1) : 위수가 t인 사교수
from number_util import * # 정수론 관련 함수 모음. 일일이 함수를 위에 적기가 귀찮아서
# 함수 의존성 (왼쪽에서 오른쪽으로 호출함)
# isSociableNumbers : sigma_fun : getDivisor2 : factorize2 : isPrime
# getSociableNumbers : sigma_fun : getDivisor2 : factorize2 : isPrime
numbers = [14316, 19116, 31704, 47616, 83328, 177792, 295488,
629072, 589786, 294896, 358336, 418904, 366556, 274924,
275444, 243760, 376736, 381028, 285778, 152990, 122410,
97946, 48976, 45946, 22976, 22744, 19916, 17716]
# 위의 숫자 목록이 사교수들인지 판정하기
def isSociableNumbers(numbers, info=False):
length = len(numbers) # 순환하는 이 수들의 개수가 위수(order)다, 물론 사교수라면.
isSociable = True # 사교수 여부를 체크하는 flag
for i, n in enumerate(numbers):
if i == length - 1: # 마지막 항목에 이르렀다면
i = -1 # 대조 항목의 인덱스인 i+1을 0(numbers의 첫번째 항목)으로 만들기 위해.
jinhap = sigma_fun(n) - n # 진합은 전체 약수 합에서 자신을 빼면 된다
if jinhap == numbers[i+1]: # 진합과 다음 항목값을 비교해서 동일하다면
if info:
print(f"{n}의 진약수의 합은 {numbers[i+1]}. 조건 만족!")
else: # 진합과 다음 항목값이 다르다면, 더 검사해볼 필요도 없이 루프를 중단해도 됨
if info:
print(f"{n}의 진약수의 합 {jinhap}가 {numbers[i+1]}와 다릅니다. 중단합니다!")
isSociable = False
break
if info:
if isSociable:
print("상기 수들은 사교수입니다.", f"위수는 {length}")
else: # False면
print("상기 수들은 사교수가 아닙니다.")
return isSociable
print(isSociableNumbers(numbers, True))
# 연습문제 15.9.a
# a) 16000보다 작은 수 중에서 5개의 수로 이루어진 사교수가 있다. 이 사교수를 찾아라.
# 순서도
# 1. 시작할 수를 정한다.
# 2. 진합을 구해서 그 값이 1이거나 n과 같은 값(완전수)이면 해당 목록을 파기하고 다음 수로 넘어감.
# 3. else: 이전에 구한 수 중에서 같은 값이 있는지 체크하고, 같은 값이 있으면
# 그것까지의 거리가 위수 + 1이 된다. 그것들을 슬라이스하면 그것이 사교수들이다.
# 사교수의 범위를 정해주면 사교수를 찾는 함수
# max_try: 하나의 시작 수에 대해 진약수 합을 연이어 찾는 횟수
def getSociableNumbers(start, end, max_try=30):
for num in range(start, end):
jinhap = num # num을 다치지 않게 복사해서 사용한다.
lst = [] # 연속적인 진약수의 합(진합)을 저장할 리스트
lst.append(num) # num을 첫번째 원소로 저장한다
while True:
prev = jinhap # 첫 실행이면 jinhap은 num 이므로 prev 는 num 이 되고,
# 두 번째부터는 jinhap은 앞서 계산된 진약수의 합이므로,
# prev에는 앞서의 진합이 저장된다.
jinhap = sigma_fun(jinhap) - jinhap # 이전 진합(jinhap)을 넣어 새 진합(jinhap)을 구한다.
# 진합이 1(막다른 골목)이거나 이전 진합과 같은 값(그러면 완전수)이면 사교수가 아니므로 다음 수 검사로 넘어감
if jinhap < 2 and jinhap == prev:
break
# 이제 목록에 같은 값이 있는지 확인한다. 있다면
# 1) 완전수인 경우: 직전 진합과 진합이 같다. 이 경우는 위의 조건문에서 걸러졌음
# 2) 친화수인 경우: [220, 284]의 예라면, 284의 진합은 220이므로 220이 이미 목록(리스트)에 있다.
# 이때 목록에서 220의 인덱스는 0이므로 목록[0:]으로 슬라이싱하면 [220, 284]를
# 최종 예비 사교수 목록으로 얻을 수 있고 이의 위수는 len(목록)으로 2가 된다.
# 위수가 2라는 소리는, (넓은 의미의) 사교수에서 위수가 2이면 친화수가 된다는 뜻이고,
# 본격적인 사교수는 위수가 3일 때부터 취급한다는 뜻이다.
# 3) 사교수(위수 3이상)인 경우: 가령 [A, B, C, D, E, F, G](A, B,...G는 모두 숫자~)라는
# 진약수 합 목록이 있고 G의 진약수 합이 D라면, D의 인덱스는 3이다.
# 목록[3:]으로 슬라이싱하면 [D, E, F, G]라는 새로운 진합 목록을 얻는데, 이는 순환하는
# 사교수 목록이다. D->E->F->G->D->E.... 가 되니까.. 위수는 목록의 원소 개수로 4가 된다.
if jinhap in lst: # 구한 진약수 합이 목록에 이미 있다면
idx = lst.index(jinhap) # 해당 숫자의 인덱스를 찾아서
lst = lst[idx:] # 순환하는 부분만 잘라낸다
if len(lst) >= 3: # 위수가 해당값 이상이면 목적 사교수로 보고 출력한다.
print(num, lst)
break
else:
lst.append(jinhap) # 목록에 새로운 진약수 합과 같은 값이 없으므로 목록에 추가한다.
# 목록에 진합을 추가하다가 한참 뒤에 사교수(순환)의 첫 원소가 생길 수 있다.
# 가령 진합 목록이 [A, B, C, D, ....., Z, a, b, c, d, e, f, g](모두 숫자~) 이렇게 되어가는데,
# g의 진합이 d가 되어 d의 인덱스를 찾아내어 목록[인덱스:]로 [d, e, f, g]를 슬라이싱할 수 있다.
# 사교수 순환의 첫 원소인 d가 이렇게 한참 뒤에 출현할 수 있기 때문에 목록의 갯수에 약간
# 여유를 두는 게 좋다(찾고자 하는 위수의 2~3배 정도?). 목록의 개수를 지나치게 크게 하면 엉뚱한 데서 한없이 찾을 수 있으므로 주의.
if len(lst) >= max_try: break # 충분히 찾았는데도 사교수를 찾지 못했다면 그 숫자는 건너뛴다
getSociableNumbers(2, 16000, 10)
# 검산
a = [12496, 14288, 15472, 14536, 14264]
print(isSociableNumbers(a, True))
# getSociableNumbers(1000000, 10000000000, 12)
# 위의 범위로 하다가 너무 오래 걸려서 검사 범위를 줄임. 아래 출력된 범위는 위의 것으로
# 하다가 Ctrl+C로 중단시킨 결과임.
getSociableNumbers(1000000, 1190621, 12)
# 검산
a = [2115324, 3317740, 3649556, 2797612]
b = [1264460, 1547860, 1727636, 1305184]
c = [3265940, 3707572, 3370604, 2784580]
print(isSociableNumbers(a, True))
print(isSociableNumbers(b, True))
print(isSociableNumbers(c, True))출력:
14316의 진약수의 합은 19116. 조건 만족!
19116의 진약수의 합은 31704. 조건 만족!
31704의 진약수의 합은 47616. 조건 만족!
47616의 진약수의 합은 83328. 조건 만족!
83328의 진약수의 합은 177792. 조건 만족!
177792의 진약수의 합은 295488. 조건 만족!
295488의 진약수의 합은 629072. 조건 만족!
629072의 진약수의 합은 589786. 조건 만족!
589786의 진약수의 합은 294896. 조건 만족!
294896의 진약수의 합은 358336. 조건 만족!
358336의 진약수의 합은 418904. 조건 만족!
418904의 진약수의 합은 366556. 조건 만족!
366556의 진약수의 합은 274924. 조건 만족!
274924의 진약수의 합은 275444. 조건 만족!
275444의 진약수의 합은 243760. 조건 만족!
243760의 진약수의 합은 376736. 조건 만족!
376736의 진약수의 합은 381028. 조건 만족!
381028의 진약수의 합은 285778. 조건 만족!
285778의 진약수의 합은 152990. 조건 만족!
152990의 진약수의 합은 122410. 조건 만족!
122410의 진약수의 합은 97946. 조건 만족!
97946의 진약수의 합은 48976. 조건 만족!
48976의 진약수의 합은 45946. 조건 만족!
45946의 진약수의 합은 22976. 조건 만족!
22976의 진약수의 합은 22744. 조건 만족!
22744의 진약수의 합은 19916. 조건 만족!
19916의 진약수의 합은 17716. 조건 만족!
17716의 진약수의 합은 14316. 조건 만족!
상기 수들은 사교수입니다. 위수는 28
True
----------------------------
9464 [12496, 14288, 15472, 14536, 14264]
12032 [12496, 14288, 15472, 14536, 14264]
12496 [12496, 14288, 15472, 14536, 14264]
14264 [14264, 12496, 14288, 15472, 14536]
14288 [14288, 15472, 14536, 14264, 12496]
14536 [14536, 14264, 12496, 14288, 15472]
15472 [15472, 14536, 14264, 12496, 14288]
15476 [12496, 14288, 15472, 14536, 14264]
(구한 수를 보면 순환하는 특성을 가진 한 가지 배열이다.)
---------------- 검산 부분 ----------
12496의 진약수의 합은 14288. 조건 만족!
14288의 진약수의 합은 15472. 조건 만족!
15472의 진약수의 합은 14536. 조건 만족!
14536의 진약수의 합은 14264. 조건 만족!
14264의 진약수의 합은 12496. 조건 만족!
상기 수들은 사교수입니다. 위수는 5
True
--------------------
1103920 [2115324, 3317740, 3649556, 2797612]
1118620 [1264460, 1547860, 1727636, 1305184]
1190620 [3265940, 3707572, 3370604, 2784580]
1202720 [1264460, 1547860, 1727636, 1305184]
1230524 [1264460, 1547860, 1727636, 1305184]
(구한 수 배열을 보면, 총 3가지 종류다)
-------------------- 검산 부분 -----------
2115324의 진약수의 합은 3317740. 조건 만족!
3317740의 진약수의 합은 3649556. 조건 만족!
3649556의 진약수의 합은 2797612. 조건 만족!
2797612의 진약수의 합은 2115324. 조건 만족!
상기 수들은 사교수입니다. 위수는 4
True
1264460의 진약수의 합은 1547860. 조건 만족!
1547860의 진약수의 합은 1727636. 조건 만족!
1727636의 진약수의 합은 1305184. 조건 만족!
1305184의 진약수의 합은 1264460. 조건 만족!
상기 수들은 사교수입니다. 위수는 4
True
3265940의 진약수의 합은 3707572. 조건 만족!
3707572의 진약수의 합은 3370604. 조건 만족!
3370604의 진약수의 합은 2784580. 조건 만족!
2784580의 진약수의 합은 3265940. 조건 만족!
상기 수들은 사교수입니다. 위수는 4
True