Introducing S-sequences: which is the shortest to contain all integers 1 to 20?

Question

Consider a sequence (finite or infinite) of different positive integers, such as the following, in which the first term is 1, and thereafter the nth term is either the previous term plus n, minus n, times n, or divided by n.

1, 3, 6, 10, 2, 12, 5, 40, 31, 21, 32, 20, 33, 19, 4, ...

Call such a sequence an S-sequence (for N. J. Sloane).

• a) Prove that for all positive integers N, there is a S-sequence which contains, in some order, all integers up to N (the above contains all integers up to 6).

• b) Which is the S-sequence of shortest length that contains, in some order, all the integers between 1 and 20?

• c) Which is the S-sequence containing all integers between 1 and 20, and whose largest term is as small as possible?

The "Slightly Spooky Sequence" Game

Answer 1

Answer to part c):

This sequence has maximum term 100 (and length 50):
1 2 5 20 100 94 87 95 86 96 85 73 60 74 59 75 58 76 4 24 3 66 43 19 44 18 45 17 46 16 47 15 48 14 49 13 50 12 51 11 52 10 53 9 54 8 55 7 56 6

Found with the following Python code:

from heapq import heappush, heappop

best_n = 0

candidates = [(1, [1], set((1,)))]
while candidates:
    prev_max, prev_list, prev_set = heappop(candidates)
    n = len(prev_list) + 1

    max_n = min(set(range(1, (n+1)+1)) - prev_set) - 1
    if max_n > best_n:
        best_n = max_n
        print(max_n, ':', prev_list)

    prev_num = prev_list[-1]
    new_nums = [prev_num + n, prev_num * n]
    if prev_num > n:
        new_nums.append(prev_num - n)
    q, m = divmod(prev_num, n)
    if m == 0:
        new_nums.append(q)
    for new_num in new_nums:
        if new_num not in prev_set:
            new_list = prev_list.copy()
            new_set = prev_set.copy()
            new_list.append(new_num)
            new_set.add(new_num)
            new_max = max(prev_max, new_num)

            heappush(candidates, (new_max, new_list, new_set))

Here are the sequences with the smallest maximum term for N up to 24:

1 (1): 1
2 (2): 1 2
3 (6): 1 3 6 2
4 (10): 1 3 6 2 10 4
5 (10): 1 2 5 9 4 10 3
6 (12): 1 2 6 10 5 11 4 12 3
9 (19): 1 3 9 13 8 14 2 16 7 17 6 18 5 19 4
12 (48): 1 2 5 20 25 19 26 18 27 37 48 4 17 3 45 29 12 30 11 31 10 32 9 33 8 34 7 35 6
13 (69): 1 2 6 10 5 11 4 12 3 13 24 36 23 37 52 68 51 69 50 30 9 31 8 32 7
17 (77): 1 2 6 24 29 23 16 8 17 7 77 65 5 19 4 20 3 54 35 15 36 14 37 13 38 12 39 11 40 10 41 9
18 (100): 1 2 5 20 100 94 87 79 70 80 69 81 68 54 39 55 72 4 23 3 63 41 18 42 17 43 16 44 15 45 14 46 13 47 12 48 11 49 10 50 9 51 8 52 7 53 6
20 (100): 1 2 5 20 100 94 87 95 86 96 85 73 60 74 59 75 58 76 4 24 3 66 43 19 44 18 45 17 46 16 47 15 48 14 49 13 50 12 51 11 52 10 53 9 54 8 55 7 56 6
24 (109): 1 2 5 20 4 24 31 39 30 3 33 21 8 22 7 23 6 108 89 109 88 66 43 19 44 18 45 17 46 16 47 15 48 14 49 13 50 12 51 11 52 10 53 9

Some values of N are missing because their S-sequences have the same length and maximum term as the S-sequence for a larger N.

Answer 2

b) The shortest sequence is

Length 37:

$1,2,5,20,15,9,16,8,17,7,18,6,19,33,48,3,51,918,937,917,896,874,38,14,39,13,40,12,41,11,42,10,43,77,112,148,4$

Method:

By computer. Sort the heap with the following heuristic:
sequence.Length + MinNeeded(sequence)

MinNeeded() (pseudocode below) returns an extremely rough approximate of the minimum number of remaining elements which would be needed to produce a valid sequence. The method may return a number too low, but never too high, which makes it safe to use.

int MinNeeded(sequence)
{
  min = 0;

  // The amount of numbers in the range [1, 20] which are not in the sequence yet
  remaining = 20 - Matches(sequence, 1, 20);

  // best case: as long as n is less than 20, we could only use elements in [2, 20]
  min += Max(0, 20 - sequence.Length);
  remaining -= min;

  // Once n >= 20, the remaining part of the sequence
  // can never have two consecutive elements which
  // are both within the range [2, 20].
  // The best case scenario is two elements per value in range [2, 20]
  min += remaining * 2;

  // to deal with extremely large numbers
  // we add the minimum amount of operations
  // it would take to get the current number
  // back to [2, 20]. A check if it is 
  // actually divisible is not needed here,
  // it's good enough.
  n = sequence.Last();
  c = 0;
  for (i = sequence.Length + 1; n > 20; i++)
  {
    n /= i;
    c++;
  }

  min += Max(0, c - 1);

  return min - 1;
}

