[seqfan] Re: Splitting algorithm(s)

[hv at crypt.org]

Neil, please find sequence below.

Earlier I wrote:
: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.

I modified it to say:
  if the heuristic is true for *all* pending elements:
    use the shortcut for them all
  else:
    split the first and continue

I'm confident now that this heuristic is conservative enough to avoid
eliding any future collisions. Happily, it agrees exactly with my
calculations for a(1)..a(14) above.

%I A000001
%S A000001 1,4,16,172,4331,232388,4865293065,40149851165417480,
%T A000001 18146043304242768613568943751063,
%U A000001 5522398183372890742378015411585945396419106762128927,
%N A000001 Number of distinct unit fractions required to sum to n when using the "splitting algorithm"
%D A000001 Beeckmans, L. "The Splitting Algorithm for Egyptian Fractions." J. Number Th. 43, 173-185, 1993.
%A A000001 Hugo van der Sanden (hv(AT)crypt.org) 10 Jun 2010, with contributions from Franklin T. Adams-Watters and Robert Gerbicz
%O A000001 1,2
%C A000001 The splitting algorithm decomposes a rational p/q to distinct unit fractions by first creating the multiset with p copies of 1/q, then repeatedly replacing a duplicated element 1/q' with the pair 1/(q'+1), 1/q'(q'+1) until no duplicates remain.
%e A000001 For n=2, the algorithm generates the multisets {1/1, 1/1}, {1/1, 1/2, 1/2}, {1/1, 1/2, 1/3, 1/6}. The final multiset has no duplicate elements, so the algorithm terminates, and has 4 elements, so a(2)=4.
%K A000001 nonn,new

Since the values quickly get too large to include on the S/T/U lines, I list
up to a(17) below to use as a b-file.

Hugo
---
1 1
2 4
3 16
4 172
5 4331
6 232388
7 4865293065
8 40149851165417480
9 18146043304242768613568943751063
10 5522398183372890742378015411585945396419106762128927
11 280230936795242388615853824454323570546288897038294614654240375622165503858308860084264
12 81285020674162487294650084910467010092186973218157875155310246781888517937947356158509288287484888848835962999011121371295969110392899
13 444520148425863584088506171080988281363214163193911750245015775943439032100407802675281479028587206508441237030856430966575540289272415833924499158576094471398405223309503632604697493602633800867366618582724232003000846405075611212596474957679278543105595277419
14 24490275459366344907543356989839500399347528716094000432426991896150600063432672593620037977013557119103630195247248935867373575877229666882435044493508594427137879017257243747088955258203006520881642717618815565783251485637327290000126197447392067483142830975649308932581160607481415685697957458441972965782237094329734342688762627441167602756521927526199199985516363289896710029220076673472087993777140300950892294110343816046182648107266335230765511621388096856206038106650718908031708375169353093875824921141599872950894990499594324849693431419927023894624366615501220271499070504971559501977
15 48099321900801256484060965328070262882714083806026227155808272823634945780646946453154370566526374835267124350295118316048770122430765111341890361614134139735974226415925605724682367635347088795374667806788824548931646352454361542966807612015720188593546624733887809816422005085529738141291351611761149336711548365143645322681422744300949435929253161158054150088000394223951514172449059001614142833586844299003417819789401853590305163055596252148938934626867794656971131930446569085515405920001621013888852366260682959192545566838302587102121102775778882437805535848506807742753585620438660413346111475975790301975175987422864946565747777447226951517126516150807139432751562346452476906069546334100467382521224169702351402923058586747058215074511204934838263959730514105827447626110089895018804613793365484713039319412389036093986355595029683773587639809282011945557273946605754776621500044179976925789181598106355484252873244208215337106181066447844591627847776758989448571871029045618!
 8609971079856113087889849075200628454766356735189639059142108078870623637440748249729723617745257483993250654015456694827495550409646885313653706084978797511180526
16 10467991433752938512976190405249354949479651740494109875087507755159910269942125683244664515439977275849647584425222418783907943509523654955041713895623924603601999072854234313461633670895653939521839335097164334904332651367881792342044607576251493164039511413630321063177128675642184502372601487417383459620291643476303962355347719710966489951380207801442577068407046385460392968108075679408146100896038474710230583541791289867249687092169886769687495473529616017542691929674549456121484536307413635993135022769853716172218216886220520125811275378087280389371642890350225042650023933557431610667768647842463957868025855302024765478055424891319034843881091211920578367926102915081650051459313295948382125872782831133708432305091665737189127933174357793321493550633741313883281744350045493541527529865491639411774890941127347759205172232072641239025250792450988721240231804929124072172003426352145549067477118111339682028931206344255500329573035084307925709881199464680974035616525491403!
 1933043527023399583580085628347788585359006895101713776056297486636956377692339046079142496039253535897686199000674318515184746941594945835810708069883361916596315788092420216351282465348756911567986227737857290456451066880672818422401073574291339935794890483403672371037615079725761982129312299351727720936348185403689808994067393260876760130184790729656691206808990796909538841108729997543896869085678647885930982882981974687645440897117472300921766259376663474368250558892532506750140494995668519225265819025130649888702713184356278145372769698237081085541530883443934242814021893543945553437005625932601762979126336225623911780543592160169279018461865252115955484452451599330620084348688537708539962399273552835638024571988856486423911980002387414460292437311176836886114461916525956199287919455368881282908389406011332893134416107085259510125858338494750958110243055504971155769483407356436920118742395120700485738961598879420166711060366434805749478245224551644591978236097943459504!
 4963750995237107319072270227833875019460020544625180638569011824203733
