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])
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()