[seqfan] Re: Splitting algorithm(s)

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

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,

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 

Franklin T. Adams-Watters

-----Original Message-----
From: hv at crypt.org

Consider a formalized version of the splitting algorithm, used to 
a set of distinct unit fractions that sum to a given rational:

Given a multiset M, if it has no duplicated elements, terminate; else, 
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 
set? I get a sequence starting: 1, 4, 16, 172, 4331 (not in OEIS), but 
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 
and b) have useful interpretations or interesting results?



Seqfan Mailing list - http://list.seqfan.eu/


More information about the SeqFan mailing list