[math-fun] Turning a fraction into an integer
Hello Math-Funsters, I was looking for a way to represent any fraction with one single integer. Do you know if there is a common way to do that or a paper about it? I came up with this (heavy?) idea: concatenate N and D and encode the place of the slash "/". So, the fraction we want to represent is N/D. We build the integer NDBA with four concatenated strings of digits. Starting from the right: A is a single digit B is a string that has length A (if A=0 then A=10) D is the denominator of the fraction N/D N is the numerator of the fraction N/D To reconstruct the fraction N/D from NDBA we: - read A - compute the length of B - read B - insert the symbol "/" after B digits, starting the count from the leftmost digit of NDBA - erase A and B Examples: The fraction 1/2 --> 1211 [or 12.1.1 --> 1/2] The fraction 113/355 --> 11335531 [113/355.3.1] The fraction 2015/1234567890 --> 2015123456789041 [2015/1234567890.4.1] The fraction 1234567890/888 --> 1234567890888102 [1234567890888.10.2] etc. This system works for N having less than 10 billion digits, of course -- which seems ok in our everyday life (we would have an integer like ND.9999999999.0 with ten 9's) Best, É. P.-S. Many integers will not represent any fraction -- but this is another story (10211 would produce the fraction 1/02, for instance).
On 2015-11-19 10:30, Eric Angelini wrote:
Hello Math-Funsters,
I was looking for a way to represent any fraction with one single integer. Do you know if there is a common way to do that or a paper about it?
Any method of showing that the rationals are countable implicitly has such a representation. There's a paper by ?? & Wilf on "counting the rationals", which, if I recall correctly, has an example of an explicit formula.
I came up with this (heavy?) idea: concatenate N and D and encode the place of the slash "/".
So, the fraction we want to represent is N/D. We build the integer NDBA with four concatenated strings of digits. Starting from the right:
A is a single digit B is a string that has length A (if A=0 then A=10) D is the denominator of the fraction N/D N is the numerator of the fraction N/D
To reconstruct the fraction N/D from NDBA we:
- read A - compute the length of B - read B - insert the symbol "/" after B digits, starting the count from the leftmost digit of NDBA - erase A and B
Examples:
The fraction 1/2 --> 1211 [or 12.1.1 --> 1/2] The fraction 113/355 --> 11335531 [113/355.3.1] The fraction 2015/1234567890 --> 2015123456789041 [2015/1234567890.4.1] The fraction 1234567890/888 --> 1234567890888102 [1234567890888.10.2] etc.
This system works for N having less than 10 billion digits, of course -- which seems ok in our everyday life (we would have an integer like ND.9999999999.0 with ten 9's)
Best, É.
P.-S. Many integers will not represent any fraction -- but this is another story (10211 would produce the fraction 1/02, for instance).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Thu, Nov 19, 2015 at 10:44 AM, Michael Greenwald <mbgreen@seas.upenn.edu> wrote:
On 2015-11-19 10:30, Eric Angelini wrote:
Hello Math-Funsters,
I was looking for a way to represent any fraction with one single integer. Do you know if there is a common way to do that or a paper about it?
Any method of showing that the rationals are countable implicitly has such a representation. There's a paper by ?? & Wilf on "counting the rationals", which, if I recall correctly, has an example of an explicit formula.
I think this is the sequence you're referring to. It has each nonnegative rational exactly once, and a(0) = 0, so define a(-n) = -a(n) and then encode the rational number as the integer index into a. https://oeis.org/A002487 -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
Why not just interleave digits (bits if base 2), and say numerator is first? So 1/2 becomes just 12. 113/355 is 131535. 1/1000 is 001/1000 is 1000010. 123/1 is 102031. -tom On Thu, Nov 19, 2015 at 10:30 AM, Eric Angelini <Eric.Angelini@kntv.be> wrote:
Hello Math-Funsters,
I was looking for a way to represent any fraction with one single integer. Do you know if there is a common way to do that or a paper about it? I came up with this (heavy?) idea: concatenate N and D and encode the place of the slash "/".
So, the fraction we want to represent is N/D. We build the integer NDBA with four concatenated strings of digits. Starting from the right:
A is a single digit B is a string that has length A (if A=0 then A=10) D is the denominator of the fraction N/D N is the numerator of the fraction N/D
To reconstruct the fraction N/D from NDBA we:
- read A - compute the length of B - read B - insert the symbol "/" after B digits, starting the count from the leftmost digit of NDBA - erase A and B
Examples:
The fraction 1/2 --> 1211 [or 12.1.1 --> 1/2] The fraction 113/355 --> 11335531 [113/355.3.1] The fraction 2015/1234567890 --> 2015123456789041 [2015/1234567890.4.1] The fraction 1234567890/888 --> 1234567890888102 [1234567890888.10.2] etc.
This system works for N having less than 10 billion digits, of course -- which seems ok in our everyday life (we would have an integer like ND.9999999999.0 with ten 9's)
Best, É.
P.-S. Many integers will not represent any fraction -- but this is another story (10211 would produce the fraction 1/02, for instance).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
Hello Tom, What if N and D have different lengths? Catapulté de mon aPhone
Le 19 nov. 2015 à 19:47, Tom Rokicki <rokicki@gmail.com> a écrit :
Why not just interleave digits (bits if base 2), and say numerator is first?
So 1/2 becomes just 12. 113/355 is 131535.
1/1000 is 001/1000 is 1000010.
123/1 is 102031.
-tom
On Thu, Nov 19, 2015 at 10:30 AM, Eric Angelini <Eric.Angelini@kntv.be> wrote:
Hello Math-Funsters,
I was looking for a way to represent any fraction with one single integer. Do you know if there is a common way to do that or a paper about it? I came up with this (heavy?) idea: concatenate N and D and encode the place of the slash "/".
So, the fraction we want to represent is N/D. We build the integer NDBA with four concatenated strings of digits. Starting from the right:
A is a single digit B is a string that has length A (if A=0 then A=10) D is the denominator of the fraction N/D N is the numerator of the fraction N/D
To reconstruct the fraction N/D from NDBA we:
- read A - compute the length of B - read B - insert the symbol "/" after B digits, starting the count from the leftmost digit of NDBA - erase A and B
Examples:
The fraction 1/2 --> 1211 [or 12.1.1 --> 1/2] The fraction 113/355 --> 11335531 [113/355.3.1] The fraction 2015/1234567890 --> 2015123456789041 [2015/1234567890.4.1] The fraction 1234567890/888 --> 1234567890888102 [1234567890888.10.2] etc.
This system works for N having less than 10 billion digits, of course -- which seems ok in our everyday life (we would have an integer like ND.9999999999.0 with ten 9's)
Best, É.
P.-S. Many integers will not represent any fraction -- but this is another story (10211 would produce the fraction 1/02, for instance).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Sorry, Tom, did''t get your 0's complelents idea! Catapulté de mon aPhone
Le 19 nov. 2015 à 19:47, Tom Rokicki <rokicki@gmail.com> a écrit :
Why not just interleave digits (bits if base 2), and say numerator is first?
So 1/2 becomes just 12. 113/355 is 131535.
1/1000 is 001/1000 is 1000010.
123/1 is 102031.
-tom
On Thu, Nov 19, 2015 at 10:30 AM, Eric Angelini <Eric.Angelini@kntv.be> wrote:
Hello Math-Funsters,
I was looking for a way to represent any fraction with one single integer. Do you know if there is a common way to do that or a paper about it? I came up with this (heavy?) idea: concatenate N and D and encode the place of the slash "/".
So, the fraction we want to represent is N/D. We build the integer NDBA with four concatenated strings of digits. Starting from the right:
A is a single digit B is a string that has length A (if A=0 then A=10) D is the denominator of the fraction N/D N is the numerator of the fraction N/D
To reconstruct the fraction N/D from NDBA we:
- read A - compute the length of B - read B - insert the symbol "/" after B digits, starting the count from the leftmost digit of NDBA - erase A and B
Examples:
The fraction 1/2 --> 1211 [or 12.1.1 --> 1/2] The fraction 113/355 --> 11335531 [113/355.3.1] The fraction 2015/1234567890 --> 2015123456789041 [2015/1234567890.4.1] The fraction 1234567890/888 --> 1234567890888102 [1234567890888.10.2] etc.
This system works for N having less than 10 billion digits, of course -- which seems ok in our everyday life (we would have an integer like ND.9999999999.0 with ten 9's)
Best, É.
P.-S. Many integers will not represent any fraction -- but this is another story (10211 would produce the fraction 1/02, for instance).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Stern's diatomic series is a common choice, see https://oeis.org/A002487 For each rational p/q there is some n with p/q = A002487(n)/A002487(n+1). Charles Greathouse Analyst/Programmer Case Western Reserve University On Thu, Nov 19, 2015 at 3:11 PM, Eric Angelini <Eric.Angelini@kntv.be> wrote:
Sorry, Tom, did''t get your 0's complelents idea!
Catapulté de mon aPhone
Le 19 nov. 2015 à 19:47, Tom Rokicki <rokicki@gmail.com> a écrit :
Why not just interleave digits (bits if base 2), and say numerator is first?
So 1/2 becomes just 12. 113/355 is 131535.
1/1000 is 001/1000 is 1000010.
123/1 is 102031.
-tom
On Thu, Nov 19, 2015 at 10:30 AM, Eric Angelini <Eric.Angelini@kntv.be> wrote:
Hello Math-Funsters,
I was looking for a way to represent any fraction with one single integer. Do you know if there is a common way to do that or a paper about it? I came up with this (heavy?) idea: concatenate N and D and encode the place of the slash "/".
So, the fraction we want to represent is N/D. We build the integer NDBA with four concatenated strings of digits. Starting from the right:
A is a single digit B is a string that has length A (if A=0 then A=10) D is the denominator of the fraction N/D N is the numerator of the fraction N/D
To reconstruct the fraction N/D from NDBA we:
- read A - compute the length of B - read B - insert the symbol "/" after B digits, starting the count from the leftmost digit of NDBA - erase A and B
Examples:
The fraction 1/2 --> 1211 [or 12.1.1 --> 1/2] The fraction 113/355 --> 11335531 [113/355.3.1] The fraction 2015/1234567890 --> 2015123456789041 [2015/1234567890.4.1] The fraction 1234567890/888 --> 1234567890888102 [1234567890888.10.2] etc.
This system works for N having less than 10 billion digits, of course -- which seems ok in our everyday life (we would have an integer like ND.9999999999.0 with ten 9's)
Best, É.
P.-S. Many integers will not represent any fraction -- but this is another story (10211 would produce the fraction 1/02, for instance).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Many thanks to all -- you made my day! Best, É.
Le 19 nov. 2015 à 22:09, Charles Greathouse <charles.greathouse@case.edu> a écrit :
Stern's diatomic series is a common choice, see https://oeis.org/A002487
For each rational p/q there is some n with p/q = A002487(n)/A002487(n+1).
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Thu, Nov 19, 2015 at 3:11 PM, Eric Angelini <Eric.Angelini@kntv.be> wrote:
Sorry, Tom, did''t get your 0's complelents idea!
Catapulté de mon aPhone
Le 19 nov. 2015 à 19:47, Tom Rokicki <rokicki@gmail.com> a écrit :
Why not just interleave digits (bits if base 2), and say numerator is first?
So 1/2 becomes just 12. 113/355 is 131535.
1/1000 is 001/1000 is 1000010.
123/1 is 102031.
-tom
On Thu, Nov 19, 2015 at 10:30 AM, Eric Angelini <Eric.Angelini@kntv.be> wrote:
Hello Math-Funsters,
I was looking for a way to represent any fraction with one single integer. Do you know if there is a common way to do that or a paper about it? I came up with this (heavy?) idea: concatenate N and D and encode the place of the slash "/".
So, the fraction we want to represent is N/D. We build the integer NDBA with four concatenated strings of digits. Starting from the right:
A is a single digit B is a string that has length A (if A=0 then A=10) D is the denominator of the fraction N/D N is the numerator of the fraction N/D
To reconstruct the fraction N/D from NDBA we:
- read A - compute the length of B - read B - insert the symbol "/" after B digits, starting the count from the leftmost digit of NDBA - erase A and B
Examples:
The fraction 1/2 --> 1211 [or 12.1.1 --> 1/2] The fraction 113/355 --> 11335531 [113/355.3.1] The fraction 2015/1234567890 --> 2015123456789041 [2015/1234567890.4.1] The fraction 1234567890/888 --> 1234567890888102 [1234567890888.10.2] etc.
This system works for N having less than 10 billion digits, of course -- which seems ok in our everyday life (we would have an integer like ND.9999999999.0 with ten 9's)
Best, É.
P.-S. Many integers will not represent any fraction -- but this is another story (10211 would produce the fraction 1/02, for instance).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
There's a 'standard' map from pairs of non-negative integers to the non-negative integers. It's used for Godel-numbering stuff. The arrangement is 0 1 3 6 10 15 21 ... 2 4 7 11 16 22 ... 5 8 12 17 23 ... 9 13 18 24 ... 14 19 25 ... 20 26 ... 27 ... ... The formula is (x,y) <=> y + (x+y)(x+y+1)/2. This can be used to map positive rationals, subtracting 1 from both numerator & denominator. The drawback is that the backmap can generate unreduced rationals like 2/4. The upside is that it's by far the easiest to compute of all the methods offered so far. The backmap needs an integer square-root. Rich ----------- Quoting Eric Angelini <Eric.Angelini@kntv.be>:
Many thanks to all -- you made my day! Best, É.
Le 19 nov. 2015 à 22:09, Charles Greathouse <charles.greathouse@case.edu> a écrit :
Stern's diatomic series is a common choice, see https://oeis.org/A002487
For each rational p/q there is some n with p/q = A002487(n)/A002487(n+1).
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Thu, Nov 19, 2015 at 3:11 PM, Eric Angelini <Eric.Angelini@kntv.be> wrote:
Sorry, Tom, did''t get your 0's complelents idea!
Catapulté de mon aPhone
Le 19 nov. 2015 à 19:47, Tom Rokicki <rokicki@gmail.com> a écrit :
Why not just interleave digits (bits if base 2), and say numerator is first?
So 1/2 becomes just 12. 113/355 is 131535.
1/1000 is 001/1000 is 1000010.
123/1 is 102031.
-tom
On Thu, Nov 19, 2015 at 10:30 AM, Eric Angelini <Eric.Angelini@kntv.be> wrote:
Hello Math-Funsters,
I was looking for a way to represent any fraction with one single integer. Do you know if there is a common way to do that or a paper about it? I came up with this (heavy?) idea: concatenate N and D and encode the place of the slash "/".
So, the fraction we want to represent is N/D. We build the integer NDBA with four concatenated strings of digits. Starting from the right:
A is a single digit B is a string that has length A (if A=0 then A=10) D is the denominator of the fraction N/D N is the numerator of the fraction N/D
To reconstruct the fraction N/D from NDBA we:
- read A - compute the length of B - read B - insert the symbol "/" after B digits, starting the count from the leftmost digit of NDBA - erase A and B
Examples:
The fraction 1/2 --> 1211 [or 12.1.1 --> 1/2] The fraction 113/355 --> 11335531 [113/355.3.1] The fraction 2015/1234567890 --> 2015123456789041 [2015/1234567890.4.1] The fraction 1234567890/888 --> 1234567890888102 [1234567890888.10.2] etc.
This system works for N having less than 10 billion digits, of course -- which seems ok in our everyday life (we would have an integer like ND.9999999999.0 with ten 9's)
Best, É.
P.-S. Many integers will not represent any fraction -- but this is another story (10211 would produce the fraction 1/02, for instance).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
="Tom Rokicki" <rokicki@gmail.com> Why not just interleave digits (bits if base 2)
Specifically, the Moser-de Bruijn sequence, A000695 (a personal fave). For example n/d --> A000695(n) + 2 * A000695(d). Note that any map from pairs to integers can be used to map larger tuples to integers by repeated application. I can't resist mentioning: such bijections can be used as transforms to define interesting "new" arithmetic operations. For example we can define a new "flavor" of integer addition by taking integer arguments, mapping them to rationals, adding the rationals using ordinary rational addition, and then transforming the resulting rational sum back into an integer. This new operation will necessarily inherit all the behavior of the original (such as commutativity, associativity etc) and moreover if you add another related mapped operation, say multiplication, the combined system will necessarily inherit their combined behaviors (such as distributivity).
I like this bijection from Z+ to Q+ : ----- Let f(1) = 1. Define f(2n) = f(n) + 1 and f(2n+1) = 1/(f(n)+1). ----- There is more information about it here: http://mathoverflow.net/questions/200656/is-there-a-natural-bijection-from-m... <http://mathoverflow.net/questions/200656/is-there-a-natural-bijection-from-mathbbn-to-mathbbq> as well as a number of very interesting related comments, in particular the one that uses factorial expansions to get a different bijection. —Dan
On Nov 19, 2015, at 10:30 AM, Eric Angelini <Eric.Angelini@kntv.be> wrote:
I was looking for a way to represent any fraction with one single integer. Do you know if there is a common way to do that or a paper about it? ... ...
On Thu, 19 Nov 2015, Eric Angelini wrote:
I was looking for a way to represent any fraction with one single integer.
Stern's "diatomic sequence" ( https://oeis.org/A002487 , also called the Stern-Brocot sequence) has the feature that f(n)/f(n+1) includes every rational number exactly once. The sequence is pretty easy to compute: f(0)=0 f(1)=1 f(2n)=f(n) f(2n+1)=f(n)+f(n+1) So you can represent rational numbers with indices into the sequence: if you specify n, I compute f(n)/f(n+1). The first few entries in the sequence are 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3 E.W. Dijkstra wrote a couple of notes about this sequence (EWD570, EWD578, available here: https://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD570.html https://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD578.html ), which he called fusc(n). Unless I missed it, he never mentioned that it enumerates the rationals. -- Tom Duff. Form follows malfunction.
The "?" in "? + Wilf" is Neil Calkin. Jim Propp On Thursday, November 19, 2015, Tom Duff <td@pixar.com> wrote:
On Thu, 19 Nov 2015, Eric Angelini wrote:
I was looking for a way to represent any fraction
with one single integer.
Stern's "diatomic sequence" ( https://oeis.org/A002487 , also called the Stern-Brocot sequence) has the feature that f(n)/f(n+1) includes every rational number exactly once. The sequence is pretty easy to compute:
f(0)=0 f(1)=1 f(2n)=f(n) f(2n+1)=f(n)+f(n+1)
So you can represent rational numbers with indices into the sequence: if you specify n, I compute f(n)/f(n+1).
The first few entries in the sequence are 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3
E.W. Dijkstra wrote a couple of notes about this sequence (EWD570, EWD578, available here: https://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD570.html https://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD578.html ), which he called fusc(n). Unless I missed it, he never mentioned that it enumerates the rationals.
-- Tom Duff. Form follows malfunction.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (10)
-
Charles Greathouse -
Dan Asimov -
Eric Angelini -
James Propp -
Marc LeBrun -
Michael Greenwald -
Mike Stay -
rcs＠xmission.com -
Tom Duff -
Tom Rokicki