Home > Sums of Powers > Description

Sums of Powers

Ends: 18 Jul 2020 15:00
Now: 5 Jun 2020 15:56

AZsPCs | Power Sums | Description

Introduction

Given a positive integer n, we are interested in finding an integer s whose nth power can be expressed as the sum of the nth powers of two or more distinct positive integers smaller than s. For example, given n = 7, we could express 407 as

17 + 37 + 57 + 97 + 127 + 147 + 167 + 177 + 187 + 207 + 217 + 227 + 257 + 287 + 397.

In general, we can write this as

sn = a1n + a2n + a3n + ... + akn.

When we are unable to exactly express an nth power as the sum of two or more nth powers, we introduce an error term E:

sn = a1n + a2n + a3n + ... + akn + E.

Some examples are:

105 = 15 + 25 + 35 + 65 + 85 + 95 + 131,

145 = 35 + 55 + 65 + 75 + 105 + 115 + 125 - 10,

88661289752875283 = 87784054428622393 + 27361114688070403 + 33.


The Contest

For each value of n from 16 to 40, submit values for s and { a1, a2, ..., ak } that minimize the absolute value of E in the equation

sn = a1n + a2n + a3n + ... + akn + E.

For technical reasons, the value of s must not exceed 203117.

For each value of n you can submit more than one solution, but only your best solution will count.

See How to Enter, below, for instructions on how to submit solutions.

See The Scoring System, below, to learn how we determine the winner.


The Prizes

The participants who finish in first or second place will each receive their choice of either

  • a freestanding crystal award plaque engraved with the details of their accomplishment, or

  • their choice of any item from Bathsheba Sculpture worth
    • $500 or less (for the first place participant), or
    • $100 or less (for the second place participant).


How to Enter

Paste your solutions into the appropriate box on the Submit page and click Submit Entry.

The format for submitting solutions is best explained by example. If your solution is

154 = 144 + 94 + 84 + 64 + 34 + 175,

then submit

15^4=>{14,9,8,6,3}

The system will automatically calculate E (which, in this example, is 175).

To submit more than one solution at a time, separate them with semicolons. Do not put a semicolon after your last solution.

Include spaces and line breaks anywhere you like (except within a number or within the arrow) to improve readability.

Over the course of the contest you may submit more than one solution for the same value of n, but you should not submit a solution unless it improves upon your previously submitted solutions. Note that your best scores can be found on the My Account page.


The Scoring System

The entrant with the highest "contest score" wins. Here's how we calculate your contest score:

  • For each of the 25 values of n, we find your best solution – that is, the solution with the smallest | E | – and we calculate its "raw score", as follows.

    Let the best solution be sn = a1n + a2n + ... + akn + E.   If E = 0, its "raw score" is 1 - 1/s.   And if E ≠ 0, its raw score is ln( | E | + 1 ) + 1.

  • For each of the 25 values of n, we compute a "subscore" from 0 to 1. We do this by dividing that n's raw score into the lowest raw score for that n across all entrants.

  • Your contest score is the sum of your 25 subscores.

If two entrants have the same contest score, we break the tie by giving preference to the entrant whose last improvement was submitted least recently.

Let's walk through a simplified example. Suppose we modify the contest by asking you to submit solutions for only three values of n: 4, 5 and 6. And further suppose that we have 3 entrants (April, May and June) and that their best solutions have raw scores as follows:

4 5 6
April 8 142 2093
May 91 70 1092
June 41 295 552

We note the smallest raw score for each value of n:

4 5 6
Smallest Raw Score 8 70 552

Finally, we compute the subscores and contest score for each entrant:

4 5 6 Contest Score
April 8 / 8 = 1.000 70 / 142 = 0.493 552 / 2093 = 0.264 1.757
May 8 / 91 = 0.088 70 / 70 = 1.000 552 / 1029 = 0.536 1.624
June 8 / 41 = 0.195 70 / 295 = 0.237 552 / 552 = 1.000 1.432

April has the highest contest score and therefore wins.


Getting Your Questions Answered

First, check the FAQ section below. If you can't find the information you need there, send your question to the discussion group. If your question is of a personal nature, and not of general interest, send an email directly to Al Zimmermann.


The Discussion Group

If you think you might enter the contest, you should join the contest discussion group. You can join either by sending a blank email to AZsPCs+subscribe@groups.io or by visiting the AZsPCs group at http://groups.io/g/AZsPCs. The discussion group serves two purposes. First, it allows contestants to ask for clarifications to the rules. Be aware that sometimes these requests result in changes to the rules, and the first place those changes are announced is in the discussion group. Second, the discussion group allows contestants to interact with each other regarding programming techniques, results and anything else relevant to the contest.

Once you've joined, you can post messages by emailing your messages to AZsPCs@groups.io.

You can leave the group at any time by sending a blank email to AZsPCs+unsubscribe@groups.io.


My Lawyer Would Want Me To Say This

I reserve the right to discontinue the contest at any time. I reserve the right to disqualify any entry or entrant for any reason that suits me. I reserve the right to interpret the rules as I see fit. I reserve the right to change the contest rules in mid-contest. In all matters contest-related, my word is final.


Frequently Asked Questions

  • Can teams enter the contest?

    Yes. But a team can only be formed by those who have not already entered the contest as individuals. Once you enter as an individual, team membership is no longer open to you. Likewise, once you've joined a team you can't resign from it and start submitting solutions on your own behalf.

    If you would like to form a team, please follow these instructions:

    • If they do not already exist, create individual accounts for each team member. Do not create a second account for any team member who already has one.

    • Let me know each team member's name and registered email address. It is important that no team member submit any entries to this contest until I notify you that the team has been created.

    After I've created the team, team members can submit entries to the contest from their individual accounts. The contest engine automatically intercepts these entries and diverts them to the team account. The team is listed on the standings page.

    Note: Teams are contest-specific. Joining a team for this contest does not affect your participation in other contests.

  • May I write a program that submits entries by bypassing my browser?

    Yes. But keep in mind the prohibition against submitting solutions that do not improve over your previously submitted solutions.

  • What topics are appropriate for the discussion group?

    With only one exception, if it's related to AZsPCs then it's fine to talk about it in the discussion group. The exception is spoilers. Spoilers include:

    • specific solutions
    • detailed algorithms

    If you are not sure if something would be considered a spoiler, ask me.

  • After I submit a solution, the scorer shows me the solution's "canonical representation". What is that?

    A canonical representation is a standardized way of displaying your solution. All "equivalent" solutions have the same canonical representation and all "non-equivalent" solutions have different canonical representations. For example, the canonical solution for both

    15^4 => { 8, 14, 4, 9, 6 }

    and

    15^4 => {14, 9, 8, 4, 6 }

    is

    15^4 => { 4, 6, 8, 9, 14 }.

    Canonical representations make it easier to tell when two solutions are equivalent.