Ruling Out Small Denominators
 

Suppose that I have the decimal expansion (up to a certain number of decimal places, which can easily be extended if I have the patience) of a real number (of no special form) and I suspect that the number is irrational. However, I don't know how to prove that the number is irrational.

What is the most computationally efficient way to set a as large as possible lower bound on the size of the denominator, if the number were rational?

[QUOTE=jinydu;85793]Suppose that I have the decimal expansion (up to a certain number of decimal places, which can easily be extended if I have the patience) of a real number (of no special form) and I suspect that the number is irrational. However, I don't know how to prove that the number is irrational.

What is the most computationally efficient way to set a as large as possible lower bound on the size of the denominator, if the number were rational?[/QUOTE]
The solution to your problem is to generate the continued fraction expansion of the number. If it is rational, the number of coefficients will be finite.

So continued fractions is the [B]fastest[/B] way? And if I stop the process after a certain number of steps, recombine the result into a single fraction, then this rules out all fractions with smaller denominators?

[QUOTE=jinydu;85799]So continued fractions is the [B]fastest[/B] way?[/QUOTE]It is the fastest I know. The trick is to compute the continued fraction fast.
[QUOTE=jinydu;85799]And if I stop the process after a certain number of steps, recombine the result into a single fraction, then this rules out all fractions with smaller denominators?[/QUOTE]
Yes.

Rational vs irrational numbers.
 

[QUOTE=alpertron;85798]The solution to your problem is to generate the continued fraction expansion of the number. If it is rational, the number of coefficients will be finite.[/QUOTE]
:no:
What about the rational number 1/3 = 0.3333333.............
The rational number in decimal form will repeat itself sooner or later unless it comes to a dead stop like 7/8 =0.875.
The irrational number will NOT. Take a random example and try it out.
This does not mean that an irratioanl number cannot have a pattern.
Take foir instance 0.123456789101112131415161718...
It is an irrational number and the digits can be predicted. The hundreth digit, the millionith digit and the trillionth didgit will end in 5,1,1,.
There are many different types of numbers besides these but it will go beyond this topic.
Mally :coffee:

[QUOTE=mfgoode;85839]:no:
What about the rational number 1/3 = 0.3333333.............
The rational number in decimal form will repeat itself sooner or later unless it comes to a dead stop like 7/8 =0.875.
The irrational number will NOT. Take a random example and try it out.
This does not mean that an irratioanl number cannot have a pattern.
Take foir instance 0.123456789101112131415161718...
It is an irrational number and the digits can be predicted. The hundreth digit, the millionith digit and the trillionth didgit will end in 5,1,1,.
There are many different types of numbers besides these but it will go beyond this topic.
Mally :coffee:[/QUOTE]
The original poster wrote:

[QUOTE=jinydu]...up to a certain number of decimal places, which can easily be extended if I have the patience...[/QUOTE]

So when he tries 0.3333333... he will find 1/3 very quickly. Adding more 3's will not change the fraction. So after trying, say 100 digits, the fraction found will still be 1/3.

The number 0.123456789101112131415161718... that you wrote above will have an infinite continued fraction expansion. So after you add more digits to the irrational number, you will be able to find more terms of the continued fraction, meaning that the number cannot be expressed by a simple fraction.

Rational vs irrational numbers.
 

[QUOTE=alpertron;85841]The original poster wrote:

So when he tries 0.3333333... he will find 1/3 very quickly. Adding more 3's will not change the fraction. So after trying, say 100 digits, the fraction found will still be 1/3.
.[/QUOTE]
:smile:
The fraction 1/3 is known as an open ended rational.
No amount of three's can give its exact value. It comes closer and closer to
1/3 as one adds more and more of 3's but never the exact 1/3.
After 100 digits the fraction will NOT be 'still' 1/3.
Hence one needs an infinite amount of fractions to describe 1/3.
Over all I agree you mean what you say, but remember, we are dealing in mathematics and rigid exactitude.

Hence this is in direct contradiction of your earlier post
[Quote=alpertron] The solution to your problem is to generate the continued fraction expansion of the number. If it is rational, the number of coefficients will be finite.[/QUOTE]

Mally :coffee:

The idea is that adding more 3's you will not be able to extend the continued fraction:

0.3 = [3, 3]
0.33 = [3, 33]
0.333 = [3, 333]
0.3333 = [3, 3333]
0.33333 = [3, 33333]
0.333333 = [3, 333333]
and so on.

So it appears that the expansion cannot continue after the first three, because the second term increases without limit. So the fraction must be 1/3.

I think that the notion of ""continued fraction expansion" and "decimal expansion " are being mixed up here.

Adding 3's to a continued fraction expansion of 1/3 changes the rational number you are dealing with.

e.g. 1/3= [0;3], but [0;3,3] is not the same as 1/3. In fact, [0;3,3 ] = 3/10.

[QUOTE=Hatori27;85855]I think that the notion of ""continued fraction expansion" and "decimal expansion " are being mixed up here.

Adding 3's to a continued fraction expansion of 1/3 changes the rational number you are dealing with.

e.g. 1/3= [0;3], but [0;3,3] is not the same as 1/3. In fact, [0;3,3 ] = 3/10.[/QUOTE]
Yes, it agrees with the first line I wrote above: 0.3 = [3, 3]. It appears that your notation [0;3,3] is 0+[3,3] (or [3,3])

Continuing with the problem set by the original poster, if the number in question is 0.12345678910111213141516... (which is obviously irrational) we find its continued fraction expansion:

[ 8 , 9 , 1 , 149083 , 1 , 1 , 1 , 4 , 1 , 1 , 1 , 3 , 4 , 1 , 1 , 1 , 15 ,
4575401113910310764836466282429561185996039397104575\
5500066200439309026265925631493795320774712865626829\
1352511788034072479309738318986794132119711326023863\
081376170,
6 , 4 , 1 , 5 , 1 , 1 , ...]

If we convert the continued fraction to standard fractions just before the huge coefficients we get:

10 / 81
60499999499 / 490050000000

The first 189 digits of the last number agrees with the decimal expansion of our irrational number.

Mathematica seems to be behaving strangely. I'm getting:

ContinuedFraction[0.3] = {0, 3}

ContinuedFraction[3/10] = {0, 3, 3}

Even worse:

ContinuedFraction[0.2] = {0}