일일 코딩 문제: 삼각수와 큰 약수

해결해야 할 또 다른 문제가 있는 여러분을 환영합니다! 오늘은 삼각수와 그 약수, 특히 거대한 수에 대해 이야기하겠습니다!

자연 속의 삼각수를 예술적으로 표현한 나의 멋진 작품에 감탄할 수 있지만 일반적인 면책 조항을 살펴보겠습니다.

1. 이 문제는 훌륭한 웹 사이트에서 제공됩니다. 프로젝트Euler.net , 구독할 수 있습니다. 여기 ! 해결해야 할 수학 및 코딩 문제가 800개가 넘고 이에 대한 토론이 담긴 방대한 아카이브가 있습니다. 말 그대로 머리를 긁적거리고 새로운 것을 배울 수 있는 완벽한 도구입니다! 가서 확인하고 문제를 해결해 보세요!

   
   

2. 저는 전문 프로그래머가 아닙니다. 단지 이런 종류의 글을 쓰는 것을 즐기고 자신의 사진을 공유하는 것을 좋아하는 사람일 뿐입니다. 이것이 최적의 솔루션은 아닐 것이라고 확신합니다. 따라서 더 나은 솔루션이 있거나 이를 최적화하는 방법에 대한 아이디어가 있다면 공유하고 싶다면 언제든지 환영입니다!

이야기는 충분히 마쳤으니 오늘의 문제가 무엇을 제공하는지 살펴보겠습니다.

일련의 삼각형 수는 자연수를 더하여 생성됩니다. 따라서 일곱 번째 삼각형 숫자는 1+2+3+4+5+6+7=28이 됩니다. 처음 10개의 항은 다음과 같습니다:1,3,6,10,15,21,28,36,45,55,…

처음 7개의 삼각형 숫자의 요소를 나열해 보겠습니다.

28은 약수가 5개 이상인 최초의 삼각형 수라는 것을 알 수 있습니다.

약수가 500개가 넘는 첫 번째 삼각형 수의 값은 얼마입니까?

문제는 매우 간단합니다. 약수가 500개가 넘는 첫 번째 삼각수가 무엇인지 이해하라는 요청을 받습니다. 먼저 삼각수가 무엇인지, 제수가 무엇인지 좀 더 자세히 살펴보겠습니다.

삼각수

삼각수는 특정 숫자까지의 모든 자연수의 합으로 형성된 숫자의 특정 하위 집합입니다. 항상 삼각형으로 배열할 수 있기 때문에 삼각형이라고 부릅니다. 여기 몇 가지 예가 있어요.

위 이미지에서는 3번째, 4번째, 5번째 삼각수입니다. 예를 들어, 세 번째 숫자는 1+2+3 = 6으로 구성되고, 네 번째 숫자는 1+2+3+4 = 10으로 구성됩니다. 일반적으로 말하면, nᵗʰ 삼각수 Tₙ는 다음과 같습니다.

이것은 물론 연속된 정수의 합은 다음과 같다고 말한 Gauss 가 제시한 수학에서 가장 유명한 급수 중 하나입니다.

따라서 기본적으로 예를 들어 세 번째 삼각수를 계산하려면 3*4/2 = 6을 계산하면 됩니다. 이는 솔루션 작성을 시작하면 매우 도움이 될 것입니다!

제수

숫자 n 의 제수 (또는 인수 )에 대한 정의를 제공하는 것은 매우 간단합니다. 즉, n을 다시 제공하기 위해 다른 정수 k를 곱할 수 있는 숫자 j 입니다. 예를 들어, 3은 18의 약수입니다. 왜냐하면 3과 6을 곱하여 다시 18을 얻을 수 있기 때문입니다.

그러나 5를 곱하면 18이 되는 숫자 k가 없기 때문에 5는 18의 약수가 아닙니다.

정의에 따르면, 우리는 또한 중요한 특성을 얻습니다. j가 n을 곱하기 위해 k 를 곱할 수 있기 때문에 j 가 n의 제수라면, k 도 n을 곱하여 n을 얻을 수 있기 때문에 n의 제수입니다.

이런 식으로 우리는 숫자 n이 항상 적어도 두 개의 약수 j 와 k를 갖는다는 것을 확신할 수 있습니다 (사실 j는 항상 1이고 k 는 n 일 수 있습니다).

또한, 다른 말로 표현하면, n / j 의 나머지가 0과 같을 때 숫자 j 는 숫자 n 의 제수입니다 . 예를 들어 18/3 = 6이고 나머지는 0입니다.

