Find nearest integer with certain prime factors Trying to answer this question, I have sketched a strategy:


Find an integer $N$ "near" to $10^9$ with factors $5$ and $7$, that is, $5^n\cdot7^m$
Conpute $k=N-\varphi(N)$ ($\varphi$ is the totient function). This is the number of multiples of $5$ or $7$ lesser than $N+1$. Think in $k$ as an estimation.
If $N$ is really near from $10^9$ we can count by hand to fix $k$.


My question is: is there some efficient method to achieve the first step? I have written $10^9$ in base $35$ (it is $19.01.13.21.18.20$), but I'm stuck.

Generally speaking: given a positive integer $N$ and some primes $p_1,\ldots,p_k$ and a tolerance $T$, is there any efficient method to find nonnegative integers $n_1,\ldots,n_k$ such that
$$|p_1^{n_1}\cdot\ldots\cdot p_k^{n_k}-N|\leq T$$
if they exist, or prove that they don't if that is the case?
For two factors there is an efficient algorithm.
The following program will find the requested approximation using $O(log(n))$ operation.
It is modeled on  the well known but unnamed algorithm that checks two sorted lists if there is a number in each list such that they sum up to a given number (here and here)

def find_min(n,factor1,factor2):
    product=factor1
    while product&lt;n:
        product*=factor2
    min_diff=product-n 
    min_diff_at=product
    while True:
        if product&gt;n:
            if product%(factor2*factor2)!=0:
                break
            product//=factor2
        elif product&lt;n:
            product*=factor1
        else:
            break
        if abs(product-n)&lt;min_diff:
            min_diff_at=product
            min_diff=abs(product-n)
    return(min_diff_at)


The program generates the following output.

print(find_min(1000000000,5,7))
1008840175


This algorithm can be extended to more factors using two sorted lists where the first list contains all products smaller than the target number that are products of powers of the first half of the given factors and the second list contains the analogous numbers created by the second half of the factors but I don't think that such an algorithm will make sense.
Either the length of the list is rather small and the probability that the approximation is very near to the target number is small or the lists are very large (about the square root of the target number) and scanning the whole list will take to long.
Here a version of the program that outputs more details.
Sketch of an plan:  Using $log$ base $10$, write 

$$n \log 5 +m \log 7 \approx 9.$$

Now we need to approximate $9$ with linear combinations of
two irrational numbers.  The method here seems to be just
the ticket:

https://mathoverflow.net/questions/70035/