[seqfan] Re: Splitting algorithm(s)

[hv at crypt.org]

Robert Gerbicz <robert.gerbicz at gmail.com> wrote:
: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
:
: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.

I wrote code along similar lines to Franklin (I think), but rather than
an absolute cutoff, I used a relative one. Specifically, I process elements
in ascending order; if at some intermediate stage I have a least repeated
element E of multiplicity C:
  if E+C >= the next smallest element, or E+C >= E(E+1):
    split E^C into E, (E+1)^{C-1}, (E(E+1))^{C-1}, and continue
  else:
    add 2^C-1 to the sum

That gives me:
a(1, 1) = 1
a(2, 1) = 4
a(3, 1) = 16
a(4, 1) = 172
a(5, 1) = 4331
a(6, 1) = 232388
a(7, 1) = 4865293065
a(8, 1) = 40149851165417480
a(9, 1) = 18146043304242768613568943751063
a(10, 1) = 5522398183372890742378015411585945396419106762128927
a(11, 1) = 28023093679524238861585382445432357054628889703829461465424037 \
  5622165503858308860084264
a(12, 1) = 81285020674162487294650084910467010092186973218157875155310246 \
  781888517937947356158509288287484888848835962999011121371295969110392899
a(13, 1) = 44452014842586358408850617108098828136321416319391175024501577 \
  59434390321004078026752814790285872065084412370308564309665755402892724 \
  15833924499158576094471398405223309503632604697493602633800867366618582 \
  724232003000846405075611212596474957679278543105595277419
a(14, 1) = 24490275459366344907543356989839500399347528716094000432426991 \
  89615060006343267259362003797701355711910363019524724893586737357587722 \
  96668824350444935085944271378790172572437470889552582030065208816427176 \
  18815565783251485637327290000126197447392067483142830975649308932581160 \
  60748141568569795745844197296578223709432973434268876262744116760275652 \
  19275261991999855163632898967100292200766734720879937771403009508922941 \
  10343816046182648107266335230765511621388096856206038106650718908031708 \
  37516935309387582492114159987295089499049959432484969343141992702389462 \
  4366615501220271499070504971559501977

I *think* my heuristic is enough to guarantee no collisions - particularly
because I know that at any stage all elements greater than the current
element must be of the form k(k+1) - but given Franklin's experience I'm
less confident than I might otherwise have been.

Note that an earlier bug in the program still managed to agree with
a(7)..a(10) to (respectively): all, 5, 15, and 34 significant digits.

Hugo