Order the Integers

Permuting the numbers first and then looking for the solutions would be very expensive for large numbers. For 19, there are $19!$ or 121645100408832000 possible permutations. For 30, it would be $30!$ or about $2.6 \times 10^{32}$ . It will takes years for a computer to compute the answer.

To deal with this, instead looking in permutation, I generated sequences by strictly following the given rules. Here is the mechanism -

1) Generate the first number. This can be anything from 1 to n. This number can be generated using a simple for loop. Let this number be $x$ . Maintain a sum variable which records the sum.

2) Look for the next number. This digit can be anything from 1 to n except for the previously generated numbers, which in this case is x.

3) Check if the generated number in step 2 divides the sum. If it does, then look for the next number. Else switch the digit generated in step 2.

And so on. This greatly reduces the execution time.

If the process continues for $19 - 1 = 18$ times, then count that sequence.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

private static final int n = 19;
private static int count = 0;

public static void main (String args[]) {
    List<Integer> list = new ArrayList<>();

    for (int i = 1; i <= n; i++) {
        list.add(i);
    }

    for (int i = 2; i <= n; i++) {
        list.remove(new Integer(i));
        recursion (i, i, list, n);
        list.add(i - 1, i);
    }

    System.out.println(count);
}

private static void recursion (int num, int sum, List<Integer> list, int tot) {
    if (tot > 1) {
        if (sum % num == 0) {
            for (int i = 0; i < list.size(); i++){
                int x = list.get(i);
                list.remove(new Integer(x));
                recursion (x, sum + x, list, tot - 1);
                list.add(i, x);
            }
        }
    } else {
        if (sum % num == 0){
            count += 1;
        }
    }
}

Takes about 0.5s.

However, 30 is a very big target. The time increases exponentially (with a few exceptions) with each step. Here are results on my machine -

(OLD TABLE)

f(20) = 1319, time = 1.6s

f(21) = 5320, time = 3.6s

f(22) = 3220, time = 9.5s

f(23) = 4489, time = 13s

f(24) = 20237, time = 53s

f(25) = 36580, time = 139s

f(26) = 52875, time = 254s

f(27) = 197103, time = 660s

f(28) = 216562, time = 2557s

EDIT

Here's a small modification which halves the time consumed -

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

private static void recursion (int num, int sum, List<Integer> list, int tot) {
    if (tot > 1) {
        for (int i = 0; i < list.size(); i++){
            int x = list.get(i);
            if ((sum + x) % x == 0){
                list.remove(new Integer(x));
                recursion (x, sum + x, list, tot - 1);
                list.add(i, x);
            }
        }
    } else {
        if (sum % num == 0){
            count++;
        }
    }
}

Takes about 0.2s

f(25) = 33s

Proceeds by computing permutations in lexicographic order, except that it skips chunks that are inadmissible.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

from itertools import combinations
from copy import copy

def downward(available,admitted,debug=False):
    global count
    if debug:
        print 'processing', admitted, available
    if len(available)>=1:
        for selection in available:
            if sum(admitted)%selection==0:
                nextAdmitted=copy(admitted)
                nextAdmitted.append(selection)
                nextAvailable=copy(available)
                nextAvailable.remove(selection)
                downward(nextAvailable,nextAdmitted,debug)
            else:
                if debug:
                    print 'look from', admitted, selection
                continue
    else:
        count+=1
        if debug:
            print '----->', admitted
        return

N=19
count=0
downward(range(1,N+1),[],debug=False)
print count

Solution in python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

from time import time

factors_ = {}

def factors(m, n):
    if not (m,n) in factors_:
        if m == 0 :
            factors_[(m, n)] =  list(range(1, n + 1))
        else:
            factors_[(m, n)] =   [k for k in range(1, min(m, n) + 1) if m%k == 0]
    return factors_[(m, n)]

def godeep(ariane, level, n):
    if level == n:
        return 1
    else:
        res = 0
        for x in factors(sum(ariane), n):
            if not x in ariane:
                res += godeep(ariane + [x], level + 1, n)
    return res

def solve(n):
    "Order the Integers"
    return godeep([], 0, n)

start = time()
print(solve(19))
print("execution time: ",time() - start)  

Result

1
2

451
execution time:  0.9340534210205078