viewimage.php?id=3ab2df2decdc3fab6fabde&no=24b0d769e1d32ca73dea8efa1bd8233ca84d96601323168f99db5dafb40d563b653d3ef8305b681723353fef777f2838324cc2b09df0dd7f3d4ac698a2ac32821fa71af517644cd9


콜라츠 수열(3):


f(n, x) = {x·3n-2n-1}/2n-1



x가 짝수이면 x/2

x가 홀수이면 (3x+1)


w(n) = 4 , 1, 10, 2, 16, 3, 22, 4, 28, 5, …


c(n, m) = w0(m), w1(m), w2(m), w3(m), w4(m), w5(m), …


c(n, m) = m, w(m), w(w(m)), w(w(w(m))), w(w(w(w(m)))), w(w(w(w(w(m))))), …


따라서 콜라츠 수열 c(n)은 수열 w(n)에 대한 연구로 귀결된다.




z가 홀수라면

3z+1은 짝수이므로 2로 나누면 (3z+1)/2


즉

z → 3z+1 → (3z+1)/2


만약 (3z+1)/2 = z'가 홀수라면

위의 과정을 반복할 수 있다.


즉

z' → 3z'+1 → (3z'+1)/2


마찬가지로

(3z'+1)/2 = z''가 홀수라면

위의 과정을 반복할 수 있다.


즉

z'' → 3z''+1 → (3z''+1)/2


만약

(3z+1)/2, (3z'+1)/2, (3z''+1)/2이 홀수가 아니고 2의 멱승이라면 단계를 끝낸다.




일반화


제1단계) z → 3z+1 → (3z+1)/2 = z'

제2단계) z' → 3z'+1 → (3z'+1)/2 = z''

제3단계) z'' → 3z''+1 → (3z''+1)/2 = z'''


z'를 z를 이용하여 나타낼 수 있고,

z''를 z를 이용하여 나타낼 수 있고,

z'''를 z를 이용하여 나타낼 수 있다.


이를테면

z'' = (3z'+1)/2 = (3(3z+1)/2+1)/2 = (9z+5)/4


f(1, z) = (3z+1)/2

f(2, z) = (9z+5)/4

…


행렬에서 해밀턴-케일리 공식과

다항식의 나머지 정리를 이용하면

다음을 얻게 된다.


f(n, z) = (3nz+3n-2n)/2n


◆◆◆◆◆◆


z가 홀수이므로

자연수 x에 대하여

z = 2x - 1로 놓으면

f(n, x) = (3nx-2n-1)/2n-1


이것이 2의 멱승

2m 꼴이 되기를 원하므로


(3nx-2n-1)/2n-1 = 2m


∴ x = 2n-1(2m+1)/3n





m=1일 때:


x = 2n-1(2m+1)/3n


x = 2n-131-n


자연수 n = 1로 놓으면

자연수 x = 1

z = 2x-1 = 1


실제로

제1단계) z=1 → 3z+1=4, (3z+1)/2=2로 2의 멱승 꼴이다.




m=2일 때:


x = 2n-1(2m+1)/3n


x = 5·2n-1·3-n


자연수 n에 대하여

x가 자연수가 될 수 없다.





m=3일 때:


x = 2n-1(2m+1)/3n


x = 2n-1·32-n


자연수 n=1에 대하여

x=3, z=2x-1=5


제1단계) 5 → 16 → 8로 1단계에서 2의 멱승이 얻어진다.


자연수 n=2에 대하여

x=2, z=2x-1=3


제1단계) 3 → 10 → 5

제2단계) 5 → 16 → 8로 2단계에서 2의 멱승이 얻어진다.




해를 갖도록 일반화 해보자.


일반화


x = 2n-1(2m+1)/3n


(2m+1) 이 3의 배수인 경우에 해를 갖는다.


m이 홀수인 경우이므로

자연수 M에 대하여

m = 2M-1을 대입하면


x = 2n-1(22M-1+1)/3n


M=3을 대입하면

x = 11·2n-1·31-n


n=1일 때

x = 11, z=2x-1=21


제1단계) 21 → 64 → 32로 제1단계에서 2의 멱승이다.






x = 2n-1(22M-1+1)/3n


M=5일 때

x = 19·2n-1·33-n


n=1일 때

x=171, z=2x-1=341


제1단계) 341 → 1024 → 512로 제1단계에서 2의 멱승이다.


n=2일 때

x=114, z=2x-1=227


제1단계) 227 → 682 → 341

제2단계) 341 → 1024 → 512로 제2단계에서 2의 멱승이다.



n=3일 때

x=76, z=2x-1=151


홀수 151은 3단계에서 2의 멱승이 나타난다.


확인해보자.



제1단계) 151 → 454 → 227

제2단계) 227 → 682 → 341

제3단계) 341 → 1024 → 512로 제3단계에서 2의 멱승이다.