Jouette’s Attractor

I have been reading a lot of mathematical recreation books of late. Some in English, some in French, with the double goal of amusing myself and of finding good exercises for my students. In [1], we find the following procedure:

Take any number, n digits long, make this number t. Make t_1 the number made of the sorted (decreasing order) digits of t, and t_2, the number made of the sorted (increasing order) digits of t. Subtract both to get t': t'=t_1-t_2. Repeat until you find a cycle (i.e., the computation yields a number that have been seen before).

Jouette states that for 2 digits, the cycle always starts with 9, for 3 digits, it starts with 495, for 4 digits, 6174, and for 5 digits, 82962. For 2, 3, and 4 digits, he’s mostly right, except that the procedure can also reach zero (take 121 for example: 211-112=99, 99-99=0). For 5 digits, however, he’s really wrong.

If we write a short program to implement Jouette’s procedure, we find that the cycle may start with 0, 53955, 59994, 61974, 62964, 63954, 71973, 74943, 75933, 82962, or 83952. We might as well see what happens for bigger numbers. We find that the number of attractors (let’s call them that for lack of a better term) grows. We find the following attractors:

digits attractors
2  0 9
3  0 495
4  0 6174
5  0 53955 59994 61974 62964 63954 71973 74943 75933 82962 83952
6  0 420876 549945 631764 642654 750843 840852 851742 860832 862632
7  0 7509843 7519743 7619733 8429652 8439552 8649432 8719722 9529641
8  0 43208766 63317664 64308654 64326654 75308643 83208762 84308652 85317642 86308632 86326632 86526432 97508421
9  0 554999445 753098643 762098733 763197633 844296552 863098632 864197532 865296432 865395432 873197622 874197522 883098612 954197541 964395531 965296431 976494321
10 0 4332087666 6333176664 6431088654 6433086654 6433266654 6543086544 7533086643 8321088762 8332087662 8433086652 8533176642 8633086632 8633266632 8653266432 8655264432 8732087622 8765264322 9751088421 9753086421 9755084421 9775084221 9975084201

The code is given here:

#include <stdint.h>
#include <iostream>
#include <set>

uint64_t reverse(uint64_t a)
 {
  uint64_t c=0;
  while (a)
   {
    c*=10;
    c+=a%10;
    a/=10;
   }

  return c;
 }

uint64_t sort(uint64_t a)
 {
  char digits[20]={0};
  int len=0;
  do
   {
    digits[len]='0'+a % 10;
    len++;
    a/=10;
   } while (a);

  for (int i=0;i<len-1;i++)
   for (int j=i+1;j<len;j++)
    if (digits[i]<digits[j])
     std::swap(digits[i],digits[j]);

  const char * p=digits;
  while ((*p=='0') && (*p)) p++;

  return std::atoll(p);
 }


int main()
 {
  std::set<uint64_t> seen;

  uint64_t low=1;
  for (int s=1;s<10;s++)
   {
    low*=10;
    uint64_t high=low*10;
    std::set<uint64_t> fixed;
    for (uint64_t i=low;i<high;i++)
     {
      uint64_t last,a=sort(i);
      if (seen.find(a)==seen.end())
       {
        seen.insert(a); // ok, on l'aura vu
        std::set<uint64_t> visited;

        uint64_t t=a;
        while ( (t>=10) && visited.find(t)==visited.end())
         {
          visited.insert(t);
          uint64_t s=reverse(t);
          last=t-s;
          t=sort(last);
         }
        fixed.insert(last);
       }
      else
       {
        // if seen, skip
       }
     }

    std::cout << low;
    for (auto x: fixed)
     std::cout << " " << x;
    std::cout << std::endl;
   }

  return 0;
 }

*
* *

Jouette’s problem is kind of fun, but it feels restrictive since all numbers have their digits sorted operating on them. What if we remove this constraint and apply the procedure without sorting, just reversing?

This simplified version produces at lot more attractors. Also, the attractors for n digits include some (but not all) of the attractors for n-1 digits!

Digits attractors
2 0
3 0
4 0 2178 6534
5 0 2178 6534 21978 65934
6 0 2178 6534 21978 65934 219978 659934
7 0 2178 6534 21978 65934 219978 659934 2199978 6599934
8 0 2178 6534 21978 65934 219978 659934 2199978 6599934 11436678 13973058 19582398 21782178 21999978 23981958 30581397 32662377 33218856 42464466 44664246 48737106 61936974 65346534 65999934 69746193 71064873 76226733
9 0 2178 6534 21978 65934 219978 659934 2199978 6599934 11436678 13973058 19582398 21782178 21999978 23981958 30581397 32662377 33218856 42464466 44664246 61936974 65346534 65999934 69746193 76226733 114396678 139703058 195802398 217802178 219999978 239801958 305801397 326692377 332198856 424604466 446604246 487307106 619306974 653406534 659999934 697406193 710604873 762296733
10 0 2178 6534 21978 65934 219978 659934 2199978 6599934 11436678 13973058 19582398 21782178 21999978 23981958 30581397 32662377 33218856 42464466 44664246 61936974 65346534 65999934 69746193 76226733 114396678 139703058 195802398 217802178 219999978 239801958 305801397 326692377 332198856 424604466 446604246 619306974 653406534 659999934 697406193 762296733 1143996678 1397003058 1958002398 2178002178 2197821978 2199999978 2398001958 3058001397 3266992377 3321998856 4246004466 4466004246 4873007106 6193006974 6534006534 6593465934 6599999934 6974006193 7106004873 7622996733

This second variant’s code is given here.

#include <cstdlib>
#include <stdint.h>
#include <iostream>
#include <set>

uint64_t reverse(uint64_t a)
 {
  uint64_t c=0;
  while (a)
   {
    c*=10;
    c+=a%10;
    a/=10;
   }

  return c;
 }

int main()
 {
  uint64_t low=1;
  for (int s=1;s<10;s++)
   {
    low*=10;
    uint64_t high=low*10;
    std::set<uint64_t> fixed;
    for (uint64_t i=low;i<high;i++)
     {
      std::set<uint64_t> vus;
      uint64_t a=i;
      while (vus.find(a)==vus.end())
       {
        vus.insert(a);
        uint64_t r=reverse(a);
        uint64_t aa=std::max(a,r);
        uint64_t ar=std::min(a,r);
        a=aa-ar;
       }

      fixed.insert(a);
     }

    std::cout << low;
    for (auto x: fixed)
     std::cout << " " << x;
    std::cout << std::endl;
   }
 }

*
* *

Jouette’s oversight can be, I think, explained by computation, or, more exactly, lack thereof. I found the statement of the problem suspicious, and so started to try different numbers and verify the procedure. The first few (will all different digits, as you’re likely to chose if you’re to choose “randomly”), did yield the attractors. Only then I wrote the programs.

[1]André Jouette — Le secret des nombres: Jeux, énigmes, et curiosités mathématiques — Albin Michel (1998) 2-226-08470-3

2 Responses to Jouette’s Attractor

  1. John Y. says:

    Minor point: If I’m reading Jouette’s procedure correctly, then your 3-digit example of 121 should not be expressed as “121-121=0” but rather “211-112=99; 99-99=0”. Of course, the quickest way to get to zero is to pick a number whose digits are all the same; any time an intermediate step leads you to such a number, your next step will be zero.

  2. You’re absolutely right. I’ll fix this right away.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: