nextn: Find Highly Composite Numbers

nextnR Documentation

Find Highly Composite Numbers


nextn returns the smallest integer, greater than or equal to n, which can be obtained as a product of powers of the values contained in factors.

nextn() is intended to be used to find a suitable length to zero-pad the argument of fft so that the transform is computed quickly. The default value for factors ensures this.


nextn(n, factors = c(2,3,5))



a vector of integer numbers (of type "integer" or "double").


a vector of positive integer factors (at least 2 and preferably relative prime, see the note).


a vector of the same length as n, of type "integer" when the values are small enough (determined before computing them) and "double" otherwise.


If the factors in factors are not relative prime, i.e., have themselves a common factor larger than one, the result may be wrong in the sense that it may not be the smallest integer. E.g., nextn(91, c(2,6)) returns 128 instead of 96 as nextn(91, c(2,3)) returns.

When the resulting N <- nextn(..) is larger than 2^53, a warning with the true 64-bit integer value is signalled, as integers above that range may not be representable in double precision.

If you really need to deal with such large integers, it may be advisable to use package gmp.

See Also

convolve, fft.


nextn(1001) # 1024
n <- 1:100 ; plot(n, nextn(n) - n, type = "o", lwd=2, cex=1/2)