6
\$\begingroup\$

This code-challenge is related to the code-golf question Analyzing Collatz-like sequences but the goal is quite different here.

If you are familiar with Collatz-like sequences you can skip to the section "The task".

We define a Collatz-like rule with 3 positive integers:

  • d > 1 divisor
  • m > 1 multiplier
  • i > 0 increment

(In the original Collatz sequence d = 2, m = 3 and i = 1.)

For a Collatz-like rule and a positive integer n starting value we define a sequence s in the following manner:

  • s(0) = n
  • if k > 0 and s(k-1) mod d = 0 then s(k) = s(k-1) / d
  • if k > 0 and s(k-1) mod d != 0 then s(k) = s(k-1) * m + i

An example sequence with d = 2, m = 3, i = 5 and n = 80 will be s = 80, 40, 20, 10, 5, 20, 10, 5, 20, ....

Every sequence will either reach higher values than any given bound (i.e. the sequence is divergent) or get into an infinite loop (for some t and u (t!=u) the s(t) = s(u) equality will be true).

Two loops are said to be different if they don't have any common elements.

The task

You should write a program which finds a Collatz-like rule with many different loops. Your score will be the number of found loops. (You don't have to find all of the possible loops and higher score is better.)

The program could be specialized in any manner to produce the best score.

For proof the program should output the values of d, m, i and the smallest values from every found loop.

Example

For d=3 m=7 i=8 the loops are 

LOOP 15 5 43 309 103 729 243 81 27 9 3 1
LOOP 22 162 54 18 6 2
LOOP 36 12 4

So a valid proof with a score of 3 could be 

d=3 m=7 i=8 min_values=[1 4 2]

You can validate your result with this Python3 code. The program expects a list of space-separated integers d m i min_value_1 min_value_2 ... as input.

\$\endgroup\$
  • \$\begingroup\$ It's not immediately obvious to me that there exist no combination of (d, m, i), all positive, that has infinite amount of loops. Even harder to disprove, who says there exist no algorithm that can produce a combination of (d, m, i) that has a finite but arbitrarily large amount of loops. \$\endgroup\$ – orlp Mar 16 '15 at 12:27
  • \$\begingroup\$ @PeterTaylor I thought of that, but i has to be positive, so it can't be 0. \$\endgroup\$ – orlp Mar 16 '15 at 12:56
  • \$\begingroup\$ I do not see the challenge, you can just bruteforce up to an arbitrary number... \$\endgroup\$ – flawr Mar 16 '15 at 15:56
  • \$\begingroup\$ @flawr Until Peter's answer there was no proof that the number of loops is actually unbounded. \$\endgroup\$ – Martin Ender Mar 16 '15 at 16:30
  • \$\begingroup\$ @flawr Finding big primes is still interesting despite the fact that there are simple algorithms that can yield arbitrarily large ones in very long time. I think this is a similar situation. (If you could suggest a modification of the question to make it clearer that would be great.) \$\endgroup\$ – randomra Mar 16 '15 at 16:35
3
\$\begingroup\$

Java, arbitrary score with relatively small numbers

In my previous answer, I considered only primitive loops. It turns out that there's a massive benefit to be gained by considering more complex loops.

Let the loop structure n_0 ... n_{k-1} denote a loop which has n_0 multiply operations, then a division, then n_1 multiplications, then a division, etc. If we start with x_0 and loop back to x_0 then we get the constraint

-(d^k - m^n) x + (d^{b_0}m^0 + d^{b_1}m^1 + ... + d^{b_{n-1}}m^{n-1}) i

where n = n_0 + ... + n_{k-1} and k > b_0 >= b_1 >= ... >= b_{n-1} with the transitions at points corresponding to division steps.

The big bonus is the divisibility constraint: (d^k - m^n) | i is sufficient for x to exist and doesn't depend on the breakdown of the loop structure. However, because we have small d we have to worry about a new problem.

The map x -> mx + i (mod d) is a permutation of 0 .. d-1, and the length of the cycle which contains 0 places an upper bound on the length of a step in the loop sequence. So we have to pick d to satisfy two constraints: d^k - m^n > 0 and the cycle length of 0 under the permutation x -> mx - m^n is greater than n.

If we do that, though, the net result is that for much smaller increments than in the primitive case we can get a number of loops whose growth is related to necklaces. We have two free variables: in the interests of keeping it simple, we'll pick n = 2k. Then the score is OEIS A082936(k+1).

This program allows you to specify k via the command line. If k isn't specified it defaults to 15 (and will take a while to run).

import java.math.BigInteger;
import java.util.*;

public class PPCG47835 {

    public static void main(String[] args) {
        int k = args.length > 0 ? Integer.parseInt(args[0]) : 15;

        BigInteger TWO = BigInteger.valueOf(2);
        int n = 2 * k;
        // We want d to allow steps of up to n without getting a division "too early".
        BigInteger d, i;
    nd: for (d = BigInteger.valueOf((k + 1) | 1); true; d = d.add(TWO)) {
            i = d.pow(k).subtract(BigInteger.ONE.shiftLeft(n));
            if (i.signum() < 0) continue;

            // Find multiplicative inverse of m and additive inverse of i.
            BigInteger half = d.add(BigInteger.ONE).shiftRight(1);
            BigInteger negI = d.subtract(i.mod(d));
            BigInteger inv = BigInteger.ZERO;
            for (int j = 0; j < n; j++) {
                inv = inv.add(negI).multiply(half).mod(d);
                // If we get a division too early, reject this value of d.
                if (inv.signum() == 0) continue nd;
            }

            break;
        }

        System.out.print(d); System.out.print(" ");
        System.out.print("2 "); // m is hard-coded for optimisation reasons
        System.out.print(i); System.out.print(" ");

        visit(d, i, new int[k], 0, n);
    }

    private static long visit(BigInteger d, BigInteger i, int[] a, int off, int unused) {
        long count = 0;
        if (off == a.length - 1) {
            a[off] = unused;

            if (canonical(a)) {
                BigInteger x0 = BigInteger.ZERO, dj = BigInteger.ONE;
                int tail = 0;
                for (int step : a) tail += step;
                for (int step : a) {
                    x0 = x0.add(dj.shiftLeft(tail));
                    tail -= step;
                    x0 = x0.subtract(dj.shiftLeft(tail));
                    dj = dj.multiply(d);
                }

                // Find min element of loop
                BigInteger x = x0, min = x0;
                for (int step : a) {
                    x = x.add(i).shiftLeft(step).subtract(i).divide(d);
                    if (x.compareTo(min) < 0) min = x;
                }
                System.out.print(min); System.out.print(" ");
                count++;
            }
        }
        else {
            for (a[off] = 0; a[off] <= unused; a[off]++) {
                count += visit(d, i, a, off + 1, unused - a[off]);
            }
        }

        return count;
    }

    private static boolean canonical(int[] a) {
        for (int i = 1; i < a.length; i++) {
            // If (a[i], a[i+1], ..., a[n], a[0], ...) < (a[0], a[1], ..., a[n]) then not canonical
            int cmp = 0;
            for (int j = 0; j < a.length; j++) {
                int l = a[(i + j) % a.length];
                if (l < a[j]) return false;
                if (l > a[j]) { cmp = 1; break; }
            }
        }
        return true;
    }
}

A table of values for small k is

k     d   m                        i                             count            time*
1     5   2                                            1                    1      <  10 ms
2     9   2                                           65                    3      <  10 ms
3    11   2                                         1267                   10      <  10 ms
4    11   2                                        14385                   43      <  10 ms
5    13   2                                       370269                  201      ~  20 ms
6    19   2                                     47041785                 1038      ~ 100 ms
7    19   2                                    893855355                 5538      ~ 200 ms
8    19   2                                  16983497505                30667      ~ 200 ms
9    25   2                                3814697003481               173593      ~   1 s
10   29   2                              420707232251625              1001603      ~   6 s
11   29   2                            12200509761511525              5864750      ~  40 s
12   29   2                           353814783188691825             34769374      ~   5 mins
13   29   2                         10260628712891493325            208267320      ~  30 mins
14   37   2                       9012061295994739864233           1258579654   Est.   3 hours
15   37   2                     333446267951814233346669           7663720710   Est.  20 hours
16   37   2                   12337511914217162067306945          46976034379   Est.   6 days
17   37   2                  456487940826035138224277733         289628805623   Est.  40 days
18   53   2             10888439761782913818653903872953        1794932468571   Est. 200 days
19   53   2            577087307374494432392024159626573       11175157356522   Est.   4 years
20   53   2          30585627290848204916790749477648625       69864075597643   Est.  30 years
21   53   2        1621038246414954860589963598385138149      438403736549145   Est. 200 years
22   53   2       85915027059992607611268286218691365993     2760351032959050   Est.   1 millennium
23   53   2     4553496434179608203397220031607758574013    17433869214973754   Est.   7 millennia
24   53   2   241335311011519234780052665123279669128225   110420300879752990   Est.  50 millennia

* Time estimates are for my desktop and do not take into account Moore's law.

By way of comparison, the primitive loop approach gets a count of 256 with d, m, i

115792089237316195423570985008687907853269984665640564039457584007913129639937 2 4996849058188708393209580433653885727675741749040256292713620895127148753968909535051831567130140427800536361944311235092312499689373069344185380298878764982917383437888265369150126268883047025906053263153342743077070213629949784932471711300338416949194858514466230930155541835492836976417521462552849829828151439491795769700761089550706865322109309518867509186521661727219794342712894514553528293333583599915855119152660168331477612260053269242986560430234705077330786794787124224746741755491125934611370153892764672649747250985223441107821742903117978482210743310404550821569990627266955020082462512267699612524608382581735872148872953982038291179038736250522214403619052671232809002689864336781865259379354540109842300836162000706609173175964765076778511263709578396744674506156294033696427487493995284581075738371090769692280216054762188589127518138288131520584197574318178660061993972695355899831800150346295612279289467959922359090181529773826032183983550966147639013053021175624446320586810044918343170506220667044512077125761303317073322670474685596439350814220641454677721525315039280131392532890829910170130067697032080409474280439338164759271511930332513867702570766544228541132375928947183068406094583347593832800564280442762290635827452583240997869953843692888192226067947959509118853654668842486758668573945360959090145811442082864634167563985839376502785026822543171326942649658233987139275721859204329035383519806823861212425057613938004931165043698511863564617462708774556582561671940716972894180648939006657896115428862959455238417230946713679067595489816862691644349147486206894779849957639007563773489185825715482918629241874646953393968589973983726055758140509670965131130784257752658746770299522875836967916417558624580056516645025818599746107786811195117610906962007211790873398885705293432124793536210298322552084298766198268069386062880805491599222083299335464318233260051056124578923476991556594627105141325720014597904262975057588563160127983394346337149559451184921223274046166216509923172453297276308866005970640160971974447253640185483049938996290913967990417218968456612292288092879853580526543382454103353323932221761043752650100958510514546836334665301844454632706732579808156076643457344106356663717319952066205422136815584557498274287416306809948333516338059512400285836031768037738728853866655085697835628961745960936579150014030594051099736611730828784952090247925149717088480177586091973077515920163783426873586357930397355117739381823232569393584442921225056292816498946180561941289525969617003960422591677532232581695494422894672826501434835010711144548693232721765524858883501584564131614106232735238273568271942114349829879812549011130627498932140219963787303666392047295347130161879688508390811456457052368641087884244432717695692861740620115568642209009685218970940995823407021508403213061601519833618919914949749932560729944863694408604885641564887722313569259885463824560811629566880766362602001251878207794809291813218122339446821220307765141235472082443011766303980475419934692291649426520786938210383159694818885907272486868034596183096946783948641773659235059865332207369753191701953074271720509354163414366530509110288778295364715304459481419726269591111113033831476467597336278202525638135387380196888108120928929912206592758873036841743174059283561849270589546973518670933574609017862101454211321814429515965605782955938554835763966653656877378114701214179045517832512518725967960474688548845690990403252570685296634735383825030851490757836070848487217727143150630122632582326713524671216431367897967185731901150978978236132858696398878770709085714611339654459381763421454140675234710546006013727311042163280262358576555574729282040697366642435486911563736228978836522862673173566191467315162837086074411440892998371617945050003690500905151896114024752033630148897533096375987946484230945160715581739543058978416964623885861267137072330824183417324312471836674446614010876008133639790379823864589219631550851493405179571521414493906211785716101489937944476318682055254570100577567674090072999567286563538674745272858654739596781140750088726701983063467568688969752541352662724693221773047489453355703592917617778058887059908843599493188178967878700874686452143244797148819513005887246430894552095242775512990445349861622693005347908216081740772797645842440456795027030576763990604473020801003631884917095834474304331601692592643761032130654520685121431539117515315693268225200842406369274142732055972271107516351776707718371533212612732159107013520630354915806085957847820144610680161443643265135769091115735240172475488336530036935621088987529766784704273310482058921733826723504067695303655124057745777998695652339401313417237600545378359269983782826433187502457173228518056004635323567580688340015973984774165661477090769751346736638695310346968397758030501161566303852426217265255722398591191019098351473721903784344165134363589741405888181012065942675147359343871187459103092866244041229108109993223374342699547815386745287202843187962286188829557304121449210276708780549039251488572270756397582413205985221344395421395049635518737128865348093874823841568937983371316576740738343238292513044856549027357915578576351486609801629929304257274357773471790868819355065396024826360103706885509503271843483111154793877823867513746205003482013383254850136869840017475534871341041292138116938828382825397532430891659421647616052007784354323227643272033212980860515552895569482447880644272893241694995323538200266661902496866765672536124101771115793440186119562870934758834332469914211918277126909910234360146175588843031763832160427580321457221813426171147486651090825672350255338379767798338514754852751959160574241424909472012585154994247156991924680323831209172410432330697604053037807192197962786954335219659163031820110755303192625450195020835881326991100974309169765041640005014715611472365781414246402252213122570415919098131699154591884131157350063759621906599381080203854855889032937243962930171652457368664360071406319452806117145761067190083953298084859254519269884722883749501672024090321844650907391589008563802642433197623190708196038351131407100941984178045116842548433308611897954232390312599198017011307546105797911654569868011782976987799416210264128310154756184365567467259009494398551766295947384897146380576382245396793373889241987820479008377997412311743646709894015813359148252258313301283889184299153129793406473881703701222455612590416732744003889932902484617131257634973060004070133252896502711647782061218611361609971662574694749260495926602224366686969990047311150080884201679996728981488118520710812618327278601460444407589606074211213957090080663615502399945386857714651565186614844412314333122014502453392170242543576716974460063320058767295512461357163238790571777214752114070006229765312550718446433992455939743654062732996740413754469311079804912790961953994591151510500261239704038783004705292859762976062678557186460315856835692674588307723297612422300166133365751696449747870026175009924677879030277287245269369336312789151863569206353258519913834278632462377186402279499961899284908021374152125308504639510171715509089393130521332230396542907226274183742848885698573267962797261125062141192512701061184417835613561043220323232109667059963731379596517409877681630411625817233838924488266416159803851815238257256168614277516058271688234585985732462993249956054443736648381983482701419671975145356689595272620256322481331445101492785842934898286002101833342039235462190679296198713921689536883229856906841183201263684674777479749085929473847806660491517425603701157665302860959730777662176570425150785835202311938136354096831249866980993616794259861835845854117418421176199633080854667126344881657631662542895289925905028578142969819415286087518098940882455989952729483779531997327494488649273006455284259053043267370835853418912662050811155900913019657231209352348480112926574039657102095884876087473666194876746198709126894313357133801570373641709683110295796515978000299954297796662679042970878156491109209665444208230699217768702297201937392225784881636876279840090835870138165111806161316770297227301487650691564365317103587821371568348101143269981586519324517595090564942087519294885031922087517288681587330380466542222497060227220537050162604322824602200290170113535161501858277867838006545831844346466194034806442380131576450959271537675724000508658849679726915437056598408013792937927141227114362412743251994338190882597149073139746490596072448773060164660739169347895959901258783428070465053826282687238934378771669572639364962979904839560364235330477757080320919527039947059413194447601787383981298676212538689477485296103049397296570288531280157609024919563855851065941638010910105560384646709196234593097906605084521338045305535792904755345201224219924428502320445234881533236804337154660386556198317895096622709136291150643935368146577340837582641212943711872479814861926352068155910369478195420457604854547683244448751567967214543458990619972188446862489648274259785899336937220855046067999361786359505421559641976378792316247582387949300465521246163335578117055735028548795594763719422736738699541296642630533888082084573026289684348979457301049686869256012474676007298881135557294195958957628784529517718092237567505152960799973511542468237339748060514055177275522546356644920257206379978900361138197232418223002389143614116982750262268484822017613557260859854004910808350180444116054487246697462671921182597328557520007524803709116401564426048826030164139682113612562792469520645274240336666170491422881583407224574691022829015426425872679142823179291411823384404095313173200532655220313944845581946604801116297587452485204102321891653252497296065433728399876167461244675305449764253268435078307801283711986671578586009286264684436204104362390391386544723198597283499456955734637401522715340623369596118953010351715420185046108716197180402241925717122946973480900227708787840964295454123417195858692889460592013320915419763437340308835506518497515860085201589224927986455979719291716573132693989317427092853853143558317091758708333764145267616705007914755045792698149071283036472822428464086088856741228716016631215547783878758671929883834494369906428205847245649225012840917664193773340444209047477429988486280138535299447611565118864241304783363205632689971712792857625784511243647509643143248551095327720912948972426297343335037384023426865187383421370665853949880986733066605013431868825195335391006085327808142899673095309021875360723327143271973297884126573300777596847436767267112917543088798555405098177451024925328691180726442277191831301226870556900673729077861444939050671557156811059380023851226891231720334318965013032070064100330383634381975028412906506295395355678452444790978454696616976724789986813771927545087399922786051808033797228288699479084027079820677015179207462217617550272110189915066586927794642058025609163955724593808278333064797970913248932392125660618277100321658867644590064528488635548641431127485294371207991049014982516104643680773973382964834015483793178102197744049635462238592167275327733292546923339775129043604441714985094750314083684907133240387883917707163358796456835397987686924216534713005695762336730269447397763864097217574109952760268457835103121553543943547809435629310136515867522942680208340806536737128823184478353143242959990851272642608176148916818828051817886303783114083089812006592761176216705594347614441463606055472386957586500346276183094076265319731919678377918297360320560002627772632644557590236386349651266017430679446587855304813232224024918707884564648617086383312268837676930129879648556066226806033264983598737963273870180406008683538066870502765126274643694149707285873677967718824093776882722180691117972650189102761309292934104669089740461036134415668848865221446996078261882182814526768112701706947180226498517853170695663841729344573278342052015046723008301621918433874221983031567612687639198997835055345880467379366931163029451870312801803511726470315829769955289349851591818071593612475202072766757738963248657407567124448621951918781538618159029362973703670269896934671690719204057594745131067952251875023632084626765243936006087054600526620439372647154657850827488036535695318255041120590011100411481633873900916581258214646904494496179596939758195054231831425168836082747331502993013427756287438517441087903599961786008386909298278800359735241068662935677608544425650719657846321454852052691775723834044594400908198292180899716699918508703411274237512220909057452682990580501470394045329054835880578311733770238116671488355288887843321133419538930103375653723136240819806205893624668637029920441525924508186362522801471857468411055709364731167749180173109152381041225890235125798544117424518503287053391388606784967403181422501533367232799113298300727864372488794091791244360066517146347445096119853127523618619989387774603206692805485063047665937622384725651483826289994106221444709113092530279642315850705184264478650016043079571493204867384523409447599619484322542738513532050703204484670544303980247078766728461706977613101261899613130517662043513339271972081972251235975033169859035355418581896198228448669579968354844786628892715151577207655883197361061211662890585360764248729868471541162143928479898407418951997535051386290530730534930560026151165076098324213154184926821609093750026236815995852658556780475134967682821248631118925017104070428898094451499792639954979456465328667490287970095214075242881311028544848657223299380348758074504431568354880277247371024894597317121330481789224710582588443205449648054404983651411380297568908997206645433653230553781879648698609026260609149688803834187259218391934990046249560429146172817143650579761257761859297473226211208667206278219296067860972769736845325013951766102162707890974241524047129069766698283443856433561074909072854715331636193384406654144996118408915969916186204990991034582141123994743281006246363244418773309542583886592219743760099707410621000747013211862289890467215605107191564422488628711780028413401350657998041060773532997666200753434984330930246760070729141021529876137350047762475861743365966029336095856677219758836594787689035185205018357566276403366154452535802171144627987651708319479415527121816151240974774436078840107212343662772776477715750384184775256437358764392331275973111716861241318140661879686519319679801102896769752321160368269922724425799654489764372406675126033400019307966109019867442499204870460048251242797485428868563472867215160396617956075157903885720307310099434050987317396200655657220175043854461242728923453980411119467361181531679041638758618219736521345788670637894340611197427923502661108157340822659596857580786194582953900407596655574826783788262911022735981656978119678641474565730051653303989949385633731442093650471540122475754443009919485973878675046850963401314781483864751375557302581467684573155791505113738005055965951713009435125987311912157727926596987123572005388314736057015170699190571405820344493222475637762501339486181531075750333412119852553171325870456424708803522445329570768027256890943118226300585466680714149071768756747694527967779674199727672292701094055293170775943256111412949493670926505408736539367529535253047072708341003528996780692853657902259275913028150504209018698234804907805247278498919519634797413485241817808178419079783258709888094877304454884720131521205774599179149123429480488010567779651411979379452575644824494229892475387567203397575808735183552481892282847389626644335519279613480902494199703628678924217971582686673640825975034520923481333309984472579382627381171628369255973885103607244595491212035782001761539696741214914762706129512567578375089310609565156381449913286012344158380239320492864404026249849048973815454746164774159434339922030881777546960949887833568228898334821009908230915439944011319029828183428059262552421184297456944791630398161505488763508397021966523608035018748184560985761579560983940241407106479560391909891820608540880959525042610278858310221371500586621282006975924565385523439737751976356817502920348486598579705135746712717373775992030008093742123303056282564663636742981218493378658577006648139426577704533991763882951649263192645696128958302774458682508716744246101462762753202058220999788915511409442209525344771224195365537635614569784596285738942261211014861702664933727291078199115822432678195321951844331080444623554620246999157898423521545573297946974122422428652326029397752834438104210058503652410756274373508416088465697266032715090998725292363530897498227425419187639104200987000860422607318856339760900173127146424909971071243260637473654539790380037614639658460560305522997166440361337061894981570673841422295174773855738308847365869493217478387479172474508265274053896459611097327023936106818279711661859859284005297902040361826173190520353917517593841501624863083979214677771922042330042673675827748971312997591074359693436600146885276393061272831771026848674974205729022674604104645424201757806126867223225784448131465477202766085702005907247381691118142391269089415654084629267909569022341540236203211059369603309522789964417608961538627817072516350216220491674006870237415111869714606032462485914507408954281769975478324758722382027359432279127858218458620792232947441170640486146251825636787536128451810679645949311091213950536391218178448207695073225067871296358597341331335713217531356565288624335529314554032617725078664095663913959361974597416021548340999638956683418152500468890055726969038106218741994537487017672841722456638886422968641806296783800167945888523244989122466691224701449664982262237117972785531364836749230841105558249654340103316289441694362722693442216036899253945726021704607038072621493933499268084713663487463143017774044438279129092669821340462049513896295477618081041499262887546707631694580468041778427628580823381409128006511951571493153746600021153661435963999060487989691871123898267446944425244061342471467727136009454595026124201763052056460442214672653497359790825439605055435122991872440002221158299699341762550894877256756028529939417765550243640288900435922207869547178775845753536267949609817042649185645282912272493053712667874785376191196069398119956793757782916374924356072575695084735734309660711501852285850955866643402275086657805910092044313723744430264679133758691920589232686933475070593762814793474217470400162285461668845768319031659656539982369978254204602854044341058091117550611680881628359376678819883087955697988567021691638648924577844895608406198662696865869262757680429534919253406317207666762722797998847968102286617199947462744384388515717884047800225997384360099073674099453433943926958137304536748624123197669309530015321037461250457783043296559014726071141322691971506241866656077924355900878578960637282033659413457848807209620231088382431141859409964587717237177543239362790004481987073446054038232537259240558114255180028836915328190646296092351956054483011032267954420757123439574864847382818633015646409597401939994336693025660304826515086683839422288515986705637705072643316687613870278218998858470677983202984981673539663144442468543317833948927182919212702863843641663595997542613708928254827365464641379927709913202191911620849647223085328456892605123433695824657504571351274013025428243687082509842033821110474526985064184156983393580296061829689988266546941090944235480994846680714229385404183320871974032123897879201819683832987908391594886931328780757166614327536050682203635249976585377958911420940431267251992093534777694827907246411775988472065876989655661619702364599163656758842666355291842043770616233988089275649544479451040620789894100592626970356486607161374832051953531569240599093218443171550007069330644889550839435299056046839265288195264247406157664954662322998046875
\$\endgroup\$
  • \$\begingroup\$ Fantastic answer! I will digest the details in the next few days. \$\endgroup\$ – randomra Mar 18 '15 at 14:26
8
\$\begingroup\$

GolfScript, arbitrary score

~:l 2:m.@?):d\1 l,{m\)?d-*}/abs.{1 m 3$)?-*m@)?d-m(*/}+l,/]' '*

