Finding N / log(2) and M / log(3) very close together

  • I
  • Thread starter Swamp Thing
  • Start date
In summary: Log[2], Log[3] pairs together.In summary, the efficient algorithm for finding pairs of M and N such that ##| M/log(2) - N/log(3) |< \delta## is to choose now ##(M/N)\in \left\{\dfrac{6}{10},\dfrac{63}{100},\dfrac{631}{1000},\dfrac{6309}{10000},\ldots\right\}## which gets as small as you like.
  • #1
Swamp Thing
Insights Author
899
556
What would be an efficient algorithm for finding pairs of M and N such that ##| M/log(2) - N/log(3) |< \delta## , for some given small ##\delta## ?

Also, such pairs would obviously become scarcer as we reduce ##\delta##, but how does it go quantitatively?
 
Mathematics news on Phys.org
  • #2
Where are ##M,N## from? How do you define "efficient"? Which computation model do you use?

The best approximation is ##\dfrac{M}{\log 2}=\dfrac{N}{\log 3}## or ##\dfrac{M}{N}=\dfrac{\log 2}{\log 3}\approx 0,6309297535714574370995271143427\ldots##

You can choose now ##(M/N)\in \left\{\dfrac{6}{10},\dfrac{63}{100},\dfrac{631}{1000},\dfrac{6309}{10000},\ldots\right\}## which gets as small as you like.
 
Last edited:
  • Like
Likes Swamp Thing, pbuk, topsquark and 1 other person
  • #3
That's not actually obvious to me @fresh_42 . In fact for ##|2/9M -N|## taking ##N=22...2## ##n## twos, and ##M=10^n## yields ##|2/9M -N|=2/9## for all ##n##
 
  • Informative
Likes FactChecker
  • #4
Office_Shredder said:
That's not actually obvious to me @fresh_42 . In fact for ##|2/9M -N|## taking ##N=22...2## ##n## twos, and ##M=10^n## yields ##|2/9M -N|=2/9## for all ##n##
It has been open and unanswered the entire day and I didn't know whether I should solve it, which would have been against the rules, ask for clarification, which I did, expecting a dialogue with the OP, or use a few scribblings with ##\dfrac{M}{\log 2}=\dfrac{N}{\log 3}+\varepsilon .##

\begin{align*}
\left|\dfrac{M}{\log 2}-\dfrac{N}{\log 3}\right|&=\varepsilon \\[6pt]
\left|M \log 3 - N \log 2\right|&=\varepsilon \cdot \log 2\cdot \log 3\\[6pt]
\left|\dfrac{M}{N}-\dfrac{\log 2}{\log 3}\right|&=\dfrac{\varepsilon \cdot \log 2 }{N}
\end{align*}
The approximation of ##\dfrac{M}{N}## by ##0,6309297535714574370995271143427\ldots## makes ##\varepsilon \cdot \log 2 ## arbitrary small for large enough ##N##.

Did I make a mistake?
 
  • #5
I think so. Maybe there's some special property of log that makes that happen to be true, but the right hand side only goes to zero because N does. If you try to do that procedure with ##2/9## (just picking something easier to compute) at least I found ##\epsilon## to not go to zero as N went to infinity
 
  • #6
fresh_42 said:
You can choose now ##(M/N)\in \left\{\dfrac{6}{10},\dfrac{63}{100},\dfrac{631}{1000},\dfrac{6309}{10000},\ldots\right\}## which gets as small as you like.
This may be a silly question, but can we be sure there isn't one between ##{\dfrac{631}{1000}}## and ##{\dfrac{6309}{10000}}## ? This list is based on base 10, but other number bases could give different lists?

How do you define "efficient"?
Loosely, I guess. :smile: But I'd like to catch all of the pairs that exist up to a given size of M and N.

I may have posed the question in a non-optimal way, so here is the motivation: We have impulse trains with periods 2 Pi / Log(2) and 2 Pi / Log(3). How can we locate all instances when a pair of pulses, one from each series, gets closer than a given delta?
 
  • #7
