[알고리즘] Ramanujan–Hardy Number (라마누잔–하디의 수: 1729)

🧠 라마누잔과 하디의 일화

하디(Hardy)가 병문안 중 라마누잔에게 말함:
“오늘 탄 택시 번호가 1729였는데, 참 평범한 숫자더군.”
라마누잔이 대답함:
“아닙니다! 그건 아주 흥미로운 숫자입니다.
1729는 두 가지 다른 방식으로 두 정수의 세제곱 합으로 표현되는 가장 작은 수입니다.”

즉,

1729 = 1³ + 12³ = 9³ + 10³

그래서 1729는 “라마누잔의 수” 또는 **“Taxicab Number”**로 알려져 있어.

---

🧩 Taxicab Numbers란?

Taxicab(n): 두 정수의 세제곱 합으로 표현되는 서로 다른 방법이 n개 이상 존재하는 수

• Taxicab(1) = 2 = 1³ + 1³
• Taxicab(2) = 1729
• Taxicab(3) = 87539319
• Taxicab(4) = 6963472309248

하지만 1729는 가장 유명하고 대중적이야.

 

 

🧾 의사코드 (Pseudocode)

Function find_taxicab_numbers(limit):
    Create a dictionary to store cube sums and their pairs

    For a from 1 to limit:
        For b from a to limit:
            sum = a³ + b³
            If sum not in dictionary:
                Add sum with pair (a, b)
            Else:
                Append (a, b) to existing list for that sum

    For each sum in dictionary:
        If it has 2 or more pairs:
            Print sum and the pairs

---

🐍 Python 코드

아래는 1729처럼 두 개 이상의 세제곱 쌍을 가지는 수를 찾는 Python 코드야.

def find_taxicab_numbers(limit):
    from collections import defaultdict

    cube_sums = defaultdict(list)

    for a in range(1, limit + 1):
        for b in range(a, limit + 1):
            result = a**3 + b**3
            cube_sums[result].append((a, b))

    for number, pairs in cube_sums.items():
        if len(pairs) >= 2:
            print(f"{number} can be expressed as:")
            for pair in pairs:
                print(f"  {pair[0]}³ + {pair[1]}³")
            print()

# 예: 1부터 100까지 검색
find_taxicab_numbers(100)

🔍 출력 예시 일부:

1729 can be expressed as:
  1³ + 12³
  9³ + 10³

4104 can be expressed as:
  2³ + 16³
  9³ + 15³

---

🎯 흥미 포인트

• 이 코드는 Taxicab(2) 수준까지만 찾지만, 더 높은 차수로도 확장 가능해
• 라마누잔이 머릿속으로 이런 걸 어떻게 찾았는지는 여전히 수수께끼
• 하디는 나중에 “라마누잔의 수학은 마치 신과 대화한 듯했다”고 회상함