A125173 Minimum number of "k-splits" required to transform {n} to {1}.

0, 1, 1, 2, 2, 2, 2, 3, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 4, 3, 4, 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 4, 4, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 5, 4, 4, 5, 4, 5, 5, 5, 5, 5, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 5, 5, 5, 5, 5, 5, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 5, 5, 5, 6

Offset

1,4

Comments

A "k-split" is a transformation T(k) of a set of positive integers obtained by replacing the maximum element m of the set by k and m-2k, where 1<=k<=m/2, unless m = 2k in which case m is simply replaced by k.

Examples: T(4)({1,2,12}) = {1,2,4}, T(5)({1,2,12}) = {1,2,5}, T(6)({1,2,12}) = {1,2,6}.

Is this the same as the sequence of the minimum number of "d-swaps" required to reverse a word of length n, which was introduced by D. E. Knuth in Problem 11264 in the American Mathematical Monthly?

Almost, see A241216! - Joerg Arndt, Apr 17 2014

Links

Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 1..200 (first 162 terms from Joerg Arndt)

Donald E. Knuth, Problem 11264, Amer. Math. Monthly, vol.114, no.1, p.77, (2007).

Richard Stong, Reversal by Swaps (Solution to Problem 11264), Amer. Math. Monthly, vol.116, no.3, p.277-278, (March 2009).

Example

a(9) = 2, as shown by the sequence of 2 k-splits:
  T(3)({9}) = {3}, followed by T(1)({3}) = {1}.
a(44) <= 5, as shown by the 5 k-splits:
  T(15)({44}) = {14,15}, T(7)({14,15}) = {1,7,14}, T(7)({1,7,14}) = {1,7}, T(3)({1,7}) = {1,3} and finally T(1)({1,3}) = {1}.
Exhaustive calculation shows that no sequence of fewer k-splits will suffice for {44}, so a(44) = 5.

Maple

b:= proc(s) option remember; local m; m:= max(s[]);
      `if`(m=1, 0, 1 +min(seq(b((s union {k, m-2*k})
       minus {m, 0}), k=1..m/2)))
    end:
a:= n-> b({n}):
seq(a(n), n=1..50);  # Alois P. Heinz, Apr 12 2014

Mathematica

b[s_List] := b[s] = Module[{m = Max[s]}, If[m == 1, 0, 1 + Min[Table[b[s ~Union~ {k, m-2k} ~Complement~ {m, 0}], {k, 1, m/2}]]]];
a[n_] := b[{n}];
Array[a, 50] (* Jean-François Alcover, Nov 05 2020, after Alois P. Heinz *)

Prog

(Sage)
def split(k, S):
    m = max( S )
    S = S.difference( [m] )
    p = m - 2 * k;
#    if p < 0:  return("invalid split")
    S = S.union(Set([k]))
    if p!=0:  S = S.union(Set([p]))
    return S
@CachedFunction
def min_split(S):
    m = max( S )
    if m <= 2:  return  int(m > 1)
    ct = 0
    mct = 999
    k = 1
    while k <= m/2:
        ct = 1 + min_split( split(k, S) )
        if ct < mct:  mct = ct
        k += 1
    return mct
def a(n):  return min_split( Set( [n] ) )
for n in [1..1100]: print(a(n))
# Joerg Arndt, Apr 12 2014

Crossrefs

Sequence in context: A167439 A272314 A241216 * A054725 A064415 A086833

Adjacent sequences: A125170 A125171 A125172 * A125174 A125175 A125176

Keyword

nonn

Author

John W. Layman, Jan 12 2007

Extensions

Terms recomputed and terms a(58) and beyond added by Joerg Arndt, Apr 12 2014

Status

approved