9 Digit Problem

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

• The first rule seems unnecessary. Any number that consists of digits 1-9 once each will always be divisible by 9. – Geobits Jun 24 '14 at 19:31
• What's the code-aspect here? This sounds like it could be posted on Puzzling – Simon Forsberg Jun 24 '14 at 19:32
• 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. – Ry- Jun 24 '14 at 21:23
• 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. – user2357112 supports Monica Jun 24 '14 at 22:07
• @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". – Cruncher Jun 26 '14 at 14:19

CJam - 26

1{;9,:)_mrs0@{_3$<i\%+}/}g  It's randomized but works pretty fast with the java interpreter. It can take a couple of minutes with the online interpreter. Explanation: 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

• Nice! You can save one more byte by using a dummy value: 0{;9,:)_mrsT@{_3$<i\%+}/}g – Dennis Jun 24 '14 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')  Golfed (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; })()  Ugly (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; })()  Bonus With 3 little changes, you can use the same function to find longer numbers using base > 10. For instance in base 14 ... (Q=(n='',d=1,b=[...'123456789ABCD'],i)=>{ 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; })()  9C3A5476B812D Ungolfed Q=(n,d,b,i,c,z)=>{ // i,c,z fake parameters instead of vars. for (i=0; b[i]; i++) { s=[...b]; m = n + s.splice(i,1); if (m % d == 0) if (z = d<9 ? Q(m, d+1, s) : m) return z; } } Q('',1,[...'123456789'])  • 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') – MT0 Jun 25 '14 at 19:38 • 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') – MT0 Jun 25 '14 at 19:50 • @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). – edc65 Jun 25 '14 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)


output:

381654729


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

Pyth, 33 characters

=Y]kFkY~Yf>ql{TlT%vTlTm+kdr1T)pk


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

After compiling into Python 3.4:

k=''
T=10
Y=[k]
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))))
print(k)


Explanation:

=Y]k:Y=['']

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

[*r=1..9].permutation{|i|r.all?{|x|eval(i[0,x]*"")%x<1}&&$><<i*""}  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 [*r=1..9].permutation{|i|r.all?{|x|eval(i[0,x]*"")%x<1}&&$><<i}


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)

1,{{10*){.)}8*}%{..&=},{.,%!},}9*


Online demo

This builds prefixes which satisfy the condition.

# Initial prefixes: [0]
1,
# Loop 9 times
{
# Extend each prefix by digits 1 to 9
{10*){.)}8*}%
# Filter out ones which repeat a digit
{..&=},
# Filter down to ones which are divisible by their length
{.,%!},
}9*


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  • Welcome to PPCG.SE! Try adding <!-- language: lang-haskell --> two lines before your code for syntax highlighting! – Flonk Jun 25 '14 at 6:57 • 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 – Flonk Jun 25 '14 at 7:19
• It seems that you counted your characters including the trailing newline: there are only 128 characters in your code. – Peter Taylor Jun 25 '14 at 8:41
• @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. – DrJPepper Jun 25 '14 at 14:33
• @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! – Flonk Jun 26 '14 at 9:26

Javascript 75 (terminating)

Bruteforce solution (super slow)

for(a=c=1;b=c&&++a;)for(c=9;~(a+'').search(c)&&b%c<1;)--c?b=b/10|0:alert(a)


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

Javascript 70 (non-terminating)

for(a=1;b=++a;)for(c=9;~(a+'').search(c)&&b%c<1;)--c?b=b/10|0:alert(a)


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

for(a=i=[..."123456789"];b=c=i&&a.sort(x=>Math.random()*9-5|0).join('');)for(i=9;c%i<1;)--i?c=c/10|0:alert(b)


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]

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

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

• You can save a character by removing the space between (2 to 8) and forall. – ProgramFOX Jun 25 '14 at 15:41
• @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. – Keith Pinson Jun 25 '14 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. Ungolfed: # 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.

• Nice hand-rolled shuffle – Miller Jun 25 '14 at 9:08

CJam, 35 bytes

0{)_$A,1>s=!1$9,{9\m1$\%@+\A/}/;}g  After roughly 27 minutes, this produces the following output: 381654729  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”.                          ";
}/      "                                                                    ";
}g        " If “a > 0”, repeat the loop.                                       ";

• Impressive size, but it seems even slower than mine, and I suspect it's not correct – aditsu quit because SE is EVIL Jun 24 '14 at 20:44
• I don't fully understand it, but it seems to accept 0 as a digit? Also, when does it stop? – aditsu quit because SE is EVIL Jun 24 '14 at 20:48

Python 2 (78)

x=1
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.

SWI-Prolog 84

g([],O,_,O).
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 ;
false.


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 ;
false.

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

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

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

?- 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 ;
false.


Python 2 – 114

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

e=""
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;
break;
}
}


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


 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
)
and(r*10+n)%l=0)
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.

• 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), – comfortablydrei Jun 27 '14 at 8:07
• Good point. In real code, I would never use a rCTE to count so it didn't even dawn on me to try it! – Michael B Jun 27 '14 at 12:36

PHP, 89 bytes

random version, 89 bytes:

for($n=123456789;$n=str_shuffle($n);$d||die("$n"))for($d=10;--$d&&substr($n,0,$d)%$d<1;);


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

Run with -nr.

for(;++$i<1e9;$d||die("$i"))for($d=10;--$d&&max(count_chars($i))<2&substr($i,0,$d)%$d<1;);  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();

--

TiO

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