Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 1 of 1
  1. #1
    Regular Coder
    Join Date
    May 2012
    Location
    France
    Posts
    224
    Thanks
    0
    Thanked 32 Times in 30 Posts

    How to pass from 2012 to 2013 ?

    A problem to solve with C++ !

    How to pass from 2012 to 2013 with only two operations : the cube function and the square root functions (the second rounded with a floor to work with integers) ?

    It seems that there is a solution with 31 operations ?

    I have build a square root function with the Matt McCutchen's C++ Big Integer Library

    Code:
    #include <math.h>
    #include <string>
    #include <iostream>
    
    // `BigIntegerLibrary.hh' includes all of the library headers.
    #include "BigIntegerLibrary.hh"
    
    BigUnsigned::Blk N=BigUnsigned::N,M=(BigUnsigned::N)>>1;
    
    BigInteger sqrt(BigInteger &a){
        if (a<0) throw " Racine illégale !";
        if (a==0) return BigInteger(0);
        if (a==1) return BigInteger(1);
    
        BigUnsigned q=0,r,e,f,g;
        BigUnsigned::Blk u,v;
        BigUnsigned::Index idx,len = p.getLength();
        /*std::cout<<a<<" Blks "<<std::endl;
        idx=len;
           while(idx--) std::cout<<a.getBlock(idx)<<" ";
         std::cout<<std::endl;
        */
        idx=len-1;
        u=a.getBlock(idx);
        v=(BigUnsigned::Blk)floor(sqrt(u));
        q=v;
        r=u-v*v;
        while(idx--)
        {
            r.bitShiftLeft(r,N);
            r+=a.getBlock(idx);
            q.bitShiftLeft(q,M);
            e=q<<1;
            f=r/e;
            //std::cout<<" r:"<<r<<" e:"<<e<<" f:"<<f<<std::endl;
            while ((g=(f+(r-f*f)/e)/2),g.compareTo(0)!=0 && g.compareTo(f)!=0 && g.compareTo(f+1)!=0) {
            //std::cout<<" f:"<<f<<" g:"<<g<<std::endl;
                f=g;}
            if (g.compareTo(0)!=0) {
                r-=(e+f)*f;
                q+=f;}
            //std::cout<<" q:"<<q<<" r:"<<r<<" e:"<<e<<" f:"<<f<<std::endl;
        }
        return q;
    }
    But my script has been running for three days without being able to inventory all the possibility ?

    Finaly I find 81 solutions with a random process. I give you only two.
    The minimal solution.
    From 2012 :
    1/- take the cube :8157016197 (10 digits)
    2/- the square root :90316 (5 digits)
    3/- the square root :300 (3 digits)
    4/- take the cube :27000000 (8 digits)
    5/- the square root :5196 (4 digits)
    6/- the square root :72 (2 digits)
    7/- take the cube :373248 (6 digits)
    8/- the square root :610 (3 digits)
    9/- the square root :24 (2 digits)
    10/- take the cube :13824 (5 digits)
    11/- the square root :117 (3 digits)
    12/- take the cube :1601613 (7 digits)
    13/- the square root :1265 (4 digits)
    14/- take the cube :2024284625 (10 digits)
    15/- the square root :44992 (5 digits)
    16/- take the cube :91076408639488 (14 digits)
    17/- the square root :9543396 (7 digits)
    18/- the square root :3089 (4 digits)
    19/- the square root :55 (2 digits)
    20/- take the cube :166375 (6 digits)
    21/- take the cube :4605366583984375 (16 digits)
    22/- the square root :67862851 (8 digits)
    23/- the square root :8237 (4 digits)
    24/- take the cube :558865368053 (12 digits)
    25/- the square root :747572 (6 digits)
    26/- take the cube :417790999850493248 (18 digits)
    27/- the square root :646367542 (9 digits)
    28/- the square root :25423 (5 digits)
    29/- take the cube :16431620361967 (14 digits)
    30/- the square root :4053593 (7 digits)
    31/- the square root :2013 (4 digits)
    Max length 18 digits.

    The maximal solution
    From 2012 :
    1/- take the cube :8157016197 (10 digits)
    2/- take the cube :542742678981731354128205477373 (30 digits)
    3/- the square root :736710715940613 (15 digits)
    4/- the square root :27142415 (8 digits)
    5/- take the cube :19996107338075844323375 (23 digits)
    6/- the square root :141407592929 (12 digits)
    7/- the square root :376042 (6 digits)
    8/- the square root :613 (3 digits)
    9/- the square root :24 (2 digits)
    10/- take the cube :13824 (5 digits)
    11/- the square root :117 (3 digits)
    12/- take the cube :1601613 (7 digits)
    13/- the square root :1265 (4 digits)
    14/- take the cube :2024284625 (10 digits)
    15/- the square root :44992 (5 digits)
    16/- take the cube :91076408639488 (14 digits)
    17/- the square root :9543396 (7 digits)
    18/- the square root :3089 (4 digits)
    19/- the square root :55 (2 digits)
    20/- take the cube :166375 (6 digits)
    21/- take the cube :4605366583984375 (16 digits)
    22/- take the cube :97677068348973470680873545788228511810302734375 (47 digits)
    23/- take the cube :931918319340007458686874904482350731938819006845121401710306697181983875344166922149431795505502402 164610398216382236569188535213470458984375 (141 digits)
    24/- take the cube :809344737308796651276603106927505405678082465995874718603053094060949779698874863504483933622555525 6121519774561359272047282991501463934960929477572061427054554285819815822915249912246955782780213432 5628267244076217163432609619302939262944521109843864042071114252086509429014565515612401270426729640 7459315318978027474231007335424238770880637951783552437450339726579211310370981827776171169119834303 273819386959075927734375 (423 digits)
    25/- the square root :284489848203551307543014989923787138853871443438404865816234528161310027667456803741296945395269731 6141816287731153977555247703703898666951437661658216092934019995063875152147771433856614109186018721 2310779270698 (212 digits)
    26/- the square root :533375897659006811202723895032141434257118228610078054910334255272365558672887266527749277190438332 2724088 (106 digits)
    27/- the square root :73032588456045210283729813378584294528040051687410808 (53 digits)
    28/- the square root :270245422636619712800250793 (27 digits)
    29/- the square root :16439143001890 (14 digits)
    30/- the square root :4054521 (7 digits)
    31/- the square root :2013 (4 digits)
    Max length : 423 digits !
    Last edited by 007julien; 01-30-2013 at 12:21 PM. Reason: complements


 

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •