Checking if a number (M) is a product of powers of other numbers (2,3,5,7)

Question

Forgive me if this is a basic question, I tried to Google but apparently I missed the key words.

I am trying to program in clFFT, and one requirement for the length (M) of the work is such that it is divisible by the product of powers of 2, 3, 5, 7:

Supported radices clFFT supports transform sizes that are powers of 2, 3, 5, and 7. This means that the vector lengths can be a combination of powers of two, three, five, and seven; examples include 2^7,2^1∗3^1,3^2∗5^4,2^2∗3^3∗5^5, up to the limit that the device can support.

Is there a fast way to check if a number M fulfill the above requirement? Following this: How to check if an integer is a power of 3? My guess is I can combine the radices such that, if a number M is divisible by either 2^a, 3^b, 5^c and 7^d, then mod(2^a*3^b*5^c*7^d,M) should be zero, i.e. M divides 2^a*3^b*5^c*7^d, but I don't have a proof for it.

score 1 · Answer 1 · answered Oct 28 '19 at 19:12

You simply do the factorization steps with the number and check if the result after removing all the 2s 3s 5s and 7s from the prime factorization that the result is one. The follow is an example of this applied to 12345 in Python:

x = 12345

a = 0
while x % 2 == 0:
    a += 1
    x /= 2
b = 0
while x % 3 == 0:
    b += 1
    x /= 3
c = 0
while x % 5 == 0:
    c += 1
    x /= 5
d = 0
while x % 7 == 0:
    d += 1
    x /= 7

x == 1
x

x == 1 is False because x is 823. As 12345 == 2**0*3**1*5**1*7**0*823. This also gives you the values of a,b,c,d.

Another example would be 79380 which is 2^2*3^4*5^1*7^2.

Checking if a number (M) is a product of powers of other numbers (2,3,5,7)

1 Answers1