PDA

View Full Version : An algorithm Dicknose might possibly like to turn into a formula

SportWagon
March 9th, 2015, 11:26 AM
Personal interest...

#!/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 (http://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence). So I think the formula is a derivative (informally speaking) of that.

Output...

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

Kchrpm
March 9th, 2015, 11:33 AM
I used to know what all that stuff meant...

SportWagon
March 9th, 2015, 01:27 PM
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.

SportWagon
March 9th, 2015, 02:03 PM
So, generating \$q each time and comparing to \$diff, also comparing totals \$pp and \$p.

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

SportWagon
March 9th, 2015, 02:29 PM
http://mathschallenge.net/library/number/sum_of_cubes

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

Dicknose
March 10th, 2015, 05:55 AM
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.

SportWagon
March 10th, 2015, 01:08 PM
Combining all sub-calculations of \$q into one function of \$i...

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

SportWagon
March 10th, 2015, 02:01 PM
Following seems to have done it.

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

SportWagon
March 11th, 2015, 12:06 PM
A slight simplification, shown in steps.
(Each recalculation of \$qsum2 overwrites the previous).

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