problem 100

[Volker Vanoni]

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

[Barry Erick]

> 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!

[John Gleason]

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

[Larry Chickola]

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?

[John Gleason]

Good one Larry, that looks right to me. With your numbers we get

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

[Larry Chickola]

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

#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

[Michael Mattias]

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

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

[John Gleason]

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.

#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

[Joseph Cote]

This may help the discussion

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

[Paul Dixon]

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.

[Tom Hanlin]

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.

[Volker Vanoni]

Re:Problem 100

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

[Michael Mattias]

I don't know why you didn't just post the code instead of an attachment, it is not that long:

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

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

[Volker Vanoni]

Problem 100

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

[Michael Mattias]

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

FOR a = &B1000000000000 TO &B1000000100000

MCM

[Mel Bishop]

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.

[Volker Vanoni]

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