해우응님이 기본적으로 풀어주신 것 같기는 한데, 생략하신 부분이 너무 많아서 조금 이해하기가 어렵군요.

m^k <= a_n < (m+1)^k 를 만족하는 자연수 m에 대해서, a_(n+1) = a_n + m 입니다.

즉

1 <= a_n < 2^k 일 때는 a_(n+1) = a_n + 1

2 <= a_n < 3^k 일 때는 a_(n+1) = a_n + 2

3 <= a_n < 4^k 일 때는 a_(n+1) = a_n + 3

...

입니다. 그러니까 m^k 직전까지는 m-1 씩 증가하다가 m^k을 넘어가고 나면 m씩 증가하는 패턴이 나오는 것이지요.

그런데 (m+1)^k - m^k = ( (m+1) - m )( (m+1)^(k-1) + (m+1)^(k-2)m + (m+1)^(k-3) m^2 + ...) 이므로

(m+1)^k - m^k 를 m으로 나눈 나머지는 (m+1)^(k-1) 과 같습니다. 즉 1입니다.

따라서 A_k 에서 m^k 이상인 최초의 항을 m^k + r 이라고 할 때,

m^k + r + m,  m^k + r + 2m, ... 으로 나가다가 최초로 (m+1)^k을 넘어가는 항은

r > 0 인 경우 (m+1)^k + (r-1) 

r = 0 인 경우 (m+1)^k + (m-1) 이 됩니다.

즉 각 m에 대해서 m^k 이상인 최초의 A_k 원소는

2 => 2^k

3 => 3^k + 1

4 => 4^k

5 => 5^k + 3

6 => 6^k + 2

7 => 7^k + 1

8 => 8^k

...

가 됩니다.

즉 m = 2^t 인 경우 [m^k, (m+1)^k) 에서 A_k의 원소는 m^k + mn 인 숫자들이,

m = 2^t + r 인 경우 (r > 0), [m^k, (m+1)^k) 에서 A_k의 원소는 m^k + (2^t - r) + mn 인 숫자들이 A_k 의 원소가 됩니다.

아마도 해우응님의 풀이는 이렇게 m^k 가 A_k 에 나타나는 숫자 m은 2^t 형태라는 것을 말씀하신 것 같은데, 확실히는 모르겠습니다.