Number of products of powers of primes less than n

175 Views Asked by At

Is there a bound for the number of products of powers of a set of prime numbers less than a given number n? For instance, if I am given the set of prime numbers {2,7,11,13} and I am only interested in products of powers of primes less than 32, then there are twelve products of powers of these primes numbers: $2=2^1$, $4=2^2$, $7=7^1$, $8=2^3$, $11=11^1$, $13=13^1$, $14=2^1\cdot 7^1$, $16=2^4$, $22=2^1\cdot 11^1$, $26=2^1\cdot 13^1$, $28=2^2\cdot 7^1$, and $32=2^5$.

I know people have asked about estimating the number of products of primes less than n and estimating the number of prime powers less than n. I am looking for a combination of these two questions.

1

There are 1 best solutions below

0
On

I thougth of this : you want to maximize the function Z = 2$^a$ + 7$^b$ + 11$^c$ + 13$^d$ , whenever z $\leq$ n. You may "linearize" this function by taking natural logarithm. By means of linear simplex method, you may find the máxima... Then you may try and analize which 4 - tuples (a,b,c,d) with integer coordinates are nearest the máxima found . Since exponentiating and taking logarithm are continous, taking "nearby" tuples should work.

I will try to find a more combinatorial answer, though. It is a very interesting question.