Magic 1089
October 3, 2014
I’ve been very busy at work this week, so I only have time for a simple exercise today.
This is a simple puzzle in arithmetic. Take any three-digit number with digits in descending order; for instance, 532 is acceptable, but 481 is not. Reverse the digits of the original number, and subtract the reversal from the original. Then reverse that difference, and add the reversal of the difference to the difference. Write the result as output.
For instance, start with the number 532. Its reversal is 235, and the difference is 532 – 235 = 297. Reversing the difference gives 792, and 297 + 792 = 1089, which is the result.
Your task is to write a program that makes this calculation, and try it on several different starting numbers; you might enjoy working out the arithmetic behind the results that you see. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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:
(define (magic-number n base) (let ((a (+ 1 (floor (/ (- n 1) 2)))) (b (- (floor (/ n 2)) 1))) (* (+ base 1) (- (expt base a) 1) (expt base b)))) (map (lambda (n) (magic-number n 10)) (iota 9 2)) (99 1089 10890 109890 1098900 10998900 109989000 1099989000 10999890000)Java:
public class Magig1089 { public static void main(String... args) { for (int n1 = 9; n1 > 2; n1--) { for (int n2 = n1 - 1; n2 > 1; n2--) { for (int n3 = n2 - 1; n3 > 0; n3--) { int n = 100 * n1 + 10 * n2 + n3; // 532 int nr = 100 * n3 + 10 * n2 + n1; // 235 int d = 100 * (n1 - n3 - 1) + 9 * 10 + (10 + n3 - n1); // int d_check = 100 * (n1 - n3) + 0 + (n3 - n1); // 297 // assert (d_check == d); int dr = 100 * (10 + n3 - n1) + 9 * 10 + (n1 - n3 - 1); // int dr_check = Integer.valueOf(new StringBuilder(Integer.toString(d)).reverse().toString()); // assert (dr_check == dr); int ddr = 100 * (10 + n3 - n1 + n1 - n3 - 1) + (9 + 9) * 10 + (n1 - n3 - 1 + 10 + n3 - n1); // 1089 int ddr2 = dr + d; // 1089 assert (ddr2 == ddr); System.out.println(n + " " + nr + " " + dr + " " + ddr + " "); } } } } }#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:
#include <stdint.h> #include <stdlib.h> #include <stdio.h> #include <string.h> typedef uint32_t T; T add(T a, T b) { T t1 = a + 0x06666666; T t2 = t1 + b; T t3 = t1 ^ b; T t4 = t2 ^ t3; T t5 = ~t4 & 0x11111110; T t6 = (t5 >> 2) | (t5 >> 3); return t2 - t6; } T tenscomp(T a) { T t1 = 0xF9999999 - a; return add( t1, 0x00000001 ); } T sub(T a, T b) { return add(a,tenscomp(b)); } // Reverse the rightmost n BCD digits of a T rev(T a, int n) { a = (a << 16) | (a >> 16); a = ((a & 0x00FF00FF) << 8 | (a & 0xFF00FF00) >> 8); a = ((a & 0x0F0F0F0F) << 4 | (a & 0xF0F0F0F0) >> 4); return (a >> (32-4*n)); } int main(int argc, char *argv[]) { T a = strtoul(argv[1],NULL,16); int n = strlen(argv[1]); T b = sub(a,rev(a,n)); printf("%x\n", add(b,rev(b,n))); }#!/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”;