Solving a John Conway puzzle with SQL

Posted by

A cool little conundrum came across my email Inbox this week which I thought I’d share. Back in 2016, Pizza Hut ran a promotional competition with famous mathematician John Conway on Pi day. Sadly John Conway passed away this year from COVID19 – another great mind lost to the pandemic Sad smile.

His puzzle involved the overlap between pandigital and polydivisible numbers, and whilst those terms might seem a little confronting, the puzzle is very easy to articulate.

“Find a 10 digit number that uses each of the digits 0 to 9 exactly once and where the number formed by the first n digits of the number is divisible by n.”

A first pass

To help explain the challenge, we can reduce the number of digits:

Find a 1 digit number that is divisible by 1. 

Well, that’s trivial, any single digit will do. Let’s up the game a little.

Find a 2 digit number that is divisible by 2, and each digit occurs only once.

Once again, that is easy – we could choose 12 or 14 or 28 etc. Let’s move on.

Find a three digit number that is divisible by 3, and the first 2 digits are divisible by 2.

Perhaps a touch more pause for thought here, but luckily a likely guess (“123”) actually fits the bill here. Let’s move up to 4 digits.

Find a four digit number that is divisible by 4, and the first three digits are is divisible by 3, and the first 2 digits are divisible by 2.

Unfortunately “1234” doesn’t work, but a few more guesses gets me to 1236, and thus I could immediately jump to the five digit case with “12365”, because a number ending with 5 is always divisible by 5.

Wow, I’m halfway through the digits and the problem seems easy! For the sixth digit, I got lazy and enlisted a little SQL to help with my modulo calculations


SQL> select 12365*10+rownum-1 x, mod(12365*10+rownum-1,6) y
  2  from dual
  3  connect by level <= 10;

         X          Y
---------- ----------
    123650          2
    123651          3
    123652          4
    123653          5
    123654          0
    123655          1
    123656          2
    123657          3
    123658          4
    123659          5

and now I have “123654”. I’ll repeat that to move into the seventh digit…and


SQL> select 123654*10+rownum-1 x, mod(123654*10+rownum-1,7) y
  2  from dual
  3  connect by level <= 10
  4  /

         X          Y
---------- ----------
   1236540          4
   1236541          5
   1236542          6
   1236543          0
   1236544          1
   1236545          2
   1236546          3
   1236547          4
   1236548          5
   1236549          6

Ker splat! The only option is a trailing digit of “3” which has already been used. Suddenly the magnitude of the puzzle becomes apparent.

Brute force

Here is where we re-join my story at the point of an email coming in. The email had built a solution in SQL (which in itself is a credit to the author), but the email was asking if better solutions existed. Before exploring that, let us look at the SQL that was presented, which I’ll build up as below:

First get a list of digits:


SQL> select rownum from dual
  2  connect by level < 10;

    ROWNUM
----------
         1
         2
         3
         4
         5
         6
         7
         8
         9

I need 10 sets of these digits to form a 10-digit number, but immediately we recognize that if the 10th digit must be divisible by 10, then the last digit must be zero, so if I can build a list of 9 digits that is pandigital and polydivisible, then the job is done. Thus I need 9 sets of the digits, to build a 9 digit number, but I also must build all the 8 digit numbers, the 7 digit numbers etc in order to test each of these levels of divisibility as well. The SQL now looks like this:


with digits as  
( 
  select  
      level c 
  from  
      (select 1 from dual)  
  connect by  
      level <= 9 
) 
select  
    to_number(x1.c) num1 
,   to_number(x1.c||x2.c) num2 
,   to_number(x1.c||x2.c||x3.c) num3 
,   to_number(x1.c||x2.c||x3.c||x4.c) num4 
,   to_number(x1.c||x2.c||x3.c||x4.c||x5.c) num5 
,   to_number(x1.c||x2.c||x3.c||x4.c||x5.c||x6.c) num6 
,   to_number(x1.c||x2.c||x3.c||x4.c||x5.c||x6.c||x7.c) num7 
,   to_number(x1.c||x2.c||x3.c||x4.c||x5.c||x6.c||x7.c||x8.c) num8 
,   to_number(x1.c||x2.c||x3.c||x4.c||x5.c||x6.c||x7.c||x8.c||x9.c) num9 
from  
    digits x1 