Office_Shredder said:
I think so. Maybe there's some special property of log that makes that happen to be true, but the right hand side only goes to zero because N does. If you try to do that procedure with ##2/9## (just picking something easier to compute) at least I found ##\epsilon## to not go to zero as N went to infinity
You are right. I must be more careful with ##N## such that it doesn't cancel or lead to a lower bound of ##\delta ##.
 
Last edited:
  • #8
Yep, it is officially not as trivial as I thought or even trivial at all. We are actually looking for integer values that make the determinant ##\left\| \begin{pmatrix}\log 3 &N \\ \log 2 &M \end{pmatrix}\right\|## or the cell of the corresponding lattice arbitrary small.

I am sure that there is a fancy algorithm for that problem.

Edit: I have found out that there is a solution: Dirichlet 1842 (p.9ff)
https://sites.math.washington.edu/~rothvoss/lecturenotes/IntOpt-and-Lattices.pdf

What a day. From ##O(1)## in the morning to NP-hard at night. It is especially embarrassing since I am 90% sure that I recorded verbal exams about the LLL algorithm many, many years ago.
 
Last edited:
  • Like
  • Informative
Likes FactChecker and Swamp Thing
  • #9
Thanks... I am trying to understand the Roth-Voss PDF.

After searching for "Mathematica, lattice" I learned that you can use for example, Rationalize[ Log[2] / Log[3], 0.00001] to find fractions that approximate the ratio to within the given delta.

Now, I would also like to find m1 Log[2], m2 Log[3] and m3 Log[5] close together within a given delta. (And so on to include Log[6], Log[7] etc) . Mathematica has a LatticeReduce function. I don't understand it fully, but I'm hoping it can be used to find such points. Can LatticeReduce or some other Mathematica function do this?
 
  • #10
I looked at some examples of LatticeReduce and did some trial and error. Finally I could use it for Log[2] and Log[3]:
Code:
v = {2 Pi/ Log[2], 2 Pi / Log[3]};
big = Round[10^9 v];
a = {{1, 0, big[[1]]}, {0, 1, big[[2]]}};
b = LatticeReduce[a];{N[b[[1, 1]] 2 Pi /Log[2], 12], N[b[[1, 2]] 2 Pi / Log[3], 12]}
{N[b[[2, 1]] 2 Pi /Log[2], 12], N[b[[2, 2]] 2 Pi /Log[3], 12]}

Output:
{288865.441279, -288865.441219}
{430284.142425, -430284.142515}
So b11, b12 gives me one pair of M, N and b21, b22 gives another pair.

But now when I try it with three logs, I can't figure out how to use the LatticeReduced "b" to get my M1, M2, M3.
I suspect that I have to try multiplying two (or three?) elements of b by each Log thing, but which ones?
 

1. What is the significance of finding N / log(2) and M / log(3) very close together?

Finding N / log(2) and M / log(3) very close together is significant because it suggests that there may be a relationship between the two values. This could potentially lead to a new mathematical formula or concept.

2. How can we determine if N / log(2) and M / log(3) are close together?

To determine if N / log(2) and M / log(3) are close together, we can calculate the difference between the two values and compare it to a predetermined threshold. If the difference is smaller than the threshold, we can consider them to be close together.

3. What factors can affect the closeness of N / log(2) and M / log(3)?

There are a few factors that can affect the closeness of N / log(2) and M / log(3). These include the values of N and M, the base of the logarithms (2 and 3 in this case), and the precision of the calculations.

4. How is finding N / log(2) and M / log(3) related to logarithms?

Finding N / log(2) and M / log(3) being close together is related to logarithms because the values are being divided by the logarithms of 2 and 3, respectively. This means that the values are being normalized and can be compared more easily.

5. Can finding N / log(2) and M / log(3) being close together have practical applications?

Yes, finding N / log(2) and M / log(3) being close together can have practical applications in various fields such as mathematics, computer science, and engineering. It can help in identifying patterns and relationships between different values and can also be used in data compression algorithms.

Similar threads

Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
612
  • General Math
Replies
16
Views
3K
Replies
17
Views
2K
  • General Math
Replies
3
Views
1K
Replies
16
Views
1K
Replies
7
Views
1K
Replies
6
Views
1K
  • General Math
Replies
4
Views
1K
Replies
4
Views
2K
Back
Top