통계, IT, AI

1. 개요 문제는 이곳에서 확인할 수 있다. 숫자 56**3의 3번째, 4번째에 같은 숫자 10개를 넣으면 그 중 7개가 소수가 된다. 즉, 56003, 56113, 56333, 56443, 56663, 56773 그리고 56993이 그 소수들이다. 이와 같이, 자리의 일부를 같은 숫자로 치환하여 8개의 소수를 만들수 있는 가장 작은 수를 구하는 것이 문제의 목표이다. 단, 치환하는 자리는 인접하지 않아도 된다. 2. 구현 문제를 제대로 파악하지 못해 굉장히 시간이 오래 걸렸다. 처음에는 예시와 같이 치환해야 하는 자리가 2개로 제한되어 있다고 생각하였고 그렇게 구현하였다. 하지만 도저히 답이 나오지 않자 다른 사람들의 의견을 참고하였고 치환해야 하는 개수의 제한이 없다는 것을 알게 되어 바로 다시 구현..

1. 개요 문제는 이곳에서 확인할 수 있다. 41은 다음과 같이 6개의 연속한 소수의 합으로 표현될 수 있다. $$41=2+3+5+7+11+13$$ 그리고 41은 100보다 작은 소수 중 가장 길게 연속하는 소수의 합이다. 이와 같은 특성을 가진 1000보다 작은 소는 953으로 21개의 연속하는 소수의 합이다. 문제의 목표는 가장 길게 연속하는 소수 들의 합으로 나타낼 수 있는 100만 이하의 소수를 찾는 것이다. 2. 구현 소수는 에라스토테네의 체를 사용한다. 연속하는 소수의 합을 구하면서 찾아야 하는 범위에 길이와 합을 반영하여 속도를 높인다. # -*- coding: utf-8 -*- lim = 1000000 is_prime = bytearray([1])*(lim+1) is_prime[0] = i..

1. 개요 문제는 이곳에서 확인할 수 있다. 1487, 4817, 8147은 3330씩 증가하는 수열인데 그 외에도 두가지 재미있는 특성이 있다. 첫번째는 각각이 모두 소수라는 점, 둘째는 각 숫자는 다른 숫자에서 배열을 바꿔 만들 수 있다는 점이다. 이와 같은 특성을 가진 4자리 숫자의 수열이 하나 더 존재한다. 그 수열을 연결한 12자리의 수를 찾는 것이 목표이다. 2. 구현 소수는 에라스토테네스의 체를 사용하여 구하며 숫자의 배열을 바꾸는 작업은 내장 모듈(itertools)를 사용한다. # -*- coding: utf-8 -*- import itertools import math lim = 10000 is_prime = bytearray([1])*(lim+1) is_prime[0] = is_pri..

1. 47번 개요 문제는 이곳에서 확인할 수 있다. 연속한 두개의 정수 중 두개의 서로 다른 소인수를 갖는 최초의 수는 \(14=2 \times 7\), \(15=3 \times 5\)이다. 연속한 세개의 정수 중 세개의 서로 다른 소인수를 갖는 최초의 수는 \(644=2^2\times 7 \times 23 \), \(645=3\times 5 \times 43 \), \(646=2 \times 7 \times 19 \)이다. 마찬가지로 연속한 네개의 정수 중 네개의 서로 다른소인수를 갖는 최초의 수에서 가장 처음 수를 구하는 것이 문제의 목표이다. 2. 47번 구현 에라스토테네스의 체를 사용하여 소수를 구하고 그것을 사용하여 소인수분해를 하는 방법을 사용한다. # -*- coding: utf-8 -*- ..

1. 개요 문제는 이곳에서 확인할 수 있다. odd composite number는 소수가 아닌 홀수인데, 골든바흐는 odd composite number를 아래와 같이 어떤 소수 \(p\)와 어떤 수 \(k\)의 제곱의 두배의 합으로 표현할 수 있을 것이라고 추측하였다. \(9=7+2\times 1^2\)\(15=7+2\times 2^2\)\(21=3+2\times 3^2\)\(25=7+2\times 3^2\)\(27=19+2\times 2^2\)\(33=31+2\times 1^2\) 하지만 이 추측은 틀렸다. 이 추측에 맞지 않는 가장 작은 odd composite number를 찾는 것이 문제의 목표이다. 2. 구현 앞선 문제와 마찬가지로 에라스토테네스의 체를 사용하여 소수를 구한다. # -*- c..