987594776020211690540487144427496401680814385037593348726253754912653496164971501191203081041918755806057313297510029974674985440925592662510071302395019450931958541450592156300736129549730685183162514167676479975989193823511212967803149959919781777073239734163316558701197179284465191581928469995416016071241498984
17 21988695128784594544929147805806326794594583388352001090498860753330574195137557403536417541569976564313806144505289297878446379710592302150513249089974976406889916164945953645013329992461317766701121062970231972717145227718861166783880481250683734208109053953626408437847013582877920767251554950438191355970405022604083699386853994528441791711503695100658124570165419082485398058566544199080191627636384082125462575590268142149089513848272250769776965478394926320416449868797952946556775461208654686158320872184455868462937050759950695941338002763128475895304264416434459917028110169292885343175247941665341418873000024926980782408752212321616651659611571133271647912966442814625107857591761717803941349098118220635084160183405252141874868128589090222075523527501787413468566857391491850171331771956341300822504829607911558874442922336928556065015306730723381592089049759366370970946027074063679400280270617858079207575765772742159637625701692383391643309518000364216404554273765577636!
 2307333682558544241050086326051087240715912149032251570059482819057229173121254025529390940294608730703377365590634657776672324470516664387679020947600334475213672127926156507087451854736052321329361567396251384006582204987853648595678162158574777927490995717558980659136080231388483753772039249485869113952906118493578147368618768740207214678743062667211275039132160041856111344099133958209295957419793832660345871953683683682467527894545446355624007692534389718238344928969305714536644688111985714006279075551173090168871886691429196379556620288877911125814471158884627975175098035136212903833658322483904803877743812047336714050892866671312157823269687645879635159221304280940877322504299787924937758997521888988365616100266995377895720214031447361241325484976069215522517517124585944916342920605553113382712304364672043919758426711335239425161087995488299348962808679927759071542743337509798025253159289915545510331458602148065678145174043318314427645186915891542598211794284625021508!
 7631817480631526750677914649452910076611458000956450441094227279153504
09902761858939161698420046503253175899701795937163107165328227547716344312586699644376918317906444901493888613245167314311284443100552395650945124823984413219105291693576322775094961331079994022519817829870643572429858097874043918166659876306380143228217629334209520836040496570655923514110794242657210077242984161133764690923195340206375983328187395430829546105774074286771127665241908440898763575262909345681970034356310281933046688959680561216361341718171549787731825819266183262653645939208625222728629405659810424195666183135666775899169235429318783565422831334135936582254447073169546184790331001734104057095696684129033028591707725183128542018831833359524985706800851096502983362585755454399828577286826524350203697453046000358445739314451912019273075639426965065120281277323236082682655885783210749311955144590428300080208789370590689866661428992347345612729768203407172384760697364353559959510528476819959732488443685745066401498585926550948758232802622847331067735431531177517188!
 9393139239242581263836368510503299265700803034197926660350499446294113795130199843073572150454191877365956905651922823485471031152740262891438659934784835798867958284165565591825079762917959355519606462577053330245574335347698355709513495261859564799825726322616336918896509107870155168246532065604267235166205512017902068794376541804394306616110321875684993476889009000623933519664780189216995775896898057181991192541346069603322914725474904320612045453715271574836495682851725164500652235562852681921912744456789584667965163170131627780223688460577976192227258349125469422965677237703150006107162837964406109557677933270585626763831455634132941984777352828847431356185623743211096445298042798673341792590087349903488056921349324981504681873781760714536545594925791197750935086253727223947520024736753305957814111722462852247005772727919126355810374392306970296648248154039150683884958209094513176481884960950122913890811948448706158115656826924458001352008534646269927765744905515677140!
 1736730596260452164724431575890818318649501510253014377671282550281519
118280060085117305171540375276680880091348540742540972891392583512157190576862439812629455523980292719266757663608325633465468007610006129365542329888413447298818776684897997951124028265475447505560944561138535259641704627314194540026442617568001612714254701818441439356183164410705449620319005541723647868054965307302017295375088382048045809976907153980343978652660145953117423760233945874117864794223297901252311299907088155696892229785221158207652635960257471326207958521133640328932726236667615760575368091023627195081868430212605173332795548417641320326634728566296280829347807990639041009340374249995067629941501314746112891348185128103821991717874861330470453054193958601726730024205205430992131201826200091639721711144501745115983531762772304477932801565135701881929738392172715771318653611654844107836191703028234286796167719371025075875615824652200224073719889436162728247783811704200419241246186662589761838799498901405830911886432831601020705238417909