프로베니우스의 동전 문제(Frobenius coin problem)와 슈어의 정리(Schur's theorem)

1. 프로베니우스의 동전 문제(Frobenius coin problem) 서로 다른 두 동전 x원, y원이 있을때, 이 두 동전을 각각 적당한 개수를 사용하여, 만들 수 없는 금액중 가장 큰 값은? 이 문제의 정답을 프로베니우스의 수(Frobenius number)라고 부른다. 예를 들어 3원, 5원짜리 동전으로 만들 수 없는 가장 큰 금액은 7원이다. 이 말은 8원 이상의 금액은 무조건 만들 수 있다는 뜻이다. 주의할 점은 7원 밑의 금액 중에서 1,2,4원은 만들 수 없다는 것은 자명하다. 프로베니우스의 수는 x,y가 서로소(최대공약수가 1)일때만 존재한다. 이때, 프로베니우스의 수는 xy - x - y임이 알려져있다. 2. 일반화된 문제 일반적으로는, n개의 동전 $a_{1}, a_{2},...,..

  • format_list_bulleted 정수론
  • · 2026. 3. 30.
  • textsms
Prime number Theorem으로 알아보는 구간 내의 소수 개수

Prime number Theorem으로 알아보는 구간 내의 소수 개수

1. prime number theorem(소수 정리) 양의 실수 x 이하에 존재하는 소수의 개수를 $\pi(x)$라고 한다면 다음이 성립한다. 양수 x이하의 소수의 개수는 근사적으로 x/logx개라는 소리다. 로그 적분 함수 li(x)는 다음과 같이 정의한다. 그래프가 다음과 같다. 구간 [0,x]가 아닌 [2,x]에서 로그 적분 함수를 Li(x)로 나타내기도 한다 이를 이용해서 다음과 같이 나타내기도 한다. 즉, $\pi(x)$는 Li(x)에 근사할 수 있고, 현대에는 이게 더 정확하다고 알려져있다. 2. 소수의 밀도 직관적으로 큰 숫자에서 소수 사이 간격이 점점 커진다는 것을 알 수 있다. 에라토스테네스의 체로 구해보면 알수 있다 그렇게 차이나지는 않네 흠.. 양수..

  • format_list_bulleted 정수론
  • · 2025. 7. 2.
  • textsms
에라토스테네스의 체 변형 segmented sieve 배우기

에라토스테네스의 체 변형 segmented sieve 배우기

https://deepdata.tistory.com/393 소수를 빠르게 구하는 에라토스테네스의 체 알고리즘1. 소수를 구하는 방법 컴퓨터가 주어진 수 n이 소수인지 판단할려면 어떻게 해야할까? 1부터 n까지 n에 나눠보면서 n의 약수인지 아닌지 판단해보면 된다. n의 약수가 1과 n만 있어야 n이 소수이다deepdata.tistory.com 에라토스테네스의 체의 문제는 수행하는 연산의 수가 아니라 메모리 요구량에 있다. n이 매우 큰 경우, 소수의 범위가 메모리에 모두 담기지 않을 수 있다. 더 나쁜 것은, n이 그리 크지 않은 경우에도 캐시 사용이 매우 비효율적이라는 점이다. 이 알고리즘은 배열 A 전체를 순차적으로 탐색하며, 참조 지역성이 거의 없다. 이러한 문제에 대한 해결책으로 분할 체(se..

  • format_list_bulleted 정수론
  • · 2025. 6. 30.
  • textsms
의외로 모르는 어떤 분수가 유한소수가 될 수 있는 조건

의외로 모르는 어떤 분수가 유한소수가 될 수 있는 조건

1. 유한소수? 유한소수는 소숫점 아래에 있는 수가 유한한 소수이다. 어떤 분수가 유한소수일려면 기약분수로 나타내고, 분모를 소인수분해 했을때, 2나 5만을 인수로 가져야한다. 왜냐하면, 유한소수는 (정수).xxxxxxx 형태로, 정수 + 0.xxxxxxx로 나타낼 수 있다. 이때, 0.xxxxxxxx = xxxxxxxxx/10^n이므로, (y + xxxxxxxxxx)/10^n형태로 나타난다. 따라서, 유한소수를 기약분수로 나타내 분모를 소인수분해해보면 반드시 2나 5만을 인수로 가진다. 2. 연습문제 https://atcoder.jp/contests/agc047/tasks/agc047_a A - Integer ProductAtCoder is a programming contest site for an..

  • format_list_bulleted 정수론
  • · 2025. 4. 29.
  • textsms

모든 양의 유리수는 단위분수의 합으로 나타낼 수 있다

1. 단위분수 분자가 1이고 분모가 양의 정수인 분수 1/1, 1/2, 1/3,...이 단위분수이다. 1/(1.5)라든지 1/(3.4)같이 분모가 실수이면 단위분수가 아니다. 흥미로운 점은 모든 유리수는 어떤 단위분수들의 합으로, 여러가지 방법으로 나타낼 수 있다는 점이다. $$\frac{4}{5} = \frac{1}{2} + \frac{1}{4} + \frac{1}{20} = \frac{1}{3} + \frac{1}{5} + \frac{1}{6} + \frac{1}{10}$$ 단위분수들의 합을 이집트 분수(Egyptian fraction)라고 부른다 이렇게 나타내는 방법에 대해 여러가지 연구들이 있다.. https://en.wikipedia.org/wiki/Egyptian_fraction Egyptia..

  • format_list_bulleted 정수론
  • · 2025. 4. 28.
  • textsms

정수의 임의의 거듭제곱들의 합을 바라보는 놀라운 방법

15319번: 동혁이의 생일선물 정수 x의 거듭제곱 $x^{0}, x^{1}, x^{2}, ... $에 대하여 이들의 모든 부분집합 A1, A2, ...을 생각하자 각 부분집합의 원소들의 합을 M1, M2,...라고 할 때 이들을 오름차순으로 정렬하면 수열 a1, a2,...를 얻는다 이때 k번째 원소 ak에 대하여 n개의 x,k가 주어질때 각각 구한 모든 ak의 합을 10^9 + 7로 나눈 나머지를 구한다 --------------------------------------------------------------------------------------------------------------------------------------------------------------- 2,3,4,....

  • format_list_bulleted 정수론
  • · 2025. 2. 11.
  • textsms