This takes an integer on stdin and outputs a sequence with that many loops, in the input format of the Python tester. The online demo runs it for l = 4 and produces output 17 2 1755 117 405 1365 26325; this fork of the tester verifies it.

Explanation

In order to keep it simple, I restricted the analysis to primitive loops: ones with only one division.

(x -> mx + i)^n = (x -> m^n x + (m^n - 1)/(m-1) i)

so this means that I'm looking for solutions to

m^n x + (m^n - 1)/(m - 1)i = dx

or

(m^n - d) x + (m^n - 1)/(m - 1)i = 0

When n > 0, m > 1, m^n - d != 0 this has exactly one solution for x. m - 1 > 0 and m^n - 1 > 0, so in order for the solution to be positive we require m^n - d < 0, and in order for the solution to be an integer we require d - m^n to be a factor of (m^n - 1)/(m - 1)i.

The rest may already be obvious. We pick the desired score, l. We're going to find primitive loops of length 1 to l, so we want d - m^l > 0. To get a smallish output we pick m = 2, d = 2^l + 1. Then to get an easy guarantee of the divisibility constraints we pick i to be the absolute value of (m - d)(m^2 - d)...(m^l - d).

\$\endgroup\$
  • 2
    \$\begingroup\$ This was exactly my conjecture why this golf's scoring is flawed - it can be arbitrary. Your answer can however be beat by a solution that provides infinite score, if it exists. \$\endgroup\$ – orlp Mar 16 '15 at 15:56
  • \$\begingroup\$ @orlp, what's the distinction you're drawing between arbitrarily large and infinite? \$\endgroup\$ – Peter Taylor Mar 16 '15 at 16:01
  • 1
    \$\begingroup\$ An infinite solution would have one m, d, i combination that would contain an infinite amount of cycles. Your solution can generate a m, d, i for an arbitrary, but finite score. I do not know if an infinite solution exists, but I do not find it obvious that it does not. \$\endgroup\$ – orlp Mar 16 '15 at 16:02
  • \$\begingroup\$ It's not obvious that there isn't an infinite solution in that sense, but it would surprise me if there is one. If you fix m, d, and the loop structure (in terms of the sequences of multiply or divide steps) then there are 0 or 1 loops of that structure, and one of the conditions required for it to exist is a divisibility constraint on i. Unless there are an infinite number of loop structures which induce the same divisibility constraint, which would be surprising, any finite i can only satisfy a finite number of them. \$\endgroup\$ – Peter Taylor Mar 16 '15 at 22:34
