All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Half Integer Base Baffle (Posted on 2022-07-29) Difficulty: 3 of 5
Devise an algorithm for writing any positive base ten integer in base 3/2.
How about writing any positive base ten rational number in base 3/2?

See The Solution Submitted by K Sengupta    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts The "standard" method? Comment 2 of 2 |
A search of the internet indicates that the "official" version of base 3/2 allows the use of the digit 2. This then allows the conversion to take place in the usual way: right to left from the radix point for the integer part and left to right for the fractional part. The only modification from the method for integral base is in doing the integer part. To get each new digit, instead of taking the number (or what's left of the number after previous divisions) mod the base, it takes the remainder mod 3. It then compensates for that by multiplying the quotient of the division by 3, by 2, achieving the base 2/3.

The program based on that:

clearvars,clc
for num=1:16
for den=1:16
 if gcd(num,den)==1
  n=sym(num)/sym(den);
  intpart=floor(n);
  fracpart=n-intpart;
  buildInt='';
  while intpart>0
    d=char(string(mod(intpart,3)));
    intpart=floor(intpart/3)*2;
    buildInt=[d buildInt];
  end
  if fracpart==0
    rep=buildInt;
  else
    buildFrac='.';
    diggoal=floor((15-length(buildInt))*log(10)/log(3/2));
    for i=1:diggoal
      d=char(string(floor(3/2 * fracpart)));
      fracpart=3/2 * fracpart - floor(3/2 * fracpart);
      buildFrac=[buildFrac d];
      if fracpart==0
        buildFrac=[buildFrac '  *'];
        break
      end
    end
    rep=[buildInt buildFrac];
  end
  fprintf('%s %s\n',n,rep)
 % disp([char(string(n)) ' ' rep]);
 end
end
end

1 1
1/2 .0100000100100101000000000100000010000100000010010010100000000000100010010000000100100
1/3 .0010000010010010100000000010000001000010000001001001010000000000010001001000000010010
1/4 .0001000100100001000100010000010010001000001001001000001000001001000100100010000010010
1/5 .0001000000000010000001001001000000010000000101000000100100001000010000000100001000000
1/6 .0000100010010000100010001000001001000100000100100100000100000100100010010001000001001
1/7 .0000100000010100000000000100100100010000100000100001000000010001001000100000010010001
1/8 .0000010010010100000000010000001000010000001001001010000000000010001001000000010010000
1/9 .0000010001001000010001000100000100100010000010010010000010000010010001001000100000100
1/10 .0000010000100000001001010000000100101000000100010000001001001001000000010000001000001
1/11 .0000010000000010010001000010010000100010000000000101000000100101000000100010000001000
1/12 .0000001001001010000000001000000100001000000100100101000000000001000100100000001001000
1/13 .0000001001000000100000000101000000100001000001010000001000100100100100001000100100101
1/14 .0000001000100000100100000010010001001000010001000000100010010000100000001000001000000
1/15 .0000001000010000000100101000000010010100000010001000000100100100100000001000000100000
1/16 .0000001000000100001000100000010001001001000001001000000100010001000001010000010010000

2 2
2/3 .1  *
2/5 .0010010000100100010010001000100001000001001000010000001000010000010001000001000100010
2/7 .0001010000000000000100100000000010010000101000001000010001000000100000100000100100010
2/9 .0001000001001001010000000001000000100001000000100100101000000000001000100100000001001
2/11 .0000100100010010100000100001010000010000000100001000101000000100100010001001000100101
2/13 .0000100001000100100100010001001010000000010000100010001000000100010010010000010100000
2/15 .0000100000000001000000100100100000001000000010100000010010000100001000000010000100000

3 20
3/2 1.0100000100100101000000000100000010000100000010010010100000000000100010010000000
3/4 .1000001001001010000000001000000100001000000100100101000000000001000100100000001001000
3/5 .0100100001001000100100010001000010000010010000100000010000100000100010000010001000100
3/7 .0010100000000000001001000000000100100001010000010000100010000001000001000001001000100
3/8 .0010001001000010001000100000100100010000010010010000010000010010001001000100000100100
3/10 .0010000000000100000010010010000000100000001010000001001000010000100000001000010000000
3/11 .0001001000100101000001000010100000100000001000010001010000001001000100010010001001010
3/13 .0001000010001001001000100010010100000000100001000100010000001000100100100000101000001
3/14 .0001000000101000000000001001001000100001000001000010000000100010010001000000100100010
3/16 .0000100100101000000000100000010000100000010010010100000000000100010010000000100100000

4 21
4/3 1.0010000010010010100000000010000001000010000001001001010000000000010001001000000
4/5 .1000100000000001000000100100100000001000000010100000010010000100001000000010000100000
4/7 .0100010100000000000001001000000000100100001010000010000100010000001000001000001001000
4/9 .01  *
4/11 .0010001000010000100000100000000000101000000000000010000100100100100100010010010100000
4/13 .0010000000010100000010010000000100100100100100000100100100000101000000000010000100010
4/15 .0001001000010010001001000100010000100000100100001000000100001000001000100000100010001

5 22
5/2 2.0100000100100101000000000100000010000100000010010010100000000000100010010000000
5/3 1.1  *
5/4 1.0001000100100001000100010000010010001000001001001000001000001001000100100010000
5/6 .1000100010010000100010001000001001000100000100100100000100000100100010010001000001001
5/7 .1000000100010000010010000001001000100100001000100000010001001000010000000100000100000
5/8 .0100100100010001001001000100100001000000100100001000000010000000000100001001000010001
5/9 .0100010001001000010001000100000100100010000010010010000010000010010001001000100000100
5/11 .0100000000010010000000100010000100100101000000000001001001000010000000100010010001000
5/12 .0010010010001000100100100010010000100000010010000100000001000000000010000100100001000
5/13 .0010010000000000001000010001010000000010000010000000010000000000100000000000001000010
5/14 .0010001000000010000000000100100000101000000100010100000010000100100100001001000001001
5/16 .0010000000100100100010000000000010000100000000001000010000000010000000100000100000000

6 210
6/5 1.0001000000000010000001001001000000010000000101000000100100001000010000000100001
6/7 .1000101000000000000010010000000001001000010100000100001000100000010000010000010010001
6/11 .0100010000100001000001000000000001010000000000000100001001001001001000100100101000000
6/13 .0100000000101000000100100000001001001001001000001001001000001010000000000100001000100

7 211
7/2 20.0100000100100101000000000100000010000100000010010010100000000000100010010
7/3 2.0010000010010010100000000010000001000010000001001001010000000000010001001000000
7/4 1.1000001001001010000000001000000100001000000100100101000000000001000100100000001
7/5 1.0010010000100100010010001000100001000001001000010000001000010000010001000001000
7/6 1.0000100010010000100010001000001001000100000100100100000100000100100010010001000
7/8 .1001000000010010010001000000000001000010000000000100001000000001000000010000010000000
7/9 .1000010001001000010001000100000100100010000010010010000010000010010001001000100000100
7/10 .1000000010001001001010000000100000100100100010010010000010000100001000000010100000100
7/11 .0100101000000001000001001000100000100000100010100000100100000000010100000001001010000
7/12 .0100100000001001001000100000000000100001000000000010000100000000100000001000001000000
7/13 .0100010000001000100000010001000001000100001001001000100100010000100000100010010010000
7/15 .0100000001000100100101000000010000010010010001001001000001000010000100000001010000010
7/16 .0010100000010001000010010100000000001000100100000100000010000010000000001010000000100

8 212
8/3 2.1  *
8/5 1.0100100001001000100100010001000010000010010000100000010000100000100010000010001
8/7 1.0000100000010100000000000100100100010000100000100001000000010001001000100000010
8/9 .1001000001001001010000000001000000100001000000100100101000000000001000100100000001001
8/11 .1000001000000001001000100001001000010001000000000010100000010010100000010001000000100
8/13 .0100100100000000000010000100010100000000100000100000000100000000001000000000000010000
8/15 .0100010000000000100000010010010000000100000001010000001001000010000100000001000010000

9 2100
9/2 21.0100000100100101000000000100000010000100000010010010100000000000100010010
9/4 2.0001000100100001000100010000010010001000001001001000001000001001000100100010000
9/5 1.1000100000000001000000100100100000001000000010100000010010000100001000000010000
9/7 1.0001010000000000000100100000000010010000101000001000010001000000100000100000100
9/8 1.0000010010010100000000010000001000010000001001001010000000000010001001000000010
9/10 .1001000010010001001000100010000100000100100001000000100001000001000100000100010001001
9/11 .1000100001000010000010000000000010100000000000001000010010010010010001001001010000001
9/13 .1000000001010000001001000000010010010010010000010010010000010100000000001000010001000
9/14 .0101000000000000010010000000001001000010100000100001000100000010000010000010010001000
9/16 .0100010010000100010001000001001000100000100100100000100000100100010010001000001001000

10 2101
10/3 20.0010000010010010100000000010000001000010000001001001010000000000010001001
10/7 1.0010100000000000001001000000000100100001010000010000100010000001000001000001001
10/9 1.0000010001001000010001000100000100100010000010010010000010000010010001001000100
10/11 .1001000100001000010000010000000000010100000000000001000010010010010010001001001010000
10/13 .1000010000100010010010001000100101000000001000010001000100000010001001001000001010000

11 2102
11/2 22.0100000100100101000000000100000010000100000010010010100000000000100010010
11/3 20.1  *
11/4 2.1000001001001010000000001000000100001000000100100101000000000001000100100000001
11/5 2.0001000000000010000001001001000000010000000101000000100100001000010000000100001
11/6 1.1000100010010000100010001000001001000100000100100100000100000100100010010001000
11/7 1.0100010100000000000001001000000000100100001010000010000100010000001000001000001
11/8 1.0010001001000010001000100000100100010000010010010000010000010010001001000100000
11/9 1.0001000001001001010000000001000000100001000000100100101000000000001000100100000
11/10 1.0000010000100000001001010000000100101000000100010000001001001001000000010000001
11/12 .1001000100100001000100010000010010001000001001001000001000001001000100100010000010010
11/13 .1000100100010000100000001010000010001001010000010001000100000010100000001000001001010
11/14 .1000010010001000000000100001001001000100010001000000100100100000001010000000000001000
11/15 .1000001000010000000100101000000010010100000010001000000100100100100000001000000100000
11/16 .1000000001000100000000010000010010000010000010010010010001000100010000100100000100001

12 2120
12/5 2.0010010000100100010010001000100001000001001000010000001000010000010001000001000
12/7 1.1000000100010000010010000001001000100100001000100000010001001000010000000100000
12/11 1.0000010000000010010001000010010000100010000000000101000000100101000000100010000
12/13 .1001001000000000000100001000101000000001000001000000001000000000010000000000000100001

13 2121
13/2 210.01000001001001010000000001000000100001000000100100101000000000001000
13/3 21.0010000010010010100000000010000001000010000001001001010000000000010001001
13/4 20.0001000100100001000100010000010010001000001001001000001000001001000100100
13/5 2.0100100001001000100100010001000010000010010000100000010000100000100010000010001
13/6 2.0000100010010000100010001000001001000100000100100100000100000100100010010001000
13/7 1.1000101000000000000010010000000001001000010100000100001000100000010000010000010
13/8 1.0100100100010001001001000100100001000000100100001000000010000000000100001001000
13/9 1.01  *
13/10 1.0010000000000100000010010010000000100000001010000001001000010000100000001000010
13/11 1.0000100100010010100000100001010000010000000100001000101000000100100010001001000
13/12 1.0000001001001010000000001000000100001000000100100101000000000001000100100000001
13/14 .1001001000001000010000000100001001001010000010001000001000001010000010010000010000100
13/15 .1001000000000010000001001001000000010000000101000000100100001000010000000100001000000
13/16 .1000100000100010000100000000000000010100000100010001001000100001001001000100000000000

14 2122
14/3 21.1  *
14/5 2.1000100000000001000000100100100000001000000010100000010010000100001000000010000
14/9 1.0100010001001000010001000100000100100010000010010010000010000010010001001000100
14/11 1.0001001000100101000001000010100000100000001000010001010000001001000100010010001
14/13 1.0000001001000000100000000101000000100001000001010000001000100100100100001000100
14/15 .1001001000010010001001000100010000100000100100001000000100001000001000100000100010001

15 21010
15/2 211.01000001001001010000000001000000100001000000100100101000000000001000
15/4 20.1000001001001010000000001000000100001000000100100101000000000001000100100
15/7 2.0000100000010100000000000100100100010000100000100001000000010001001000100000010
15/8 1.1001000000010010010001000000000001000010000000000100001000000001000000010000010
15/11 1.0010001000010000100000100000000000101000000000000010000100100100100100010010010
15/13 1.0000100001000100100100010001001010000000010000100010001000000100010010010000010
15/14 1.0000001000100000100100000010010001001000010001000000100010010000100000001000001
15/16 .1001001000100010010010001001000010000001001000010000000100000000001000010010000100010

16 21011
16/3 22.0010000010010010100000000010000001000010000001001001010000000000010001001
16/5 20.0001000000000010000001001001000000010000000101000000100100001000010000000
16/7 2.0001010000000000000100100000000010010000101000001000010001000000100000100000100
16/9 1.1000010001001000010001000100000100100010000010010010000010000010010001001000100
16/11 1.0100000000010010000000100010000100100101000000000001001001000010000000100010010
16/13 1.0001000010001001001000100010010100000000100001000100010000001000100100100000101
16/15 1.0000001000010000000100101000000010010100000010001000000100100100100000001000000

The integers now do not extend past the radix point. However, this method, using conventional multiplication by the base for doing the fractional part, still produces.

.1000001000100100001000100010000010010001000001001001000001000001001000100100010000010

for 20/27, rather than .011.

An asterisk marks the finite representations. The other ones, except the integers, presumably would go on forever if they hadn't been cut off.

As all the online info I found about fractionl-base numeration actually limit themselves to representing integers, we might as well use the look-ahead method for the fractional part.  But I'm not sure we can always look ahead far enough to find all finite possibilities, so the method used here has at least the advantage of working exactly like conventional base conversion for the fractional part, and almost the same for the integral part.

So not only are there greedy algorithms vs look-ahead algorithms, but also choice as to whether or not to allow 2's. And in doing the fractional part you can swich strategies midstream, so there are apparently infinitely many ways of expressing the same number in base-3/2.

  Posted by Charlie on 2022-07-29 11:17:19
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (14)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information