A351289 Square array read by descending antidiagonals: A(n,k) is the smallest m such that the base-n expansion of m contains the base-n expansions of the k-th row of A048793 as substrings.
1, 2, 1, 2, 2, 1, 3, 5, 2, 1, 3, 3, 6, 2, 1, 6, 3, 3, 7, 2, 1, 6, 11, 7, 3, 8, 2, 1, 4, 11, 11, 8, 3, 9, 2, 1, 4, 4, 27, 13, 9, 3, 10, 2, 1, 4, 4, 4, 38, 15, 10, 3, 11, 2, 1, 4, 14, 4, 4, 51, 17, 11, 3, 12, 2, 1, 12, 14, 18, 9, 4, 66, 19, 12, 3, 13, 2, 1, 12, 12, 18, 14, 10, 4, 83, 21, 13, 3, 14, 2, 1
Offset: 2
Examples
The binary expansion of 7 is 111. This means that the base-n expansions of the 7th column will contain the base-n expansions of 1, 2, and 3 as substrings. So A(6,7) = 123_6 (as that is the arrangement of those digits with the lowest value) and 123_6 = 51_10. For another example, the binary expansion of 10 is 1010, so the 10th column will contain the base-n expansions of 2 and 4 as substrings. So A(7,10) = 24_7 (as that's the arrangement with the lowest value) and 24_7 = 18_10. Also, frequently, two or more of the substrings will overlap. For example, A(2,7) = 110_2 = 6 as the final digit of 11_2 is the same as the first digit of 10_2 and 1 is a substring of both of those. The square array begins: n\k| 1 2 3 4 5 6 7 8 9 10 ... ===+========================================== 2 | 1 2 2 3 3 6 6 4 4 4 ... 3 | 1 2 5 3 3 11 11 4 4 14 ... 4 | 1 2 6 3 7 11 27 4 4 18 ... 5 | 1 2 7 3 8 13 38 4 9 14 ... 6 | 1 2 8 3 9 15 51 4 10 16 ... 7 | 1 2 9 3 10 17 66 4 11 18 ... 8 | 1 2 10 3 11 19 83 4 12 20 ... 9 | 1 2 11 3 12 21 102 4 13 22 ... 10 | 1 2 12 3 13 23 123 4 14 24 ... 11 | 1 2 13 3 14 25 146 4 15 26 ... ..
Links
- Davis Smith, Table of n, a(n) for n = 2..5051; the first 100 antidiagonals of this array
- Theodoros P. Gevezes and Leonidas S. Pitsoulis, The Shortest Superstring Problem, Optimization in Science and Engineering, Springer, 2014, 189-227.
- Matthias Englert, Nicolaos Matsakis, and Pavel Veselý, Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios, arXiv:2111.03968 [cs.DS], 2021.
Programs
-
PARI
A351289(n,k)=if(hammingweight(k)==1,return(logint(k,2)+1), my(OverSumBase(X)=fold((x,y)->my(B1=digits(x,n),B2=digits(y,n),b=select(z->B1[#B1-(z-1)..#B1]==B2[1..z],[1..min(#B1,#B2)]));fromdigits(concat(B1,B2[if(#b,vecmax(b)+1,1)..#B2]),n),Vec(X)), K=select(z->bittest(k,z-1),[1..logint(k,2)+1]), V=apply(x->my(X=if(x,digits(x,n),[0]));setbinop((y,z)->fromdigits(X[y..z],n),[1..#X]),K), W=select(X->my(L=List(V));listpop(L,setsearch(K,X));!setsearch(Set(concat(L)),X),K), P1); if(#W==1, return(W[1]), vecmax(K)
Comments