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

%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