Smallest repunit base

Given an integer n (3 <= n <= 10^18) provided as a Python int, find the smallest base k >= 2 such that the representation of n in base k consists entirely of 1s, i.e. n = 1 + k + k^2 + ... + k^m for some m >= 1. Return k. For example n = 13 = 111 in base 3, so the answer is 3. Every n has the trivial representation 11 in base n-1, so an answer always exists.