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
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 
, 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 )
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.
Learning is not a spectator sport 
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.
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
True, but one could perhaps argue that you’re getting pretty close to “boundary case” here 🙂
Still – please log a bug