 # 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 .

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

-----------------------------------------
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 , 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 ```
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  )
19  from digit
20  where pos=9
21  and  sum_of_digit = 45;

----------
3816547290
```

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

RIP John Conway.

1. Tony says:

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. Sayan Malakshinov (@xtner) says:

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

1. Connor McDonald says:

True, but one could perhaps argue that you’re getting pretty close to “boundary case” here 🙂
Still – please log a bug

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