# Magic number of a given length

Your program must take an input (n for the purpose of description) and output all permutations of a number that is n digits long with no repeating digits, where each of the digits preceding and including its index are divisible by the place in the number that it falls.

## Rules:

• 1 <= n <= 10
• No digits may be repeated
• The leading 0 must be present (if applicable)
• The 1st through xth digit of the number (starting with the first character as 1) must be divisible by x, i.e. in 30685, 3 is divisible by 1, 30 is divisible by 2, 306 is divisible by 3, 3068 is divisible by 4, and 30685 is divislbe by 5.
• The program must take an integer as input (through the command line, as a function argument, etc.) and print all permutations that satisfy the rules.
• Output must be separated by 1 or more white space character
• Permutations may start and with zero (so they're not technically magic numbers).
• The order of output does not matter
• You do not need to handle unexpected input
• Least characters in bytes wins

## Examples

Given 1:

0
1
2
3
4
5
6
7
8
9


Given 2:

02
04
06
08
10
12
14
16
18
20
24
26
28
30
32
34
36
38
40
42
46
48
50
52
54
56
58
60
62
64
68
70
72
74
76
78
80
82
84
86
90
92
94
96
98


Given 10:

3816547290


Credit to Pizza Hut & John H. Conway for the original puzzle (Option A). Thanks to @Mego and @sp3000 for their links.

• Commented Apr 5, 2016 at 16:46
• @DavisDude "Related" doesn't mean "duplicate". The purpose of posting a related link is for that challenge to show up as "Linked" in the sidebar. Commented Apr 5, 2016 at 16:59
• Related reading: polydivisible numbers Commented Apr 5, 2016 at 17:38
• Do leading 0's need to be included output numbers that have them?
– xnor
Commented Apr 6, 2016 at 4:19
• You mention printing and whitespace when it comes to output, but for a function, the most natural form of output would probably be returning a list. Is that allowed? Commented Apr 6, 2016 at 4:44

## JavaScript (Firefox 30-57), 77 bytes

f=n=>n?[for(s of f(n-1))for(c of"0123456789")if(s.search(c)+(s+c)%n<0)s+c]:[""]


Edit: Saved 1 byte thanks to @edc65.

• A gem! just save 1 byte with ...of"012... Commented Apr 5, 2016 at 19:55
• @edc65 Ugh, I can't believe I overlooked that.
– Neil
Commented Apr 5, 2016 at 20:21

# Jelly, 2017 16 bytes

QḣQV%S
ØDṗçÐḟRj⁷


This is very slow and memory intensive... Try it online!

### How it works

ØDṗçÐḟRj⁷  Main link. Input: n (integer)

ØD         Yield d := '0123456789'.
ṗ        Compute the nth Cartesian power of d.
R    Range; yield [1, ..., n].
Ðḟ     Filter false; keep strings of digits for which the following yields 0.
ç         Apply the helper link to each digit string and the range to the right.
j⁷  Join the kept strings, separating by linefeeds.

QḣQḌ%S     Helper link. Arguments: s (digit string), r (range from 1 to n)

Q          Unique; deduplicate s.
ḣ         Head; get the prefixes of length 1, ..., n or less.
If s had duplicates, the final prefixes fill be equal to each other.
Q        Unique; deduplicate the array of prefixes.
V       Eval all prefixes.
%      Compute the residues of the kth prefixes modulo k.
If s and the array of prefixes have different lengths (i.e., if the
digits are not unique), some right arguments of % won't have corr. left
arguments. In this case, % is not applied, and the unaltered right
argument is the (positive) result.
S     Add all residues/indices. This sum is zero iff all digits are unique
and the kth prefixes are divisible by k.

• If this is slow... my answer is a sleepy slug Commented Apr 5, 2016 at 21:31

# Pyth, 19 bytes

jf!s%VsM._TS;.PjkUT


Demonstration

A brute force solution. Explanation to follow. Inspiration thanks to FryAmTheEggman

# 22 bytes

juf!%sThH{I#sm+LdTGQ]k


Demonstration

Numbers are built and stored as strings, and only converted to ints to check divisibility.

Explanation:

juf!%sThH{I#sm+LdTGQ]k
u                 Q]k    Apply the following input many times, starting with ['']
m    G       For each string at the previous step,
+LdT        Append each digit to it
s             Concatenate
{I#              Filter out strings with repeats
f                       Filter on
sT                   The integer
%  hH                 Mod the 1 indexed iteration number
!                      Is zero.
j                         Join on newlines.

• I'm curious: just how masochistic do you have to be to learn Pyth? /s Commented Apr 5, 2016 at 20:06
• @DavisDude I think it is easier than what people think when they see it. The scariest part is beginning. Once you're in, you're in.
– THC
Commented Apr 5, 2016 at 20:16
• It's fairly easy, imho, because of how much the debug mode helps you. The docs are also pretty good, and explain what you need to know.
– Ven
Commented Apr 5, 2016 at 20:17
• Just for reference, I wound up with one more using ._ and some other stuff, but it's waaay slower for big inputs: jjLkf!s.e%ib10hk._T.PUT Commented Apr 5, 2016 at 21:11

# MATL, 30 bytes

4Y2Z^!"@Sd@!U10G:q^/kPG:\~h?@!


Try it online!

It's very slow. For input 3 it takes a few seconds in the online compiler. To see the numbers appearing one by one, include a D at the end of the code.

### Explanation

4Y2       % predefined literal: string '0123456789'
Z^        % implicit input. Cartesian power: 2D char array. Each number is a row
!         % transpose
"         % for each column
@       %   push current column
Sd      %   sort and compute consecutive differences (*)
@!U     %   push current column. Convert to number
10G:q^  %   array [1 10 100 ... 10^(n-1)], where n is the input
/k      %   divide element-wise. Round down
P       %   reverse array
G:      %   array [1 2 ... n]
\~      %   modulo operation, element-wise. Negate: gives 1 if divisible (**)
h       %   concatenate (*) and (**). Truthy if all elements are nonzero
?       %   if so
@!    %     current number as a row array of char (string)
%   implicitly end if
% implicitly end if
% implicitly display stack contents

• Something is wrong with your code; It stops producing output for me after 5, and with 5 the last number (the only one I've bothered to check) is incorrect. 986 is not divisible by 3 Commented Apr 5, 2016 at 20:04
• Update: for 2 it skips 10, 12, 32, 34, 54, 56, 76, 78 Commented Apr 5, 2016 at 20:09
• I think you misunderstood the prompt. Looking at 3 I can see you have a couple indications (e.g. 026). Also an explanation would be appreciated Commented Apr 5, 2016 at 20:20
• This still doesn't work- 3 skips 021, 024, etc. The first correct number is 063. Commented Apr 5, 2016 at 20:25
• @DavisDude Edited, now that I read the challenge more carefully Commented Apr 5, 2016 at 21:29

# Ruby, 87 bytes

Basic recursive solution.

f=->n,x="",j=1{j>n ?puts(x):([*?0..?9]-x.chars).map{|i|f[n,x+i,j+1]if((x+i).to_i)%j<1}}


If you're allowed to return a list of the permutations instead of printing, 85 bytes:

f=->n,x="",j=1{j>n ?x:([*?0..?9]-x.chars).map{|i|f[n,x+i,j+1]if((x+i).to_i)%j<1}-[p]}


## Python, 132 bytes

lambda n:[x for x in map(("{:0%s}"%n).format,(range(10**n)))if all(int(x[:i])%i<1and len(set(x))==len(x)for i in range(1,len(x)+1))]


Dropped 26 bytes by getting rid of itertools, thanks to Sp3000 for making me realize I shouldn't be using it.

Dropped 2 bytes by using a list comprehension rather than filter, thanks again to Sp3000 for the tip.

Try it online: Python 2, Python 3