Home > Sums and Products I > Description

Sums and Products I

The Concept

Given a set A of positive integers, let R(A) be the number of different results you can get by choosing 2 (not necessarily different) numbers from A and either adding or multiplying them. In other words, R(A) is the size of the set of pairwise sums and pairwise products from A.

Mathematically, R(A) = | {A+A} ∪ {A×A} |.

Here are two examples:

Example 1

Suppose that A is the set { 1, 2, 3, 4, 6, 8, 12 }. Its pairwise sums are:

1 + 1 = 2
1 + 2 = 3
1 + 3 = 4
1 + 4 = 5
1 + 6 = 7
1 + 8 = 9
1 + 12 = 13
2 + 2 = 4
2 + 3 = 5
2 + 4 = 6
2 + 6 = 8
2 + 8 = 10
2 + 12 = 14
3 + 3 = 6
3 + 4 = 7
3 + 6 = 9
3 + 8 = 11
3 + 12 = 15
4 + 4 = 8
4 + 6 = 10
4 + 8 = 12
4 + 12 = 16
6 + 6 = 12
6 + 8 = 14
6 + 12 = 18
8 + 8 = 16
8 + 12 = 20
12 + 12 = 24

which gives us the set { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 24 }. Similarly, the pairwise products of A are { 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 32, 36, 48, 64, 72, 96, 144 }. Merge these two sets together and you get { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 24, 32, 36, 48, 64, 72, 96, 144 }, which has 26 elements. Therefore, R(A) = 26.



Example 2

If A = { 3, 5, 8, 9 } then the sums and products are { 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 24, 25, 27, 40, 45, 64, 72, 81 } and R(A) = 20.




The Contest

For each of 25 different values of n, submit (see How to Enter, below) the set A of n positive integers with the smallest R(A) you can achieve. The values of n you must use are 40, 80, 120, …, 1000 (that is, the multiples of 40 from 40 through 1000). Note that, by definition of a set, the members of a set are distinct – so a set can't contain the same number twice.

You can submit more than one solution for each value of n, but if you do we count only your best solution. There is no penalty for submitting multiple solutions for the same problem.

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

The idea for this contest came from Richard K. Guy's book, Unsolved Problems in Number Theory.


The Prizes

First prize is a $500 electronic gift certificate redeemable at Bathsheba Sculpture. Second prize is a $100 gift certificate.


How to Enter

Just paste your sets into the large box on the Submit page and click the Submit Entry button. Format your sets as follows:

  • Each set is a comma-delimited list of integers.

  • Submit multiple sets (for different values of n) at the same time by separating them with semicolons. Do not put a semicolon after your last set.

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

For example, to submit the two examples above you might enter: 1,2,3,4,6,8,12; 3,5,8,9

Do not submit entries under more than one account. This is important. Do not submit entries under more than one account.


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 the set A you submitted with the smallest R(A). Your raw score for that n is R(A).

  • For each of the 25 values of n, we compute a subscore from 0 to 1 by dividing your raw score for that n into the smallest raw score of any entrant for that n.

  • 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 that we reduce the contest to only 3 values of n: 40, 80 and 120.

Further suppose that we have 3 entrants (Bob, Otto and Hannah) and that their raw scores are as follows:

40 numbers 80 numbers 120 numbers
Bob 462 1960 4100
Otto 490 1824 4180
Hannah 530 1890 4022

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

40 numbers 80 numbers 120 numbers
Smallest Raw Score 462 1824 4022

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

40 numbers 80 numbers 120 numbers Contest Score
Bob 462 / 462 = 1.000 1824 / 1960 = 0.931 4022 / 4100 = 0.981 2.912
Otto 462 / 490 = 0.943 1824 / 1824 = 1.000 4022 / 4180 = 0.962 2.905
Hannah 462 / 530 = 0.872 1824 / 1890 = 0.965 4022 / 4022 = 1.000 2.837

Bob has the highest contest score and therefore wins. However, because this was just an example, Bob does not win a $500 gift certificate. Instead, he wins a t-shirt saying PALINDROMES ARE RASEMORDNILAP .


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 here or by visiting the group on groups.io. 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.


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 I enter the contest more than once, using different accounts?

    No. Submitting solutions from more than one account is not permitted. In fact, just having more than one account is against the rules.

  • 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 break away and start submitting solutions on your own behalf. If you would like to form a team, please email me.

  • Can I write a program that bypasses my browser and submits solutions directly to AZsPCs?

    Yes and no. If your program keeps track of your submissions and only submits improved solutions, yes. Otherwise, no. For the Son of Darts contest a few years ago, there was one participant who wrote a program to exhaustively generate all possible solutions and submit every one of them. Within two weeks he'd submitted over a million entries and the AZsPCs database had grown to 10 times its normal size. Please compute responsibly.

  • How can I find out what my individual subscores are?

    You can't. I know this is frustrating, but it's a longstanding policy that isn't going to change. Over the years it's been hotly debated in the discussion group and the contest administrator appears to have very strong feelings on the matter. You're going to have to learn to live with it. And I'd think twice before raising the issue yet again.

  • 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
    • any calculation of the best raw scores

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