352
2016-01-04 09:13:32
2
x^n = x*x^(n-1), x^(n+1) = x*x^n 이므로
둘 사이의 x의 배수는
x*(x^(n-1)+1), x*(x^(n-1)+2), ... , x*(x^n -1)
이들의 개수를 세어보면 x^n - x^(n-1) -1 개 임을 알 수 있습니다.
위 수는 다시 (x-1)*x^(n-1) - 1 인데, 첫 항을 보면 x가 짝수고 n이 2보다 크거나 같으면 x^n-1이 짝수, 홀수면 x-1이 짝수이므로 항상 짝수입니다. 그래서 개수를 나타내는 식은 홀수가 됩니다.
예외가 있다면, x가 짝수고 n이 1인 경우입니다.
이 경우 위 식에서 x^n-1이 1, 홀수가 되어버립니다.
예를들어 4 와 16 사이의 4의 배수는 8, 12로 두개죠.