HP Forums - "Counting in their heads"

There's a mental arithmetic challenge in this painting - see below for a plain rendering.
$[Image: Math+puzzle+painting.jpg]$

The challenge is - and I have run this through my own brain, and it's not unfair:
$[Image: math+puzzle+itself.jpg]$

Which is to say, calculate (10²+11²+12²+13²+14²)/365

It's hardly worth noting that this is very easy with a calculator.

(via TYWKIWDBI)

That's quite fun, in fact, because as you're partway through it, you realise that 10^2+11^2+12^2=365 and also that 13^2+14^2=365

So I make the answer 2 Smile

(08-08-2020 05:29 PM)EdS2 Wrote: [ -> ]calculate (10²+11²+12²+13²+14²)/365

With only 5 terms, it is trivial to calculate.
(x-y)² + (x+y)² = 2(x²+y²)

12² + (11²+13²) + (10²+14²) = 5*12² + 2*(1+4) = 730

730/365 = 2

---

Here is a way to fit it to polynomial, then "integrate" (see Funny Factorial and Slick Sums)
We know f(x) is quadratic, thus only 3 points needed.

Code:

x    f(x)   Δ     Δ² 

0    10²

1    11²    21

2    12²    23    2

$f(x) = 100 + 21\binom{x}{1} + 2\binom{x}{2}$

$F(x) = \sum_{t=0}^{x-1} f(t) = 100\binom{x}{1} + 21\binom{x}{2} + 2\binom{x}{3}$

F(5)/365 = (100*5 + 21*10 + 2*10) / 365 = 730/365 = 2

Indeed, grsbanks, I too had a sense of impending relief as I summed the last two terms first (for no special reason.)

But Albert, you have been much more mathematical! Thanks for the link to your thread, which in turn links to some older threads. Some good material in there.

I'm tempted to say that if I were the same distance from 16 as I am presently from 60 I might have been able to see deeper into this challenge. It seems my head is now filled with pink blancmange.

(08-08-2020 07:42 PM)Albert Chan Wrote: [ -> ]$F(x) = \sum_{t=0}^{x-1} f(t) = 100\binom{x}{1} + 21\binom{x}{2} + 2\binom{x}{3}$

F(5)/365 = (100*5 + 21*10 + 2*10) / 365 = 730/365 = 2

Another way to get F(x), via Triangular numbers

$\sum_{x=1}^n \binom{x+0}{1} = \binom{n+1}{2} $ // triangular numbers
$\sum_{x=1}^n \binom{x+1}{2} = \binom{n+2}{3} $ // sum of triangular numbers

10² + 11² + 12² + 13² + 14²
= 10² + (10²+21) + (10²+21+23) + (10²+21+23+25) + (10²+21+23+25+27)
= 100*5 + 21*4 + 23*3 + 25*2 + 27*1
= 100*5 + 21*(4+3+2+1) + 2*(1+1+1+2+2+3)
= 100*5 + 21*(1+2+3+4) + 2*(1+(1+2)+(1+2+3))

= $100\binom{5}{1} + 21\binom{5}{2} + 2\binom{5}{3}$

This matched the quoted F(x) equation, thus gives the same answer

An elegant way to get sum of squares formula is with geometry.
[Image: 93d0fee733e2156bbedcb4a2854d1483.png]

sum-of-n-squares = 1/3 * (2*n+1) * n*(n+1)/2 = n*(n+1)*(2*n+1)/6

Falling factorial derivation is also simple:

s(x) = x² = x + x*(x-1) = x¹ + x²
S(x) = Σ(s(t), t=0 .. x-1) = x²/2 + x³/3
= x*(x-1)*(1/2 + (x-2)/3)
= x*(x-1)*(2*x-1)/6 // note: sum-of-n-squares = S(n+1)

10²+11²+12²+13²+14²
= S(15) - S(10)
= 15*14*(30-1)/6 - 10*9*(20-1)/6
= 35*(30-1) - 15*(20-1)
= (1050-300) - (35-15)
= 730

Alternatively, you can use this formula:

n[c + (n² - 1)/12]

where n is the number of elements in the sequence and c is the central element.

5[12² + (5² - 1)/12] = 5[144 + 2] = 730

This should work also for sequences with even number of elements. For instance,

5² + 6² + 7² + 8² = 4[6.5² + (4² - 1)/12] = 174

A bit more difficult to do it in one’s head, though.

$
\frac{{55}^{2}+{65}^{2}+{75}^{2}+{85}^{2}+{95}^{2}+{105}^{2}+{115}^{2}+{125}^{2}+{135}^{2}+{145}^{2}}{10825}$

