2

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?

Community
  • 1
ajotatxe
  • 65,084
  • 2
    Bruteforcing it for such "small" numbers doesn't seem to be bad here. Calculate all $5^n·7^m$ for $n\leq9·ln(10)/ln(5)$ and $m\leq9·ln(10)/ln(7)$ , that doesn't take too long. – Michael Stocker Oct 16 '14 at 09:06
  • @MichaelStocker Yes, it seems that a brute force approach is not bad, after all. Possible algorithms seems to have a logarithmic cost, more or less. If the number of primes is big, its exponents will be small, and the number of cases to check doesn't become very big. – ajotatxe Oct 16 '14 at 21:27
  • You want integers $n_1,\dots,n_k$ such that $$|(\log p_1)n_1+\cdots+(\log p_k)n_k-\log N|$$ is small. The keyphrase is "inhomogeneous diophantine approximation". – Gerry Myerson Oct 19 '14 at 09:11

2 Answers2

0

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<n:
        product*=factor2
    min_diff=product-n 
    min_diff_at=product
    while True:
        if product>n:
            if product%(factor2*factor2)!=0:
                break
            product//=factor2
        elif product<n:
            product*=factor1
        else:
            break
        if abs(product-n)<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.

miracle173
  • 11,049
-1

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/

B. Goddard
  • 1