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

You can read about magic numbers here.

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

• 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. Apr 5, 2016 at 16:59
• Related reading: polydivisible numbers Apr 5, 2016 at 17:38
• Do leading 0's need to be included output numbers that have them?
– xnor
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? 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... Apr 5, 2016 at 19:55
• @edc65 Ugh, I can't believe I overlooked that.
– Neil
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 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 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. 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
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 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 Apr 5, 2016 at 20:04
• Update: for 2 it skips 10, 12, 32, 34, 54, 56, 76, 78 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 Apr 5, 2016 at 20:20
• This still doesn't work- 3 skips 021, 024, etc. The first correct number is 063. Apr 5, 2016 at 20:25
• @DavisDude Edited, now that I read the challenge more carefully 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