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 100a + 10b + c. It’s reversal is 100c + 10b + c, and subtracting gives 99a – 99c = 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.
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”;