[seqfan] Re: Splitting algorithm(s)

[Robert Gerbicz]

2010/6/9 <franktaw at netscape.net>

> If we start with { k^n } with k sufficiently large, so that there are
> no "collisions", the result will be 2^n-1.
>
> Making the assumption that, starting with { 1^n },  there are no
> collisions beyond 2^n, I get the sequence starting:
>
> 1, 4, 16, 172, 4331, 232388, 4865293065, 40149713684529166,
> 18146043304242732580476958015509,
> 5522398183372890742378015411585945108751680563839006,
> 2802309367952423886158538244543235705462888970382946\
>      14654240375622165503858308860084264
>
> I don't really have any theoretical justification for the 2^n limit,
> except that it seems to be quite sufficiently large, at least for small
> values of n. Extending to n! instead, I can verify the first 7 values -
> still working on a(8). (Hugo's first 5 values I can verify without
> qualification.)
>
> Franklin T. Adams-Watters
>
> -----Original Message-----
> From: hv at crypt.org
>
> Consider a formalized version of the splitting algorithm, used to
> generate
> a set of distinct unit fractions that sum to a given rational:
>
> Given a multiset M, if it has no duplicated elements, terminate; else,
> pick
> a duplicated element e, and replace one copy of e with the two elements
> e+1 and e(e+1).
>
> If we start with the multiset { 1^n }, how many elements are in the
> resulting
> set? I get a sequence starting: 1, 4, 16, 172, 4331 (not in OEIS), but
> my
> naive algorithm quickly runs out of memory. Starting instead with { 2^n
> }
> I get: 1, 3, 7, 15, 46, 171, 785, 4330, 28607 (also not in OEIS).
>
> This multiset -> multiset operation gives a multiset -> set algorithm.
> Are there other operations of the form "replace a duplicate e with the
> values (f_1(e), f_2(e), ... f_k(e))" that a) are guaranteed to
> terminate,
> and b) have useful interpretations or interesting results?
>
> Hugo
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>

a(6)=232388 is true (without "qualification"). For the other sequence if we
start by n 2's then the next term is b(10)=232387 found. From this one would
conjecture that a(n)=b(2*n-2)+1, and the proof is really trivial.