|
Problem 3.
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
주어진 수의 소인수 중, 최대값 구하기.
참고로, factor 찾을때마다 덮어쓰면서 갱신하지 않고 list 에 저장하고,
나눠서 소모시킬때마다 또다른 list 저장하면, 소인수분해하는 코드가 됨.
NOTE:
나누기를 시도하는 숫자를 어떻게 점프시키느냐로 약간의 효율성을 높일수 있음. 가령 모든 짝수는 건너뛰고, 또 3의 배수도 건너뛰고, 그래서 6n-1, 6n+1 꼴만 체크한다던가... 근데 그정도론 order 자체를 바꿀정도는 아님. 차라리 체크범위를 가령 sqrt N 으로 줄여준다던가 하는게 수가 커질수록 이득.
Problem 2.
Each new term in the Fibonacci sequence is generated by adding the previous two terms.
By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
: 4,000,000 이하의 짝수인 피보나치 넘버들의 합 구하기
재밌는 주제들:
- 피보나치 수열의 일반항
- Characteristic Equation (특성방정식)
- Generating Function (생성함수)
- Golden Ratio (황금비)
- Pascal Triangle (파스칼 삼각형)
Problem 1.
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
: 1000 보다 작은 3 또는 5의 배수의 합 구하기
MATH:
" A 를 B 로 나눈 나머지 ( A mod B ) 가 0 이면, 즉, A 가 B 로 나누어 떨어지면,
A 를 B 의 배수, B 를 A 의 약수라고 한다 "
구글링 도중 갑자기 화면이 깨지면서 "you ... our language" 어쩌고 하더니, code challenge 해보겠냐고 물어봄.
구글이 easter eggs 나 prank (가령, recursion 을 검색한다던가) 를 많이 심어놓은 건 익히 알아서, 이건 또 뭔가 하고 클릭해봄.
갑자기 page 가 linux 스러운 terminal 로 변함.
무슨 창작 우주 동화같은 스토리가 좀 나오더니, 다음과 같이 문제가 나옴.
둥그런 케이크의 테두리를 M&Ms 로 둘러서 장식했는데,
M&Ms 에 알파벳 소문자가 써있고,
M&Ms 의 놓인 모양이 모두 똑같은 케잌 조각으로 나누어 먹으려고 함.
M&Ms 알파벳들이 놓인 전체 string s 로 부터,
최대로 나눠먹게을수 있는 케잌 조각수를 구하는 함수 answer(s) 를 작성하라는 내용.
가령,
'abccbaabccba' 인 경우, abccba / abccba 이므로 2
'abcabcabcabc' 인 경우, abc / abc / abc / abc 이므로 4
파이썬이나 자바로 풀라고 함. 다른 언어는 지원 안하는 듯
파이썬 버전은 어떤거 쓰나 궁금해짐.
문제 푸는데는 차이가 없을거 같았지만 그래도 궁금해서 보니까
문제의 제한조건등은 다음과 같이 볼 수 있음.
파이썬은 2.7 임. (3.x 는 언제쯤 널리 쓰일런지 ...)
암튼, 풀면 어떻게 되나 궁금해서 (문제가 만만해 보이기도 하고?) 일단 풀어봄.
알고보니 레벨 1 이라 ㅎㅎㅎ
코드를 작성하는 법은,
디렉토리 안에 solution.py 가 있는데,
edit solution.py 라고 커맨드를 치면,
vi 같은 text editor 가 화면 오른쪽에 생김.
editor 안에는 이미 함수 definition 이 시작되어 있고,
comment 로 여기다 코드를 치라고 나옴.
거기에 코드를 치면 됨.
저장하기랑 나가기가 있음. 다쓰고 저장하고 나간다음,
verify solution.py 라고 치면, 코드를 테스트 해 볼수 있음.
test case 들로 테스트를 돌려주는 거 같음.
모든 테스트 케이스에 대해 패스하면, 다음과 같이 녹색으로 메시지가 뜸.
이 때 submit solution.py 로 제출하면 되는듯.
제출 했더니 다음과 같은 화면이 나옴.
참고로, 저 토끼는 막 뛰어다님.
일단 초대를 받으면, google 로 로그인한 상태에서는 google.com/foobar 로 들어갈 수 있는 거 같음. 들어가니까 계속 이어서 나옴.
검색해보니, level 5 까지 다 풀면 무슨 구글에서 인터뷰 초대(?) 같은게 온다는 전설의 레전드가 있는 모양이던데, 그냥 낚시라는 얘기들도 있음.
아니면 엄청 impressive 한 방법으로 풀어야 연락이 오나 ㅋㅋㅋ 근데 그 많은 사람들의 코드를 창의성까지 따져가며 리뷰할 확률이 ...
진짜든 장난이든 확실히 구글스러움.
다음 레벨들도 궁금해서 시간날때 한번씩 풀어보고 싶긴 한데... 늘 그렇듯 시간이...
암튼, 재미있은 경험이었음.
앞서 [어린이를 위한 미적분학] 테일러 급수 에서, 1변수 테일러 급수를 어떻게 구하는지 살펴보았다.
이번에는 같은 논리를 2변수로 확장해보자.
일단, 2변수에서 테일러 급수를 논하기위해서는, 다변수 함수의 미분에 대해 짚고 넘어가지 않을 수 없지만, 일단 여기서는 필요한 모든 조건이 성립한다는 가정하에서, 테일러 급수의 계수를 구하는데만 초점을 맞추도록 한다. (다변수 함수의 미분에 관해서는 Calculus on Manifolds - M. Spivak 를 추천)
어떠한 2변수 함수 f = f (x,y) 가 (x0, y0) 을 지나고, 가령 무한번 미분 가능성 등의 조건들을 만족해, 어쨌든 다음과 같이 2변수 멱급수로 전개 가능하다고 하자.
계수의 첨자는 a_m,n 이라고 할때, m 은 x의 차수, n은 y의 차수랑 대응된다.
[ ] 는 첨자의 합이 0, 1, 2, ... 이런식으로 되도록 묶은것이다.
( 이런걸 weight 가 같다고 했던듯, 그래서 심지어는 isobaric 하다고 했던 거 같기도... -_-; )
암튼, 1 변수때와 마찬가지로, 계수만 결정하면 되는데, 기억을 되살려 보면...
우리의 메인 아이디어는, 미분과 대입을 통해, 구하고자 하는 계수만 빼고 전부다 날려버리는 것이었다.
a_0,0 부터 구해보자.
(x_0, y_0) 의 대입으로, a_0,0 를 제외한 나머지 모든 항은 사라진다. 따라서...
이제 a_1,0 과 a_0,1 을 구해보자. 어차피 (x0,y0) 를 대입할 것이므로, x 텀이든 y 텀이든 하나라도 살아있으면, 모두 0 으로 날아간다.
x 의 차수만 하나 떨어뜨리는 것은 x 로 편미분을 하면 되고, y 의 차수 하나만 떨어뜨리는 것은 y 로 편미분 하면 된다.
가령, x 로 한번 편미분 한 후에, (x0,y0) 를 대입하면, x 를 아예 포함하지 않는 항들은 기본적으로 모두 0 이 되고,
x 를 2차 이상으로 포함하는 항들은 (x-x0) 가 남아서, xo,yo 가 대입될때 모두 0 으로 사라진다.
결과적으로 (x-x0) 의 1차식만 가지고 있고, y항은 없는, a_1,0 의 항만 살아남는다. 따라서...
2차 까지만 더 해보자.
a_2,0 을 구하기 위해서, x로 두번 미분하고, x0,y0 를 대입하면 된다. x로 두번 미분하는 과정에서, x의 차수가 2차보다 낮은항들은 모두 사라지고, x의 차수가 2차보다 높거나, (y-y0) 를 가지고 있는 항들도 모두 사라진다.
단, 이때, (x-x0) 차수가 낮아지는 과정에서, 2! 이 앞으로 튀어나옴에 주의하자.
a_1,1 을 구하기 위해서는 x, y 한번씩 미분해주면 된다. 나머지항들은 x0,y0 대입하면 모두 사라진다.
마찬가지로, a_0,2 를 구하기 위해서는 y 로 두번 미분해주면 된다.
이쯤되면, 감이 와야 정상이다.
x로 미분할때마다, x항의 차수가 앞으로 나오고, y로 미분할때마다 y항의 차수가 앞으로 나오므로...
보통의 사람이라면 다음을 유추한다.
이것으로 2변수 테일러급수는 다 구한거지만, 좀더 간결하게 써보자.
우선, 맨처음에 대괄호를 이용해서 표현했던 급수식은, 대괄호단위로 묶어서 생각하고, 다시 각 대괄호 안의 내용을 서메이션으로 표현하면, 다음과 같이 쓸수있다.
계수는 앞에서 구한 식에다 p 대신 k-m, q 대신 m 을 넣으면 되므로, 다음을 얻는다.
예제를 풀어보자.
하나 더 풀어보자.
같은 방식으로, n 변수로 확대하는 것도 어렵지 않다.
다음번에는 '테일러급수와 근사(approximation)' 에 대해서 살펴보도록 하자.
스무드하고 연속인 곡선에 대한 직관적인 이해는, 다음의 정리들을, 적어도 직관적으로는, 상당히 straightforward 하게 느껴지게 만든다.
중간값 정리 (Intermediate Value Theorem): 부드럽고 연속인 곡선이 중간에 수평선을 자르고 지나지 않을 수 없음
Rolle의 정리 (Rolle's Theorem) & 평균값 정리 (Mean Value Theorem): 부드럽고 연속인 곡선은 중간에 평균기울기와 같은 기울기를 갖을 수 밖에 없음. 그려보면 당연하게 느껴진다.
물론, 당연하게 느껴지는 것들을 엄밀하게 증명하는 것은 수학의 중요한 일 중에 하나이다.
그리고, 간단한 (하지만 엄밀한) 증명을 통해, 위와같은 우리의 직관이 틀리지 않았음을 쉽게 확인할 수 있다. (텍스트북 참고)
그런데, 일반화된 평균값 정리 (Generalized Mean Value Theorem, Cauchy's Extended Mean Value Theorem 코시의 확장된 평균값 정리) 에 대해서는, 많은 텍스트북들이 직관적인 부분을 생략하곤 한다.
정리의 내용은, 간단히 말해, 다음과 같은 c 가 a 와 b 사이에 존재한다는 거다.
물론, 분모가 0 인 경우는 그냥 빼고, g 와 f 는 정하기 나름이므로, 바꿔써도 어차피 상관은 없다. f 를 identity function 으로 하고, g 대신 f 로 쓰면, mean value theorem 이 되므로, 확장된거 같긴 한데, mean value theorem 처럼 직관적으로 당연해 보이느냐고 물으면, 머뭇거리는 경우가 꽤 있다.
mean value theorem 은 y = f(x) 를 염두에 두면 상당히 직관적인데, 이번엔 다음과 같은 매개변수 그래프에 같은 직관을 적용해보자.
마찬가지로, 부드럽고 연속인 곡선에 대한 우리의 느낌은 다음과 같이 직선을 긋는것에 대해서도 당연하게 느껴지게 한다.
따라서, 다음과 같은 정리를 추측해 볼 수 있다.
매개변수 곡선에서 dy/dx 는 다음과 같으므로...
따라서, 우리는 원하던 추측을 얻는다. (평균값 정리에서와 마찬가지로, 증명은 보통 텍스트북에 나온다)
위와 같은 매개변수 곡선에서, f 와 g 에는 어떠한 차별도 없으므로, 굳이 f 가 분모로 가서 0이면 안되는 희생을 할 필요도 없고, g 도 마찬가지다.
0이되면 안되는 상황을 제외시키는게 찝찝하면, 다음과 같이 써보자.
이렇게 적으면, 앞에서 제외시켰던 '분모가 0 이 되던 상황'은 f(b)=f(a) 인 경우라고 생각할 수 있고, 분자가 0이 아닌 경우, 매개변수 그래프에서 f(a)와 f(b)가 수직으로 놓인 경우가 된다.
매개변수 곡선에서는 괜찮지만, xy평면에서 y=f(x) 를 다룰땐, 기울기가 무한대가 되는 상황이다. 암튼, 분수꼴로 적지않은 식에서는 f '(c)=0 이 되게 만드는데, 이는 t가 변하는데도, x가 변하지 않는 상황으로 우리의 직관과 일치한다.
이처럼 우리는 엄밀한증명(from 텍스트북)과 함께 직관적인 느낌도 함께 가져가는 것이 좋다.
Windows 8.1 로 업데이트 하면서, Taskbar 에 있는 explorer 의 경로 수정이 전보다는 귀찮아졌다.
이전에는 7 때와 마찬가지로 우클릭 properties 로 경로를 "explorer.exe /e, [원하는 경로, 생략시 내컴퓨터]" 로 바꿔주면 되었던거 같은데...
뭐 암튼, 일단 taskbar 에 있는 explorer 아이콘을 우클릭해서 정보를 보니, File Explorer.lnk 라는 shortcut 이다.
파일의 경로는, C:\Users\유저명\AppData\Roaming\Microsoft\Internet Explorer\Quick Launch\User Pinned\TaskBar\File Explorer.lnk 라고 나온다.
저 shortcut 파일을 다른 shortcut 으로 대체해주면 될듯?
explorer.exe 를 찾아서 shortcut 을 만든다.
생성된 shortcut 파일을 우클릭 properties 로 들어가서, target 을 변경해준다.
나는 거의 항상 C:\로 드가므로, 위와같이 설정했다. 위의 그림에서 네모로 보이는건 백슬래쉬(\) 이다.
변경사항을 저장하고, 파일의 이름을 File Explorer 로 변경해준다. 아까 File Explorer shortcut 이 있던 경로에 덮어씌워준다.
그리고, 다시 taskbar 의 file explorer 을 눌러보니, 바로 C:\ 로 들어간다. 굿.
전체집합의 임의의 원소 a,b,c,d 에 대해...
기호 ☆ 는 다음과 같은 성질이 있다.
☆( a, b ) = ☆( b, a )
☆( a, ☆( b, c ) ) = ☆( ☆( a, b ), c )
기호 ♡ 는 기호 ☆ 에 대해 다음과 같은 성질이 있다.
☆( a, ♡ ) = a
♤( a, b ) 는 ☆( ♤( a, b ), b ) = a 을 만족하는 대상에 대한 이름(Naming) 이다.
다음을 증명하라.
☆( ♤(a,b), ♤(c,d) ) = ♤( ☆(a,c) , ☆(b,d) )
한국어 IME 를 쓰는 경우에, 액세스에서 텍스트 필드로 들어가면 자동으로 한글로 바뀌는 경우가 있다.
뭐 간단하게 한국어 IME 를 지우면 한글로 바뀌는 현상을 방지할 수 있기는 한데... 그럼 한글을 써야할때 애로사항이 꽃피게 된다.
한국어IME의 영어로 작성된 엑셀파일 하나를 임포트 해보았다.
필드만 클릭하면 한글로 바뀐다. 영문입력을 하려면 매번 한/영 키를 눌러줘야 하는 번거로움이 따른다.
영문 키보드를 기본으로 설정해도, default editing language를 영어로 설정해도... 별 소용이 없다.
필드 속성을 보니, IME mode 가 한글(Hangul) 로 되어있다.
이걸 일일이 No Control 로 바꿔주면 되기는 하는데... 필드가 여러개일땐 상당히 번거롭다.
임포트 해오기 전에, 데이타 유효성 검사에서 IME 모드를 미리 세팅하면 되려나 해서 드가보았지만, IME mode 와 같은 탭은 있지도 않고...
(영문 윈도우즈/ 영문 오피스 라서 그런가...)
암튼 요따위 문제가 있을땐, 요따위 방법을 시도해보자.
액세스를 종료했다가 다시 실행시킨다.
아까 저장한 액세스 파일을 다시 열어서 필드속성을 보니까 여전히 IME mode 는 Hangul 로 되어있는데, 자동으로 한글로 바뀌는 현상은 없어졌다 :)
성적도 평균내고, 이익도 평균내고, 심지어 사람의 가치도 평균 내고...
일전에 산술평균과 기하평균편에서, 시퀀스의 중간항으로서의 평균을 살펴봤었다.
이번엔 산술평균의 개념을 일반적인 함수까지 확장해보도록 한다.
평균의 가장 원시적 이미지는 두 값의 중간쯔음에 해당하는 값이라고 할 수 있다.
샘플의 개수를 늘리면서 정의는 다음과 같이 확장된다.
이쯤 되면, 평균에 중간이라는 말을 쓰기가 좀 애매해진다.
우변의 분모에 있는 n을 좌변으로 이동시켜보자.
이와 같은 짓은 미분의 정의를 매니폴드로 확장할때도 볼 수 있다.
암튼 n을 옮기면...
요래 되고, 다음과 같이 된다.
결과적으로 (산술) 평균이라는 값은 샘플들에 대해 오바되는 총 값과 마이너스 되는 총 값이 같아지는 지점의 값이라고 할 수 있다.
이제 이 정의를 "특정구간에서의 함수의 평균"으로 확장해보자.
(사실 방금 한것도 함수였지만, 이제 연속의 개념을 넣자는 거다.)
함수가 어느부분이든 연속인 부분이 있다면, 샘플의 수는 무한개가 된다.
[a,b] 구간 내에서, 일단 유한하게 샘플링을 하자.
그러면 일단은, 앞에서 정의한 개념을 쓸 수가 있다.
함수가 무한개의 데이터 포인트를 가지고 있는 반면, 우리는 고작 유한개의 샘플링만을 했기 때문에, 일정간격으로 구간내의 샘플의 수를 계속 무한히 늘려나가면서 앞에서 정의한 평균의 개념을 적용한 값이 어디로 다가가는지를 보는 거다.
주어진 간격내에서 샘플링의 수를 무한히 늘려나가면, 등간격 샘플포인트들간의 간격은 좁아지게 된다.
x 에서의 샘플링간격을 일정하게 하기로 하고, 그 간격을 델타 x 라고 놓자.
위의 극한개념의 정의에서 분모,분자에 델타x 를 곱해보자. 분모 분자에 0 아닌 같은것을 곱했으므로 값의 변화는 없다. 샘플링의 수가 무한개로 늘어나면, 샘플링간격 델타x는 0으로 다가간다.
여기서 n 곱하기 델타x 는 구간의 길이와 같으므로 다음과 같이 쓸 수 있다.
여기서 fi 곱하기 델타x 는 델타x를 밑변으로 하고 fi 를 높이로 하는 가느다란 막대기의 면적이다.
샘플링수를 무한히 늘려가면, 막대기의 폭은 점점 좁아지고, 이러한 막대기들의 면적을 합한것은 점점 그래프의 밑면적으로 다가간다.
즉, 윗식의 분자는 요래된다.
따라서 다음을 얻는다.
구간길이를 좌변으로 넘겨보면, 구간길이를 밑변으로 하고 면적이 '그래프 아래넓이'와 같은 직사각형의 높이가 f의 평균값임을 알 수 있다.
그러므로, 평균값을 기준으로 위로 넘친 넓이와, 아래로 부족한 넓이가 같게 됨을 확인할 수 있다.
--------------------------------------------------------------------------------------------------------
저저번주 과외 내용 중...
글라스에 얼음넣고 술따라 마시다가 떠오른 문제 :)
그림과 같이 얼음이 물에 떠있다.
A 의 각 원소들의 mod p 에 대한 역원을 찾아보자.
즉, A 의 원소 x 에 대해, x x' ≡ 1 ( mod p ) 인 x' 를 찾는것이다. ( 참고 : 선형 합동식 )
우선, x 는 A 의 원소이므로, p 와 서로소이다. 따라서, 임의의 x 에 대해, 역원 x' 은 항상 유일하게 존재한다.
역원은 당연히 0 일 수 없고, A는 0 아닌 모든 나머지를 포함하므로, x 에 대한 역원은 반드시 A 내에 들어있다.
(참고 : x 에서 x' 으로 가는 대응은 일대일이다. 다른 x 에 대해 같은 역원을 가질수 없음은 쉽게 보일수 있다. )
역원이 자기 자신이 되는 경우에는 다음과 같이 쓸 수 있다.
x 2 ≡ 1 ( mod p )
정의에 따라, p | x 2 -1 이고, 따라서, p | (x+1)(x-1) 인데, p 가 소수이므로, x-1 , x+1 과 모두 서로소이다.
따라서, p | x+1 이거나 p | x-1 이다. 즉, x ≡ 1 (mod p ) 이거나 x ≡ -1 (mod p )
A 내에 이를 만족하는 수는 각각 1 과 p-1 이다.
따라서, A에서 1 과 p-1을 제외시킨 집합 B = { 2 , 3 , ... , p-2 } 는 자신의 인버스와 짝을 지을 수있다.
( 참고 : p 는 5 이상이 가정되었기 때문에, A 는 짝수개의 원소를 갖고, 따라서, B 도 짝수개의 원소를 갖는다 .)
B 내에서 각각의 원소와 그 인버스를 짝지어서 곱하면, 정의에 의해 1 과 합동이므로, B 의 모든 원소를 곱한것은 1 과 합동이다.
따라서, 2 × 3 × ... × p-2 ≡ 1 (mod p) , 즉, 따라서 (p-2)! ≡ 1 (mod p)
여기서 양변에 p-1 을 곱하면... (p-1)! ≡ p-1 (mod p) 즉, (p-1)! ≡ -1 (mod p)
따라서, 윌슨의 정리는 소수 판별에 사용할수 있다. 그러나 팩토리얼이 너무 빠르게 증가하는 탓에 좋은 판별법은 아니다.
a 와 b 는 m 으로 나누어도 나머지가 같고, n 으로 나누어도 나머지가 같다면,
