|
Search: id:A125173
|
|
|
| A125173 |
|
Minimum number of "k-splits" required to transform {n} to {1}. |
|
+0
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
(list; graph; listen)
|
|
|
OFFSET
|
1,4
|
|
|
COMMENT
|
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=0 in which case m is simply replaced by k. Examples: T(4)({1,2,12}) ={1,2,3,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 of the January 2007 issue of the American Mathematical Monthly?
|
|
REFERENCES
|
D. E. Knuth, Problem 11264, Amer. Math. Monthly 114(2007)77.
|
|
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 five 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 show that no sequence of fewer k-splits will suffice for {44}, so a(44)=5.
|
|
CROSSREFS
|
Sequence in context: A139325 A068211 A089050 this_sequence A054725 A064415 A086833
Adjacent sequences: A125170 A125171 A125172 this_sequence A125174 A125175 A125176
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
John W. Layman (layman(AT)math.vt.edu), Jan 12 2007
|
|
|
Search completed in 0.002 seconds
|
