The math formula is

n = 1 + k + k^2 + ... + k^(m-1)

The question is : Given n , find integer value of k and m. There are two ways to solve this :

- k = 2 ... n-1, find m
- m = 2 ... log2(n) , find k

It is quite obvious that , we can have a possible O(log(n) ) solution with the second.

After multiplied by k,

nk = k + k^2 + ... + k^(m-1) + k^m

then if the second equation minus the first equation,

nk - n = k^m - 1

we can further have ,

m = pow( nk - n + 1 , 1 / k )

```
class Solution {
func smallestGoodBase(_ n: String) -> String {
let n = Int64( n )!
if n < 3 {
return String( n + 1 )
}
let maxm = Int64( ceil(log2(Double(n))) )
for m in (3...maxm).reversed() {
let maxk = Int64( ceil (pow( Double( n ), 1 / Double( m - 1 ) ) ))
for k in max(2, maxk - 1 )...maxk{
let m1 = log( Double( n ) * Double( k - 1 ) + 1 , forBase: Double(k) )
if abs( Double(m) - m1 ) < 0.00000000000001 {
return String( k )
}
}
}
return String( n - 1 )
}
}
func log( _ val: Double, forBase base: Double) -> Double {
return log(val)/log(base)
}
```