Also easily done, when you know the right formula :-)

(08-10-2020 11:50 AM)Gerson W. Barbosa Wrote: [ -> ]$
\frac{{55}^{2}+{65}^{2}+{75}^{2}+{85}^{2}+{95}^{2}+{105}^{2}+{115}^{2}+{125}^{2}+{135}^{2}+{145}^{2}}{10825}$

Also easily done, when you know the right formula :-)

$s(x) = (a+bx)^2 = a^2 + 2abx + b^2x^2 = a² + b(2a+b)\binom{x}{1} + 2b^2\binom{x}{2}$

→ Σ(s(x), x=0..n-1) = [a², b(2a+b), 2b²] • [nC1, nC2, nC3]

With a=55, b=10, n=10

S = [a², b(2a+b), 2b²] • [nC1, nC2, nC3]
= [3025, 1200, 200] • [10, 45, 120]
= 30250 + 54000 + 24000
= 108250

→ S / 10825 = 10

---

We can also use central element, c = a + b(n-1)/2

→ S = c²n + b²(n+1)(n)(n-1)/12

With c = (55+145)/2 = 100, b=10, n=10:

S = 100²*10 + 10²*11*10*9/12 = 100000 + 8250 = 108250

Or, simply force b=1

(55² + 65² + ... + 145²) / 10825
= (5.5² + 6.5² + ... + 14.5²) / 108.25 // c=n=10
= (1000 + 11*10*9/12) / 108.25
= 10

(08-09-2020 08:11 PM)Gerson W. Barbosa Wrote: [ -> ]This should work also for sequences with even number of elements. For instance,

5² + 6² + 7² + 8² = 4[6.5² + (4² - 1)/12] = 174

A bit more difficult to do it in one’s head, though.

"Central element" can be any number, even irrationals.

$s(x) = (x+a)^2 = a^2 + 2ax + x^2 = a^2 + (2a+1)\binom{x}{1} + 2\binom{x}{2}$

For sum of n consecutive squares, starting from a^2:

XCas> S(a,n) := [a^2, 2*a+1, 2] * [n, n*(n-1)/2, n*(n-1)*(n-2)/6]
XCas> expand(S(a,n)) → n^3/3+a*n^2+a^2*n-n^2/2-a*n+n/6

S(a,n) = S(0,a+n-0) - S(0,a). What happens if we replace 0 by c ?

XCas> expand(S(c,a+n-c) - S(c,a-c)) → n^3/3+a*n^2+a^2*n-n^2/2-a*n+n/6

c got *eliminated*, giving same expression as S(a,n) Smile

For exact center, c = a+(n-1)/2, we got a nice compact formula

XCas> simplify(S(c-(n-1)/2, n)) → (12*c^2*n+n^3-n)/12

---

Since we can pick any c, lets try summing T = 88² + 89² + ... + 115², with c=100

[c^2, 2*c+1, 2] = [10000, 201, 2]

$[\binom{16}{1}, \binom{16}{2}, \binom{16}{3}] - [\binom{-12}{1}, \binom{-12}{2}, \binom{-12}{3}]$ = [16,120,560] - [-12,78,-364] = [28,42,924]

T = [10000, 201, 2] • [28,42,924] = 280000 + 8442 + 1848 = 290290

Confirm above with exact center: c = (88+115)/2 = 203/2, n = 115-88+1 = 28

T = c²n + (n+1)(n)(n-1)/12
= (203/2)²*28 + 29*28*27/12
= 203²*7 + 29*7*9
= (41209 + 261)*7
= 290290

(08-10-2020 03:06 PM)Albert Chan Wrote: [ -> ]XCas> expand(S(c,a+n-c) - S(c,a-c)) → n^3/3+a*n^2+a^2*n-n^2/2-a*n+n/6

c got *eliminated*, giving same expression as S(a,n)

We never assume variables as integer. Formula work even if they are not. Big Grin

sum-of-n-squares = n*(n+1)*(2*n+1)/6 = $\binom{2(n+1)}{3}/4$ // 1/4 of tetrahedral numbers, side 2n

Formula is meaningless for non-integer, but the difference still gives S(a,n).

XCas> expand(simplify(comb(2*(a+n),3)/4 - comb(2*a,3)/4)) → n^3/3+a*n^2+a^2*n-n^2/2-a*n+n/6

