Al Zimmermann's: Statue of Liberty

[jcmeyrignac]

I believe that any large power is decomposable into the sum of smaller distinct powers.
So you can take any large number and focus on it.
With some luck, you might be able to get zero

Please note that Herbert's method doesn't work on prime powers.

dimkadimon в сообщении #1457579 писал(а):

Herbert thank you for your informative post. It is very useful and I have learned a lot from it. It has given me some new hope.

220 is only the lowest solution found. But perhaps there are other values that are easier to find with these methods? At this stage I would be happy with ANY solution, no matter how large.

[Herbert Kociemba]

jcmeyrignac в сообщении #1457674 писал(а):

Please note that Herbert's method doesn't work on prime powers.

Unless I do not find a solution for n=16 I do not think about n>16, so eventually never...
I also believe that for any n there is a smallest $s_0$ such that for any s>$s_0$ you can decompose $s^n$ in smaller distinct powers. The number of possible sums you can build with s distinct powers grows exponential while the number range in which these sums lie only grows polynomial.

[Archimedes]

Herbert, thank you so much! Your explanation clarified everything.

I suppose the solution for n=16 lies in much distant numbers than for next n (=17).
For example, it is true for n=4 and n=8 - powers of 2:
15^4=>{4,6,8,9,14}
12^5=>{4,5,6,7,9,11}

84^8=>{1,2,3,5,7,9,10,11,12,13,14,15,16,17,18,19,21,23,24,25,26,27,29,32,33,35,37,38,39,41,42,43,45,46,47,48,49,51,52,53,69,73}
47^9=>{1,2,4,7,11,14,15,18,26,27,30,31,32,33,36,38,39,43}

[dimkadimon]

I've managed to improve the trivial solution for ^18. I wonder what is the highest power that you all managed to improve?

[Herbert Kociemba]

dimkadimon в сообщении #1458126 писал(а):

I wonder what is the highest power that you all managed to improve?

16, 17 18 for me. But I do not try to get approximate solutions since a couple of weeks and only try to find a way to an exact solution for 16. Meanwhile Tomas Rokicki has improved the 220^16 solution to 198^16 and I am quite sure this is not the end of the road.

[Archimedes]

dimkadimon в сообщении #1458126 писал(а):

I wonder what is the highest power that you all managed to improve?

С 16 по 20. Искал ещё и 21, но пока тривиальное решение - минимум.

[jcmeyrignac]

dimkadimon в сообщении #1458126 писал(а):

I've managed to improve the trivial solution for ^18. I wonder what is the highest power that you all managed to improve?

N=21, but not submitted yet.

[Jarek]

Herbert Kociemba в сообщении #1457654 писал(а):

Yes, there must be a method which gets easier for large s. Jarek takes s=1.513.151.757 for n=31. I wonder how many parts the sum has. Thousends? Millions? A billion?

Between 10.000 and 11.000. You don't expect anyone submitting billion terms, do you?

BTW, the s value above is not accurate. You can suspect that large numbers given at Best Raw Scores page are not accurate, when you see odd value of |E| for n=33.

[Herbert Kociemba]

Jarek в сообщении #1460546 писал(а):

You don't expect anyone submitting billion terms, do you?

I also did not expect that anyone wants to submit solutions with s larger than a 32 bit signed integer.

For prime exponents p there is an interesting connection with the the denominator DB of the Bernoulli number B(p-1), see http://oeis.org/A166062. We have

n^p = n mod DB(p-1) for all n>0.

From this we can conclude for example, that the for the sum K of the bases of the p-powers which sum up to s^p we have

s^p = K mod DB(p-1)

