Announcement

Collapse
No announcement yet.

problem 100

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

  • Volker Vanoni
    replied
    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

    Leave a comment:


  • Barry Erick
    replied
    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!

    Leave a comment:


  • John Gleason
    replied
    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

    Leave a comment:


  • Larry Chickola
    replied
    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?

    Leave a comment:


  • John Gleason
    replied
    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

    Leave a comment:


  • Larry Chickola
    replied
    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

    Leave a comment:


  • Michael Mattias
    replied
    > Oops, I added the wrong two numbers to get to a trillion....

    .. But you'd be perfect for a job in the Obama Administration....

    Leave a comment:


  • John Gleason
    replied
    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, 03:06 PM. Reason: Nope, not correct yet

    Leave a comment:


  • Joseph Cote
    replied
    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.)

    Leave a comment:


  • Paul Dixon
    replied
    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.

    Leave a comment:


  • Tom Hanlin
    replied
    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.

    Leave a comment:


  • Volker Vanoni
    replied
    Re:Problem 100

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

    Leave a comment:


  • Michael Mattias
    replied
    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

    Leave a comment:


  • Volker Vanoni
    replied
    Problem 100

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

    Leave a comment:


  • Michael Mattias
    replied
    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

    Leave a comment:


  • Mel Bishop
    replied
    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.

    Leave a comment:


  • Volker Vanoni
    started a topic problem 100

    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
Working...
X