정수의 두 번째 소인수 중앙값이 37인 이유

(grossack.site)

2P by GN⁺ 2023-11-13 | ★ favorite | 댓글 1개

자연수 전체에서 균등하게 뽑는 일은 불가능하므로, 1부터 N까지 균등 선택한 뒤 N → ∞ 극한을 보는 방식으로 “무작위 정수”를 정의함
Those Fascinating Numbers에는 무작위 정수의 두 번째 소인수가 37보다 작을 확률이 대략 1/2이라는 사실이 나오며, 이를 밀도 계산과 실험으로 확인함
작은 소수는 정수의 작은 소인수로 자주 등장하므로, 37처럼 작은 수가 중앙값이 될 수 있다는 직관이 생김
De Koninck와 Tenenbaum의 방법은 에라토스테네스의 체처럼 특정 소수로 나누어지는 조건을 조합해 λ₂(p)를 계산함
λ₂(p)를 소수별로 더하면 37에서 누적 밀도가 약 0.5002에 도달하고, N=10⁷ 직접 계산값 0.5002501과도 매우 가까움

37이라는 수가 나온 출처

Those Fascinating Numbers 서문에는 37이 정수의 두 번째 소인수의 중앙값이라는 문장이 있음
- 무작위로 고른 정수의 두 번째 소인수가 37보다 작을 확률이 대략 1/2이라는 내용임
처음에는 37이 너무 작아 믿기 어려워 보이지만, 작은 소수가 정수의 작은 소인수로 자주 나타난다는 점을 생각하면 그럴듯해짐
- 예를 들어 정수의 약 절반은 2를 가장 작은 소인수로 가짐
목표는 이 사실을 직접 실험하고, De Koninck와 Tenenbaum의 논문을 바탕으로 왜 37이 나오는지 계산하는 것임

“무작위 정수”를 정의하는 방법

자연수 전체에는 균등분포가 없으므로, 먼저 큰 수 N을 고정함
1부터 N까지의 정수 중 하나를 무작위로 고른 뒤, N → ∞일 때 확률의 극한을 봄
N이 작을 때는 각 정수의 두 번째 소인수를 직접 구해 중앙값을 확인할 수 있음
N=10⁷로 실행하면 누적 확률 근사값이 0.5002501로 나옴
- 온라인 SageCell에서는 이 정도 크기의 인수분해가 오래 걸려 타임아웃될 수 있어 로컬 실행이 필요함

λ₂(p): p가 두 번째 소인수일 밀도

De Koninck와 Tenenbaum의 논문 Sur la loi de répartition du k-ième facteur premier d’un entier는 p가 두 번째 소인수가 되는 정수의 밀도를 λ₂(p) 로 둠
계산의 핵심은 에라토스테네스의 체와 비슷하게, 특정 소수로 나누어지는지 여부를 조합해 밀도를 세는 것임
두 번째 소인수가 5인 경우는 두 가지뿐임
- 2^a 3^0 5^b ...: 2와 5의 배수이고 3의 배수가 아닌 수
- 2^0 3^a 5^b ...: 3과 5의 배수이고 2의 배수가 아닌 수
첫 번째 경우의 밀도는 1/2 × 2/3 × 1/5 = 1/15
두 번째 경우의 밀도는 (1 - 1/2) × 1/3 × 1/5 = 1/30
두 집합은 서로 겹치지 않으므로 합산할 수 있고, 두 번째 소인수가 5인 정수의 밀도는 1/10이 됨

일반 소수 p에 대한 공식

p가 두 번째로 작은 소인수가 되려면, p보다 작은 소수 중 하나 q는 포함되고 q와 p를 제외한 p보다 작은 소수 r들은 포함되지 않아야 함
이 조건은 다음과 같은 꼴의 소인수분해로 표현됨

[ p^b q^a \prod_{q \neq r \lt p} r^0 ]

각 q < p에 대해 밀도를 계산하고 합하면 다음 공식이 나옴

[ \lambda_2(p) = \sum_{q \lt p} \frac{1}{p} \frac{1}{q} \prod_{q \neq r \lt p} \left ( 1 - \frac{1}{r} \right ) ]

같은 식은 다음처럼 정리할 수 있음

[ \lambda_2(p) = \frac{1}{p} \left[ \prod_{q \lt p} \left(1 - \frac{1}{q}\right) \right] \sum_{q \lt p} \frac{1}{q} \left(1 - \frac{1}{q}\right)^{-1} ]

37이 중앙값이 되는 계산

찾고 싶은 소수 (p^)는 두 번째 소인수가 (p^) 이하일 밀도 합이 약 1/2가 되는 지점임

