Determining the next highest number that can be factored into prime numbers {2,3,5,7}

Question

I would like to write a function that is given an unsigned integer as an input argument and returns the next highest number that can be factored into prime numbers {2, 3, 5, 7}. Here is a short code snippet showing what I want to do.

unsigned int getHigherNumber(unsigned int x)
{
    // obtain the next highest number that can be factored into
    // prime numbers (2, 3, 5, and 7)
    if (~(x % 2 || x % 3 || x % 5 || x % 7))
        return  x;
    else
    {
         // ???
    }  
} // end

The purpose of this function is to find the number of zeros that an array should be padded with to ensure that algorithms such as FFTW (link) can run in an efficient manner. The given link discusses that the algorithm is optimal for an input of a length that can be factored into small primes.

As suggested in the comments to this question, if the FFTW algorithm is to be optimal, it appears that only numbers of the form 2^a * 3^b * 5^c * 7^d are allowed.

I am a bit confused about what you want to do. From the code snippet it looks like you are trying to not find multiples of those primes. Maybe reword the question? — Fantastic Mr Fox, Nov 25 '12 at 23:05
"the standard FFTW distribution works most efficiently for arrays whose size can be factored into small primes (2, 3, 5, and 7)," <- that means the number has no other prime divisors than these. Finding the smallest number `>= x` with that property is considerably harder. But you probably don't need the smallest, just one that is not too much larger than `x`, which is simpler. — Daniel Fischer, Nov 25 '12 at 23:15
@FredOverflow No, that finds the next number that is divisible by all of them, but that may have other prime divisors. Consider `2309 = 210*11 - 1`. — Daniel Fischer, Nov 25 '12 at 23:18
If you mean "divisible by 2, 3, 5 AND 7" then FredOverflows answer is perfect. If you mean "only divisible by primes 2,3,5 and/or 7, but no others", you might want to increment your value until this condition holds (or use some kind of heuristic) — stefan, Nov 25 '12 at 23:20
@Daniel: Aha, so only numbers of the form 2^a * 3^b * 5^c * 7^d are allowed? Why didn't Nicholas specify it like that then? :) I'm still not sture what he actually wants. — fredoverflow, Nov 25 '12 at 23:36
@FredOverflow I think he just didn't quite understand what the remark means. — Daniel Fischer, Nov 25 '12 at 23:39
Thank you all for your help! I have to admit: the remark on the FFTW website is somewhat open to interpretation, and I think that FredOverflow's comment is somewhat on the right track. Given `x`, I would like to find the next highest number `y` such that `y` can be factored into small primes. — Nicholas Kinar, Nov 25 '12 at 23:49

cacba · Answer 1 · 2012-11-25T23:44:56.703

For example, the standard FFTW distribution works most efficiently for arrays whose size can be factored into small primes (2, 3, 5, and 7), and otherwise it uses a slower general-purpose routine.

Really you dont need the next highest, but just something that is reasonably close. The simplest way to do this is just pick the power of 2 that is closest. This will waste at most the size of the original array.

To do this find the most significant bit and multiply it by 2.

The obvious way of finding the most significant bit:


    unsigned int v; // 32-bit word to find the log base 2 of  
    unsigned int r = 0; // r will be most significant bit

    while (v >>= 1)   
    {  
        r++;
    }

Thank you as well for this answer. It is a very simple and useful solution. — Nicholas Kinar, Nov 28 '12 at 00:24

score 2 · Answer 2 · answered Nov 25 '12 at 23:39

Building on a previous answer, If the array is going to be very big ~ 2^10, and you want to use as little extra space as possible while keeping it simple, you could also choose the largest power of 7 less than x, multiplied by the largest power of 5, and so on. That is

unsigned int getHigherNumber(unsigned int x)
{
    unsigned int ans=1;
    unsigned int primes[4]={2,3,5,7};
    for(int i=3; i>=0; i--)
    {
        for(int j=0; ; j++)
        {
            if(pow(primes[i],j)>x)
            {
                ans*=pow(7,j-1);
                if(i==0)
                    ans*=2;
                break;
            }
        }
    }
    return ans;
}

(Untested). I think that ought to get you a smaller number than just the nearest power of 2, at the cost of some speed. It definitely isn't optimal though.

Thank you drowdemon for contributing your answer; it adds to this discussion. — Nicholas Kinar, Nov 28 '12 at 00:23

score 0 · Accepted Answer · answered Nov 26 '12 at 03:01

The following algorithm and source code may not be highly optimized to find the next highest number of the general form (2^a * 3^b * 5^c * 7^d), but it is useful in that the code will return the highest number with one of these powers.

The algorithm first checks if the number is a power of {2,3,5,7}. If it is, then the number is simply returned. If not, then the algorithm finds the smallest power that is higher than the input number.

More sophisticated methods would use prime-factorization algorithms and searching/sorting, or perhaps a hard-coded look-up table, but these solutions may be too complex for this application.

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

// http://stackoverflow.com/questions/1804311/how-to-check-if-an-integer-is-power-of-3
// Checks if n^x
int powerOf(int n, int x)
{
    while (n % x == 0) 
    {
        n /= x;
    }
return n == 1;
}

unsigned int hN(unsigned int x, unsigned int base)
{
    double exponent = std::ceil( std::log(x) / std::log(base) );
    double num = std::pow(base, exponent);
return static_cast<unsigned int>(num);
}

unsigned int getHigherNumber(unsigned int n)
{
    unsigned int rv = n;
    const int pnum = 4;

    // 1) Is the number a power of {2,3,5,7}?
    // If it is, then simply return it
    if(powerOf(n,2)) return rv;
    if(powerOf(n,3)) return rv;
    if(powerOf(n,5)) return rv;
    if(powerOf(n,7)) return rv;

    // 2) If not, then find next highest power of {2,3,5,7} that is the smallest
    // number higher than n
    unsigned int num0 = hN(n, 2);
    unsigned int num1 = hN(n, 3);
    unsigned int num2 = hN(n, 5);
    unsigned int num3 = hN(n, 7);

    std::vector<unsigned int>v(pnum);
    v[0] = num0;
    v[1] = num1;
    v[2] = num2;
    v[3] = num3;
    rv = *std::min_element(v.begin(),v.end());

    // 3) TODO: More sophisticated methods would use prime-factorization
    // algorithms and searching/sorting, or perhaps a look-up table, 
    // but these may be too complex for this application

 return rv;
} // end


int main()
{
    // const unsigned int num = 64;
    // const unsigned int num = 18;
    const unsigned int num = 2234;
    std::cout << "num = " << num << std::endl;
    std::cout << "higher number = " << getHigherNumber( num ) << std::endl;

} // end

Determining the next highest number that can be factored into prime numbers {2,3,5,7}

3 Answers3