,   digits x2 
,   digits x3  
,   digits x4  
,   digits x5  
,   digits x6  
,   digits x7  
,   digits x8  
,   digits x9  

A nine-way join is billions of rows territory and running that SQL above never came back on my machine, so we need to start pruning the candidate rows down to a more manageable size (even for the database, or more accurately, my laptop!).

Pandigital means none of the digits are allowed to repeat so we can add that into the SQL.


SQL> with digits as
  2    (
  3      select
  4          level c
  5      from
  6          (select 1 from dual)
  7      connect by
  8          level <= 9
  9    )
 10  select
 11      to_number(x1.c) num1
 12  ,   to_number(x1.c||x2.c) num2
 13  ,   to_number(x1.c||x2.c||x3.c) num3
 14  ,   to_number(x1.c||x2.c||x3.c||x4.c) num4
 15  ,   to_number(x1.c||x2.c||x3.c||x4.c||x5.c) num5
 16  ,   to_number(x1.c||x2.c||x3.c||x4.c||x5.c||x6.c) num6
 17  ,   to_number(x1.c||x2.c||x3.c||x4.c||x5.c||x6.c||x7.c) num7
 18  ,   to_number(x1.c||x2.c||x3.c||x4.c||x5.c||x6.c||x7.c||x8.c) num8
 19  ,   to_number(x1.c||x2.c||x3.c||x4.c||x5.c||x6.c||x7.c||x8.c||x9.c) num9
 20   from
 21       digits x1
 22   ,   digits x2
 23   ,   digits x3
 24   ,   digits x4
 25   ,   digits x5
 26   ,   digits x6
 27   ,   digits x7
 28   ,   digits x8
 29   ,   digits x9
 30   where
 31       x2.c <> x1.c
 32   and x3.c <> x1.c and x3.c <> x2.c
 33   and x4.c <> x1.c and x4.c <> x2.c and x4.c <> x3.c
 34   and x5.c <> x1.c and x5.c <> x2.c and x5.c <> x3.c and x5.c <> x4.c
 35   and x6.c <> x1.c and x6.c <> x2.c and x6.c <> x3.c and x6.c <> x4.c and x6.c <> x5.c
 36   and x7.c <> x1.c and x7.c <> x2.c and x7.c <> x3.c and x7.c <> x4.c and x7.c <> x5.c and x7.c <> x6.c
 37   and x8.c <> x1.c and x8.c <> x2.c and x8.c <> x3.c and x8.c <> x4.c and x8.c <> x5.c and x8.c <> x6.c and x8.c <> x7.c
 38   and x9.c <> x1.c and x9.c <> x2.c and x9.c <> x3.c and x9.c <> x4.c and x9.c <> x5.c and x9.c <> x6.c and x9.c <> x7.c and x9.c <> x8.c

Temporarily I’ll replace the string concatenation with a COUNT to see what the candidate set now looks like


SQL>       with digits as
  2        (
  3          select
  4              level c
  5          from
  6              (select 1 from dual)
  7          connect by
  8              level <= 9
  9        )
 10        select  count(*)
 11        from
 12            digits x1
 13        ,   digits x2
 14        ,   digits x3
 15        ,   digits x4
 16        ,   digits x5
 17        ,   digits x6
 18        ,   digits x7
 19        ,   digits x8
 20        ,   digits x9
 21        where
 22            x2.c <> x1.c
 23        and x3.c <> x1.c and x3.c <> x2.c
 24        and x4.c <> x1.c and x4.c <> x2.c and x4.c <> x3.c
 25        and x5.c <> x1.c and x5.c <> x2.c and x5.c <> x3.c and x5.c <> x4.c
 26        and x6.c <> x1.c and x6.c <> x2.c and x6.c <> x3.c and x6.c <> x4.c and x6.c <> x5.c
 27        and x7.c <> x1.c and x7.c <> x2.c and x7.c <> x3.c and x7.c <> x4.c and x7.c <> x5.c and x7.c <> x6.c
 28        and x8.c <> x1.c and x8.c <> x2.c and x8.c <> x3.c and x8.c <> x4.c and x8.c <> x5.c and x8.c <> x6.c and x8.c <> x7.c
 29        and x9.c <> x1.c and x9.c <> x2.c and x9.c <> x3.c and x9.c <> x4.c and x9.c <> x5.c and x9.c <> x6.c and x9.c <> x7.c and x9.c <> x8.c
 30  /

  COUNT(*)
