Write a program to find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number must also satisfy these divisibility requirements:

  1. The number should be divisible by 9.
  2. If the rightmost digit is removed, the remaining number should be divisible by 8.
  3. If the rightmost digit of the new number is removed, the remaining number should be divisible by 7.
  4. And so on, until there’s only one digit (which will necessarily be divisible by 1).

Credit Dávid Németh

  • 29
    \$\begingroup\$ The first rule seems unnecessary. Any number that consists of digits 1-9 once each will always be divisible by 9. \$\endgroup\$
    – Geobits
    Commented Jun 24, 2014 at 19:31
  • 6
    \$\begingroup\$ What's the code-aspect here? This sounds like it could be posted on Puzzling \$\endgroup\$ Commented Jun 24, 2014 at 19:32
  • 11
    \$\begingroup\$ Even if we’re going to call it a “standard loophole”, code golf challenges that produce a fixed output generally shorter than any code that could build it are usually not particularly interesting. \$\endgroup\$
    – Ry-
    Commented Jun 24, 2014 at 21:23
  • 9
    \$\begingroup\$ The problem I have with challenges like this is that the border between hardcoding and applying mathematical properties is vague. For example, the divisibility rule for 5 is that the number has to end in 0 or 5. Is restricting the choices for that digit to 0 and 5 hardcoding part of the output? It'd get even worse if we were dealing with 10-digit numbers. \$\endgroup\$ Commented Jun 24, 2014 at 22:07
  • 4
    \$\begingroup\$ @Sylwester What you've done is assume there's only 1 way to solve the problem, because you're afraid of breaking the loophole. "Loop through numbers checking requirements". This completely excludes any interesting examples. And the question is: "Which language can check these things and loop in the fewest characters". \$\endgroup\$
    – Cruncher
    Commented Jun 26, 2014 at 14:19

23 Answers 23


CJam - 26


It's randomized but works pretty fast with the java interpreter. It can take a couple of minutes with the online interpreter.


1 pushes 1 (to be explained later)
{…}g is a do-while loop
; removes a value from the stack (initially the 1 we started with)
9, makes the array [0 ... 8]
:) increments the array elements, resulting in [1 ... 9]
_ duplicates the array
mr shuffles the array
s converts to string
0@ pushes 0 then brings the other copy of the array on top
{…}/ is a for-each loop (over the numbers 1 ... 9)
_ duplicates the current number (let's call it "k")
3$ copies the numeric string from the stack
<i gets the substring with the first k characters then converts to integer
\% swaps with the other copy of k then gets the remainder (%k)
+ adds the remainder to the previous value on the stack (initially 0 from above)
At this point, we have the numeric string on the stack, followed by a 0 if the number matches all the requirements (i.e. all the remainders were 0) or a non-0 value otherwise.
The top of the stack becomes the do-while loop condition. It is popped and the loop continues if the condition was true.
If we found the solution, the condition is 0 (false), the loop ends and the rest of the stack (the numeric string) is printed.
If it's not the solution, the condition is the non-0 value (true) and the loop continues with the string on the stack. The string gets popped at the start of the next iteration (so the loop expects a value on the stack, and that's the reason for the initial 1).

Thanks Dennis for making the code shorter and more convoluted :p

  • \$\begingroup\$ Nice! You can save one more byte by using a dummy value: 0{;9,:)_mrsT@{_3$<i\%+}/}g \$\endgroup\$
    – Dennis
    Commented Jun 24, 2014 at 22:09

Javascript (E6) 105 125 134

Recursive building of the number, each step check the divisibility.
Runtime near 0 sec
No I/O this time, as the OP asked for a program to find the number, and the number is found and automatically logged to console

Golfed more Courtesy of MT0

(Q=(n,d,b)=>([(m=n+(s=[...b]).splice(i,1))%d||Q(m,d+1,s)for(i in b)],d>9&&(Q.z=n),Q.z))('',1,'123456789')


