Special Number Count

Question

It is a number whose gcd of (sum of quartic power of its digits, the product of its digits) is more than 1. eg. 123 is a special number because hcf of(1+16+81, 6) is more than 1.

I have to find the count of all these numbers that are below input n. eg. for n=120 their are 57 special numbers between (1 and 120)

I have done a code but its very slow can you please tell me to do it in some good and fast way. Is there is any way to do it using some maths.

import math,numpy
t = int(input())

ans = []

for i in range(0,t):
    ans.append(0)
    n = int(input())
    for j in range(1, n+1):
        res = math.gcd(sum([pow(int(k),4) for k in str(j)]),numpy.prod([int(k) for k in str(j)]))
        if res>1:
            ans[i] = ans[i] + 1

for i in range(0,t):
    print(ans[i])

Answer 1

The critical observation is that the decimal representations of special numbers constitute a regular language. Below is a finite-state recognizer in Python. Essentially we track the prime factors of the product (gcd > 1 being equivalent to having a prime factor in common) and the residue of the sum of powers mod 2×3×5×7, as well as a little bit of state to handle edge cases involving zeros.

From there, we can construct an explicit automaton and then count the number of accepting strings whose value is less than n using dynamic programming.

def is_special(digits):
    greater_than_zero = False
    greater_than_one = False
    prod_zero = False
    prod_two = False
    mod_two = 0
    prod_three = False
    mod_three = 0
    prod_five = False
    mod_five = 0
    prod_seven = False
    mod_seven = 0
    for d in digits:
        if d > 1:
            greater_than_one = True
        elif d == 1:
            if greater_than_zero:
                greater_than_one = True
            else:
                greater_than_zero = True
        if d == 0:
            prod_zero = True
        if d % 2 == 0:
            prod_two = True
        mod_two = (mod_two + d ** 4) % 2
        if d % 3 == 0:
            prod_three = True
        mod_three = (mod_three + d ** 4) % 3
        if d % 5 == 0:
            prod_five = True
        mod_five = (mod_five + d ** 4) % 5
        if d % 7 == 0:
            prod_seven = True
        mod_seven = (mod_seven + d ** 4) % 7
    return (
        greater_than_one
        if prod_zero
        else (
            (prod_two and mod_two == 0)
            or (prod_three and mod_three == 0)
            or (prod_five and mod_five == 0)
            or (prod_seven and mod_seven == 0)
        )
    )


# Test case
import functools
import math
import operator


def digits_of(n):
    return [int(digit) for digit in str(n)]


def is_special_reference(digits):
    power_sum = sum(digit ** 4 for digit in digits)
    product = functools.reduce(operator.mul, digits, 1)
    return math.gcd(power_sum, product) > 1


def test():
    for n in range(10000):
        digits = digits_of(n)
        assert is_special(digits) == is_special_reference(digits), str(n)


if __name__ == "__main__":
    test()