Help with power series refinement

[ktoz]

Hi

I stumbled across a power series pattern while working on a C algorithm and was wondering if this "discovery" has a name/reference anywhere.

Basically, Here's what I found:

for p = 1 the minimum number of terms, on the left side, satisfying the following is 1
a^p + b^p + c^p ... = m^p

for p = 2 the minimum number of terms, on the left side, satisfying the following is 2
a^p + b^p + c^p ... = m^p (pythagorean theorum)

for p = 3 the minimum number of terms, on the left side, satisfying the following is 3
a^p + b^p + c^p ... = m^p

for p = 4 the minimum number of terms, on the left side, satisfying the following is 5
a^p + b^p + c^p ... = m^p

for p = 5 the minimum number of terms, on the left side, satisfying the following is 6
a^p + b^p + c^p ... = m^p

I wasn't able to take it any farther than this as even on a 2.16 GHz core duo, my brute force method ran for almost a half hour without returning.

So the minimum terms form the sequence 1, 2, 3, 5, 6, ?, ?, ?. I tried looking it up on Sloan's encyclopedia of integer http://www.research.att.com/~njas/sequences/?q=1%2C+1%2C2%2C3%2C5%2C6&sort=0&fmt=0&language=english&go=Search" but the small number of terms gave multiple hits.

Is this pattern known? And if so, what is it called? Is there a generating function for it?

Thanks in advance.

Ken

 

[Werg22]

for p = 1 the minimum number of terms, on the left side, satisfying the following is 1
a^p + b^p + c^p ... = m^p

Well then, isn't 1 the minimum for all p? The case of n = 1 is kind of absurd to consider.

Anyway, Fermat's last theorem states that the Diophantine equation a^n + b^n = c^n, in which a and b are not 0, has no solution for n>2. Hence, your minimums do not contradict any number theorem that I'm aware of. As for being a new discovery, don't get your hopes up like that; I'm certain it's a known result.

 

[ktoz]

Well then, isn't 1 the minimum for all p? The case of n = 1 is kind of absurd to consider.

True. I only added a^1 = b^1 to turn it into a sequence for lookup at Sloan's

Anyway, Fermat's last theorem states that the Diophantine equation a^n + b^n = c^n, in which a and b are not 0, has no solution for n>2. Hence, your minimums do not contradict any number theorem that I'm aware of.

Some concrete examples:

for p = 3
1^3 + 6^3 + 8^3 = 9^3
14^3 + 28^3 + 34^3 = 40^3
etc...

for p = 4
1^4 + 2^4 + 12^4 + 24^4 + 44^4 = 45^4
8^4 + 12^4 + 16^4 + 18^4 + 28^4 = 30^4
etc...

for p = 5
4^5 + 5^5 + 6^5 + 7^5 + 9^5 + 11^5 = 12^5
15^5 + 16^5 + 17^5 + 22^5 + 24^5 + 28^5 = 32^5
etc...

The speculation here is that for any power p there exists one or more integral solutions to

a^p + b^p + c^p ... + x^p = m^p

where the minimum number of left hand terms = p + (v >= 0)

As for being a new discovery, don't get your hopes up like that; I'm certain it's a known result.

That's why I put "discovery" in quotes. It was a sort of "Hmmm, that's interesting" artifact of a C algorithm I'm working on.

I'm not a Fermat's last theorum chaser, it just occurred to me that if a generating function for the minimum term count for any given p could be found and proven to be a minimum, that proof would indirectly prove Fermat's last theorum. I have no idea whether a proof of these minimums would be simpler than Wiles's Fermat proof but it would be interesting if it was.

 

[ktoz]

Found one more term

For p = 6 minimum number of terms satisfying a^p + b^p + c^p ... + m^p = x^p is 14. But that's as far as I can take it as my brute force algorithm brought my computer to it's knees.

Checking with http://www.research.att.com/~njas/sequences/?q=1%2C1%2C2%2C3%2C5%2C6%2C14&sort=0&fmt=0&language=english&go=Search" seems to indicate that this is an unknown sequence.

 

[matt grime]

So, you're definging n(p) by: you can write some p'th power as n(p)>1 smaller p'th powers, and that n(p) is minimal with this property, for p>1. There is no need to artificially and confusingly define n(1)=1. The sequence 2,3,5,6,14 you write down is just as good as anything to put into sloan. However, since you've only verified these as bounds for very small numbers, I would refrain from asserting that they were the correct values of p(n).

I clicked your link to Sloan: you're searching for sequences that go 1,1,2,3,5,6,14, which isn't what you wrote above. Omitting the leading ones gives you 2 hits. But don't be confused by the 'law of small numbers'.

 

[ktoz]

After giving it more thought...

This seems to be a kind of partitioning problem ie

Given
x = element of positive integers

what is the width of the minimum partition of x^p, whose members equal (x - m)^p where m element of positive integers and 0 < m < x

Is this sort of thing solvable?

 