n % j = 0 인 경우 j가 n 의 약수라는 모듈러 산술을 사용하여 이 개념을 더 잘 공식화할 수 있습니다. 즉, 다음 두 번째 속성을 얻습니다.

우리가 관심을 갖고 있는 세 번째이자 마지막 속성 은 n 자체가 아닌 n/2 보다 큰 수 n 의 약수가 있을 수 없다는 것입니다. 이것은 이해하기 매우 간단합니다. 첫 번째 속성을 통해 우리는 요소가 1,…,n 범위에서 어떻게든 서로 "연결"되어 있음을 알 수 있습니다.

이는 다시 j\n 이면 j * k = n이기 때문입니다. 그러므로 k\n도 된다. 다시 18을 예로 들어 약수를 찾고 이 속성을 반영하도록 색상을 지정해 보겠습니다.

따라서 예를 들어 j = 3, k = 6 이고 그 반대로 j = 6, k = 3이면 이는 1 외에 사용할 수 있는 가장 작은 j 가 2라는 것을 의미하며 이는 가장 큰 k를 제공합니다. 가능합니다. n/2 (우리의 경우 9)입니다 . 이것은 작동합니다:

• 짝수인 경우, 가장 큰 인수는 정확히 n의 절반과 같습니다.

• 홀수의 경우: n을 2로 나눌 수 없는 경우(홀수가 유리수를 제공하기 때문입니다) 이는 j > 2만 사용할 수 있다는 의미이며, 이는 항상 k < n/2라는 결과를 제공합니다.

  
  

마지막으로 j 와 k가 동일할 수 있는 경우는 n 이 제곱수인 경우뿐입니다. 예를 들어, n = 36 일 때 가능한 인자 j = 6 은 또 다른 인자 k = 6을 생성합니다. 이 경우에 대해서는 나중에 코드 부분에서 더 자세히 논의하겠습니다.

물론 이러한 개념은 매우 사소하지만 우리 솔루션에서는 매우 중요합니다!

코드

코드는 Go 로 작성될 것입니다. Go는 여전히 높은 수준의 가독성을 유지하는 매우 빠른 언어이기 때문입니다. 우리는 솔루션을 두 개로 나눌 것입니다. 먼저 숫자의 제수를 찾는 함수를 만든 다음 이를 삼각형 숫자에 적용합니다 .

먼저 함수를 살펴보겠습니다.

정수 n 을 받아들이고 제수를 포함하는 정수 배열 out 을 반환하는 함수를 만듭니다. 그 후, 우리는 사소한 요소, 즉 1과 n 자체를 out 합니다.

그런 다음 j 2에서 n/2 로 반복하기 시작합니다(두 번째 속성에서; n 이 짝수인 경우 k = n/2 j = 2 에 의해 제수에 추가되기 때문에 n/2 자체에는 관심이 없습니다). j = 2 반복: 이것이 j<n/2 가 아닌 j≤ n/2 에서 멈추는 이유입니다.

이렇게 하면 n 의 전반부에서만 제수를 확인할 수 있어 프로세스 속도가 상당히 빨라집니다.

각 루프에서 우리는 3가지를 확인합니다:

• 세 번째 if 문은 실제로 n%j==0 , 즉 0 ñ n(mod j)인지 확인합니다. 그렇다면 요인을 찾았고 목록에 j 추가합니다. n/j 를 계산한 후 다음 j 로 이동하여 대응하는 k 를 목록에 추가할 수도 있습니다.

• 두 번째 if 문은 n 이 정사각형인지 확인하므로 j 는 n 의 근입니다. 그렇다면 중복을 피하기 위해 하나의 제수 j 만 out 에 추가되고 알고리즘은 계속 진행됩니다.

  
  

  n = 36 이라고 가정합니다. 이 작은 블록이 누락되면 세 번째 if 문이 트리거되어 j = 6 및 k = n/j = 36/6 = 6 out 하게 되어 복제본이 생성됩니다.

• 첫 번째 if 문은 가장 복잡합니다. 그 목적은 반복되는 jk 쌍이 시작되는지 확인하는 것입니다. 그렇다면 루프를 즉시 중단할 수 있습니다. 왜냐하면 우리 요소가 이미 out 에 모두 존재하기 때문입니다.

  
  

