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) {
      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)));
    }
    
  11. Ben said

    #!/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”;

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: