login
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.
2

%I #42 Jan 16 2024 18:30:04

%S 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,

%T 20,25,22,1,15,14,10,11

%N 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.

%C 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.

%C 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.

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

%C 9

%C 8 88

%C 7 77 777

%C ... ...

%C 1 11 111 ... 11...1

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

%C 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.

%C 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.

%H Eric Angelini, <a href="http://cinquantesignes.blogspot.com/2020/06/du-recuit-simule.html">Du recuit simulé</a> (Simulated annealing), personal blog, June 26 2020.

%e For n = 1, the triangle is reduced to a single number, [ 1 ].

%e For n = 2, we have the triangle: 2

%e so row 2 = [ 2 ; 1, 10 ]. 1 10

%e (Obviously the symmetric triangle [2; 10, 1] has the same minimal sum, but it comes later in lexicographical order.)

%e For n = 3, we have the triangle to the right: 3

%e This gives row 3 = [3; 2, 20; 10, 1, 11] 2 20

%e with minimal sum = 47 (using base 10). 10 1 11

%e (Using base 4 the sum is 113[4] = 23[10].)

%e For n = 4, we have the triangle: 4

%e The entries yield row 4 = 3 30

%e [4; 3, 30; 20, 2, 22; 1, 14, 10, 11]. 20 2 22

%e See below for the sum. 1 14 10 11

%e This is the lexicographically earliest triangle for n = 5 with minimal sum. Indeed:

%e - 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.

%e - 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.

%e - 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).

%e - 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.

%e If we consider these as numbers written in base 5, the sum is 232[5] = 67[10].

%e In any case this is the smallest possible sum.

%e For n = 5, we have the triangle 5

%e 4 44

%e 3 33 30

%e 2 20 25 22

%e 1 15 14 10 11

%e The sum of these base-6 numbers is 423[6] = 159[10].

%e 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).

%e One possibly minimal solution for n = 6 could be:

%e 5

%e 6 66

%e 30 3 40

%e 4 44 55 33

%e 2 25 26 20 22

%e 1 10 13 15 14 11, sum in base 7: 652[7] = 331[10].

%e and for n = 7:

%e 5

%e 6 7

%e 77 55 44

%e 40 4 3 30

%e 3 36 50 47 66

%e 2 20 27 26 22 222

%e 1 11 16 15 13 10 111, sum in base 8: 1353[8] = 747[10].

%e A proof of minimality of these, using, e.g., exhaustive search with backtracking, would be appreciated.

%o (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(9<d=self()(n,r,c--)\10,); d*100+d%100)} \\ _M. F. Hasler_, Aug 16 2020

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

%Y Row lengths are A000217 (triangular numbers).

%K nonn,base,tabf,hard,more

%O 1,2

%A _M. F. Hasler_, Jul 02 2020