4
\$\begingroup\$

Python 3, (d = 2, m = 3, i = 96521425) → Score = 2369

The program below writes the output to collatz.txt, and also prints summaries to the shell.

I used the observation that, if (d, m, i) had a lot of loops, then in general (d, m, i*k) also tended to have a lot of loops for different values of k. I started with (2, 3, 13), and eventually worked i up like so:

13 -> 65 -> 1235 -> 35815 -> 250705 -> 2757755 -> 13788775 -> 96521425

before ending up with the lengthy output that can be found here.

The respective scores of the above chain are (using a bound of 10000):

10 -> 16 -> 28 -> 146 -> 304 -> 535 -> 766 -> 1094

2369 was obtained by bumping the bound up to 100000.

This raises a question similar to the one that @orlp has brought up — if I keep doing this multiplication process, will I always be able to get more and more loops? If anyone can prove that, then they'd probably win :)

from collections import defaultdict
import itertools

def f(d, m, i, bound=1000):
    D = defaultdict(set)
    S = set()

    for j in range(1, bound):
        A = [j]
        B = {j}

        for _ in range(bound):
            if j > bound**3:
                break

            if j % d == 0:
                j //= d

            else:
                j = j*m + i

            if j in B:
                S.add(min(A[A.index(j):]))
                break

            A.append(j)
            B.add(j)

    return S