For the smallest solution for p = 13 (see https://oeis.org/A030052/a030052.txt)

102^13 = Total[{1, 3, 7, 9, 11, 13, 14, 15, 16, 18, 21, 23, 24, 26, 27, 30, 31,32, 33, 34, 36, 41, 42, 43, 44, 45, 46, 47, 48, 51, 52, 53, 55, 56, 57, 59, 60, 64, 66, 67, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 82, 83, 86, 88, 89, 90}^13]

the bases of the right side sum up to 2832. Because the denominator of DB(13-1) = DB(12) is 2730 we must have

102^13 mod 2730 = 2832 mod 2730 = 102,

which indeed is true. Necessarily the sum of the bases must exceed DB(p-1) which also gives lower bounds for the smallest s which is possible. In the example with p =13 we know for example without further examination, that the smallest s is at least 75, since Sum[i, {i, 1, 73}]<2730. But since the sum of the 13.th powers of 1..74 is greater than 75^13, the bound for s could be further improved.

For p = 541 we have DB(541-1)=115471236091149548610 , which leads to quite a large minimum s in this case.

Btw. DB(p-1) is the product of all primes p', where p'-1 divides p-1. For p = 13 for example p-1=12 is divided by 2-1, 3-1, 5-1, 7-1 and 13-1. 2*3*5*7*13 = 2730.

[Jarek]

Herbert Kociemba в сообщении #1460556 писал(а):

Jarek в сообщении #1460546 писал(а):

You don't expect anyone submitting billion terms, do you?

I also did not expect that anyone wants to submit solutions with s larger than a 32 bit signed integer.

Well, what I had in mind was technical problem with submitting such a solution. While in principle submitting a 1000-digit integer should be easy, I am not sure how submitting a set of 1.000.000.000 numbers, each occupying 10 characters, would work. Would you just open a 10GB text file with the solution, copy the content to the buffor, and then paste the 10GB into "Submit An Entry" page?

[Herbert Kociemba]

It would be fun, but probably it indeed will not work.

[jcmeyrignac]

I've spent my 2 last weeks on improving my program for searching zeroes on N=16.
It's now able to explore 150^16 in 4 seconds on a slow computer (Intel Core 2 duo at 2Ghz).

Herbert Kociemba в сообщении #1457654 писал(а):

Also thanks to Jean-Charles for his tip. This also gives me some new idea where to go. Within a few hours I now can completely check s^16 up to 151^16 and no solution exists. But this still is not enough.

[dimkadimon]

Wow some really big changes in the scoring system. Does anyone know why Al did it? If I was Jarek, I would be quite upset.

[Herbert Kociemba]

Then look at Paulsen/Paulsen. They dropped from 2. to 224. But I understand Al. These big solutions (I downloaded the example for 459280922^25 with its 421318 parts) are not really in the spirit the competition was designed for. I do not want to be misunderstood - I do not belittle this kind of solution. I would be glad if I would be able to generate *any* solution with error 0.

[Archimedes]

Готовые решения нельзя сюда постить, но несколько интересных равенств, надеюсь, можно:
^16:{4,17,23,25,28,38,41,43,46,58,59,61,66,69,71,83,84,85,87,90,91,93,95,96}={9,12,16,22,27,31,33,39,45,49,50,63,65,68,73,77,79,81,82,88,92,97,99}

^16: 1+{8,9,13,14,15,17,19,22,25,26,34,38,43,46,49,50,60,63,64,65,66,67,69,74,82,94,103}={3,5,6,11,16,20,26,27,28,35,41,48,51,57,59,61,62,70,78,79,83,84,86,88,91,92,101}

^16: 2+{2,5,7,8,14,19,20,22,26,49,50,55,61,66,69,71,73,74,82,87,94,97}={6,9,11,13,16,17,18,30,31,34,41,42,43,44,52,54,57,58,59,68,70,76,81,83,84,85,88,90}

^16: 3+{9,13,14,17,21,22,23,27,28,29,30,34,35,37,42,48,49,50,54,58,64,68,71,79,94}={3,4,10,11,15,19,20,32,36,39,40,41,47,51,52,53,60,63,65,66,69,75,83,92,93,97,98}

^16: 4+{4,7,9,18,23,27,33,41,44,62,66,68,76,80,89,90,94}={14,19,21,28,29,32,37,38,48,51,52,56,63,65,73,75,79,82,88,96,98}

^16: 4+{4,8,12,21,22,25,31,36,41,50,53,59,61,62,66,70,71,72,79,86,91,98,100}={3,5,11,13,16,26,27,30,37,38,47,49,52,56,58,60,64,68,76,80,81,82,83,84,87,89,90,93}