The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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
 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 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 2,2 COMMENTS A(n,k) is the least m such that m contains the base-n expansions of the active bits (plus 1) in k as substrings. The Shortest Superstring Problem is, given a set of strings, S, to find the shortest string which contains each element of S as a substring. All possible solutions to this problem are contained in this array. The values of k represent the set of strings (where the active bits represent the strings in base n). The value of k for non-numeral strings (or numeral strings with an initial 0) is generated by mapping each character to a unique value 1 through n, converting from base n+1, subtracting 1 from each, raising 2 to the power of each and then summing the result. A(n+1,k) in base n+1 is the shortest superstring. The value of k for numeral strings in base n (without initial 0's) is generated by just raising 2 to the power of the value of each and then summing the result. A(n,k) in base n is the shortest superstring. 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. FORMULA A(n,2^k) = k + 1. A(n,2^k - 1) = A350510(n,k). A(2,2^k - 1) = A056744(k). For n > A070939(k), A(n,k) = Sum_{i=1..A000120(k)} A048793(k,i)*n^(A000120(k) - i). EXAMPLE 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 ... .. PROG (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), )); 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), vecmax(K)P, P1=P), P1=P)); print(P1); return(P1))) CROSSREFS Cf. A000120, A048793, A056744, A070939, A133457, A350510. Sequence in context: A227925 A035388 A255716 * A177954 A337312 A077053 Adjacent sequences: A351286 A351287 A351288 * A351290 A351291 A351292 KEYWORD nonn,tabl AUTHOR Davis Smith, Feb 06 2022 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 1 14:54 EDT 2023. Contains 365826 sequences. (Running on oeis4.)