Script / CSS

G1sUtil.js

G1sBlogger.js

CSS

G1sNavigationList.js

Posts List


2012년 3월 4일 일요일

[Project Euler] 21. 10000 이하 모든 친화수(우애수)의 합은?

21. 10000 이하 모든 친화수(우애수)의 합은?
n의 약수들 중에서 자신을 제외한 것의 합을 d(n)으로 정의했을 때,
서로 다른 두 정수 a, b에 대하여 d(a) = b 이고 d(b) = a 이면
a, b는 친화쌍이라 하고 a와 b를 각각 친화수(우애수)라고 합니다.

예를 들어 220의 약수는 자신을 제외하면 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 이므로 그 합은 d(220) = 284 입니다.
또 284의 약수는 자신을 제외하면 1, 2, 4, 71, 142 이므로 d(284) = 220 입니다.
따라서 220과 284는 친화쌍이 됩니다.

10000 이하의 친화수들을 모두 찾아서 그 합을 구하세요.
Click
친화수를 구하는 공식이 있다고하지만....
친화수는 피타고라스 학파 시대에 이미 알려져 있었다.
850년경에 이탈리아의 수학자 사빗 이븐 쿠라(826-901)에 의해 친화수를 구할 수 있는 관계식이 도출되었다.

p = 3 × 2ⁿ-¹ - 1,
q = 3 × 2ⁿ - 1,
r = 9 × 22ⁿ-¹ - 1,

여기서, n은 1이상의 정수이고, p,q,r이 소수인 p,q,r,n이 존재할 때 2npq와 2nr은 친화수의 관계에 있다.

이 식은 모든 친화수의 짝에 대하여 성립하지는 않는다.
예를 들어, 친화수 (220, 284), (17296, 18416), (9363584, 9437056)은 이 관계식을 만족하지만, (6232, 6368)은 친화수임에도 이 관계식을 만족하지 않는다.
100%적용되는 조건이 아니므로... 결국 단순 방식으로 구현.
<script>
function sumOfDivisior(n){
    var sum = 1;
    for(var i=2; i<=n/i; i++)
        if(n%i == 0)
            sum += i + (((n/i))==i?0:(n/i));
    return sum;
}
function p021(max){
    var sum = 0;
    for(var i=2; i<=max; i++){
        var temp1 = sumOfDivisior(i);
        if(i==sumOfDivisior(temp1) && temp1 != i)
            sum += i;
    }
    return sum;
}
</script>

댓글 없음:

댓글 쓰기