----------
    362880

We’re down from a billion to 360 thousand which is much more palatable for my laptop, but definitely still not in the realm of manual inspection to find the answer. We can finally add in our polydivisibility check and we arrive at the anwer


SQL> select
  2      to_char(num9)||'0' answer
  3  from
  4      (
  5        with digits as
  6        (
  7          select
  8              level c
  9          from
 10              (select 1 from dual)
 11          connect by
 12              level <= 9
 13        )
 14        select
 15            to_number(x1.c) num1
 16        ,   to_number(x1.c||x2.c) num2
 17        ,   to_number(x1.c||x2.c||x3.c) num3
 18        ,   to_number(x1.c||x2.c||x3.c||x4.c) num4
 19        ,   to_number(x1.c||x2.c||x3.c||x4.c||x5.c) num5
 20        ,   to_number(x1.c||x2.c||x3.c||x4.c||x5.c||x6.c) num6
 21        ,   to_number(x1.c||x2.c||x3.c||x4.c||x5.c||x6.c||x7.c) num7
 22        ,   to_number(x1.c||x2.c||x3.c||x4.c||x5.c||x6.c||x7.c||x8.c) num8
 23        ,   to_number(x1.c||x2.c||x3.c||x4.c||x5.c||x6.c||x7.c||x8.c||x9.c) num9
 24        from
 25            digits x1
 26        ,   digits x2
 27        ,   digits x3
 28        ,   digits x4
 29        ,   digits x5
 30        ,   digits x6
 31        ,   digits x7
 32        ,   digits x8
 33        ,   digits x9
 34        where
 35            x2.c <> x1.c
 36        and x3.c <> x1.c and x3.c <> x2.c
 37        and x4.c <> x1.c and x4.c <> x2.c and x4.c <> x3.c
 38        and x5.c <> x1.c and x5.c <> x2.c and x5.c <> x3.c and x5.c <> x4.c
 39        and x6.c <> x1.c and x6.c <> x2.c and x6.c <> x3.c and x6.c <> x4.c and x6.c <> x5.c
 40        and x7.c <> x1.c and x7.c <> x2.c and x7.c <> x3.c and x7.c <> x4.c and x7.c <> x5.c and x7.c <> x6.c
 41        and x8.c <> x1.c and x8.c <> x2.c and x8.c <> x3.c and x8.c <> x4.c and x8.c <> x5.c and x8.c <> x6.c and x8.c <> x7.c
 42        and x9.c <> x1.c and x9.c <> x2.c and x9.c <> x3.c and x9.c <> x4.c and x9.c <> x5.c and x9.c <> x6.c and x9.c <> x7.c and x9.c <> x8.c
 43      )
 44  where
 45      mod(num1,1) = 0
 46  and mod(num2,2) = 0
 47  and mod(num3,3) = 0
 48  and mod(num4,4) = 0
 49  and mod(num5,5) = 0
 50  and mod(num6,6) = 0
 51  and mod(num7,7) = 0
 52  and mod(num8,8) = 0
 53  and mod(num9,9) = 0
 54  /

ANSWER
-----------------------------------------
3816547290

Finding improvements

We now have a SQL that solves Conway’s puzzle, but it is a weighty tome hence the request asking for “cleaner” solutions. Just like the original solution, I figured I would start with a list of digits and work from there.