[ \lambda_2(2) + \lambda_2(3) + \lambda_2(5) + \ldots + \lambda_2(p^*) \approx \frac{1}{2} ]

λ₂(p)를 구현해 소수별로 더하면, 37에서 누적 밀도가 약 1/2에 도달함
계산된 실제 기대 밀도는 약 0.5002임
직접 인수분해 기반 실험에서 N=10⁷일 때 나온 값 0.5002501도 이 값과 매우 가까움

k번째 소인수로의 확장

k번째 소인수가 p일 밀도 λₖ(p) 의 일반 공식은 다음과 같음

[ \lambda_k(p) = \frac{1}{p} \left[ \prod_{q \lt p} \left(1 - \frac{1}{q}\right) \right] s_{k-1}(p) ]

여기서 (s_j(p) = \sum \frac{1}{m})이며, 합은 정확히 j개의 소인수를 갖고 그 소인수들이 모두 p보다 작은 m에 대해 취함
k번째 소인수 중앙값 (p_k^*)의 점근식은 다음과 같음

[ \log \log p_k^* = k - b + O\left(\frac{1}{\sqrt{k}}\right) ]

여기서 b는 아래 값임

[ b = \frac{1}{3} + \gamma - \sum_p \left( \log((1-1/p)^{-1}) - 1/p \right) ]

(\gamma)는 Euler-Mascheroni Constant임

GN⁺ 2023-11-13 [-]

Hacker News 의견들

여기서 37 자체에 특별히 흥미로운 게 있다는 뜻은 아님
오히려 흥미로운 사실은 여기서 유한한 중앙값이 존재한다는 것 자체임. 그게 성립하면, 중앙값을 목록의 원소로 정의했기 때문에 어떤 소수 하나가 될 수밖에 없음. 이 목록에서는 우연히 37일 뿐, 다른 값이어도 됨
37이 정말 흥미로워지려면 중앙값이 집합 바깥의 값도 될 수 있도록 정의를 완화했는데도 극한이 여전히 37로 수렴해야 함. 그랬다면 꽤 놀라웠을 것
- N → ∞ 극한을 취하면 목록은 계속 커짐. 따라서 37의 등장 횟수도 계속 늘어나고, 전체 값 중 점근적으로 일정한 비율, 약 0.963%를 차지함
  37보다 작은 값은 약 49.061%뿐이고, 37보다 큰 값은 약 49.975%뿐임. 어느 시점 이후로 짝수 N에서는 50% 지점 양쪽에 항상 37이 두 개 있게 되므로 중앙값은 다른 값이 아니라 정확히 37임. 더 긴 설명은 다른 댓글에 써둠 [0]
  [0] https://news.ycombinator.com/item?id=38245162
- N 이하 정수들의 두 번째 소인수 중앙값이 특정한 수가 된다는 게 자명한가? 이 중앙값이 계속 커진다고 보는 것도 그만큼 그럴듯하지 않나?
- 아무 흥미로운 말도 붙일 수 없는 첫 번째 수가 뭔지 궁금함
- 중앙값은 그냥 특정 백분위수일 뿐, 마법처럼 특별한 값은 아님
  중앙값의 존재는 다른 모든 백분위수에도 극한이 있을 가능성을 시사함. 더 나아가 어떤 수에 대해서든, 두 번째 소인수가 그 수보다 큰 정수들의 극한 비율이 존재할 수 있고, 37에서는 그 비율이 우연히 0.5인 셈
- 여기서 “이 목록”이 무슨 뜻임? 결과를 오해한 것처럼 보임
글이 처음 떠오른 질문인 “도대체 이걸 어떻게 증명하지?”에 대한 답을 이렇게 명확히 설명해줘서 좋았음
흥미롭게도 37은 최적 정지 문제 / 비서 문제에도 등장함
- 그 문제는 모르고 검색할 마음도 없지만, 아마 이유는 1/e ≈ 0.36787944라서라고 추측할 수 있음
- 사람들이 1부터 100 사이의 무작위 숫자를 떠올리라고 하면 37을 가장 많이 고른다고도 함
우연히도 37은 첫 번째 비정규 소수이기도 함. 페르마의 마지막 정리가 어려운 이유와 관련 있음
https://en.wikipedia.org/wiki/Regular_prime
“두 번째 소수가 2인 수는 0.000000000000000”이라고 했는데, 글 제목은 중복 없는이라는 표현을 명시하지 않아도 맞는 건가?
- 수학을 읽을 때는 용어의 “올바른” 해석을 머릿속으로 보완하는 게 중요한 부분임. 적절한 상세함의 양은 보통 대상 독자에 따라 달라짐
  영어로 표기를 완전히 명시하면 대체로 장황해지기 때문임. “두 번째 중복 없는 소수”라고 썼다면 누군가는 “두 번째로 작은”이나 “오름차순”도 써야 하는 것 아니냐고 할 수 있음. 논문에서는 이런 용어를 보통 더 정확한, 하지만 완전히 정밀하지는 않은 수학 표기와 함께 형식적으로 정의함
  꼬투리를 잡으려는 게 아니라, 수학에서 “보이지 않는” 부분을 사람이 일일이 명시하게 하지 않고 추론하게 하는 것이 정리 증명기의 사용성을 크게 높인다는 점 때문임. Andrej Bauer의 관련 발표가 좋음: https://www.youtube.com/watch?v=wZSvuCJBaFU