N = 1000
THRESHOLD = 0
BOUND = 10000

MULTIPLIER = 96521425

with open("collatz.txt", "w") as outfile:
    for d, m, i in itertools.product([2], [3], range(1, N)):
        result = f(d, m, MULTIPLIER*i, bound=BOUND)

        if len(result) > THRESHOLD:
            print(d, m, MULTIPLIER*i, " ".join(map(str, sorted(result))), file=outfile, flush=True)
            print(d, m, MULTIPLIER*i, len(result))

(Proof in progress for a possibly different arbitrary score method)

Pick d, m, i such that d and i are coprime and suppose we have a loop for (d, m, i):

a_0 -> a_1 -> a_2 -> ... -> a_(n-1) -> a_n = a_0

Now pick k coprime to i and d, and we want to look at (d, m, i*k). Consider the number k*a for some a.

  • If d divides a then d divides k*a, and in this case we map k*a -> k*a/d = k*(a/d).
  • Otherwise, d can't divide k*a since d and k are coprime, and we map k*a -> m*(k*a) + i*k = k*(m*a + i).

Hence one step for a in (d, m, i) is equivalent to one step for k*a in (d, m, i*k). This forms a bijection between the loop in (d, m, i) with the loop

k*a_0 -> k*a_1 -> k*a_2 -> ... k*a_(n-1) -> k*a_n = k*a_0

in (d, m, i*k).

This means that (d, m, i*k) has at least as many loops as (d, m, i). But since i is coprime to d, we can apply the same reasoning to any loops in (d, m, k).

(This explains why the multiplication method managed to give at least as many loops each time, but the proof is incomplete until I can constrain i, k such it always gives strictly more loops each time).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.