SQL> select rownum from dual
  2  connect by level < 10;

    ROWNUM
----------
         1
         2
         3
         4
         5
         6
         7
         8
         9

Simply due to years of telling people not to treat numbers as strings Smile, my plan to get the next set of digits to not use concatenation but derive the next set of digits to be that list times 10, joined to itself, because multiplying by 10 will “shift” a digit to the left. The term “itself” was lightbulb moment for me, namely, we can use a recursive SQL to generate our digits rather than a join.  I’ll build it up through the powers of 10:


SQL> with digit(pos,val) as
  2  ( select 1 pos,
  3           rownum val
  4    from   dual
  5    connect by level < 10
  6    union all
  7    select digit.pos+1,
  8           10*digit.val+(x-1)
  9    from digit, ( select level x
10                  from dual
11                  connect by level <= 10)
12    where digit.pos < 2
13  )
14  select *
15  from digit;

       POS        VAL
---------- ----------
         1          1
         1          2
         1          3
         1          4
         1          5
         1          6
         1          7
         1          8
         1          9
         2         10
         2         11
         2         12
         2         13
     ...
         2         96
         2         97
         2         98
         2         99

99 rows selected.

Line 12 being less than 2, gives me the 1 and 2 digit numbers. Bumping up line 12 to 3, and I get the 1,2 and 3 digit numbers:


SQL> with digit(pos,val) as
  2  ( select 1 pos,
  3           rownum val
  4    from   dual
  5    connect by level < 10
  6    union all
  7    select digit.pos+1,
  8           10*digit.val+(x-1)
  9    from digit, ( select level x
10                  from dual
11                  connect by level <= 10)
12    where digit.pos < 3
13  )
14  select *
15  from digit;

       POS        VAL
---------- ----------
        1          1
         1          2
         1          3
         1          4
         1          5
         1          6
         1          7
         1          8
         1          9
         2         10
         2         11
         2         12
       ...
         2         96
         2         97
         2         98
         2         99
         3        100
         3        101
         3        102
       ...
         3        997
         3        998
         3        999

999 rows selected.

And so forth.  Thus to get all of the 9 digit numbers (and then append a 0 to each one for the tenth digit which we know to be zero) we just need this:


with digit(pos,val) as
( select 1 pos,
         rownum val
  from   dual
  connect by level < 10 
  union all
  select digit.pos+1,
         10*digit.val+(x-1)
  from digit, ( select level x 
                from dual 
                connect by level <= 10)
  where digit.pos < 9
)
select val*10
from digit
where pos = 9;

At this point, whilst the SQL is leaner, it still going to spit out a billion rows so the task now becomes folding our rules into the recursive definition. However, because within each level (depth) of the recursion, we have access to the digit position, ie, the “first”, the “second” etc, we can fold our MODULO arithmetic right there into the recursive definition to eliminate candidates at each level before descending into the next level.


SQL> with digit(pos,val) as
  2  ( select 1 pos,
  3           rownum val
  4    from   dual
  5    connect by level < 10
  6    union all
  7    select digit.pos+1,
  8           10*digit.val+(x-1)
  9    from digit, ( select level x
10                  from dual
11                  connect by level <= 10)
12    where digit.pos < 9
13    and   mod(10*digit.val+(x-1),digit.pos+1) = 0
14  )
15  select val*10 potential
16  from digit
17  where pos=9;

POTENTIAL
----------
1020005640
1020061620
1020068010
1020068820
...
...
9872527230
9872583210
9876006450
9876062430
9876069630
9876545640

2492 rows selected.

This immediately drops us from billions of rows to 2492 candidates. All that remained is to ensure now that no digit was duplicated. Because we are building up the numbers from the individual digits, as we recurse we can add up each of the individual digits to get a sum of digits.  For example, just with 3 digits we get:


