Wenn du eine Vermutung für einen Algorithmus hast, setz dich hin und programmieren ihn. Dann siehst du ja, ob er funktioniert oder nicht.
Deinem Lösungsweg kann man übrigens nicht vertrauen, denn es kommt unabhängig der Eingabe immer n-1 raus.
x^(log n / log x) - 1 ist immer n - 1.
Und versuche dich nicht gleich an den Mersenne-Zahlen, die sind im wahrsten Sinne noch etwas zu groß für dich.
