Thread: project euler problems

  1. #1
    Registered User
    Join Date
    Apr 2019
    Posts
    662

    project euler problems

    am i missing something here the first few are supposed to be easy but a lot of them seem to be imposable for the simple fact the numbers required are above a long long unsigned int. for example problem 12 asks what is the first triangular number that has over 500 divisors . we proved yesterday that just having 43 divisors caused overflow on a long long unsigned int. other questions ask you to add all the digits of 2^1000 the number is huge (1.071508...........4906e 301) the list goes on

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,495
    You need a "bignum" library, such as
    GNU Multiple Precision Arithmetic Library - Wikipedia
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    May 2019
    Posts
    209
    @Salem 's right of course, and GMP is among the best, but don't overlook MPIR (a fork of GMP) if you're using MSVC.

    If, instead, you're more interested in how that kind of thing is done (and it can get quite involved), if limited to the integer domain we could say that for a 32 bit machine to handle, say, 128 bit integers, you'd first think of the 32 bit "atomic sized" value (4 bytes) as one digit of a base (2^32) number. The 128 bit integer would be 4 of them, analogous to a 4 digit base 10 number (but instead of digits just 10 digits in one place, there are a little over 4 billion digits in each place). The rest basically operates similar to the grade school method of adding 3 and 4 digit numbers. Of course, then comes the evaluation (printing the output as a base 10 value to a string/stream).

    For a 64 bit machine, naturally, it would be like a base of (2^64).

    Lest you think this is unusual, and it is in the 21st century, back in the day it was the only way.

    In '78 I had a 6502 based machine. The registers were 8 bits, and the CPU can't multiply (that had to be done as an algorithm, there was no 'mul' instruction in the CPU).

    Just to handle 16 bit math required we put two bytes together and operate as if that was a base 255 (2^8) number.

    Even in the first IBM PC, the CPU had 16 bit registers, but it did have the ability to provide a 32 bit result by placing the answer into two separate registers (which also happens on the modern CPU with two 64 bit numbers giving a potential 128 bit result from a standard math instruction).
    Last edited by Niccolo; 06-04-2019 at 11:51 AM.

  4. #4
    Registered User
    Join Date
    Feb 2019
    Posts
    533
    Just an example, from the previous post, using GMP:

    Code:
    /* lcm-gmp.c */
    /*
      Compile with:
     
        gcc -O2 -o lcm lcm.c -lgmp
    
      Install libgmp-dev package first.
    */
    #include <stdlib.h>
    #include <stdio.h>
    #include <stdint.h>
    #include <inttypes.h>
    #include <gmp.h>
     
    int main( void )
    {
      int32_t max, i;
      mpz_t n, m;
     
      /* Read from redirection (or keyboard) */
      if ( scanf( "%" SCNi32, &max ) != 1 )
      {
        fputs( "\033[31;1mError\033[m: Cannot read upper limit.\n", stderr );
        return EXIT_FAILURE;
      }
     
      // MAX can be as bit as 2^31 - 1!
      if ( max < 2 )
      {
        fputs( "\033[31;1mError\033[m: Upper limit must be greater than 1.\n", stderr );
        return EXIT_FAILURE;
      }
     
      mpz_init_set_ui( n, 2 );
     
      for ( i = 3; i <= max; i++ )
      {
        mpz_init( m );
        mpz_lcm_ui( m, n, i );   // libgmp has an LCM function already.
        mpz_set( n, m );
        mpz_clear( m );
      }
     
      // Show the result.
      mpz_out_str( stdout, 10, n );
    
      mpz_clear( n );
    
      printf( " is lcm of the range [1..%" PRIi32"].\n", max );
    
      
      return EXIT_SUCCESS;
    }
    Compiling, linking and running:

    $ cc -O2 -o lcm-gmp lcm-gmp.c -lgmp
    $ ./lcm-gmp <<< 10000
    579333967028764296869227087916624009863486029799
    851882539313835114897930014577318230883259817618
    292216657441767940234070565594914024678915773283
    267630212994668431184746378526568319385215494723
    479710730681616793017054726852369264633873384952
    205710644202506773150005994579413408494962272276
    289264937710182648218422303703496401025734928814
    243173061895694671014958346019912700399187809245
    064954057979237622053607906520731593333827956704
    260410335666993424490503097866736816704833691556
    895675542398988790397441473339719882580610420909
    704767292934845130724436147957668787263257958548
    553944912908211671483555147491496837075852833815
    461537030142104424703181805119066911083251464942
    193434988993829180182465866098276674703291660121
    108749811048004157415275862800267378481826736356
    458722309052345151696111210428670439567278393141
    987286262740666554678461833435991947615903686084
    725783981697401114859240469868707148838942858413
    949646274080941610192306627491012307830086686769
    072111994881075233064105317720454528539577068732
    384668299886498221575571035032835633982817754649
    119047891595159009874015746788859424939076047408
    918789076986226795709655694836824560429182364447
    197945344111719076063360905340293493513002761418
    925297954487518263943991532161832703857377957487
    705086120963747653335782379733959072654843375029
    039019477996633883298491980457562079695900556866
    076781952063672736006329094170242247547504287112
    369179136634192159258309440355398487491631784896
    142275466560907901641081957410480336143684958272
    312813921900630513152480701922634008013150956085
    121395107314697323113138989957460405634331214277
    760714826559043465382810106684767311324158298449
    846004141367814047742135395078597902292058902717
    216003091699268061218717500081637387739116100095
    086091496653325796327673970788779969265813374193
    518347543704110086861368185010308623455053853571
    980608944638213422987178515678365629843448064696
    137680247649673729796551790660743981982468051045
    761344748230164888428180770416616760983993788097
    138942849948653706486168006892255954319671810728
    653634300052508407678909121645307057049368379155
    848566069606873473723913392544321190859321755413
    929543436847166951626292712297892894047521042185
    969770369419105212663217268219405339863842379944
    037806183013790993479752601227241944542750888255
    870444882089656903737069040569265093246963088109
    743317901194564381471685855520119269219121674505
    099416461040768187620608819039696164316463849858
    959442312185056205470938742411697592054501454787
    461127968986267119663209650572122199585673388513
    566317399471250962504529424974733092999076123304
    351974543927886373592531163086850070142496054926
    595244291345133441375171018722794282022859516528
    563548272307659315028053416964701486980027377008
    230789046345547767501691782592162559039688655887
    498277898889501724524554482488337123098356575613
    692331579774055793652936719431314120341099019448
    928192450016574966718225812741805962553405070544
    999340602823204582407224542099335697359400328591
    099346868782741108643949244635738520153384288819
    618432920835660346698146196126066382836157665218
    975045666162723052539319383728304460733840192993
    553208643427340195176336623467904229159519548226
    451370914941261003901045109873733663286153630560
    421374408082259736008095668457180737916169277842
    605578450218230949993269043735923194075166608967
    643880922625103691821535592854460749909418635162
    472265326531421985518400636319894287767995332862
    154646606441294115032873068385513411847399768070
    977631153680317486460437805490551434282972306780
    537384530102349490082537693552072081679992033531
    575246660170298036796121318247407946525928756628
    184799801175057685411948355242318182035522564267
    527304551157522808370997632376063481928679364579
    939708664462640158128191799941386422951088723817
    091819370922903925443354640253246612847460036602
    471611966982090621646372641149307664444734710834
    082003296620590642018967211650156874877283008545
    017808101558448374897981443099429990917744664062
    700653054618482423293806362747546605198673431122
    758618212935011121014348682253780418138368087454
    176062891599042941659414086929222506011278049719
    623428079277433900303950482632756169351653476207
    180011574780884564390835908344644096227816937908
    832895970240439825842200692241702358634587453443
    656840821144303628674461936010755698036507730180
    267000038122984605279762191003080165375380085977
    515656315827456431394345083325155696454267719324
    83266712323523039014220800000 is lcm of the range [1..10000].
    Last edited by flp1969; 06-04-2019 at 12:09 PM.

  5. #5
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    Project Euler, problem 12's answer is an 8 digit number -> A 32bit integer is fine.


    There is one question that I remember doing that had a massive number (I can't remember which one*) - To do that I created an array with element 0 being the LSB (little endian), and '-1' to indicate the upper limit of a number (like using a NUL character at the end of a string)

    [edit] *Question 13 [/edit]

    i.e.
    For the number 9876543210 I would have
    Code:
    BigNumber[0] = 0 
    BigNumber[1] = 1
    BigNumber[2] = 2
    BigNumber[3] = 3
    BigNumber[4] = 4
    BigNumber[5] = 5
    BigNumber[6] = 6
    BigNumber[7] = 7
    BigNumber[8] = 8
    BigNumber[9] = 9
    BigNumber[10] = -1
    ...
    Adding 2 numbers together is really easy to do with a "for" loop (which was all I had to do).


    That being said, it is great experience using 3rd party libraries.
    Last edited by Click_here; 06-04-2019 at 04:06 PM.
    Fact - Beethoven wrote his first symphony in C

  6. #6
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    i must be misunderstanding q 12 then as with the project the other day that asked what was the smallest number dividable by all the numbers 1 to 20 we proved that the limit of smallest number devisable by all the numbers 1 to 43 that was using a long long unsigned int

  7. #7
    Registered User
    Join Date
    May 2009
    Posts
    3,675
    Quote Originally Posted by cooper1200 View Post
    i must be misunderstanding q 12 then as with the project the other day that asked what was the smallest number dividable by all the numbers 1 to 20 we proved that the limit of smallest number devisable by all the numbers 1 to 43 that was using a long long unsigned int
    Edit: Divisors maybe counted differently the divisors of 8 are 2,2, and 2 for a count of 3. I am guessing this is the way they are counting the divisors.

    Edit: I was wrong.

    Code:
    28: 1,2,4,7,14,28
    6

    Prime factor would have given 2,2,7 which is only three.

    Tim S.
    Last edited by stahta01; 06-05-2019 at 06:22 AM.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  8. #8
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    Quote Originally Posted by stahta01 View Post
    Edit: Divisors maybe counted differently the divisors of 8 are 2,2, and 2 for a count of 3. I am guessing this is the way they are counting the divisors.

    Edit: I was wrong.

    Code:
    28: 1,2,4,7,14,28
    6

    Prime factor would have given 2,2,7 which is only three.

    Tim S.
    How to Find How Many Factors Are in a Number: 4 Steps


    I don't know if you are already doing this, but it pays to do a bit of research on a topic before starting.

    I always try to
    1) Read up to understand the problem and what it is asking - You can burn a lot of time working on something that has nothing to do with the problem.
    2) Research different algorithms and try to understand why they work - You can also go back to things you have done that have worked well in the past. (A good example is using a sieve of eratosthenes for anything prime related).
    3) Create a version of the programme that can solve the example case (either given, or something that I have came up with). Can any data be put in a text file? Does it come in a text file? What would be the best way to work through the numbers (linked list, array, stack, anything else...)?
    4) Try the programme with "full scale" inputs.


    The first few questions you can fly through, but as they go on you'll need to get more of a research phase before any development. I'd imagine that you are now familiar with a development process (A development process). This is why I like Project Euler so much - It is actually getting you "job ready".

    More on the job readiness - I've used printed out solutions for some Project Euler questions in job interviews. They are great because I could talk my way through the development process and I didn't have to worry about any IP problems with my current/past jobs.
    Fact - Beethoven wrote his first symphony in C

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Project Euler Questions
    By BlackDeath in forum C Programming
    Replies: 8
    Last Post: 02-05-2015, 06:27 AM
  2. Project Euler Progress
    By Click_here in forum General Discussions
    Replies: 6
    Last Post: 11-03-2014, 04:18 PM
  3. Project Euler 22
    By deadrabbit in forum C Programming
    Replies: 1
    Last Post: 06-23-2012, 11:22 PM
  4. Project Euler Problem 8
    By deadrabbit in forum C Programming
    Replies: 2
    Last Post: 10-06-2011, 10:56 PM
  5. Project Euler
    By CodeGuru25 in forum C Programming
    Replies: 2
    Last Post: 01-13-2010, 06:25 AM

Tags for this Thread