Announcement

Collapse
No announcement yet.

problem 100

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • problem 100

    you will find the problem in project Euler.net.
    Because the formula I used is - so I think - not obvious, here is its development:
    b = blue disks
    a = amount od blue and red disks
    b/a * (b-1)/(a-1) = 1/2
    b^2 - b = a^2- a/ 2
    b^2 - b +(1/2)^2 = a^2 - a/2 + 1/4
    (b-1/2)^2 = (2*(a^2 - a) + 1)/4
    b = sqrt(2*(a^2 - a) + 1)/2 + 1/2
    b = (sqrt(2(a^2 - a)+1)/2

    It looks like that it could work. But to my disappointment the solution is not correct.
    Can anybody help me?
    greetings
    Volker
    Attached Files

  • #2
    FOR a = 1000000000000 TO 1000000100000
    Looks to me like you are trying to use binary numbers in your FOR/NEXT loop. If this is correct, try using decimal. That's what FOR is looking for.
    There are no atheists in a fox hole or the morning of a math test.
    If my flag offends you, I'll help you pack.

    Comment


    • #3
      Looks to me like you are trying to use binary numbers in your FOR/NEXT loop. If this is correct, try using decimal
      Or use type specifiers....
      Code:
      FOR a = &B1000000000000 TO &B1000000100000
      MCM
      Michael Mattias
      Tal Systems (retired)
      Port Washington WI USA
      [email protected]
      http://www.talsystems.com

      Comment


      • #4
        Problem 100

        I dont use any binary numbers. 10^12 =1000.000.000.000. I have to start there.
        volker

        Comment


        • #5
          I don't know why you didn't just post the code instead of an attachment, it is not that long:
          Code:
          #COMPILE EXE
          #DIM ALL
          
          FUNCTION PBMAIN () AS LONG
              DIM a AS QUAD
              DIM b AS DOUBLE
              FOR a = 1000000000000 TO 1000000100000
                  b = (SQR(2*(a^2 - a)+1)+1)/2
                  IF b = INT(b) THEN
                      PRINT "The first arrangement over 10 ^2 disks is "+ STR$(a)
                      PRINT "it contains "+ STR$(b)+ " blue disks "
                      EXIT FOR
                  END IF
              NEXT a
              SLEEP 15000
          
              END FUNCTION
          You are almost certainly hitting a numeric overflow here somewhere, and if even if not, you absolutely positively are going to have rounding issues, since A^2 has 24 decimal digits and PB has no data type supporting more than 18 decimal digits.

          Here...
          Code:
          b = (SQR(2*(a^2 - a)+1)+1)/2
          .. there is absolutely no way the "+1" is affecting the internal value of 2*(a^2 -a)

          MCM
          Michael Mattias
          Tal Systems (retired)
          Port Washington WI USA
          [email protected]
          http://www.talsystems.com

          Comment


          • #6
            Re:Problem 100

            You are right. Overflow is happening. Thank you for your hint.
            best wishes
            Volker

            Comment


            • #7
              PowerBASIC can support 18-19 decimal digits but. The numeric processor only goes just that far, also. Intel didn't really design for numbers that large, it was sort of a "my kids will deal with that, not my problem" consideration, back when.

              Time just slips away, doesn't it?

              If you're dealing with Really Big Numbers, you really want to get yourself a BIGNUM-type library. Trying to use more than 18 significant digits in a standard math package is just pounding on the desk and demanding trouble.

              Comment


              • #8
                Volker,
                b/a * (b-1)/(a-1) = 1/2
                b^2 - b = a^2- a/ 2
                Are you sure that second line is correct? I think you've missed () out around the (a^2-a).

                Paul.

                Comment


                • #9
                  This may help the discussion

                  Code:
                   
                  [URL="http://projecteuler.net/index.php?section=problems&id=100"]Project Euler - Problem 100[/URL]
                   
                  If a box contains twenty-one coloured discs, composed of fifteen blue discs
                  and six red discs, and two discs were taken at random, it can be seen that
                  the probability of taking two blue discs, P(BB) = (15/21)[IMG]http://projecteuler.net/images/symbol_times.gif[/IMG](14/20) = 1/2.
                   
                  The next such arrangement, for which there is exactly 50% chance of taking
                  two blue discs at random, is a box containing eighty-five blue discs and
                  thirty-five red discs.
                   
                  By finding the first arrangement to contain over 10^12 = 1,000,000,000,000
                  discs in total, determine the number of blue discs that the box would contain.
                  Euler problems are written so that first-try and/or brute force methods usually fail. Something a little subtler is called for, usually without the need for external packages. (Although the Mathematica people seem to have the advantage there.)
                  The boy just ain't right.

                  Comment


                  • #10
                    Starting near a trillion, I got
                    414219641499, 585795034809, 1st solution = 1,000,014,676,308
                    but I think it is probably not be correct because likely there are precision errors at this magnitude. I think it works well in the lower (billions) values. With Mathematica or Eddy's big math program, I think it would be not too long to calculate with the high initial values shown.

                    Added: Oops, I added the wrong two numbers to get to a trillion. I'm only at 586 billion. Heck, only half way there and probably wrong at that level. I'll see if I can correct it when I get a while to check it.
                    Code:
                    #COMPILE EXE
                    #DIM ALL
                    
                    FUNCTION PBMAIN () AS LONG
                    ' 414219641499                585795034809               1,000,014,676,308
                    
                        LOCAL num, numm1, denom, denomm1 AS QUAD, ex, ex2 AS EXT
                           num   = 414213000000
                           denom = 585786400000    '~1.41421 * num
                        DO
                           numm1 = num - 1
                           denomm1 = denom - 1
                           ex = num / denom * (numm1 / denomm1)
                           ex2 = ex - .5
                           IF ABS(ex2) < 10e-20 THEN
                              IF num + denom > 1000000000000 THEN
                                 PRINT num, denom, FORMAT$(num + denom, "0,")
                                 WAITKEY$
                              END IF
                              INCR denom
                           ELSEIF ex < .5 THEN
                              INCR num
                              ITERATE DO
                           ELSE
                              INCR denom
                              ITERATE DO
                           END IF
                        LOOP
                    
                    END FUNCTION
                    Last edited by John Gleason; 19 Oct 2009, 04:06 PM. Reason: Nope, not correct yet

                    Comment


                    • #11
                      > Oops, I added the wrong two numbers to get to a trillion....

                      .. But you'd be perfect for a job in the Obama Administration....
                      Michael Mattias
                      Tal Systems (retired)
                      Port Washington WI USA
                      [email protected]
                      http://www.talsystems.com

                      Comment


                      • #12
                        The key is to find the first several solutions to the problem, it takes PB only a few seconds to find the first 6 or 7 solutions, where n is < 1,000,000.

                        When n gets very high it just takes too long to check all the values of n.

                        Notice that the value of n in consecutive solutions has a ratio of about 5.828427. By using this value, you can find the next approximate solution of n, and check near it to find the exact solution. Then multiply by 5.828427 to find the next approximate solution, and search again.

                        The answer I get is:
                        n = 1,070,379,110,497
                        blue disks = 756,872,327,473
                        red disks = 313,506,783,024

                        Code:
                        #COMPILE EXE
                        #DIM ALL
                        
                        FUNCTION PBMAIN () AS LONG
                        
                            LOCAL n, b, sum AS QUAD
                            LOCAL sqrt2 AS EXTENDED
                            LOCAL rat1, rat2 AS EXTENDED
                        
                            sqrt2 = SQR(2)
                        
                            FOR n =  1070379110400 - 1000000 TO 1070379110400 + 1000000
                                b = INT(n/sqrt2)+ 1
                                'sum = 2*b*b - 2*b - n*n + n
                                rat1 =  b/n
                                rat2 = (b-1)/(n-1)
                                IF ABS(rat1*rat2 - .5) < .5e-19 THEN
                                    PRINT "n","blue","red"
                                    PRINT n,b,n-b
                                END IF
                            NEXT n
                            PRINT "done"
                            WAITKEY$
                        
                        END FUNCTION
                        
                        'n               blue            red             ni/n(i-1)
                        '4               3               1
                        '21              15              6               5.2500000000000
                        '120             85              35              5.7142857142857
                        '697             493             204             5.8083333333333
                        '4060            2871            1189            5.8249641319943
                        '23661           16731           6930            5.8278325123153
                        '137904          97513           40391           5.8283250919234
                        '803761          568345          235416          5.8284096182852
                        '4684660         3312555         1372105         5.8284241211007
                        '27304197        19306983        7997214         5.8284266094018
                        '159140520       112529341       46611179        5.8284270363271
                        '927538921       655869061       271669860       5.8284271095759
                        '5406093004      3822685023      1583407981      5.8284271221434
                        '31509019101     22280241075     9228778026      5.8284271242996
                        '183648021600    129858761425    53789260175     5.8284271246696
                        '1070379110497   756872327473    313506783024    5.8284271247330

                        Comment


                        • #13
                          Good one Larry, that looks right to me. With your numbers we get
                          Code:
                          756872327473 / 1070379110497 * 756872327472 / 1070379110496 should = 1/2
                          
                          and using easily verifiable big integer multiplication of 
                          (numer * numer2) / (denom * denom2) it will equal:
                          
                          572855720093639278238256 / 1145711440187278556476512
                          
                          which is 1/2, because long addition shows: 
                          
                          572855720093639278238256 + 572855720093639278238256 = 1145711440187278556476512

                          Comment


                          • #14
                            Thanks John. I got sucked into that problem and lost an hour or 2 of my life last night.

                            Couple of comments:
                            1) The answer to the problem (first number greater than 10^12) is the limit of powerbasic to calculate. Trying to go any higher the error limit has to be lowered below .5e-19, and then you get multiple "solutions" from the program.
                            2) Trying to use an integer algorithm to check the solution did not work because it needs a squared term, which quickly overflows the EXTENDED integer size.

                            Where in Meechigan are you located?

                            Comment


                            • #15
                              Originally posted by Larry Chickola View Post
                              Couple of comments:
                              1) The answer to the problem (first number greater than 10^12) is the limit of powerbasic to calculate. Trying to go any higher the error limit has to be lowered below .5e-19, and then you get multiple "solutions" from the program.
                              You did better than I because I hit the multiple solutions probably before a billion, which isn't even close. Possibly the SQR of 2 was the brainwave?
                              2) Trying to use an integer algorithm to check the solution did not work because it needs a squared term, which quickly overflows the EXTENDED integer size.
                              Yes, I used a big num calculator I've been working on for quite a while now to check it.

                              Where in Meechigan are you located?
                              Venerable Day-twaa

                              Comment


                              • #16
                                Originally posted by Michael Mattias View Post
                                > Oops, I added the wrong two numbers to get to a trillion....

                                .. But you'd be perfect for a job in the Obama Administration....
                                Right on!
                                Barry

                                Comment


                                • #17
                                  This code which is a translation from Python, yields the correct result.
                                  The iterative steps can be concluded by the 2 examples in the text

                                  #COMPILE EXE
                                  #DIM ALL

                                  FUNCTION PBMAIN () AS LONG

                                  CALL solution()
                                  SLEEP 12000

                                  END FUNCTION
                                  SUB solution()
                                  DIM b AS QUAD
                                  DIM n AS QUAD
                                  DIM temp AS QUAD
                                  DIM y AS SINGLE
                                  y = TIMER
                                  b = 15
                                  n = 21
                                  WHILE n < 10^12
                                  temp = b
                                  b = 3*temp + 2*n -2
                                  n = 4*temp + 3*n -3
                                  WEND
                                  PRINT " The answer is " + STR$(b)+ " time = "+ STR$(TIMER - y)
                                  END SUB
                                  kind regards
                                  Volker

                                  Comment

                                  Working...
                                  X