/*
Finding Powers using only additions?
Multiplication is repeated addition:
3*2 = 3+3 or 2+2+2
Powering is repeated multiplication:
3^3 = 3*3*3
= 3*(3+3+3)
= (3+3+3)+(3+3+3)+(3+3+3)
But here's something different. It came along while I wrote Cube Root code,
it went off topic, thus another topic, this one.
x x^4
0 0 1 14 36 24 0
1 1 15 50 60 24 0
2 16 65 110 84 24 0
3 81 175 194 108 24 0
4 256 369 302 132 24 0
Above each black number is the sum of the numbers above and right above it,
because: "see Cube Root".
_ _ _ _
| 0 1 14 36 24 | | A B C D E | F=A+B , G=B+C , ...
| 1 15 50 60 24 | | F G H I . |
| 16 65 110 84 24 | = | J K L . . |
| 81 175 194 108 24 | | M N . . . |
|_ 256 369 302 132 24 _| |_ P . . . . _|
Each row depends on the row above it, depends on the first (magic?) row.
The other way round: How to get the first row: " 0,1,14,36,24,0 ",
from the first colum (x^4): " 0,1,16,81,256 ".
C=G-B G=J-F C=1J-2F+1A
B=F-A
D=H-C H=K-G D=1K-2G+1B K=M-J D=M-J-2J+2F+F-A D=1M-3J+3F-1A
C=G-B G=J-F
B=F-A
E=I-D I=L-H E=1L-2H+1C L=N-K E=N-K-2K+2G+G-B E=N-3K+3G-B N=P-M E=P-M-3M+3J+3J-3F-F+A E=1P-4M+6J-4F+1A
D=H-C H=K-G K=M-J
C=G-B G=J-F
B=F-A
A= 1.0 A=1.0^4=0 A= +2A+1.0
B= 1F-1A B=1.1^4-1.0^4 B= 1F-2A+1A
C= 1J-2F+1A C=1.2^4-2.1^4+1.0^4 C=1J-2F+1A+1B-(1F-1A) C= 1J-3F+2A+1B
D= 1M-3J+3F-1A D=1.3^4-3.2^4+3.1^4-1.0^4 D=1M-3J+3F-1A+1C-(1J-2F+1A) D= 1M-4J+5F-2A+1C
E=1P-4M+6J-4F+1A E=1.4^4-4.3^4+6.2^4-4.1^4+1.0^4 E=1P-4M+6J-4F+1A+1D-(1M-3J+3F-1A) E=1P-5M+9J-7F+2A+1D
Pascal's Triangle
The first row is part of A131689 (~A019538): Triangle of numbers: T(n,k)=k!*Stirling2(n,k)
Next step: Use Pascal's triangle, use Binomial Coefficients ( C(.,.) ).
C(1,1).1^1 = 1 \
\
C(1,1).1^2 = 1 \
C(2,2).2^2 - C(2,1).1^2 = 2 \
\
C(1,1).1^3 = 1 \
C(2,2).2^3 - C(2,1).1^3 = 6 A019538
C(3,3).3^3 - C(3,2).2^3 + C(3,1).1^3 = 6 /
/
C(1,1).1^4 = 1 /
C(2,2).2^4 - C(2,1).1^4 = 14 /
C(3,3).3^4 - C(3,2).2^4 + C(3,1).1^4 = 36 /
C(4,4).4^4 - C(4,3).3^4 + C(4,2).2^4 - C(4,1).1^4 = 24 /
*/
using System;
class Power_Addition_Only
{
private static uint T(uint n, uint k) // OEIS: A019538 =============================>> // 1
{ // 1
return F(k) * S2(n, k); // 2
} // 1
private static uint S2(uint n, uint k) // Stirling numbers // 6
{ // 2nd kind // 6
if (n == k) return 1; // 1
if (n == 0 || k == 0) return 0; // 14
n--; // 36
return k * S2(n, k--) + S2(n, k); // 24
} // 1
private static uint F(uint k) // Factorial // 30
{ // 150
uint f = 1; // 240
while (k > 1) f *= k--; // 120
return f; // 1
} // 62
// 540
static void Main() // 1560
{ // 1800
Console.WriteLine(); // 720
powers(4, 4); // 1
powers(3, 1); // 126
powers(21, 6); // 1806
powers(15, 7); // 8400
powers(9, 9); // 16800
Console.ReadLine(); // 15120
} // 5040
private static void powers(uint x, uint p) // up to x^p // 1
{ // 254
Console.WindowWidth = 105; // 5796
Console.WindowHeight = Console.LargestWindowHeight - 10; // 40824
Console.WriteLine(" x^" + p); // 126000
Console.WriteLine(); // 191520
int i = 0, j; // 141120
uint[] v = Init(p); // 40320
int vL = v.Length - 1; // 1
for (j = 0; j <= vL; j++) Console.Write("{0,10}", v[j]); // 510
Console.WriteLine(); // 18150
for (; i < x; i++) // 186480
{ // 834120
for (j = 0; j < vL; ) v[j++] += v[j]; // 1905120
for (j = 0; j <= vL; j++) Console.Write("{0,10}", v[j]); // 2328480
Console.WriteLine(); // 1451520
} // 362880
Console.WriteLine(); // 1
Console.WriteLine(); // 1022
} // 55980
private static uint[] Init(uint i) // get Initial value's // 818520
{ // 5103000
uint[] v = new uint[i + 1]; // 16435440
v[0] = 0; // 29635200
for (uint j = 1; j <= i; j++) // 30240000
v[j] = T(i, j); // 16329600
return v; // 3628800
} // 1
}
No comments:
Post a Comment