Here are the shortest ones for all $N$ up to $30$. My method is currently too naive to reasonably calculate anything bigger.

1 (1): 1
2 (2): 1,2
3 (4): 1,3,6,2
4 (6): 1,3,6,2,10,4
5 (7): 1,2,5,20,4,10,3
6 (9): 1,2,6,10,5,11,4,12,3
7 (12): 1,2,6,10,5,11,4,12,3,30,19,7
8 (15): 1,3,9,13,8,14,2,16,7,17,6,18,5,19,4
9 (15): 1,3,9,13,8,14,2,16,7,17,6,18,5,19,4
10 (17): 1,2,6,10,15,9,16,8,17,7,77,65,5,19,4,20,3
11 (20): 1,2,5,9,4,10,3,11,99,89,78,66,53,39,24,8,25,7,26,6
12 (21): 1,2,6,10,5,11,4,12,3,13,24,36,23,9,135,151,134,152,8,28,7
13 (21): 1,2,6,10,5,11,4,12,3,13,24,36,23,9,135,151,134,152,8,28,7
14 (26): 1,2,5,9,4,10,3,24,15,25,14,26,13,27,12,28,11,198,217,197,176,8,31,7,32,6
15 (26): 1,2,5,9,4,10,3,24,15,25,14,26,13,27,12,28,11,198,217,197,176,8,31,7,32,6
16 (29): 1,2,6,24,120,20,13,5,14,4,15,3,16,224,209,193,210,228,12,32,11,33,10,34,9,35,8,36,7
17 (31): 1,2,5,9,14,8,15,7,16,6,17,29,42,56,71,55,72,4,23,3,63,85,62,38,13,39,12,40,11,41,10
18 (32): 1,2,5,9,14,8,15,7,16,6,17,29,42,3,18,288,4896,272,253,273,13,35,12,36,11,37,10,38,67,97,128,4
19 (34): 1,2,6,10,5,11,4,12,3,30,19,31,18,32,17,33,16,34,15,35,14,36,13,312,7800,300,327,299,270,9,40,8,41,7
20 (37): 1,2,5,20,15,9,16,8,17,7,18,6,19,33,48,3,51,918,937,917,896,874,38,14,39,13,40,12,41,11,42,10,43,77,112,148,4
21 (41): 1,2,6,10,15,9,16,8,17,7,77,65,5,19,4,20,3,21,40,60,1260,1238,1215,1191,1216,1242,46,18,522,552,521,489,456,490,14,50,13,51,12,52,11
22 (42): 1,2,6,24,19,25,18,26,234,244,255,267,280,20,5,21,4,22,3,60,39,17,40,16,41,15,42,14,43,13,44,12,45,11,46,10,47,9,48,8,49,7
23 (44): 1,2,5,20,4,24,31,39,30,3,33,21,8,22,7,23,6,108,89,109,88,66,43,19,44,18,45,17,46,16,47,15,48,14,49,13,50,12,51,11,52,10,53,9
24 (44): 1,2,5,20,4,24,31,39,30,3,33,21,8,22,7,23,6,108,89,109,88,66,43,19,44,18,45,17,46,16,47,15,48,14,49,13,50,12,51,11,52,10,53,9
25 (45): 1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,882,904,881,857,832,32,5,33,4,120,89,121,88,54,19,55,18,56,17,57,16,58,15,59,14
26 (46): 1,2,5,20,15,21,14,22,13,23,12,24,11,25,10,26,9,27,8,28,7,29,6,144,119,93,66,94,65,35,4,36,3,102,137,173,136,98,59,19,60,18,61,17,62,16
27 (46): 1,2,5,20,15,21,14,22,13,23,12,24,11,25,10,26,9,27,8,28,7,29,6,144,119,93,66,94,65,35,4,36,3,102,137,173,136,98,59,19,60,18,61,17,62,16
28 (46): 1,2,5,20,15,21,14,22,13,23,12,24,11,25,10,26,9,27,8,28,7,29,6,144,119,93,66,94,65,35,4,36,3,102,137,173,136,98,59,19,60,18,61,17,62,16
29 (46): 1,2,5,20,15,21,14,22,13,23,12,24,11,25,10,26,9,27,8,28,7,29,6,144,119,93,66,94,65,35,4,36,3,102,137,173,136,98,59,19,60,18,61,17,62,16
30 (52): 1,2,5,9,4,24,17,25,16,26,15,27,14,28,13,29,12,30,11,31,10,220,243,267,242,216,8,36,7,37,6,38,71,105,3,108,145,107,146,106,65,23,66,22,67,21,68,20,69,19,70,18