50 секунд как-то нереально долго. У меня почти тупой перебор в 0,1 с примерно уложился (не java, но jvm). Ну да, я степени закешировал и последнее число проверяю по HashSet, а не в цикле. Но не в 500 же раз.