## Magic 1089

### October 3, 2014

We begin with a function that reverses a number, using `quotient`

and `modulo`

to extract the digits and add them to the accumulating reversal:

`(define (rev n)`

(let loop ((n n) (r 0))

(if (zero? n) r

(loop (quotient n 10)

(+ (* r 10) (modulo n 10))))))

Then we compute the magic number in two stages:

`(define (magic n)`

(let ((d (- n (rev n))))

(+ d (rev d))))

Here are some examples:

`> (magic 532)`

1089

> (magic 235)

21

> (magic 854)

1089

For *n* with digits in descending order, the result is always 1089. Simple algebra shows the reason. A number *abc* represents the polynomial 100*a* + 10*b* + *c*. It’s reversal is 100*c* + 10*b* + *c*, and subtracting gives 99*a* – 99*c* = 99(*a* – *c*). Since the original digits must be decreasing, the difference (*a* – *c*) must be on the range 2 to 9, so the difference must be 198, 297, 396, 495, 594, 693, 792, or 891. Those numbers are reversals of each other in pairs: 198:891, 297:792, 396:693, and 495:594, which we can write as 99*2:99*9, 99*3:99*8, 99*4:99*7 and 99*5:99*6, and now it is obvious that each of the differences, reversed, when added to its reversal, is 99 * 11 = 1089.

You can run the program at http://programmingpraxis.codepad.org/eBHSOzIP.

You don’t actually have to enumerate the possible values for 99(a-c) to prove this. Define d=a-c, and write the difference as 99d = 100d-d = 100*(d-1)+10*9+(10-d). (That last expansion is the borrowing necessary to keep all digits positive.) The reverse of this is 100*(10-d)+10*9+(d-1) = 1089-99d. Adding the two numbers together gives 1089-99d+99d = 1089.

[This holds as long as d > 0, in particular it holds when d=1. So the difference (a-c) can be 1, such as in numbers like 554 or 877. In that case, the original difference is 99, which can be thought of as the three-digit decimal (not octal!) number 099, the reverse of which would be 990. (For d=0 you end up with 99d=0 and the remarkable claim that the digit-wise reversal of 0 is 1089.)]

It’s also instructive to solve the more general case for a 3-digit integer of arbitrary base. It turns out that the solution is of the form (Base^2 – 1)(Base + 1), in this case 99*11.

There’s also a pattern moving to n-digit integers, which turns out to be:

Java:

#include

#include

using namespace std;

int reverse(int number)

{

int digitOne = number/100;

int digitThree = number%10;

number = number – digitOne*100;

int digitTwo = number/10;

int reverseNumber = digitThree*100+digitTwo*10+digitOne;

return reverseNumber;

}

int GetMagicNumber(int number)

{

int diff = number – reverse(number);

int result = diff + reverse(diff);

return result;

}

int main( int argc, char **argv)

{

if(argc >1 )

{

int number = atoi(argv[1]);

int result = GetMagicNumber(number);

cout<<"The result is :" <<result<<endl;

}

return 0;

}

c++( Another version not only for three-digits number, but for 98 and 9876543210, the result is incorrect. )

#include

#include

#include

using namespace std;

int reverse(int number)

{

int i = 0,j=0;

int result = 0;

int tmp[100];

while(number)

{

tmp[i++]= number%10;

number = number/10;

}

i–;

for(j=0;i>=0;i–,j++)

{

result += tmp[j]*pow(10,i);

}

return result;

}

int GetMagicNumber(int number)

{

int diff = number – reverse(number);

int result = diff + reverse(diff);

return result;

}

int main( int argc, char **argv)

{

if(argc >1 )

{

int number = atoi(argv[1]);

long result = GetMagicNumber(number);

cout<<"The result is :" <<result<<endl;

}

return 0;

}

In Python:

public static int mathPuzzle(int num) throws Exception {

int large = 0;

while (num > 0) {

int rem = num % 10;

num = num / 10;

if (rem < large)

throw new Exception("Not a decending number");

}

int rev = reverse(num);

int sub = rev – num;

return reverse(sub) + sub;

}

private static int reverse(int num) {

int rev = 0;

if (num 10) {

int rem = num % 10;

num = num / 10;

rev = rev * 10 + rem;

}

rev = rev * 10 + num;

return rev;

}

{{ public static int mathPuzzle(int num) throws Exception {

int large = 0;

while (num > 0) {

int rem = num % 10;

num = num / 10;

if (rem < large)

throw new Exception("Not a decending number");

else

large = rem;

}

int rev = reverse(num);

int sub = rev – num;

return reverse(sub) + sub;

}

private static int reverse(int num) {

int rev = 0;

if (num 10) {

int rem = num % 10;

num = num / 10;

rev = rev * 10 + rem;

}

rev = rev * 10 + num;

return rev;

}

}}

It hurts my soul when converting to strings in order to do things like reverse the digits of an integer.

It hurts my soul to see all those `quot`s and `rem`s, so here’s a version that uses BCD arithmetic (don’t hear much about BCD these days). I nicked the BCD arithmetic directly from this excellent page: http://homepage.cs.uiowa.edu/~jones/bcd/bcd.html

As an added bonus, using the length of the original number to control how many digits get reversed means that we get the right answer eg. for 98 -> 98 – 89 -> 09 -> 90 + 09 -> 99:

#!/usr/software/bin/perl -w

@d1 = split(“”, $ARGV[0]);

foreach (reverse(@d1)){$r1 .= $_;}

$df = $ARGV[0] – $r1;

@d2 = split(“”, $df);

foreach (reverse(@d2)) {$r2 .= $_;}

print $r2 + $df, “\n”;