SQL> with digit(pos,val,sum_of_digit) as
  2  ( select 1 pos,
  3           rownum val,
  4           rownum sum_of_digit
  5    from dual
  6    connect by level < 10
  7    union all
  8    select digit.pos+1,
  9           10*digit.val+(x-1),
10           digit.sum_of_digit+x-1
11    from digit, ( select level x
12                  from dual
13                  connect by level <= 10)
14    where digit.pos < 3
15  )
16  select *
17  from digit
18  /

       POS        VAL SUM_OF_DIGIT
---------- ---------- ------------
         1          1            1
         1          2            2
         1          3            3
...
         2         43            7
         2         44            8
         2         45            9
         2         46           10
         2         47           11
         2         92           11
         2         93           12
         2         94           13
         2         95           14
         2         96           15
...
         3        770           14
         3        771           15
         3        772           16
         3        773           17
         3        774           18
         3        775           19
         3        776           20
         3        777           21
         3        778           22

This is useful because we know that for no repeated digits, the sum of digits must be (1+2+3+…+9=45), which gets us down to 672 candidates:


SQL> with digit(pos,val,sum_of_digit) as
  2  ( select 1 pos,
  3           rownum val,
  4           rownum sum_of_digit
  5    from dual
  6    connect by level < 10
  7    union all
  8    select digit.pos+1,
  9           10*digit.val+(x-1),
10           digit.sum_of_digit+x-1
11    from digit, ( select level x
12                  from dual
13                  connect by level <= 10)
14    where digit.pos < 9
15    and   mod(10*digit.val+(x-1),digit.pos+1) = 0
16  )
17  select val*10 potential
18  from digit
19  where pos=9
20  and  sum_of_digit = 45;

POTENTIAL
----------
1088528850
1088584830
1232588880
...
9872520840
9872527230
9872583210
9876006450
9876062430

672 rows selected.

All that is left now is to ensure there are no repeated digits. To do that, within the recursive layer I have two things:

  • all the digits so far in a number, plus
  • the incoming number to be appended.

So I can just compare the incoming digit with the existing list of them to make sure there is not a duplicate. Having been on my high horse about not using numbers as strings, I decide the best way to do this was with some simple INSTR Smile


SQL> with digit(pos,val,sum_of_digit) as
  2  ( select 1 pos,
  3           rownum val,
  4           rownum sum_of_digit
  5    from dual
  6    connect by level < 10
  7    union all
  8    select digit.pos+1,
  9           10*digit.val+(x-1),
10           digit.sum_of_digit+x-1
11    from digit, ( select level x
12                  from dual
13                  connect by level <= 10)
14    where digit.pos < 9
15    and   mod(10*digit.val+(x-1),digit.pos+1) = 0
16    and   instr(to_char(digit.val),to_char(x-1))=0
17  )
18  select val*10 answer
19  from digit
20  where pos=9
21  and  sum_of_digit = 45;

    ANSWER
----------
3816547290

We’re done! Another example of just cool the SQL language is.

RIP John Conway.

3 comments

  1. This also seems like a case where the model clause might come in handy. However, I’ve never been smart enough to figure that thing out and apply it anywhere. But I am curious if it could be used here and what, if any, performance differences it would yield.

  2. Hi Connor,

    It’s really disappointing that there is a bug in Recursive subquery factoring (with-clause) in Oracle 18, 19 and 21 that fails with wrong “ORA-32044: cycle detected while executing recursive WITH query”…
    THe following query works fine in Oracle 11.2, but not on 18,19 and 21…

    with
     digits as (
        select
            level digit, 
            ku$_vcnt(1,2,3,4,5,6,7,8,9) 
              multiset except 
            ku$_vcnt(to_char(level)) as digits 
        from dual 
        connect by level<10
    )
    ,v(pos, num, digit, digits) as (
       select
         1, digit, digit, digits
       from digits
       union all
       select
         v.pos+1,
         v.num*10 + to_number(d.column_value),
         to_number(d.column_value),
         v.digits multiset except ku$_vcnt(d.column_value)
       from v, table(v.digits)(+) d
       where v.pos<3
    )
    select *
    from v
    /
    

    Best regards,
    Sayan Malakshinov

Got some thoughts? Leave a comment

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.