특히 이 세 번째 점에 대해 확인해야 할 두 가지 경우가 있습니다: out[len(out)-1] == j 인지 out[len(out)-2] == j .

첫 번째 경우는 고전적인 경우입니다. 예를 들어 숫자 T₇ = 28을 사용합니다.

j = 7 이면 마지막으로 삽입된 값과 같습니다. 그러므로 우리는 루프를 끊을 수 있습니다.

두 번째 경우는 정사각형 n 찾았을 때만 발생합니다. 예를 들어 36을 다시 살펴보겠습니다.

j = 9 인 경우 n 의 제곱근 앞에 추가된 마지막 값과 같으며 이는 한 번만 나타납니다. 따라서 이 시점에서 루프를 끊을 수 있습니다.

마지막으로, 우리는 제수를 가지기 위해 간단히 return out 수 있습니다.

결과 적용

이제 함수가 생겼으므로 이를 모든 삼각수에 적용할 수 있습니다. 우리는 삼각수 생성기 역할을 할 카운터 c 를 만들 것입니다. 가우스 방정식을 사용하여 관련 삼각수 tn 을 계산하고 약수가 몇 개인지 확인합니다.

500보다 크면 해당 tn 결과로 반환합니다.

하지만... 함정이 있어요!

ProjectEuler.net은 정말 멋진 프로젝트입니다. 수학 수수께끼와 문제를 제시하는 것 외에도 주요 초점은 수학에 대해 배우고, 생각하고, 추론하기 위한 도구를 제공하는 것입니다 .

그리고 나는 그것을 좋아합니다: 그들은 너무 헌신적이어서 그들의 문제에 대한 결과와 가이드를 출판하는 것이 실제로 금지되어 있습니다(이것은 처음 100개의 문제 중 하나이므로 허용된다는 것을 이해합니다).

그런 점에서 그냥 복사해서 붙여넣기 하는 방법으로 해결방법을 알려주고 성과를 얻는 것은 공정하지 않다고 생각합니다 . 이러한 이유로, 나는 여러분에게 실제 해결책을 제시하지 않습니다. 스스로 시도해 보고 내 것보다 더 나은 알고리즘을 생각해 보십시오(그런 알고리즘이 많이 있습니다). 미안해요! 😅

시간 복잡도

나는 이것이 꽤 끔찍한 기회라고 생각하기 때문에 더 나은 해결책이 많이 있다고 확신합니다!

FindDivisor 함수는 선형 시간으로 실행됩니다. 인스턴스 n 의 크기에 따라 달라지며 최대 n/2 루프에서도 실행되기 때문입니다. 우리는 그것을 O(n)이라고 생각할 수 있습니다.

그러나 먼저 각 삼각수를 계산해야 하며 이 계산에도 O(tn) 시간이 소요됩니다. 여기서 tn은 결과(실제로 계산한 마지막 값)입니다. 이를 감안할 때 전체 알고리즘의 시간 복잡도는 대략 O(tn*n)이 되어야 합니다.

tn 인수 또는 함수가 되고 그 안에서 최대 n/2 개의 루프를 실행하므로 시간 복잡도를 O(tn*tn/2) = O(tn²/2) = O(tn²)로 다시 작성할 수 있습니다. 불행하게도 이차 시간 솔루션 입니다!

알고리즘이 그 정도로 복잡하더라도 꽤 빠르게 실행된다는 사실에 놀랐습니다. 내 컴퓨터(AMD Ryzen 5, 평균 ck. 2700MHz)에서 결과를 제공하는 데 322.564227ms가 걸렸습니다.

하지만 1000개의 약수를 초과하는 첫 번째 삼각수를 찾는 데 3.827144472초가 걸렸으므로 시간 소모가 급격히 증가하고 있음을 분명히 알 수 있습니다.

결론

우리는 마침내 해냈습니다! 여러분이 이 기사를 재미있게 읽으셨기를 바라며, 이 기사에서 흥미로운 점을 얻으실 수 있기를 바랍니다. 그렇다면 박수를 한두 번 남겨주시고 이 주제에 관심이 있는 사람과 기사를 공유해 주세요!

환상적인 작업을 수행한 ProjectEuler에게 다시 한 번 큰 박수를 보냅니다. 가서 그들이 무엇을 제공할 수 있는지 확인해 보시기 바랍니다. 나는 당신이 그것이 매우 흥미로울 것이라고 확신합니다!

그리고 언제나처럼 읽어주셔서 감사합니다.

니콜라