Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Numeric Combinations of Pi and Sqrt(2)

Date: 09/25/2005 at 15:03:19
From: anonymous
Subject: Combinations of Pi and Sqrt(2)  

Say I am given a number X = A*[sqrt]2 + B*[pi], where A and B are
integers.  Given X, how can you find A and B?

My immediate intuition was dot products, because whenever I see a
function which is a linear combination of basis functions, I know I
can take the dot product of the function with each basis function to
get the coefficients of the linear combination.  However, these are
integral coefficients, and it doesn't make sense to say [pi] and
[sqrt]2 are orthogonal functions.  
 
[pi] cannot be expressed as a rational multiple of [sqrt]2.  So there
is only one possible solution, if any.  
 
Is it true that for any [epsilon] > 0, [exists] integers A and B such
that [epsilon] = A[pi] + B[sqrt]2?  How to prove/disprove this?  If it
is true, then perhaps we can argue that the problem is uncomputable,
because finding a solution would require infinite precision
computations, and thus infinite time/space.

A different, simpler, proof that numbers of the form (A[sqrt]2 +
B[pi]) do not consist of all positive reals is simply to note that the
set of such numbers is countable, while the positive reals are not.
 
My thought is to find an integer B satisfying x[sup2] - 2B[pi]x +
B[sup2][pi][sup2] [equiv] 0 mod 1. I may be wrong, but I suspect that
if such a B exists, it has to be unique.



Date: 09/25/2005 at 21:08:46
From: Doctor Vogler
Subject: Re: Combinations of Pi and Sqrt(2)

Hi Anonymous,

Thanks for writing to Dr. Math.  The answer to your question depends
very much on what you know about x.  If you know x exactly, then the
answer to your question is almost certainly obvious, because x will
probably be something like

  x = 2*sqrt(2) + 3*pi.

But I'm guessing that you have x in decimal, as something like

  x = 12.25320508551556981299130759825790480973085194887921360927.

In that case, I will tell you that there are either no solutions, or
infinitely many solutions, and you are just looking for a *good*
solution.  So let's back up and look at a simpler problem.  Suppose
you have a number like

  0.235294117647058823529411764705882352941176470588235294117647

and you think it's a rational number (indeed, it's 4/17) and want to
figure out what the numerator and denominator should be.  It turns out
that there is a convenient way of doing this.  You invert the number
(1/x) and then subtract off the integer part, and repeat until you get
zero.  But here are the issues, and they are precisely the same issues
that appear in your problem.

There is an obvious answer to the above problem, not 4/17 but

   235294117647058823529411764705882352941176470588235294117647
  -------------------------------------------------------------.
  1000000000000000000000000000000000000000000000000000000000000

Now consider why this is not as good an answer as 4/17.  Notice that
this answer is closer to the value that you started with.  The
problem, you see, is round-off error.  You didn't start with
infinitely many digits; you only started with (hopefully) enough to
tell what the number is, which means it should be sufficiently more
than the number of digits in the numerator and denominator of the
solution you're looking for.  Then when you find an answer that's
close (like 4/17), you have to concede that it's not exact, but it's
close enough.  In particular, it's much closer than you would expect a
random fraction of that size.

For example, try to find a rational number that equals

  pi = 3.1415926...

There are plenty of fractions (such as 22/7) that get close, but
you'll find that you have to get very big numbers to get very close;
this is what I mean by being "randomly close."  If we start with a
(supposedly) rational number, then we should expect our solution to be
more than just randomly close.

So perhaps you have a number

  x = A*sqrt(2) + B*pi,

known to several digits, and you want to find small integers A and B
that will be more than randomly close to your number x.  Notice, first
of all, that the right side of the equation is dense, in the sense
that no matter what x value you pick, you can choose integers for A
and B so that the right side will get the first ten million digits of
x correct.  But that's like the "obvious" solution to the rational
number problem I gave above, not the kind of answer you're really
looking for.  You want small numbers A and B, compared to the number
of digits of x (and r) that you have.  In any case, much like the
rational number problem, there are algorithms to find the numbers A
and B.  I won't describe them here.  Instead, I'll tell you where you
can find several of them.

If you search MathWorld for the phrase

  integer relations

at their search site

    http://mathworld.wolfram.com/search/ 

it will give you several links, including a description of what that
phrase means at

  Integer Relation
    http://mathworld.wolfram.com/IntegerRelation.html 

and a list of several algorithms that can accomplish this task, with
links to very short (and not very detailed) descriptions of those
algorithms.  But then you can search the Internet for one (or more) of
these algorithms by name and find out how it works.

I hope this helps.  If you have any questions about this or need more
help, please write back and show me what you have been able to do, and
I will try to offer further suggestions.  And happy searching!

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 



Date: 09/26/2005 at 02:00:49
From: anonymous
Subject: Thank you (Combinations of Pi and Sqrt(2)  )

The links were quite helpful. Thank you.
Associated Topics:
College Discrete Math

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/