[seqfan] Re: Splitting algorithm(s)

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