%I #52 Nov 05 2020 15:02:25
%S 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,
%T 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,
%U 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
%N Minimum number of "k-splits" required to transform {n} to {1}.
%C 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.
%C 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}.
%C 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?
%C Almost, see A241216! - _Joerg Arndt_, Apr 17 2014
%H Joerg Arndt and Alois P. Heinz, <a href="/A125173/b125173.txt">Table of n, a(n) for n = 1..200</a> (first 162 terms from Joerg Arndt)
%H Donald E. Knuth, <a href="https://www.jstor.org/stable/27642122">Problem 11264</a>, Amer. Math. Monthly, vol.114, no.1, p.77, (2007).
%H Richard Stong, <a href="https://www.jstor.org/stable/40391081">Reversal by Swaps (Solution to Problem 11264)</a>, Amer. Math. Monthly, vol.116, no.3, p.277-278, (March 2009).
%e a(9) = 2, as shown by the sequence of 2 k-splits:
%e T(3)({9}) = {3}, followed by T(1)({3}) = {1}.
%e a(44) <= 5, as shown by the 5 k-splits:
%e 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}.
%e Exhaustive calculation shows that no sequence of fewer k-splits will suffice for {44}, so a(44) = 5.
%p b:= proc(s) option remember; local m; m:= max(s[]);
%p `if`(m=1, 0, 1 +min(seq(b((s union {k, m-2*k})
%p minus {m, 0}), k=1..m/2)))
%p end:
%p a:= n-> b({n}):
%p seq(a(n), n=1..50); # _Alois P. Heinz_, Apr 12 2014
%t 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}]]]];
%t a[n_] := b[{n}];
%t Array[a, 50] (* _Jean-François Alcover_, Nov 05 2020, after _Alois P. Heinz_ *)
%o (Sage)
%o def split(k, S):
%o m = max( S )
%o S = S.difference( [m] )
%o p = m - 2 * k;
%o # if p < 0: return("invalid split")
%o S = S.union(Set([k]))
%o if p!=0: S = S.union(Set([p]))
%o return S
%o @CachedFunction
%o def min_split(S):
%o m = max( S )
%o if m <= 2: return int(m > 1)
%o ct = 0
%o mct = 999
%o k = 1
%o while k <= m/2:
%o ct = 1 + min_split( split(k,S) )
%o if ct < mct: mct = ct
%o k += 1
%o return mct
%o def a(n): return min_split( Set( [n] ) )
%o for n in [1..1100]: print(a(n))
%o # _Joerg Arndt_, Apr 12 2014
%K nonn
%O 1,4
%A _John W. Layman_, Jan 12 2007
%E Terms recomputed and terms a(58) and beyond added by _Joerg Arndt_, Apr 12 2014