# [seqfan] Re: Splitting algorithm(s)

franktaw at netscape.net franktaw at netscape.net
Wed Jun 9 17:26:58 CEST 2010

```Nope, using the n! bound, I get a(8) >= 40149851165417480. Presumably
the subsequent values below are also wrong.

-----Original Message-----
From: 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.)

-----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

```