Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Counting continued fraction numbers

  1. Aug 7, 2011 #1
    I've been playing with a computational system that represents numbers in their simple continued fraction form.

    That is, CF([a0,a1, ... , an]) =a0 + [itex]\frac{1}{ a_{1}+\frac{1}{a_{2}+\ddots\frac{1}{a_{n}}} }[/itex]

    Considering what types of numbers such a system can represent, the finite CF's correspond to the set of rational numbers. Therefore this set is countably infinite (as are the rationals).

    Cantor showed that the real numbers, which corresponds to the set of all finite and infinite CF's, is not countably infinite. What about the quadratic surds, which correspond to infinite continued fractions with a simple repeated pattern? Surds can be represented as a finite 'rational' part and a repeat length, which seems to be countable.

    A wide variety of transcendental numbers also have repeating CF representations, such as [itex]e^{1/n}[/itex] = CF([1, (n-1), 1],[0,2n,0]) = CF([1,(n-1),1,1,(3n-1),1,1,(5n-1),... ]) = [itex]1+\frac{1}{(n-1)+\frac{1}{1+\frac{1}{1+\frac{1}{3n-1+\ddots}}}}[/itex]

    Consider the set of repeating CF's. { [itex] CF( [a_{0}, a_{1}, ..., a_{n} ], [v_{0},v_{1},...,v_{m}]), m<=n [/itex] }, clearly each part, being finite, is countable, is the set of pairs still countably infinite?
    Last edited: Aug 7, 2011
  2. jcsd
  3. Aug 10, 2011 #2
    Quadratic surds are countable.In fact, the set of algebraic numbers is countable.
    Could you help me understand the term 'repeating CFs' and the notation?
    Is it composed of the two parts [itex] CF( [a_{0}, a_{1}, ..., a_{n} ] and [v_{0},v_{1},...,v_{m}]) [/itex]?
  4. Aug 10, 2011 #3
    By 'repeating CFs' I'm referring to continued fractions who's coefficients have an arithmetic progression. For example e ~ 2.718281828 = CF([2,1,2,1],[0,2,0]) = CF([2,1,2,1,1,4,1,1,6,1,1,...]). While quadratic surds have the form [itex] CF( [a_{0}, a_{1}, ..., a_{n} ] and [v_{0},v_{1},...,v_{m}]) [/itex] where all the vi terms are 0's, allowing non-zero vector or offset terms provides exact representations for many non-algebraic numbers (like e).

    Intuitively it seems like this set is also countable, but I'm not sure.
  5. Aug 10, 2011 #4
    Consider f([v0,v1,..vm])=2^(v0+1).3^(v1+1)... p_m^(vm+1). f maps each [v0,v1,..vm] to a unique natural number. Therefore,
    ([a0,a1,...an] ,[v0,v1,..vm])-> (a0,...,an,f([v0,v1,..vm])) is one-one from the set of repeating CFs to Union N^(n+1) over all n. Since the latter is a countable, so are the repeating CFs.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook