Compute elements from OEIS A258484 ... https://oeis.org/A258484

A258484.py

from itertools import combinations, chain
from math import prod


def _powA258484(i, n):
    """Return i**n for two integers i and n."""

    # NOTE: Putting in these special cases sped up the search
    #       process enough to be worth it (measured via timeit)
    if n == 0:
        if i == 0:
            raise ValueError("0 ** 0")
        return 1
    elif n == 1:
        return i
    elif n == 2:
        return i * i
    # generic algorithm for all other cases
    r = 1
    for _ in range(n):
        r *= i
    return r


def primefactors_gen(n):
    i = 2
    while i * i <= n:
        while (n % i) == 0:
            yield i
            n //= i
        i += 1
    if n > 1:
        yield n


def primefactors(n):
    return list(primefactors_gen(n))


def A258484(n):
    """Return 'base' per OEIS sequence A258484 (https://oeis.org/A258484).

    Given the digits d[0], d[1], ... d[k] of integer n, if the sum:
        b**d[0] + b**d[1] + ... b**d[k]
    equals n, then b is an A258484 'base' of n. Return the lowest such b
    or zero if no such b is found for n.
    """

    # Optimization: if there are no zero digits, then if the number
    # meets the A258484 sequence criteria then, by definition:
    #
    #   n = b**d[0] + b**d[1] + b**d[k], all d[i] > 0
    #
    # therefore
    #
    #   n = b * (b**(d[0]-1) + ... + b**(d[k]-1)), and thus:
    #   n / b = (b**(d[0]-1) + ... + b**(d[k]-1))
    # and if there are no zero digits then all the exponents on the right
    # hand side are non-negative; therefore the sum is an integer value.
    # Therefore b can only be a base of n if it divides n evenly.
    #
    # More generally, if there are Z zero digits, each of those will
    # become a 1 in the expansion (b**0 being 1), and therefore b can
    # only be a base of n if b divides n-Z evenly, where "Z" is the
    # number of zero digits.
    #
    # It follows from this that only prime factors of n-Z and their
    # multiplicative combinations need be explored. This loop does that.
    #
    digits = [int(a) for a in str(n)]
    factors = primefactors(n - digits.count(0))

    # construct all the unique possible candidates from the prime factors
    powerset = chain.from_iterable(
        combinations(factors, k) for k in range(1, len(factors) + 1))
    candidates = set(prod(f) for f in powerset)
    # NOTE: None of the results known/shown in OEIS have more than one
    #       base, so sorting MIGHT be superfluous. Do it anyway.
    for b in sorted(candidates):
        if sum([_powA258484(b, d) for d in digits]) == n:
            return b


if __name__ == "__main__":
    import unittest
    import time

    class TestMethods(unittest.TestCase):
        # test data downloaded from
        #     https://oeis.org/A258484/a258484.txt
        # but without the "trivial" examples of numbers that
        # contain only 0 and 1 digits.
        #
        # Each entry is a tuple: (number, base)

        SEQUENCE_DATA = (
            (12, 3), (1033, 8), (2112, 32), (4624, 4), (20102, 100),
            (31301, 25), (101121, 316), (120202, 200), (121101, 346),
            (595968, 4), (1010203, 100), (1053202, 16), (1224103, 33),
            (2210210, 858), (3909511, 5), (13177388, 7), (52135640, 19),
            (102531321, 40), (1347536041, 20), (2202212102, 19158),
            (2524232305, 66), (2758053616, 15), (4303553602, 40),
            (5117557126, 22), (7413245658, 17), (10111202111, 71101),
            (16250130152, 50), (21320202203, 2200), (25236435456, 48),
            (35751665247, 29), (77399307003, 15), (165781640676, 25),
            (235515132012, 151), (405287637330, 28), (419370838921, 18),
            (453362316342, 78), (833904227332, 21), (835713473952, 21),
            (985992657240, 19)
        )

        def test1(self):
            for n, b in self.SEQUENCE_DATA:
                self.assertEqual(A258484(n), b)

        def test2(self):
            members = [t[0] for t in self.SEQUENCE_DATA]
            arbitrary_time_limit = 10      # in seconds
            t0 = time.time()
            k = 1
            while time.time() - t0 < arbitrary_time_limit:
                unroll_batch = 1000
                for unroll in range(unroll_batch):
                    n = k + unroll
                    if A258484(n):
                        # if it is all 0 and 1 digits it won't be in members
                        if any(d not in '01' for d in str(n)):
                            self.assertTrue(n in members)
                        else:
                            self.assertFalse(n in members)
                k += unroll_batch

    unittest.main()