(55² + 65² + ... + 145²) / 10825
= (5.5² + 6.5² + ... + 14.5²) / 108.25
= $ \Large {\binom{31}{3} - \binom{11}{3} \over 4×108.25}\\ $
= (4495 - 165 ) / 433
= 10

It looks like we can proceed to the next level:

$
\frac{{10}^{3}+{11}^{3}+{12}^{3}+{13}^{3}+{14}^{3}}{450}
$

I have to admit, I admired this wonderful piece of art more than diving into the mathematical task.

It reminds me very much of my old school days. Some of us strongly trying to have the first answer. Some staring at the board to find a smart solution (or pretending to do so). The desperated one. And always the same guys sucking up to the teacher. Ahh, the teacher! He seems to be ostentatiously relaxed, waiting patiently to grant every child a chance of success.

Did you notice the tonal scale beside the board. It is smaller but seems equally important. A balance of logic and arts.

Ok, but this is a calculator forum.

It is a calculator forum, but there's an intersection: the prodigal calculator. This is W. W. Rouse Ball writing about George Parker Bidder:

Quote:Halfpence rewarded his efforts, and by the time he was eight years old, he could multiply together two numbers each of six digits. In one case he even multiplied together two numbers each of twelve digits, but, he says, "it required much time," and "was a great and distressing effort."

(08-11-2020 12:33 AM)Gerson W. Barbosa Wrote: [ -> ]It looks like we can proceed to the next level:

$
\frac{{10}^{3}+{11}^{3}+{12}^{3}+{13}^{3}+{14}^{3}}{450}
$

Sum of cubes = squared triangular number = $\binom{n+1}{2}^2$

S = (10³+11³+12³+13³+14³) = $\binom{15}{2}^2 - \binom{10}{2}^2$ = (105-45)*(105+45) = 60*150 = 9000

→ S/450 = 20

---

We can rewrite formula in terms of central element, c = a + (n-1)/2

(x+y)³ + (x-y)³ = (x³+3x²y+3xy²+y³) + (x³-3x²y+3xy²-y³) = 2x³+6xy²

sum-of-n-cubes $= c^3 n + 6c×(1^2 + 2^2 + \cdots + ({n-1\over2})^2)
= c^3 n + 6c × \binom{n+1}{3}/4 $

→ sum-of-n-cubes = cn*(c² + (n²-1)/4)

S = 12*5*(12² + (4*6)/4) = 60*150 = 9000

(08-11-2020 10:39 AM)Albert Chan Wrote: [ -> ]→ sum-of-n-cubes = cn*(c² + (n²-1)/4)

S = 12*5*(12² + (4*6)/4) = 60*150 = 9000

That’s equivalent to what I’ve come up with, except that I have introduced a factor to generalize for evenly spaced sequences:

sum-of-n-cubes = nc(c² + d²(n² - 1)/4)

where

n = number of elements in the evenly spaced sequence
c = central element
d = interval distance

For example,

S = 33³ + 40³ + 47³ + 54³ + 61³ + 68³

n = 6
c = (33 + 68)/2 = 50.5
d = (68 - 33)/(n - 1) = 7

S = 6×50.5(50.5² + 7²(6² - 1)/4) = 902637

Likewise,

sum-of-n-squares = n(c² + d²(n² - 1)/12)

Considering the similarities between both formulae, perhaps they somehow can be generalized for all positive integer powers.

(08-11-2020 10:39 AM)Albert Chan Wrote: [ -> ]Sum of cubes = squared triangular number = $\binom{n+1}{2}^2$

Proof:

f(x) = x³ = (x³-x) + x = (x+1)³ + x¹
F(x) = (x+1)⁴/4 + x²/2 = $\binom{x}{2} × {(x+1)(x-2) + 2 \over 2} = \binom{x}{2}^2$

sum-of-n-cubes = F(n+1) = $\binom{n+1}{2}^2$

(08-11-2020 10:39 AM)Albert Chan Wrote: [ -> ]sum-of-n-cubes $= c^3 n + 6c×(1^2 + 2^2 + \cdots + ({n-1\over2})^2)
= c^3 n + 6c × \binom{n+1}{3}/4 $

→ sum-of-n-cubes = cn*(c² + (n²-1)/4)

Although above formula assumed (n-1)/2 is integer, this is not necessary.

XCas> S(a,n) := simplify(sum((a+x)^3, x=0..n-1))
XCas> factor(S(c-(n-1)/2,n)) → n*c*(4*c^2+n^2-1)/4

Again, any "central element" work, with differences back to S(a,n)

XCas> simplify(S(c,a+n-c) - S(c,a-c) - S(a,n)) → 0

