2010년 10월 30일 토요일

19의 배수 판정법에 대하여..

학교에서 Number Theory 배우다가 Division Test라는 게 있더라.

거긴 1001=7*11*13까지만 나와있었는데..

순간 생각난 게 있어서 한번 써본다.

일단 10^k승의 least nonnegative residue(modulo 19)를 k로 나타내보면 어떻게 나타낼수 있을까.. 하는 것에 대해서 생각해보니까...

일반항은 못구해도 간단한 방법으로 점화식은 가능할 듯 싶다.

뭐 10의 k승이라고 할 것도 없이.

x가 mod 19일때 a와 컨그런스하다고 하다면,

a가 even이면 2k꼴로 나타낼 수 있으며

10x는 20k와 mod 19일때 컨그런스하고, 곧 20k는 k와 컨그런스하다.

한마디로, x 가 2k와 컨그런스하면, 10x는 k와 컨그런스 하다는 이야기.

a가 odd면 a+19는 even이며, 위와 같은 방식으로 할 수 있다.

이걸 이용해보면 10^0, 10^1, 10^2... 10^k까지의 mod 19의 absolute value가 least한 residue를 바로바로 구할 수 있다.

간단히 1, -9, 5, -7, 6, 3...로, 매우 간결한 알고리즘을 이용해서 구할 수 있다.
그 수들을 A_0 = 1, A_1 = -9, A_2= 5 등등으로 나타내서 10^k의 absolute value가 least한 residue를 A_k로 하고.

배수를 판정해야되는 k+1자리 10진수가 (N_k N_k-1 N_k-2 ... N_0)_(10)이 있으면, 그 수는

N_k * 10^k + N_k-1 * 10^k-1 + ... + N_0 * 10^0 = 은
k
시그마 N_i * A_i 로 나타낼 수 있다.
i=0

더 간단히 말하자면, 자리수가 있을때 저 A_k를 손쉽게 전개해서, 각 자리수와 대응해서 곱한다면(마치 벡터처럼) 한 자리 수 * 한 자리 수의 합으로 나타낼 수 있으므로 훨씬 쉽게 구할 수 있다.

현재 19의 배수 판정법이라는 것도 위와 비슷한 이치다. 원리상으론 굉장히 간단하게, ABCDE가 있으면 ABCD+2E와 mod 19일때 컨그런스하기 때문에 한 자리씩 줄인다는 이야기인데..

자릿수가 세~네자리면 굉장히 유용한 방법이라고 생각한다. 하지만 10자리가 넘는다면(아 솔까말 열자리 넘으면 손으로 안하겠제..) 이번에 제안한 방법도 방법이 되지 않을까.

이걸 응용한 방법도 생각해 봤다.

사실 17의 배수 판정법도 금방 응용할 수 있을텐데.

x가 mod 17일때 even인 a(=2k)라고 하면, 10x는 20k, 곧 3k이므로..

뭐 특별한 경우에는, 예를 들자면 16이 mod 17일때 16이니까.

160은 24, 1600은 36, 16000은 54, 160000은 81이 되겠다.

근데 사실 응용하긴 힘들 것 같고.. 그럴 수 있다고만 보면 되겠다.

에고, 피곤하다.

2010년 3월 30일 화요일

Missed Love Number;엇갈린 사랑 수

http://www.research.att.com/~njas/sequences/A005188
의 수열과 비슷한 이치지만..

a = a1a2a3...ap
b = b1b2b3...bq
c = c1c2c3...cr

일때.

a1^p+a2^p+...+ap^p = b
b1^q+b2^q+...+bq^q = c
c1^r+c2^r+...+cr^r = a

를 만족하는 (a, b, c)를

엇갈린 사랑 수라고 한다.

100000 이하의 엇갈린 사랑 수는 (160, 217, 352) 1쌍만이 존재한다.


이 수열과는 무슨 관련이 있는 걸까. 일반화가 더 되어있는 것 같긴 하지만 어떻게 정의를 봐야 할지 잘 모르겠다.

어렵구만.. 참..

Narcissus Number;나르시스 수

n자리의 10진수 a가 있을 때.
a = a1a2a3a4...an 이라고 하자.
그 때, a1^n + a2^n + a3^n + ... + an^n = a을 만족하는 a를,

나르시스 수라고 한다.

ex) 153 = 1^3 + 5^3 + 3^3

나르시스 수는 100000 이하의 범위에 19개가 있으며.

다음과 같다.


1
2
3
4
5
6
7
8
9
153
370
371
407
1634
8208
9474
54748
92727
93084

아니 이런 수열은 없길래, 그냥 명명해봤다.

뭐, 누가 했으면 말고..