Finding Collatz-like rules with many loops

Question

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.

Answer 1

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).

Answer 2

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).

Answer 3

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