Redo previous example, using simple sum-of-n-cubes formula (c=1)

S = 33³ + 40³ + 47³ + 54³ + 61³ + 68³
= 7³ * ((33/7)³ + (33/7+1)³ + ... + (68/7)³)
= $7^3 \left(\binom{75/7}{2}^2 - \binom{33/7}{2}^2) \right)$
= $\Large{(75×68)^2 - (33×26)^2 \over 7×4}$
= 902637

(08-11-2020 12:43 PM)Gerson W. Barbosa Wrote: [ -> ]sum-of-n-squares = n(c² + d²(n² - 1)/12)
sum-of-n-cubes = nc(c² + d²(n² - 1)/4)

Considering the similarities between both formulae, perhaps they somehow can be generalized
for all positive integer powers.

Perhaps this explain the similarity, for S_p = a^p + (a+1)^p + ... + b^p, b = a+n-1
With center c = (a+b)/2, g = (n-1)/2 = b-c = c-a, we have

S(a,n) = S(c,b-c+1) - S(c,a-c)
= S(c,g+1) - S(c,-g)
= Finite-Difference-Diagonals • $\left(
[\binom{g+1}{1},\binom{g+1}{2},\cdots] - [\binom{-g}{1},\binom{-g}{2},\cdots] \right)$

Let's see what the combinatorial coefficients look like:

XCas> g := (n-1)/2
XCas> coef := makelist(r -> simplify(comb(g+1,r) - comb(-g,r)),1,6)

→ $\Large [n,\,0,\,\frac{(n^{3}-n)}{24},\,\frac{(-n^{3}+n)}{24},\,\frac{(n^{5}+70\cdot n^{3}-71\cdot n)}{1920},\,\frac{(-n^{5}-30\cdot n^{3}+31\cdot n)}{960}]$

coef(1) = n, which make first term of S_p = c^p*n
coef(2) = 0, which make the central element based formula compact (Δf * 0 = 0)
coef(3) = -coef(4), which meant dot-products have this common factor.

Finite Difference table for (c+x)² and (c+x)³ // note: [1,0,0] ≡ c², [1,2,1] ≡ c²+2c+1

Code:

x (c+x)^2

0 [1,0,0]     

1 [1,2,1]     [2,1]

2 [1,4,4]     [2,3]       [2]

x (c+x)^3

0 [1,0,0,0]

1 [1,3,3,1]   [3,3,1]

2 [1,6,12,8]  [3,9,7]     [6,6]

3 [1,9,27,27] [3,15,19]   [6,12]      [6]

If we let k = coef(3) = (n³-n)/24:

sum-of-n-squares = c^2*n + 2k
sum-of-n-cubes = c^3*n + (6c+6)*k + 6*(-k) = c*(c^2*n + 6k)

coef(4) and coef(5) are not close, which meant similarity ends after cubes

XCas> sumpow(p) := expand(simplify(sum(x^p, x=c-g .. c+g)))
XCas> for(p=1; p<6; p++) {print(p, sumpow(p))}

1, c*n
2, (n^3)/12+c^2*n-n/12
3, (c*n^3)/4+c^3*n-(c*n)/4
4, (n^5)/80+(c^2*n^3)/2+c^4*n-(n^3)/24-(c^2*n)/2+(7*n)/240
5, (c*n^5)/16+(5*c^3*n^3)/6+c^5*n-(5*c*n^3)/24-(5*c^3*n)/6+(7*c*n)/48

(08-11-2020 09:37 AM)EdS2 Wrote: [ -> ]It is a calculator forum, but there's an intersection: the prodigal calculator.

IMHO, this does belong in the General Forum:

Quote:General Forum
Including all HP calculators except the HP Prime. Also HP news, general math and science etc. (Essentially this is the original HP forum.)

Thank you very much for posting!

Gerson.

I was wrong. There seems to be a pattern to sum of powers formula after all ...

$ S_p = n c^p + \large {n^3-n \over 12} \left(
\binom{p}{2} c^{p-2} +
{3n^2-7 \over 20} \binom{p}{4} c^{p-4} +
{3n^4-18n^2+31 \over 112} \binom{p}{6} c^{p-6} +
{5n^6-55n^4+239n^2-381 \over 960} \binom{p}{8} c^{p-8} +
\cdots \right) $

Example:

50^5 + 51^5 + 52^5 + ... + 150^5 // p=5, c=100, n=101

= 101*100^5 + 102*101*100/12 * (10*100^3 + (3*101^2-7)/20*5*100)
= 1934166665000