더블릿
30 계단 | 옥 상 | 제출 현황 | Ranking | FAQs | 오류보고 | QandA | 푼   후 | 자유게시판 |
 
오일러 totient 함수
삭제 | 편집 | 답글
오일러 totient 함수란?

n 보다 작은 수 중 n 과 서로 소인 수의 갯수 구하는 함수.


 pi 는 n 의 소인수.

예를 들어  n 이 20 인 경우 


proof) 

1 에서 20 까지의 수 중 2 의 배수는 개수는 10 개 입니다.

20 - 20/2  = 20(1 - 1/2) = 10 개 

남은 10 개의 수는 

1 , 3 , 5 , 7 ,  9 , 11 , 13 ,15 , 17 , 19 

입니다. 

이 중 5 의 배수의 갯수는  두개가 있습니다.

10 - 10/5 = 10(1-1/5)= 8 개 


작업중....
 
2011-09-27 20:02 , testid
삭제 | 편집 | 답글
이 문서를 쓰다보니 milk 님 생각이 나는군요.
 
2011-09-27 22:52 , testid
삭제 | 편집 | 답글
소수들은 서로 다른 소수들과 "독립적인" 관계이므로 "여사건"으로 설명하는 것이 더 이해가 빠를듯 합니다. ^^



 

 
2011-09-28 15:07 , pl0892029
삭제 | 편집 | 답글
제 설명이 제가 보기에도 답답해서 식으로 해봤는데요. 

N = i * j * K... 

N - (N/i + N/j  - N / (i*j) )....i의배수,j의배수의 갯수를 더해서 교집합인, i*j의 배수의 갯수를 빼기.. 
=(N - N/i) - (N/j - N/(i*j) ) 
=(N - N/i) - (N - N/i)/j  ....재귀적인 식이 보이지요 

N = 60. i=2, j=3, N-N/i=30..... 

예전 milk 님이 설명해 주신 글을 이쪽으로 옮겨 왔습니다. 
 
2011-09-28 15:48 , testid
삭제 | 편집 | 답글
그렇지 않아도 이 부분 고민하고 있었습니다.

소수들끼리는 서로 독립적인 관계에 있지만 임의의 수는 소인수를 여러개 가질수 있으니 여사건으로
설명할 수가 없는 것 아닌지요.

예를 들어 , 10 이면 2 의 인수 , 5 의 인수 모두를 가집니다. 
 
2011-09-28 15:20 , testid
삭제 | 편집 | 답글
소인수 여러개가 있는것과 여사건이 무슨 관계죠?
 
2011-09-28 16:37 , ainta
삭제 | 편집 | 답글

독립인 것은 다음과 같이 확인이 됩니다.

3의 배수일 확률 x 5의 배수일 확률 = 15의 배수의 확률일까?

여기서 이것이 성립하기 때문에, 여사건으로 다루어도 아무 문제가 없습니다.

 
2011-09-28 16:38 , pl0892029
삭제 | 편집 | 답글
n 이 20 인 경우 

10 은 2 에 의해서도 지워지고 5 에 의해서도 지워 집니다. 독립적인 사건이라고 할 수 없지 않나요?
 
2011-09-28 22:23 , testid
삭제 | 편집 | 답글
 입니다.

2와 5의 공배수 관련 때문이라면, 걱정하지 않아도 되는 이유가

이미 중복되는 모든 경우를 고려한  의 여집합이 으로 정리가 됩니다.

그러므로 저희는 두 개가 독립, 종속인지 여부에 따라 곱셈의 여부만 확인해준다면 여사건으로 충분히 해결이 됩니다.

다행히 모든 소수는 서로 다른 소수에 대해 독립이기에 오일러totient 는 참으로 증명이 됩니다.
 
2011-09-28 22:49 , pl0892029
삭제 | 편집 | 답글
오류가 있어 이제야 글을 보았습니다.

지금도 그런가요?.
 
2011-09-28 22:52 , testid
삭제 | 편집 | 답글
끼적여봤습니다. 증명해보겠습니다.

p와 q가 독립일 때, 1-p 와 1-q 가 독립인지만 증명한다면, 위 문제는 쉽게 해결될 것입니다. (p와 q가 독립이라면,  이 성립합니다.)


그러므로 두 여사건은 각각에 대해 독립이다.


 
2011-09-28 23:14 , pl0892029
[previous]