1. 개요 문제는 이곳에서 확인할 수 있다. 양의 정수 \(n\)에 대하여 Triangle, pentagonal 그리고 hexagonal number는 다음과 같이 정의된다. Triangle \(T_n=n(n+1)/2\) 1, 3, 6, 10, 15, ... Pentagonal \(P_n=n(3n-1)/2\) 1, 5, 12, 22, 35, ... Hexagonal \(H_n=n(2n-1)\) 1, 6, 15, 28, 45, ... 이 세가지 수열은 서로 같은 수를 가질 수도 있다. 즉, \(40755=T_{285}=P_{165}=H_{143}\)이다. 40755보다 크면서 Triangle, pentagonal 그리고 hexagonal number인 수를 찾는 것이 목표이다. 2. 구현 문제의 범위를 좁..

1. 개요 문제는 이곳에서 확인할 수 있다. pentagonal number \(p_n\)은 \(n(3n-1)/2\)로 정의되며 처음 10개는 다음과 같다. 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ... 합과 차가 pentagonal number인 어떤 두 pentagonal number가 존재할때, 가장 작은 차 \(D=|P_k-P_j|\)를 구하는 것이 문제의 목표이다. 2. 구현 합은 \(P_l=P_k+P_j\)로 차는 \(P_i=P_k-P_j\)로 정의하자. 또한 \(i

1. 개요 문제는 이곳에서 확인할 수 있다. 1406357289는 0부터 9까지의 수가 한번씩 등장하는 수(0 to 9 pandigital)이다. 그리고 \(d_n\)을 \(n\)번째 자리의 수라고 하면 이 숫자의 sub-string은 다음과 같은 특징이 있다. \(d_{2}d_{3}d_{4}=406\)은 2로 나누어 떨어진다. \(d_{3}d_{4}d_{5}=063\)은 3으로 나누어 떨어진다. \(d_{4}d_{5}d_{6}=635\)은 5로 나누어 떨어진다. \(d_{5}d_{6}d_{7}=357\)은 7로 나누어 떨어진다. \(d_{6}d_{7}d_{8}=572\)은 11로 나누어 떨어진다. \(d_{7}d_{8}d_{9}=728\)은 13으로 나누어 떨어진다. \(d_{8}d_{9}d_{10}=..

1. 개요 문제는 이곳에서 확인할 수 있다. \(n\)번째 triangle number는 \(t_n=n(n+1)/2\)으로 정의된다. 그리고 어떤 단어의 각 알파벳의 순서의 합이 triangle number일때 그 단어를 triangle word라고 한다. 예를 들어 SKY의 각 알파벳의 순서의 합은 19 + 11 + 25 = 55=\(t_{10}\)이므로 SKY는 triangle word이다. 주어진 텍스트 파일에서 triangle word의 개수를 찾는 것이 목표이다. 2. 구현 어떤 수가 \(K\)가 triangle number인지 파악하기 위해서는 \(K=n(n+1)/2\)의 해 \(n\)이 정수인지 확인하면 된다. 이때, round error 등을 방지하기 위하여 sqrt 함수를 사용하지 않고 ..

1. 개요 문제는 이곳에서 확인할 수 있다. 어떤 수의 각 자리수가 1부터 \(n\)까지의 정수가 한번만 등장할 때 이 숫자를 \(n\) pandigital이라고 한다. 예를 들어 2143은 4 pandigital인데 소수이기도 하다. 이와 같이 pandigital이면서 소수인 \(n\) panditial 중 가장 큰 수를 구하는 것이 문제의 목표이다. 2. 구현 \(n\) pandigital의 정의상 확인해야 할 가장 큰 수는 987654321이다. 그런데 9 pandigital과 8 pandigital 각각은 그 자리 수의 합이 3의 배수이기 때문에 소수가 아니다. 따라서 7654321부터 문제의 조건을 확인하면 된다. 이를 이용하여 구현한다. # -*- coding: utf-8 -*- import ..