A332080 Irregular table in which row n = 1, 2, 3... lists the lexicographically first triangle of height and width n with minimal sum, distinct positive entries using only digits <= n and no diagonal having the same digit in two entries.

1, 2, 1, 10, 3, 2, 20, 10, 1, 11, 4, 3, 30, 20, 2, 22, 1, 14, 10, 11, 5, 4, 44, 3, 33, 30, 2, 20, 25, 22, 1, 15, 14, 10, 11

Offset: 1

Author

M. F. Hasler, Jul 02 2020

Keywords

• nonn
• base
• tabf
• hard
• more

Comments

The triangles consist of n rows of length 1, 2, ..., n, respectively. Diagonals are considered in both directions, SE & SW. Alternatively, these are rows and columns if the triangle is the upper left half of an n X n matrix, entries read by rising antidiagonals.

To have digits up to n, we use base n+1 for the entries in row n. To make the data easier to read, we give the terms in the base-(n+1) representation. Up to row 9 or a(165) this is the same as if we used always base 10. For rows n >= 10^D, we can use D+1 decimal digits for each base-(n+1) digit.

There is always a "trivial" solution, non-minimal for n > 2, of the form:

9

8 88

7 77 777

... ...

1 11 111 ... 11...1

Here, (9, 8, 7, ...) represent the digits (n, n-1, n-2, ...).

This solution, where the k-th row is filled with repdigits (A010785), can always be improved towards a smaller total sum of elements by replacing the largest terms in each row by smaller terms involving the additional digit '0' or a larger digit. In particular, one could replace 88 by 80 in the second row above; replace (7, 777) by (70, 7) in the 3rd row; (666, 6666) by (60, 666) in the 4th row. One can also avoid 666 by using 69 in the second position of the 4th row.

Then, no digit 0 would be possible in the 5th row, but one can still avoid 5555 and 55555 in favor of 58 and 59, etc. However, following this algorithm in a greedy manner will not always give a minimal solution, see examples for n >= 5.

Examples

			For n = 1, the triangle is reduced to a single number, [ 1 ].
For n = 2, we have the triangle:       2
  so row 2 = [ 2 ; 1, 10 ].          1   10
  (Obviously the symmetric triangle [2; 10, 1] has the same minimal sum, but it comes later in lexicographical order.)
For n = 3, we have the triangle to the right:               3
  This gives row 3 = [3; 2, 20; 10, 1, 11]                2   20
  with minimal sum = 47 (using base 10).               10   1    11
  (Using base 4 the sum is 113[4] = 23[10].)
For n = 4, we have the triangle:                   4
  The entries yield row 4 =                      3   30
  [4; 3, 30; 20, 2, 22; 1, 14, 10, 11].       20   2   22
  See below for the sum.                    1   14   10  11
This is the lexicographically earliest triangle for n = 5 with minimal sum. Indeed:
- We have to start with 4 to avoid the larger number 40 elsewhere in the table; using 40 somewhere would make the sum of the entries larger by 10 or more.
- For a similar reason, we use leading digit 3 in the second row. If we used leading digit 2 here, we would need an entry >= 33 in the 3rd row.
- We can't for example put 2 in the first place of the second row, because in the second and third place, no digit 0 may appear, since there is already the one from "30" in the second "SW/NE" diagonal and in the rightmost "NW/SE" diagonal. Thus, if we don't start the row with 20, we'd have to use 222 later in that row (or in the next one if we use a digit 1 in this 2nd row).
- In the last row we can use "10" only in the 3rd place because of the digits 0 in 20 and 30. But we can use 14 in the 2nd place. This achieves the minimal sum of 117 if we compute 4 + 3 + 30 + 20 + 2 + 22 + 1 + 14 + 10 + 11 in base 10.
  If we consider these as numbers written in base 5, the sum is 232[5] = 67[10].
  In any case this is the smallest possible sum.
For n = 5, we have the triangle    5
                                 4  44
                               3  33  30
                             2  20  25  22
                           1  15  14  10  11
The sum of these base-6 numbers is 423[6] = 159[10].
Here we do not use 40 in place of 44, which would allow only solutions with larger total sum: more precisely, one would then need to use a term >= 55 in the last row (or larger terms in earlier rows).
One possibly minimal solution for n = 6 could be:
                         5
                       6  66
                    30   3  40
                   4  44  55  33
                 2  25  26  20  22
               1  10  13  15  14  11,  sum in base 7: 652[7] = 331[10].
and for n = 7:
                          5
                        6   7
                     77  55  44
                   40   4   3  30
                  3  36  50  47  66
                2  20  27  26  22  222
              1  11  16  15  13  10  111,  sum in base 8: 1353[8] = 747[10].
A proof of minimality of these, using, e.g., exhaustive search with backtracking, would be appreciated.
		

Links

• Eric Angelini, Du recuit simulé (Simulated annealing), personal blog, June 26 2020.

Crossrefs

Cf. A010785 (repdigit numbers), A000042 and A002275 (repunits).

Row lengths are A000217 (triangular numbers).

Programs

PARI

A332080(n,r,c,d=n-r+1)={if(c==1, d*10^(r==3&&n<5), !r, n>5 && warning("non-minimal result for n>5!"); [[self()(n,r,c)|c<-[1..r]]|r<-[1..n]], c==r, d*((r!=(n>4)+2)+10), r<4, d*11^(n>4), 1<#d=setminus(concat([0,[d+1..n],d*10]), Set(concat([digits(self()(n, r-abs(c-.5-k)\/1, min(k,c))) | k<-[1..r-1]]))), d[1]+d[#d], c<3, d[1]\10*111, until(9M. F. Hasler, Aug 16 2020