## 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(ac). Since the original digits must be decreasing, the difference (ac) 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.

Pages: 1 2

### 11 Responses to “Magic 1089”

1. Axio said
```foo :: Int -> Int
foo x = diff + (read (reverse (show diff)))
where diff = x - (read (reverse (show x)))

test = all (== 1089) \$ map foo [(h*100+d*10+u)|h<-[1..9],d<-[0..h-1],u<-[0..d-1]]
```
2. Jamie Hope said

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)
```
3. András said

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 + " ");
}
}
}
}
}
```
4. Claire said

#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;
}

5. Claire said

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;
}

6. Rutger said

In Python:

```def reverse(i):
return int(str(i)[::-1])

def is_descending(i):
largest_so_far = 10
for c in str(i):
v = int(c)
if v >= largest_so_far:
return False
else:
largest_so_far = v
return True

# main, prints only 1089
for i in range(600,700):
if is_descending(i):
difference = i - reverse(i)
print difference + reverse(difference)

```
7. Naresh said

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;
}

8. Naresh said

{{ 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;
}

}}

9. Josef said

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

```descending n | n < 10 = True
descending n = aux (n `quot` 10) (n `rem` 10)

aux 0 _ = True
aux m r = r < d && aux n d
where (n,d) = quotRem m 10

reverseDigits n | n < 10 = n
reverseDigits n = revDig (n `quot` 10) (n `rem` 10)

revDig 0 r = r
revDig m r = revDig n (10*r + d)
where (n,d) = quotRem m 10

puzzle n = d + reverseDigits d
where d = n - reverseDigits n

check = all (== 1089) [ puzzle n | n <- [100..999], descending n ]
```
10. matthew said

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) {
}

// 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));