|
| |
|
|
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.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
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.
|
|
|
LINKS
|
Eric Angelini, Du recuit simulé (Simulated annealing), personal blog, June 26 2020.
|
|
|
EXAMPLE
|
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.
|
|
|
PROG
|
(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
|
|
|
CROSSREFS
|
Row lengths are A000217 (triangular numbers).
|
|
|
KEYWORD
|
nonn,base,tabf,hard,more
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