[uart]

Hi ktoz. I was just wondering exactly how larger numbers your program searches for and whether you are using a standard data type (eg xx bit integer) or if you are using extended precision routines.

 

[ktoz]

Hi ktoz. I was just wondering exactly how larger numbers your program searches for and whether you are using a standard data type (eg xx bit integer) or if you are using extended precision routines.

I'm using 64 bit unsigned integers to hold "a^p" and unsigned 32 bit ints to store "a." The program started out as a mere curiosity so no effort was made to make it efficient. Basically given a power, the number of terms and the maximum term, it recursively checks every value between 1 and max for every term, adds them all up and tests the pth root of the sum to see if it's an integer. As the number of terms goes up, the recursion really gets out of hand.

I gave the problem a little more thought and I think it could be made much more efficient by doing something similar to Newton's method. Not sure how exactly to go about that at the moment but will return to it when I get some free time.

Two things I've noticed is that for p = 2, 3, 4, 5, 6, the minimum partition, that is the partition of width w with the smallest sum, follows this pattern

a^p + b^p + c^p ... + m^p = (m + 1)^p

And (with the exception of p = 2) this smallest sum has a pth root that is a multiple of the number of terms. There are too few data points to state this definitively (law of small numbers etc) but that seems to be the pattern so far.

 

[Moo Of Doom]

For p = 4, why is the minimum value 5? Here are 3 fourth powers that sum to a fourth power...

95800⁴ + 217519⁴ + 414560⁴ = 422481⁴.

 

[ktoz]

For p = 4, why is the minimum value 5? Here are 3 fourth powers that sum to a fourth power...

95800⁴ + 217519⁴ + 414560⁴ = 422481⁴.

Hmmm. You may be right. If you used a computer, what size numbers were you using?

If this isn't a rounding error, looks like you blew my whole idea out of the water. Oh well. If this had been a real pattern, it might have proven interesting.

As a previous poster warned me: "Beware the law of small numbers."

Good catch. Thanks

 

[Moo Of Doom]

I didn't use a computer program to find those numbers. I knew there was such a triplet from reading about it some time ago, and I searched Google for "sum of fourth powers." The Wikipedia page on Fourth Powers provided the example.

Euler conjectured that it takes at least n smaller n-th powers to sum to an n-th power. This is a counterexample to this conjecture.

Unless the sequence goes 2, 3, 3, 3, 3, ..., I think finding the values of the sequence is going to be almost as hard as proving Fermat's last theorem. :/

 

[ktoz]

Euler conjectured that it takes at least n smaller n-th powers to sum to an n-th power. This is a counterexample to this conjecture.

I was wrong, but it looks like I was in good company :)

Unless the sequence goes 2, 3, 3, 3, 3, ..., I think finding the values of the sequence is going to be almost as hard as proving Fermat's last theorem. :/

Proving Fermat's is way above my pay grade. Thanks again, I was becoming very interested in this problem and would have wasted all kinds of time chasing it down.

 

[ktoz]

Another series pattern

In light of the last mistake, I almost hesitate to bring up another pattern I've noticed in these types of series but what the heck.

If you repeatedly subtract consecutive terms, you eventually end up with something similar to an arithmetic series where terms less than p are separated by numbers in Euler's triangle and whose terms greater than p equal p!. For example:

power: 2
----------------------------------------------------------------
1 1 0 0 0 0 Euler numbers
----------------------------------------------------------------
1 2 2 2 2 2 Constant for m > 1
----------------------------------------------------------------
1 3 5 7 9 11
1 4 9 16 25 36 power: 3
----------------------------------------------------------------
1 4 1 0 0 0 0 Euler numbers
----------------------------------------------------------------
1 5 6 6 6 6 6 Constant for m > 2
----------------------------------------------------------------
1 6 12 18 24 30 36
1 7 19 37 61 91 127
1 8 27 64 125 216 343 power: 4
----------------------------------------------------------------
1 11 11 1 0 0 0 0 Euler numbers
----------------------------------------------------------------
1 12 23 24 24 24 24 24 Constant for m > 3
----------------------------------------------------------------
1 13 36 60 84 108 132 156
1 14 50 110 194 302 434 590
1 15 65 175 369 671 1105 1695
1 16 81 256 625 1296 2401 4096power: 5
----------------------------------------------------------------
1 26 66 26 1 0 0 0 0 Euler numbers
----------------------------------------------------------------
1 27 93 119 120 120 120 120 120 Constant for m > 4
----------------------------------------------------------------
1 28 121 240 360 480 600 720 840
1 29 150 390 750 1230 1830 2550 3390
1 30 180 570 1320 2550 4380 6930 10320
1 31 211 781 2101 4651 9031 15961 26281
1 32 243 1024 3125 7776 16807 32768 59049
etc...

I'm sure this is nothing new but, if it's not another example of "the law of small numbers," did this discovery lead to any interesting mathematical ideas?