for(i=0;s=[...b],m=n+s.splice(i,1),b[i];i++)m%d||Q(m,d+1,s);d>9&&(Q.z=n);return Q.z;


(Q=(n='', d=1, b=[...'123456789'], i) => {
   for(i=0; s=[...b], m=n+s.splice(i,1), b[i]; i++)
     m % d || Q(m,d+1,s);
   d > 9 && (Q.z=n);
   return Q.z;


With 3 little changes, you can use the same function to find longer numbers using base > 10. For instance in base 14 ...

  for(i=0; s=[...b], m = n+s.splice(i,1), b[i]; i++)
    parseInt(m,14)%d || Q(m,d+1,s);
  d>13 && (Q.z=n);
  return Q.z;



Q=(n,d,b,i,c,z)=>{ // i,c,z fake parameters instead of vars.
  for (i=0; b[i]; i++)
    m = n + s.splice(i,1);
    if (m % d == 0)
      if (z = d<9 ? Q(m, d+1, s) : m) return z;
  • 1
    \$\begingroup\$ 105 Characters: (Q=(n,d,b)=>([(m=n+(s=[...b]).splice(i,1))%d||Q(m,d+1,s)for(i in b)],d>9&&(Q.z=n),Q.z))('',1,'123456789') \$\endgroup\$
    – MT0
    Commented Jun 25, 2014 at 19:38
  • \$\begingroup\$ 101 Characters: (Q=(n,d,b)=>Math.max(...[(m=n+(s=[...b]).splice(i,1))%d||Q(m,d+1,s)for(i in b)],n))('',1,'123456789') \$\endgroup\$
    – MT0
    Commented Jun 25, 2014 at 19:50
  • \$\begingroup\$ @MT0 wow! Array comprehension strikes back. I'll take the 1st one, becouse the other one can find a wrong number if there is not one correct (IE counting up to 7 instead of 9). \$\endgroup\$
    – edc65
    Commented Jun 25, 2014 at 20:37

Perl, 56

Usage: perl -E '...'

{$s++;redo if grep{$s!~$_||substr($s,0,$_)%$_}1..9}say$s

Output: 381654729

This program is really slow. As in more than 3.5 hours.

As a more fun exercise, I decided to develop an extremely fast algorithm:

my $set = [1..9];
for my $divisor (2..9) {
    my $newset = [];
    for my $element (@$set) {
        my $num = $element * 10;
        for (my $digit = $divisor - ($num % $divisor); $digit < 10; $digit += $divisor) {
            if (index($element, $digit) == -1) {
                push @$newset, $num + $digit;
    $set = $newset;

print "@$set\n";

The above runs in .00095 seconds, and confirms that there is only one solution to this problem.


Python3, 214, 199, 184, 176, 174, 171, 165, 150, 146

from itertools import*
g=lambda i,d:d==1!=print(i)or int(i[9:])%d==0!=g(i[:-1],d-1)
for x in permutations("123456789"):g("".join(map(str,x))*2,9)



This is my first golf script. Hope you like it :)


Pyth, 33 characters


To test it, put the above code as standard input in the link in the title.

After compiling into Python 3.4:

for k in Y:
 Y+=list(filter(lambda T:(len(set(T))==len(T))>(eval(T)%len(T)),
                map(lambda d:k+repr(d),range(1,T))))



FkY: for k in F:

~Y: Add to Y

f: Filter by

>ql{TlT: All unique elements and

%vTlT: eval(element)%len(element)=0

m+k` d On the list of k + repr(d)

r1T: for d from 1 to 9.

): End for loop

pk: print k


Ruby, 66 78 chars


Runtime is ~8 seconds (output printed after 3 s).

This doesn't stop after finding the first number, so technically it prints all numbers that fulfill the criteria - but since there's only one such number, it doesn't make a difference.

Ruby 1.8, 63


Essentially the same solution as above. In Ruby 1.8, arrays are converted to strings by implicitly calling Array#join on them, so we can save the call to that. Interestingly, the code also runs much faster in Ruby 1.8 than 2.0 (4.5 seconds total runtime, output printed after 1.6 s).


GolfScript (35 chars)


Online demo

This builds prefixes which satisfy the condition.

# Initial prefixes: [0]
# Loop 9 times
    # Extend each prefix by digits 1 to 9
    # Filter out ones which repeat a digit
    # Filter down to ones which are divisible by their length

Haskell 129 121

Here is my amateurish Haskell attempt (suggestions/improvements would be greatly appreciated). It might not be the shortest, but it does execute in only .19 .65 seconds after Flonk's changes on my system.

import Data.List;f=foldl1$(+).(*10);main=print$[f x|x<-permutations[1..9],f[mod(read.take y.show$f x)y|y<-[9,8..1]]<1]!!0
  • \$\begingroup\$ Welcome to PPCG.SE! Try adding <!-- language: lang-haskell --> two lines before your code for syntax highlighting! \$\endgroup\$
    – Flonk
    Commented Jun 25, 2014 at 6:57
  • \$\begingroup\$ And I did indeed find a way to save 8 more characters! Instead of checking if each remainder==0, you could sum over all of them and check if that==0, which is just as long. By seperating out the foldl1 into a function however, you can use that instead of sum or any. import Data.List;f=foldl1$(+).(*10);main=print$[f x|x<-permutations[1..9],f[mod(read.take y.show$f x)y|y<-[9,8..1]]<1]!!0 \$\endgroup\$
    – Flonk
    Commented Jun 25, 2014 at 7:19
  • \$\begingroup\$ It seems that you counted your characters including the trailing newline: there are only 128 characters in your code. \$\endgroup\$ Commented Jun 25, 2014 at 8:41
  • \$\begingroup\$ @Flonk I absolutely love the use of the f function on the mod predicate to avoid writing foldl1, although the extra cycles do hamper performance severely. \$\endgroup\$
    – DrJPepper
    Commented Jun 25, 2014 at 14:33
  • \$\begingroup\$ @DrJPepper 0.65 seconds? Meh. Lets make that worse! You can also replace !!0 with a call to f, which works out since there's only one item in the list. The list [9,8..1] can also be replaced by x, because the order doesn't matter. Talk about code reuse! \$\endgroup\$
    – Flonk
    Commented Jun 26, 2014 at 9:26

Javascript 75 (terminating)

Bruteforce solution (super slow)


If you want to see the result in this lifetime, update the initial value to something like a=c=38e7

Javascript 70 (non-terminating)


And just for fun, a random bruteforce that runs much faster: (ES6 only)


Python, 142, 139, 125, 124

Essentially same as @Ventero's solution if I understood his code correctly, but in Python.(Much of the credit goes to @Greg Hewgill.)

from itertools import*;print[s for s in map(''.join,permutations('123456789'))if all(t(s[:i])%i==0 for i in range(1,9))][0]
  • \$\begingroup\$ You should be able to replace r(9,1,-1) with r(9), as the order of iteration doesn't really matter. \$\endgroup\$
    – Ventero
    Commented Jun 24, 2014 at 20:39
  • \$\begingroup\$ You'd have to use r(1,9) because %0 is an error. \$\endgroup\$ Commented Jun 24, 2014 at 20:40
  • \$\begingroup\$ @GregHewgill Ah, of course you're right, didn't realize it starts with 0. Guess it's obvious I'm not a Python expert. :) \$\endgroup\$
    – Ventero
    Commented Jun 24, 2014 at 20:41
  • \$\begingroup\$ @Ventero Thanks for the tip, Greg is right I'll have to use r(1, 9) in Python. \$\endgroup\$ Commented Jun 24, 2014 at 20:44
  • 1
    \$\begingroup\$ Using permutations("123456789") and ''.join(s[:i]) is probably shorter than what you have (and then you can eliminate r=range) \$\endgroup\$ Commented Jun 24, 2014 at 20:46

Python 2 (78)

while len(set(`10*x`))<=9+sum(x/10**i%(9-i)for i in range(9)):x+=1
print x

No need to generate permutations, just try each number and check if its digits plus 0 are distinct. Takes a while to run.


Scala (128 chars)

My stab at this...

Seq(1,2,3,4,5,6,7,8,9).permutations.filter(p=>(2 to 8)forall{n=>(p.take(n).mkString.toLong%n==0)}).map(_.mkString.toLong).toList
  • \$\begingroup\$ You can save a character by removing the space between (2 to 8) and forall. \$\endgroup\$
    – ProgramFOX
    Commented Jun 25, 2014 at 15:41
  • \$\begingroup\$ @ProgramFOX I had no idea. I've always thought a dot or a space was required there. Thanks, I've edited down to 128 chars. \$\endgroup\$ Commented Jun 25, 2014 at 17:34

Perl, 72

Usage: perl -M5.010 find-9-digits.pl

{$s=join'',sort{4-rand 8}1..9;redo if grep{substr($s,0,$_)%$_}2..9}say$s

Output: 381654729

This program is slow. It might take more than 10 seconds, because it shuffles the digits "123456789", but the shuffle has a flaw.


# Enter a block.
     # Shuffle the characters "123456789".
     $s = join('', sort({2 - rand(4)} 1..9));

     # Redo block if any divisiblity test fails; grep returns the
     # number of failing tests.
     redo if grep({
        # For each divisor $_ in 2..9, test if the first $_ digits of
        # of $s are divisible by $_.  The test fails if the remainder
        # is a true value (not zero).
        substr($s, 0, $_) % $_
     } 2..9);
say $s;

I golfed the code that shuffles the array of digits 1..9:

  • use List'Util shuffle;shuffle 1..9 (34 characters)
  • sort{(-1,1)[rand 2]}1..9 (24 characters)
  • sort{.5<=>rand}1..9 (19 characters)
  • sort(2-rand 4}1..9 (18 characters)
  • sort{4-rand 8}1..9 (18 characters)

Perl expects the sort block to compare $a and $b in a consistent way. My sort blocks never look at $a and $b. They return a random ordering so the sort becomes a shuffle.

If I would use sort{.5<=>rand}1..9, my program would run faster. That one compares 0.5 with a random float from 0.0 to 1.0, excluding 1.0, for a 1/2 chance that $a < $b, and an almost 1/2 chance that $a > $b. (Beware: This is a "Microsoft shuffle", which is not a fair shuffle. This has bias because .5<=>rand does not provide a consistent ordering.)

Suppose that I golf away one character and use the much worse sort(2-rand 4}1..9. Perl expects the sort block to return an integer, but 2-rand 4 is a float. It is a random float from -2.0 to 2.0, excluding -2.0. Perl truncates this float toward zero, with these results:

  • 1/4 chance that $a < $b, integer -1 from -2.0 < float <= -1.0
  • near 1/2 chance that $a == $b, integer 0 from -1.0 < float < 1.0
  • near 1/4 chance that $a > $b, integer 1 or 2 from 1.0 <= float <= 2.0

When $a == $b, Perl does not shuffle well. So, my program would do more shuffles, until it gets enough shuffles where 2-rand 4 did not return 0 too often. My program would run so slow, it might take more than one minute.

I use sort{4-rand 8}1..9, so there is only a 1/4 chance that $a == $b, and my program uses fewer shuffles.

  • \$\begingroup\$ Nice hand-rolled shuffle \$\endgroup\$
    – Miller
    Commented Jun 25, 2014 at 9:08

Jelly, 13 11 bytes


Try it online!

How it works

9Œ!JḍḌƤPƲƇḌ - Main link. No arguments
9           - Yield 9
 Œ!         - Yield all permutations of [1, 2, ..., 9]
        ƲƇ  - Keep those for which the following is true:
      Ƥ     -   Over each prefix:
     Ḍ      -     Convert into an integer
   J        -   Yield [1, 2, ..., 9]
    ḍ       -   Pair each [1, 2, ..., 9] with the prefixes, 
                then return 1 if they divide each other else 0
       P    -   All return 1
          Ḍ - Convert back to an integer

Of course, there's the obvious 9 byter:


Try it online!


CJam, 35 bytes


After roughly 27 minutes, this produces the following output:


How it works

0         " Push 0 (“n”).                                                      ";
{         "                                                                    ";
  )_`$    " Increment “N”, duplicate, stringify and sort the resulting string. ";
  A,1>s   " Push '123456789'.                                                  ";
  =!      " Push 0 if the strings are equal and 1 otherwise (“a”).             ";
  1$      " Copy “n”.                                                          ";
  9,{     " For each i in [ 0 1 2 3 4 5 6 7 8 ].                               ";
    9\m   " Calculate “9 - i”.                                                 ";
    1$\%  " Calculate “n % (9 - i)”.                                           ";
    @+    " Add the result to “a”.                                             ";
    \A/   " Swap “a” with “n” and calculate “n / 10”.                          ";
  }/      "                                                                    ";
  ;       " Discard “n”.                                                       ";
}g        " If “a > 0”, repeat the loop.                                       ";
  • \$\begingroup\$ Impressive size, but it seems even slower than mine, and I suspect it's not correct \$\endgroup\$ Commented Jun 24, 2014 at 20:44
  • \$\begingroup\$ I don't fully understand it, but it seems to accept 0 as a digit? Also, when does it stop? \$\endgroup\$ Commented Jun 24, 2014 at 20:48

SWI-Prolog 84

g(L,N,I,O):-nth1(_,L,D,R),M is N*10+D,J is I+1,0 is M mod J,g(R,M,J,O).

It is a bit cheating, because the list of digits needs to be supplied in the query:

?- g([1,2,3,4,5,6,7,8,9],0,0,O).
O = 381654729 ;

However, it is what makes this code interesting: you can solve the problem for any list of digits. For example:

?- g([1,2,3,4,5,6,7,8,9,0],0,0,O).
O = 3816547290 ;

?- g([1,2,3,4,5,6,7,8],0,0,O).
O = 38165472 ;

?- g([1,2,3,4,5,6,7],0,0,O).

?- g([1,2,3,4,5,6],0,0,O).
O = 123654 ;
O = 321654 ;

?- g([2,2,3,3,5,6,7,8,9],0,0,O).
O = 363258729 ;
O = 363258729 ;
O = 363258729 ;
O = 363258729 ;
O = 723258963 ;
O = 723258963 ;
O = 723258963 ;
O = 723258963 ;

Python 2 – 114

Not even the shortest Python solution, but I am sharing it anyway:

f=lambda s,n:[[n,e.join(f(s.replace(j,e),n+j)for j in s)][s>e],e][n>e>0<int(n)%len(n)]
print f("123456789",e)

Bash+coreutils, 159 bytes

l=`echo {1..8}`
for d in {2..8};{
l=$(printf "a=%s;if(!a%%$d)a\n" $(eval echo {${l// /,}}{1..8}|tr \  '
'|grep -Pv '(\d).*\1')|bc|paste -d\  -s -)
echo ${l}9

This is kind of long, but I think the algorithm is perhaps one of the fastest, considering this is a (usually slow) shell script that runs in less than 0.1 second.

The algorithm goes something like this:

  • Start with the leftmost digit (1-8)
  • append the next digit to the right (1-8)
  • remove any numbers with repeated digits (grep)
  • check for divisibility by $d (the digit number) using bc, with an expression generated by printf
  • Repeat the above until an 8 digit number is obtained

Note we take a couple of shortcuts, but I think these are mathematically sound:

  • The leftmost digit must be divisible by 1, which is all digits, so we don't explicitly check for the first set of leftmost digits
  • The rightmost digit must be 9 (actually I'm not sure if this is a valid assumption - I'll have to think about it a bit)

C++, 187

I just had to try this in C++. Obviously, it's not going to be the shortest solution but here it is:

#include <algorithm>
using namespace std;bool c(int n,int d=9){return d<2||n%d==0&c(n/10,d-1);}int main(){for(char n[]="123456789";next_permutation(n,n+9);)if(c(atoi(n)))return atoi(n);}

returns the number instead of printing it to save some characters (damn include). Under POSIX-systems this will of course be converted to an 8-bit unsigned and thus not correct - but the program will calculate a correct number.

Ungolfed (requires C++11):

#include <iostream>
#include <algorithm>
using namespace std;

bool check(int n, int digit = 9)
  return (n % digit==0) && (digit == 1 || check(n/10,digit-1));

int main()
  string num {"123456789"};
  while (next_permutation(begin(num), end(num)))
    if (check(stoi(num))){
      cout << num << endl;

T-SQL 2005+ - 203

T-sql is not a very competitive golf language...

with A(n)as(select top 10 number from spt_values where'p'=type),R as(select \r,1l union all select r*10+n,l+1from R,A where n not in(select substring(str(r),n,1)from A)and(r*10+n)%l=0)select max(r)FROM R

Must be run on the master database. You can replace the first CTE with this to make it database agnostic but then it uses a few more characters (and requires 2008)

with A as(select*from(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9))f(n))

Readable formation:

 with A(n)as(select top 10 number from spt_values where'p'=type),
    R as(select \ r,1 l 
        union all 
        select r*10+n,l+1
        from R,A
        where n not in (
            select substring(str(r),n,1)
            from A
select max(r) FROM R

Basically we keep adding digits to the back of the r number that we haven't seen in the string yet, and making sure that the new string is still modulo 0 of the current level. We initialize R to \, This is really the only trick in this code. Which is a crazy way to set it to 0 in money datatype. It's I'm guessing a way to let you type \ instead of currency. $ also does the same thing in T-SQL, but $l would try to interpret a pseudo column that doesn't exist and throw an error. This lets us avoid the worry about using int which would cause an overflow normally at the 10th concatenation, forcing us to actually check the level. Edit: Fun fact T-sql even in 2014 doesn't have a built in way to turn a string into a table of values (e.g. no split func), so we actually also get to reuse our A table twice to iterate the characters in the stringified R.

T-Sql precedence rules are annoying so we have to use numeric concatenation (*10+n), rather than string concat.

  • \$\begingroup\$ You can save 5 bytes and allow it to run on all kinds of databases by replacing the first row with: with A as(select 1n union all select n+1 from A where n<9), \$\endgroup\$ Commented Jun 27, 2014 at 8:07
  • \$\begingroup\$ Good point. In real code, I would never use a rCTE to count so it didn't even dawn on me to try it! \$\endgroup\$
    – Michael B
    Commented Jun 27, 2014 at 12:36

PHP, 89 bytes

random version, 89 bytes:


shuffles a string containing the digits, then tests divisibility in a loop.

Run with -nr.

brute force loop, 90 bytes, very slow:


loops from 100000001, tests divisibility in inner loop, and exits when it finds a solution.

recursive function, 94 bytes, very fast:

function f($n="",$e=1){while($d++<9)strpos(_.$n,"$d")|($x=$n.$d)%$e||print$e>8?$x:f($x,$e+1);}

appends one digit that´s not yet in the number, if divisibility by length is given, recurse (or print).

This exploits that there is only one solution. without that, print$e>8?$x:f($x,$e+1) had to be print$e>8?"$x\n":f($x,$e+1) (+3 bytes, print all solutions) or ($e>8?die("$x"):f($x,$e+1)) (+4 bytes, exit at first solution) or the solutions would be printed without a delimiter.

Call with f();



The brute force version has no TiO for obvious reasons, but you can try the other two.

The function call´s runtime is measured inline (somewhere between 2 and 4 milliseconds);
total runtime is measured by the website (usually between 50 and 500 ms).


Husk, 15 bytes


Try it online!


05AB1E, 9 bytes


Try it online!

The same as my answer on the newer challenge, but with fixed input of 9. Hardcoding is shorter:


Try it online!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.