Conference rusure::math

213.0. "flt pt bas rvrsl (see 209 too)" by SPRITE::OSMAN () Wed Jan 23 1985 10:30

I've done some work on asking my computer to tell me if there any
solutions to

	0 . d1 d2 d3 ... dn (octal) = 0 . dn ... d3 d2 d1 (decimal)

I wrote a BLISS program to search all octal fractions of the form 0.n
where n goes from 1 through 77777777.  The program took about two
hours to tell me there are no solutions in this range.

Unfortunately, I haven't found an easy way to check if my program is
valid.  In the integer version of the problem, we have the trivial solutions
that all integers 1 through 7 are solutions to the problem.  Hence a
confidence check for computer programs for the integer version is to
see if the program finds the trivial solutions.

However, for the floating version, I know of no trivial solutions (which
perhaps makes it a "better" problem, since you don't have to say
"other than the obvious answers of ... can you find ...".  Ther ARE no
obvious answers, at least not to me), and hence I don't yet have a
confidence check for my program.

To set up a solution, I started with the original statement:

	0 . d1 d2 d3 ... dn (octal) = 0 . dn ... d3 d2 d1 (decimal)

I then expressed it as a series, like this:

	d1     d2     d3         dn   	dn     d(n-1) d(n-2)      d1
	--  +  --  +  -- ...  +  -- = 	--  +  --  +  --     ...+ --
	 1      2      3          n   	  1      2      3           n
	8      8      8	         8    	10     10     10          10	 

			      n n
By multiplying each side by 10 8 , the equality can be represented
in summation form like this:

          n                     n-i         n                     n-i
	10 (sum i = 1 to n of (8   di)) = 8 (sum i = 1 to n of (10   d(n-i+1)))

So I then programmed Bliss to let a variable "val" to run from 1 to octal
77777777, and for each one fill an array called "d" with the octal digits,
throw out any whose last digit was 0, and evaluate the rest per the above
formula.  For any whose two sides came out closer than the contents of
"margin", I printed out "val".

As I say, the program found none.  Can anyone spot any bugs in the program ?
Or can anyone state any answer to the problem or a simple nonexistence
proof ?

Here's the Bliss program:
--------------------------------cut here-------------------------------------
module bf (main = beg, addressing_mode (external = general,
nonexternal = general)) = begin

library 'blisslib:usefulbli';

literal

	max_n = 8,
	max_val = %o'77777777';

own

	skip_0s,
	margin : initial (30),
	rs,
	ls,
	n,
	best_dif,
	eight_to_the : vector [1 + max_n],
	ten_to_the : vector [1 + max_n],
	ltc,
	d : vector [1 + max_n];

routine beg =

	begin

	skip_0s = 0;

	eight_to_the[0] = 1;
	eight_to_the[1] = 8;
	ten_to_the[0] = 1;
	ten_to_the[1] = 10;

	incr i from 2 to max_n do
	eight_to_the[.i] = .eight_to_the[.i-1] * 8;

	incr i from 2 to max_n do
	ten_to_the[.i] = .ten_to_the[.i-1] * 10;

	best_dif = 10000000;

	incr val from 1 to max_val do

	if .val mod 8 eql 0
	then skip_0s = .skip_0s + 1
	else

	begin

	n = 0;
	ltc = .val;
	until .ltc eql 0 do
		begin
		n = .n + 1;
		d[.n] = .ltc mod 8;
		ltc = .ltc / 8
		end;

	ls = rs = 0;

	incr i from 1 to .n do
		begin
		ls = .ls + .d[.i] * .eight_to_the[.n - .i];
		rs = .rs + .d[.n - .i + 1] * .ten_to_the[.n - .i]
		end;

	ls = .ten_to_the[.n] * .ls;
	rs = .eight_to_the[.n] * .rs;
	if abs (.ls - .rs) lss .margin
	then
		begin
!		if abs (.ls - .rs) geq 0
!		then best_dif = abs (.ls - .rs);

		type ('Good val = ', decimal (.val), '(10) = ',
		    octal (.val), '(8), dif = ', decimal (abs (.ls - .rs)))
		end

	end;   ! of loop over all values

	1

	end;

end
eludom

You might have done well to print the values of best_diff whenever a new 
least value appeared. These would not be hard to verify and you would be
able to see them decreasing but not reaching zero.

On further thought, there is an easy proof. 

	.a...z (dec) = .z...a (oct), so

	 n             n
	8 (a...z)  = 10 (z...a), or

	 n             n
	4 (a...z)  =  5 (z...a)
since 4 and 5 are relatively prime, z...a (octal) is divisible by 4**n,
thus if n>1 the digit a must be zero.

I should have made myself clearer. There is an unspoken assumption in
the statement of the problem, that the first and last of the n digits are
non-zero (otherwise it's not at all clear what is meant by reversing them),
so I thought that a proof that either of them was zero would suffice. Let
me continue from the end of the previous note, with a stronger argument. 

Since 4**n divides the integer (z...a), the last [n/2] digits of the octal
form are all zero. Thus the reversed (decimal) form of the fraction has
[n/2] leading zeroes. But the octal form of the fraction must have at least
as many leading zeroes as the decimal form, since the radix is smaller.
Therefore there are [(n+1)/2] leading zeroes in the octal fraction as well.
Therefore all [n/2] + [(n+1)/2] = n digits of the fraction are zero. 

The proof does not extend to all radix pairs. .10 [4] = .01 [2].

Given that Lynn's proof shows nonexistence of the original problems, perhaps
these are interesting:

	0.*abc (8) = 0.*cba (10)	"*" means ANY number of 0's, not
					necessarily the same number of 0's
					on each side.   "abc" and "cba" are
					reversed arbitrary strings of
					digits, first and last digits not
					0.

	0.*a*b*c (8) = 0.*c*b*a (10)

As usual, if you can't solve them, think about nonexistence proofs.