Find minimum integer such that any integer \in [1, n] can be constructed from its consequent subsums

21 Views Asked by At

For example, here's (SPOILERS) breakdown for $1143$, which is the solution for $n = 9$

  1. $\underline{1}143$
  2. $\underline{11}43$
  3. $114\underline{3}$
  4. $11\underline{4}3$
  5. $1\underline{14}3$
  6. $\underline{114}3$
  7. $11\underline{43}$
  8. $1\underline{143}$
  9. $\underline{1143}$

The questions are:

  • are there more anomalies like $18$, what are they?
  • are most solutions like that: $111 \dots some\ digits\ within \pm1$?

Those digits at the tail seem to grow and they cannot be more than $9$

Appendix A: Brute-force solution in JavaScript

function partialSums(numbers) {
  let sum = 0;
  const result = [0];
  for (const number of numbers) {
    result.push(sum += number);
  }
  return result;
}

function solve(maxSum) {
  for (let n = 1; true; n++) {
    const s = n.toString();
    // simple shortcut for speed up
    if (s.includes('0')) continue;
    const digits = s.split('').map(Number);
    const sums = new Set();
    const partials = partialSums(digits);
    for (let start = 0; start < digits.length; start++) {
      for (let end = start + 1; end <= digits.length; end++) {
        const subSum = partials[end] - partials[start];
        // sum will only increase further in the inner loop
        // so we can just break from it
        if (subSum > maxSum) break;
        sums.add(subSum);
        if (sums.size === maxSum) return n;
      }
    }
  }
}

Appendix B: Brute-force results (More SPOILERS)

$$\begin {array} {r|r} \ n & solution\\ \hline 1 & 1 \\ 2 & 11 \\ 3 & 12 \\ 4 & 112 \\ 5 & 113 \\ 6 & 132 \\ 7 & 1114 \\ 8 & 1133 \\ 9 & 1143 \\ 10 & 11134 \\ 11 & 11144 \\ 12 & 11154 \\ 13 & 11443 \\ 14 & 111155 \\ 15 & 111165 \\ 16 & 111544 \\ 17 & 111554 \\ 18 & 256318 \\ 19 & 1111555 \\ 20 & 1111655 \\ 21 & 1111665 \\ 22 & 1115554 \\ 23 & 1194332 \\ 24 & 11111766 \\ 25 & 11111776 \\ 26 & 11116565 \\ 27 & 11116665 \\ 28 & 12337741 \\ 29 & 12377441 \\ 30 & 111116766 \\ \end {array}$$