- 좋은 지적임. 중복 소수를 허용하면 두 번째 소수가 2인 수는 4의 배수가 됨. 그러면 전체의 1/4임
- 두 번째 소수가 2인 수는 알레프 0개 있음
- 12의 약수는 1, 2, 3, 4, 6, 12이고, 12의 소인수는 2와 3임
이 결과를 포괄하는 L-함수나 모듈러 형식 쪽의 흥미로운 정리나 결과가 있는지 궁금함
요즘 배우는 중인데 주제가 매력적임
https://www.peakmath.org/quest-for-f1 영상을 보다가 알게 됐고, http://lmfdb.org도 탐색해볼 만함
이 사실은 37을 꽤 흥미롭게 만든다고 봄
적어도 31보다는 확실히 더 흥미로움
31도 소수라서 어느 정도 흥미롭지만, 방금 배운 것처럼 정수의 두 번째 소인수 중앙값인 37만큼 흥미롭지는 않음
더 흥미로운 정수 후보가 있을까? 그리고 가장 흥미로운 정수라고 할 만한 수가 존재할까?
- 수학자들은 덧셈 항등원이 0을 진정한 기반이자 가장 흥미로운 정수로 축복한다고 믿는 Zeroastrian과, 곱셈 항등원을 중시해 1을 옹호하는 Unitarian 사이의 격렬한 투쟁에 갇혀 있음. 이 두 진영의 충돌로 셀 수 없이 많은 영혼이 사라졌음
- “가장 흥미로운 정수”라면 664571016291591957042161991109590159107314773607과 590488317782859198927092718316232684864014739572가 해당한다고 봄
  각각 ASCII 문자열 “the most interesting”의 빅 엔디언 및 리틀 엔디언 버전임
- https://en.wikipedia.org/wiki/Interesting_number_paradox
- 소수가 가질 수 있는 또 다른 특별한 성질은 비정규성임. 첫 번째 비정규 소수가 뭔지 맞혀보면 37임
  비정규 소수는 전체 소수의 약 41%를 차지하는데도 이렇게 늦게 처음 나타난다는 점이 흥미로움. 참고: https://encyclopediaofmath.org/wiki/Irregular_prime_number#:~:text=An%20odd%20prime%20number%20p,prime%20numbers%20are%20called%20regular
  가장 흥미로운 소수가 무엇인지는 무엇을 더 흥미롭게 보느냐에 달려 있음. 두 번째 소인수의 중앙값을 좋아하면 37이 최고이고, 첫 번째 비정규 소수를 좋아해도 37이 최고임. 결국 관점의 문제임
  37이 좋은 또 다른 이유는 7로 끝나서 누가 숫자를 하나 말하라고 할 때 “무작위처럼 들리고”, 27보다 나은데 그 이유는 소수이기 때문임. 7은 너무 낮고 17은 불운의 뉘앙스가 있음. 다만 37도 꽤 무서운 수임. 그냥 소수라서 이미 꽤 불규칙한데, 비정규 소수이기까지 함
- 역사적으로는 60을 꼽겠음. 크기에 비해 약수가 많고(12개), 그중 2, 3, 4, 5, 10처럼 유용한 약수가 많기 때문임
  그래서 시간 체계와 삼각법이 아마 60을 기반으로 했을 것임. 360 = 6*60이고, 360은 약수가 24개임
증명이 이렇게 단순하다니 놀라움. 37이 새 최애 소수가 됐음
두 번째 소인수의 평균값 증가율은 어떨지 궁금함. 무한히 커질 것 같긴 한데, 꽤 느리게 커질지도 모르겠음
평생 이 숫자에 꽂혀 있었음. 시계를 볼 때마다, 앞차 번호판을 볼 때마다 37이 보이는 느낌임
Channel 37처럼 이것저것 무작위로 관련된 것도 있음: https://en.wikipedia.org/wiki/Channel_37

답변달기