Results 1 to 9 of 9

Thread: An algorithm Dicknose might possibly like to turn into a formula

  1. #1
    Subaru Unimpreza SportWagon's Avatar
    Join Date
    Jan 2014
    Location
    The Real Grand Valley, Ontario, Canada
    Posts
    1,418

    An algorithm Dicknose might possibly like to turn into a formula

    Personal interest...

    Code:
    #!/usr/bin/perl -w
    
    $a = 1500;
    $b = 1000;
    $m = 400;
    
    $diff = $b;
    $p = $a;
    $ddiff = 1;
    for ($i = 1; $i <= 40; ++$i) {
    
            $ddiff += $i;
            $diff += $m*$ddiff;
    
            $p += $diff;
    
            printf("%4d%12d%12d%12d\n", $i, $p, $diff, $ddiff);
    
    }
    Can someone give a formula to give p as a function of i (and a,b, and m).

    I think the difference is incremented by the terms of the Lazy Caterer's Sequence. So I think the formula is a derivative (informally speaking) of that.

    Output...
    Code:
       1        3300        1800           2
       2        6700        3400           4
       3       12900        6200           7
       4       23500       10600          11
       5       40500       17000          16
       6       66300       25800          22
       7      103700       37400          29
       8      155900       52200          37
       9      226500       70600          46
      10      319500       93000          56
      11      439300      119800          67
      12      590700      151400          79
      13      778900      188200          92
      14     1009500      230600         106
      15     1288500      279000         121
      16     1622300      333800         137
      17     2017700      395400         154
      18     2481900      464200         172
      19     3022500      540600         191
      20     3647500      625000         211
      21     4365300      717800         232
      22     5184700      819400         254
      23     6114900      930200         277
      24     7165500     1050600         301
      25     8346500     1181000         326
      26     9668300     1321800         352
      27    11141700     1473400         379
      28    12777900     1636200         407
      29    14588500     1810600         436
      30    16585500     1997000         466
      31    18781300     2195800         497
      32    21188700     2407400         529
      33    23820900     2632200         562
      34    26691500     2870600         596
      35    29814500     3123000         631
      36    33204300     3389800         667
      37    36875700     3671400         704
      38    40843900     3968200         742
      39    45124500     4280600         781
      40    49733500     4609000         821

  2. #2
    Corvette Enthusiast Kchrpm's Avatar
    Join Date
    Jan 2014
    Location
    Cincinnati, OH
    Posts
    8,697
    I used to know what all that stuff meant...
    Get that weak shit off my track

  3. #3
    Subaru Unimpreza SportWagon's Avatar
    Join Date
    Jan 2014
    Location
    The Real Grand Valley, Ontario, Canada
    Posts
    1,418
    Each $diff is sum(1 to n) (caterer(i))

    I.e. sum(1 to n) (i^2 + i + 2)/2

    So $diff is ( sum(1 to n) i^2 + sum(1 to n) i + sum(1 to n) 2 ) / 2

    I.e.
    • (i * (i+1) * (2*i + 1)) / 6 -- sum i^2
    • + (i * (i+1)) / 2 -- sum i
    • + i*2 -- sum 2
    all divided by 2.

  4. #4
    Subaru Unimpreza SportWagon's Avatar
    Join Date
    Jan 2014
    Location
    The Real Grand Valley, Ontario, Canada
    Posts
    1,418
    So, generating $q each time and comparing to $diff, also comparing totals $pp and $p.
    Code:
    #!/usr/bin/perl -w
    
    $a = 1500;
    $b = 1000;
    $m = 400;
    
    $diff = $b;
    $p = $a;
    $pp = $a;
    $ddiff = 1;
    for ($i = 1; $i <= 40; ++$i) {
    
            $ddiff += $i;
            $diff += $m*$ddiff;
    
            $p += $diff;
    
    
            # $diff = sum(1 to n) (caterer(i))
            #  i.e. sum(1 to n) i^2 / 2 + sum(1 to n) i/2 + sum(1 to n ) 2
            # sum(1 to n) i^2 / 2 =  (n * (n + 1) * (2n + 1)) / 6 / 2
            # sum(1 to n) i / 2 = (n*(n+1))/2/2.
            # sum(1 to n) 2/2 = n.
    
            $q1 = ($i * ($i+1) * (2*$i + 1)) / 6;   # sum (n^2)
            $q2 = ($i * ($i+1)) / 2;                # sum (n)
    	# must  add before dividing by 2, to ensure even
            $q = (($q1 + $q2) / 2 ) + $i;           # /2 + sum 1
            $pp += $b + $q*$m;
    
            printf("%4d%12d%12d%12d%12d%12d\n", $i, $p, $diff, $ddiff, $b+$q*$m, $pp);
    
    }
    So now we need to take the sum of each component of the total sum to arrive at a formula for each iteration of the loop. I think it involves sum of cubes.

    All-in-all, the formula is probably more clearly expressed as an algorithm.
    Last edited by SportWagon; March 9th, 2015 at 02:21 PM.

  5. #5
    Subaru Unimpreza SportWagon's Avatar
    Join Date
    Jan 2014
    Location
    The Real Grand Valley, Ontario, Canada
    Posts
    1,418
    http://mathschallenge.net/library/number/sum_of_cubes
    Code:
    ∴ ∑ r3 	 =  	n2(n+1)2/4
      	 =  	(n(n+1)/2)2
    
    In other words, the sum of the first n cubes is the square of the sum of the first n natural numbers.
    I need to say something in order to be able to quote this.

    I think I'm close. I need to add my $q1 and $q2 above, and pull out the products and then sum the sums.
    Last edited by SportWagon; March 9th, 2015 at 02:32 PM.

  6. #6
    Senior Member
    Join Date
    Jan 2014
    Location
    Sydney, Australia
    Posts
    2,291
    Had a quick look and went
    Fixed amount
    Multiple of i
    Sum of sum of i, with the one offset at the start making it a bit tricky

    And while an iterative (or recursive) description is nest, it often is slower.
    From a programming point of view it depends if speed is critical or clarity of code.

  7. #7
    Subaru Unimpreza SportWagon's Avatar
    Join Date
    Jan 2014
    Location
    The Real Grand Valley, Ontario, Canada
    Posts
    1,418
    Combining all sub-calculations of $q into one function of $i...

    Code:
    #!/usr/bin/perl -w
    
    $a = 1500;
    $b = 1000;
    $m = 400;
    
    $diff = $b;
    $p = $a;
    $pp = $a;
    $ddiff = 1;
    for ($i = 1; $i <= 40; ++$i) {
    
            $ddiff += $i;
            $diff += $m*$ddiff;
    
            $p += $diff;
    
    
    	# $diff = sum(1 to n) (caterer(i))
    	#  i.e. sum(1 to n) i^2 / 2 + sum(1 to n) i/2 + sum(1 to n ) 2
    	# sum(1 to n) i^2 / 2 =  (n * (n + 1) * (2n + 1)) / 6 / 2
    	# sum(1 to n) i / 2 = (n*(n+1))/2/2.
    	# sum(1 to n) 2/2 = n.
    
            # $q1 = ($i * ($i+1) * (2*$i + 1)) / 6;   # sum (n^2)
            # $q2 = ($i * ($i+1)) / 2;                # sum (n)
            # $q = (($q1 + $q2) / 2 ) + $i;           # /2 + sum 1
    
    	$q = ( 2*$i*$i*$i + 6*$i*$i + 16*$i ) / 12;
            $pp += $b + $q*$m;
    
            printf("%4d%12d%12d%12d%12d%12d\n", $i, $p, $diff, $ddiff, $q*$m, $pp);
    
    }
    So now we have the increment expressed as the sum of a cube, a square, and order 0.

  8. #8
    Subaru Unimpreza SportWagon's Avatar
    Join Date
    Jan 2014
    Location
    The Real Grand Valley, Ontario, Canada
    Posts
    1,418
    Following seems to have done it.

    Code:
    #!/usr/bin/perl -w
    
    $a = 1500;
    $b = 1000;
    $m = 400;
    
    $diff = $b;
    $p = $a;
    $ddiff = 1;
    for ($i = 1; $i <= 40; ++$i) {
    
            $ddiff += $i;
            $diff += $m*$ddiff;
    
            $p += $diff;
    
            # $qsum = ( 2*(($i*$i*($i+1)*($i+1)/4) + ($i*($i+1)*(2*$i + 1)) + 8*($i*($i+1)) ) ) / 12;
            $qsum = ( (($i*$i*($i+1)*($i+1)/2) + ($i*($i+1)*(2*$i + 1)) + 8*($i*($i+1)) ) ) / 12;
            $qp = $a + $i*$b + ($qsum*$m);
            printf("%3d%10d%10d\n", $i, $p, $qp);
    
    }
    The $qp value calculated purely as a function of $i (and $a,$b and $m) matches the accumulated calculation of $p.

    So now there's two more components to the actual calculation I'm analyzing. One is simply the addition of $i*(-800).

    But the other increments an increment by 400 for even levels only, leaving that increment unchanged for intervening levels.

    Given the complexity of the above, there's no way expressing the overall calculation as a function of the level is going to be clear.

  9. #9
    Subaru Unimpreza SportWagon's Avatar
    Join Date
    Jan 2014
    Location
    The Real Grand Valley, Ontario, Canada
    Posts
    1,418
    A slight simplification, shown in steps.
    (Each recalculation of $qsum2 overwrites the previous).

    Code:
    #!/usr/bin/perl -w
    
    $a = 1500;
    $b = 1000;
    $m = 400;
    
    $diff = $b;
    $p = $a;
    $ddiff = 1;
    for ($i = 1; $i <= 40; ++$i) {
    
            $ddiff += $i;
            $diff += $m*$ddiff;
    
            $p += $diff;
    
    	# $qsum = ( 2*(($i*$i*($i+1)*($i+1)/4) + ($i*($i+1)*(2*$i + 1)) + 8*($i*($i+1)) ) ) / 12;
    	$qsum = ( (($i*$i*($i+1)*($i+1)/2) + ($i*($i+1)*(2*$i + 1)) + 8*($i*($i+1)) ) ) / 12;
    	$qsum2 = $i*($i+1)*(($i*($i+1)/2) + (2*$i + 9)  ) / 12;
    	$qsum2 = $i*($i+1)*(($i*$i/2 + $i/2) + (2*$i + 9)  ) / 12;
    	$qsum2 = $i*($i+1)*(($i*$i + 5*$i + 18)) / 24;
    	if ($qsum != $qsum2) { printf("%10d%10d\n", $qsum, $qsum2); };
    	$qp = $a + $i*$b + ($qsum*$m);
    	printf("%3d%10d%10d\n", $i, $p, $qp);
    
    }
    I don't seem to find matches for i2 + 5i + 18.

Posting Permissions

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