17
$\begingroup$

There is a deck of 52 playing cards (e.g. poker cards). Assign every card a unique number (ID) at will. Every combination of 5 of these cards (a "hand") shall be represented by a unique result number, calculated from the 5 card IDs. Permutations of the same 5 cards must yield the same result.

E.g.

  • You could enumerate all cards 1..52 and simply add the values. However, if you got 150 as result you could not differentiate between 10+20+30+40+50 or 11+19+30+40+50, so this is not a solution.
  • You could just write down the IDs as they occur, but 1020304050 would be different from 5040302010, so this is also not a solution.

Constraints:

  • No sorting allowed. Whatever your formula is, the 5 card IDs must be able to go in any order.
  • The ID number assigned to any card must always be a positive integer not to exceed 3 digits.
  • The unique result number must always be a positive integer not to exceed 12 digits.
  • Calculating the result from the 5 given card ID numbers must rely only on (one, some or all of) the 4 basic operations +-*/

Questions:

What numbers will you assign?
How do you calculate the result?
Show that the biggest possible result has no more than 12 digits.

$\endgroup$
17
$\begingroup$

If we take the IDs to be

the first 52 primes

and the result to be

the product of the IDs of the cards in the hand

then you can find the card IDs by

factoring the number

and the number will be at most

223.227.229.233.239 = 645535342583.

We can actually do better than this while using the same basic idea:

suppose that in addition to primes $p$ we use some of $p^2$, $p^4$, $p^8$, etc.; then we can still determine the IDs from their product. Taking the 52 smallest numbers of the form $p^{2^k}$ yields a set whose largest element is the prime 193 and whose largest 5 elements have product 206618110301.

A little better:

as Jonathan Allen remarks in comments, we can (relying on the fact that there are always exactly five cards in the hand) replace our largest number with 1; the largest is then 191 and the product of the five largest is 180924666533.

The crude information-theoretic lower bound for the maximum hand ID is

$\binom{52}{5}=2598960$

so there is quite a lot of scope for improvement here.

$\endgroup$
  • 1
    $\begingroup$ Right. I am at work and was called away while writing the answer, which is why I didn't say that explicitly :-). I will edit it in. $\endgroup$ – Gareth McCaughan Oct 20 '16 at 12:41
  • 1
    $\begingroup$ One could actually use 1 and the first 51 (not that it saves digits) $\endgroup$ – Jonathan Allan Oct 20 '16 at 12:43
  • 1
    $\begingroup$ @ZsoltSzigaly, acceptance of this answer seems premature; what will you do if someone proposes a simple but entirely different scheme that does it with a maximum hand ID that's only 8 digits long? $\endgroup$ – Gareth McCaughan Oct 20 '16 at 12:56
  • 1
    $\begingroup$ @ZsoltSzilagy but you only have one card numbered 1. $\endgroup$ – Jonathan Allan Oct 20 '16 at 12:58
  • 2
    $\begingroup$ A minor improvement: with both optimisations ($p^{2^k}$ and a single card with ID $1$), the smallest result will be for the hands containing the ids $\{1,2,3,4,5\}$, and will be $120$. You can therefore subtract $120$ from all results, with $0$ being the new smallest result, and $180924666413$ the new largest result. $\endgroup$ – Georges Dupéron Oct 20 '16 at 15:06
3
$\begingroup$

This is my second attempt at a solution. It is vastly different from my first attempt, so I posted this as a separate answer. It achieves the smallest maximum result for a hand possible (with a hand whose result is $0$):

$\binom{52}{5} - 1 = 2598959$

Many thanks to @2012rcampion for some improvements to this solution (see the comments).

The given operators ($+$, $-$, $\times$, $/$) can be used to build a minimal program operating on a bounded number of allowed values. Since the problem is bounded, let's try it out! I'll define a series of functions for clarity. Each function does not use functions defined later, and does not call itself recursively, therefore the functions can be inlined trivially to form a single, huge function.

We will number the cards from $0$ to $51$.

The puzzle specifies that only the four operators $+$, $-$, $\times$ and $/$ are allowed, but does not indicate whether numerical constants are allowed. Assuming that the five inputs are implicitly allowed, we use the following function to extract the constant $1$:

$$\operatorname{ExtractOne}(a,b,c,d,e) = (a + b) / (a + b)$$

In the formulas that follow, any positive constant $n$ can be replaced by (this is the simplest solution, other schemes will give fewer terms):

$$\underbrace{\operatorname{ExtractOne}(a,b,c,d,e)+\cdots+\operatorname{ExtractOne}(a,b,c,d,e)}_{n\text{ times}}$$

We will take care to never perform a division by zero:

Given the fact that at most one of the inputs is zero (there is only one card with the ID $0$), we know that the sum of any two of the five inputs will be non-zero, and therefore can safely be used as the divisor in $\operatorname{ExtractOne}$.

We then write an $\operatorname{IsZero}$ function, which operates on positive integers between $0$ and $52\times 52=2704$. It returns $1$ when its input is $0$, and it returns $0$ otherwise:

$$\operatorname{IsZero}(x) = \frac{(x-1) \times (x-2) \times (x-3) \times (x-4) \times \cdots \times (x-2703) \times (x-2704)}{2704!}$$

The $\operatorname{IsZero}$ operates following this principle:

When the input is $0$, the formula becomes $\frac{(0-1) \times (0-2) \times (0-3) \times (0-4) \times \cdots \times (0-2703) \times (0-2704)}{2704!}$, which is the same as $\frac{(-1) \times (-2) \times (-3) \times (-4) \times \cdots \times (-2703) \times (-2704)}{2704!}$. Since there is an even number of negative numbers, the result of their product is positive and is equal to: $\frac{1 \times 2 \times 3 \times 4 \times \cdots \times 2703 \times 2704}{2704!} = \frac{2704!}{2704!} = 1$. When the input is non-zero, i.e. $x ∈ \{1,\ldots,2704\}$, the formula instead becomes $\frac{(x-1) \times \cdots \times (x-(x-1)) \times (x-x) \times (x-(x+1)) \times \cdots \times (x-2704)}{2704!}$. The $x-x$ results in a $0$ which nullifies the whole formula: $\frac{(x-1) \times \cdots \times (x-(x-1)) \times 0 \times (x-(x+1)) \times \cdots \times (x-2704)}{2704!} = \frac{0}{2704!}=0$

Since we only call $IsZero$ on integers which are squares in the set $\{0, 1, 4, 9 …, 51²\}$, we skip some of the terms (thanks @2012rcampion):

$$\operatorname{IsZero}(x) = \frac{(x-1) \times (x-4) \times (x-9) \times (x-4) \times \cdots \times (x-2500) \times (x-2601)}{1*4*9*⋯*2500*2601}$$

We can now compare numbers by comparing their squares (remember that our $\operatorname{IsZero}$ function only supports integers in the set $\{0,\ldots,52\times 52\}$, the domain of $\operatorname{IntEqual}$ will therefore be $\{0,\ldots,52\} \times \{0,\ldots,52\}$). The $\operatorname{IntEqual}(x,y)$ function returns $1$ when $x=y$ and $0$ otherwise:

$$\operatorname{IntEqual}(x,y) = \operatorname{IsZero}((x - y) \times (x - y))$$

We then define an $\operatorname{IfThenElse}(c,x,y)$ function, which returns $x$ when $c=1$ and $y$ when $c=0$:

$$\operatorname{IfThenElse}(c,x,y) = (c \times x) + ((1 - c) \times y)$$

Since we always use $0$ as the third argument of $\operatorname{IfThenElse}$, we can define a simpler version $\operatorname{IfThen}$ (thanks @2012rcampion):

$$\operatorname{IfThen}(c,x) = c \times x$$

We finally use $\operatorname{IfThenElse}$ to build a decision tree, which assigns a unique number to each combination of input IDs, regardless of their order. The formula is a bit cumbersome to read and write, so what follows covers only hands of $2$ cards among $5$:

$$\begin{array}{c}\;\;\;\operatorname{IfThen}\left(\operatorname{IntEqual}(a, 0),\left(\begin{array}{l}\;\;\;\operatorname{IfThen}(\operatorname{IntEqual}(b,1),0)\\+\operatorname{IfThen}(\operatorname{IntEqual}(b,2),1)\\+\operatorname{IfThen}(\operatorname{IntEqual}(b,3),2)\\+\operatorname{IfThen}(\operatorname{IntEqual}(b,4),3)\end{array}\right)\right)\\+\operatorname{IfThen}\left(\operatorname{IntEqual}(a, 1),\left(\begin{array}{l}\;\;\;\operatorname{IfThen}(\operatorname{IntEqual}(b,0),0)\\+\operatorname{IfThen}(\operatorname{IntEqual}(b,2),4)\\+\operatorname{IfThen}(\operatorname{IntEqual}(b,3),5)\\+\operatorname{IfThen}(\operatorname{IntEqual}(b,4),6)\end{array}\right)\right)\\+\operatorname{IfThen}\left(\operatorname{IntEqual}(a, 2),\left(\begin{array}{l}\;\;\;\operatorname{IfThen}(\operatorname{IntEqual}(b,0),1)\\+\operatorname{IfThen}(\operatorname{IntEqual}(b,1),4)\\+\operatorname{IfThen}(\operatorname{IntEqual}(b,3),7)\\+\operatorname{IfThen}(\operatorname{IntEqual}(b,4),8)\end{array}\right)\right)\\+\operatorname{IfThen}\left(\operatorname{IntEqual}(a, 3),\left(\begin{array}{l}\;\;\;\operatorname{IfThen}(\operatorname{IntEqual}(b,0),2)\\+\operatorname{IfThen}(\operatorname{IntEqual}(b,1),5)\\+\operatorname{IfThen}(\operatorname{IntEqual}(b,2),7)\\+\operatorname{IfThen}(\operatorname{IntEqual}(b,4),9)\end{array}\right)\right)\\+\operatorname{IfThen}\left(\operatorname{IntEqual}(a, 4),\left(\begin{array}{l}\;\;\;\operatorname{IfThen}(\operatorname{IntEqual}(b,0),3)\\+\operatorname{IfThen}(\operatorname{IntEqual}(b,1),6)\\+\operatorname{IfThen}(\operatorname{IntEqual}(b,2),8)\\+\operatorname{IfThen}(\operatorname{IntEqual}(b,3),9)\end{array}\right)\right)\\\end{array}$$

We use the form

$$\operatorname{IfThen}(c_1,v_1)+\operatorname{IfThen}(c_2,v_2)+⋯+\operatorname{IfThen}(c_n,v_n)$$

instead of

$$\operatorname{IfThenElse}(c_1,v_1,\operatorname{IfThenElse}(c_2,v_2,\ldots))$$

to avoid the rightward drift caused by deeply nested function calls.

With a hand of five cards, the decision tree would be five levels deep instead of two, and with 52 cards to choose from, each level would contain many more cases.

The solution proposed by Carl Löndahl can also be applied using this technique to compute the modulus.

$\endgroup$
  • 4
    $\begingroup$ Congrats on making the rational function restriction completely meaningless (I never liked the arbitrary restriction in the first place!) $\endgroup$ – ffao Oct 21 '16 at 6:44
  • $\begingroup$ If IfThenElse you can use $1-c$ instead of $(c-1)^2$. $\endgroup$ – 2012rcampion Oct 21 '16 at 6:52
  • $\begingroup$ To get fewer terms, you could define IsZero like $\prod_{i=1}^{51}\left[\left(\frac{x}{i}\right)^2-1\right]$, and then IntEqual could be just $\operatorname{IsZero}(x-y)$. Plus, since you never use the third argument of IfThenElse you can eliminate the last term altogether (maybe just an IfThen function?). $\endgroup$ – 2012rcampion Oct 21 '16 at 7:23
  • $\begingroup$ @2012rcampion Thanks a lot for the formatting edit! I merged in your suggestions (keeping the square out of $\operatorname{IsZero}$, to keep the same shape as the original one, I think the fully-inlined version with the new $\operatorname{IsZero}$ has roughly the same number of terms as with your idea). $\endgroup$ – Georges Dupéron Oct 21 '16 at 9:58
  • 1
    $\begingroup$ @GeorgesDupéron You could achieve the same tight result by (polynomially) mapping all permutations of $(a,b,c,d,e)$ composed in some way (say, concatenation) to a specific number in the range $[0, {52 \choose 5}-1]$. Then for another $(a,b,c,d,e)$ a different one in the range and so on. Your solution is probably more efficient, since this would require a polynomial of degree $\sim 52^5$. $\endgroup$ – Carl Löndahl Oct 21 '16 at 10:44
3
$\begingroup$

Number the cards 1 to 52 arbitrarily. Then, make a dictionary of all $52 \choose 5$ hands. Order each hand from the smallest (i.e., $(5,47,21,30,3)$ becomes $(3,5,21,30,47)$) and then order these hands lexicographically from the smallest and assign them numbers $1$ to ${52 \choose 5} = 2598960$; this is an ordered dictionary we have to keep.

The trick is, looking up in such a dictionary method is doable using a closed formula, as the space of solutions is finite.

More precisely: Let $a_{n,1},\dots,a_{n,5}$ denote the ordered card numbers on position $n$ in the dictionary, $N={52 \choose 5}$ the total number of ordered hands (i.e., the length of the dictionary), $S_5$ the set of all permutations of $\{1,\dots,5\}$ and $[x,y] = 1\div\bigl((x-y)^2+1\bigr)$ (considering the integer division) the selector function for $x=y$. Then the hash function is $$f(x_1,x_2,x_3,x_4,x_5) = \sum_{n=1}^N \sum_{\sigma\in S_5} n \prod_{i=1}^5 [x_{\sigma(i)},a_{n,i}].$$ Note that all the sums and products are finite so this is a closed formula. The range is $\{1,\dots,N\}$, which is the minimal possible range, as exactly one summand of all $5!N$ of them is non-zero and it is equal to $n$. Therefore, I can do it in 7 decimal digits.

The only necessary trick is getting the $x=y$ selector. If integer division wasn't allowed, then we would have to find a polynomial with zeros as positions $1,4,9,\dots,51^2$ and such that its value at $0$ is $1$. Such polynomial exists, it's e.g. $p(t) = q(t)/q(0)$ where $$ q(t) = \prod_{j=1}^{51} (t-j^2)$$ (we know that $q(0)\neq0$ from the definition of $q$). Then $[x,y]= 1-p((x-y)^2)$. With this definition of $[x,y]$, we have that $f$ is a degree $51\cdot5=255$ polynomial.

$\endgroup$
  • $\begingroup$ No sorting allowed. Whatever your formula is, the 5 card IDs must be able to go in any order. $\endgroup$ – paparazzo Oct 22 '16 at 15:30
  • 1
    $\begingroup$ @Paparazzi you need sorting only in the construction of the formula... $\endgroup$ – yo' Oct 22 '16 at 17:19
  • $\begingroup$ That is sorting. If the value in the dictionary is (3,5,21,30,47) then you will not get a match on (5,47,21,30,3). You will have to sort the hand to get a match on the dictionary value. $\endgroup$ – paparazzo Oct 22 '16 at 18:31
  • $\begingroup$ @Paparazzi better explanation? $\endgroup$ – yo' Oct 22 '16 at 18:44
  • 2
    $\begingroup$ yo' is correct. The 5 card IDs are able to go in any order into the formula, as required. You don't have to sort the hand. The sorting is done by the formula. The formula poses no restriction on the order in which the IDs are fed into it. $\endgroup$ – Rosie F Oct 23 '16 at 8:42
6
$\begingroup$

Here is another take. We can use the modulus $53$ using only operations $(+,-,x)$, simply by removing $53$ until we have reached a non-negative number strictly less than $53$.

Let $a,b,c,d,e \in \mathbb{Z}_{53}$ encode the $52$ cards (we need to use $53$ since it is prime) so we may use the last number for other fun stuff as a joker.

Take any polynomial

$(x-a)(x-b)(x-c)(x-d)(x-e) \mod 53$,

which will be of the form

$x^5 + Ax^4 + Bx^3 + Cx^2 + Dx + E \mod 53$

where each $A,B,C,D,E \in \mathbb{Z}_{53}$. Hence, we can encode our hand as $ABCDE$ (using two digits per number, so if e.g. $A = 1$, we write it as $01$).

Finding the roots of the polynomial can be found efficiently, but lets us assume for simplicity that we simply try all the numbers $a,b,c,d,e$ until we match the numbers $A,B,C,D,E$ (there is no restriction on the complexity, right? :-). This will give a number which is strictly less than $5252525252$. For instance, $1812213610$ will give a polynomial $x^5+18 x^4+12 x^3+21 x^2+36 x+10 \mod 53$, which is $(x-3)(x-4)(x-52)(x-12)(x-17) \mod 53$


Apart from this we need to prove the permutatation-invariant property. If we exchange $a$ and $b$, we get $(x-b)(x-a)(x-c)(x-d)(x-e) \mod 53$, but it will of course give rise to the same product.

The uniqueness property relies on the fact that we cannot replace e.g. $a$ and $b$ with $a'$ and $b'$ (or even more roots):

$(x-a')(x-b')(x-c)(x-d)(x-e) = x^5 + Ax^4 + Bx^3 + Cx^2 + Dx + E \mod 53$.

Since the modulus is prime, we are guaranteed to get the same roots. A sketch proof. If $x^5 + Ax^4 + Bx^3 + Cx^2 + Dx + E = 0 \mod 53$, for some $x$ then at least one of the factors of $(x-a)(x-b)(x-c)(x-d)(x-e)$ must divide $53$. For one factor, this only holds if $x = a + 53k$, $x = b + 53k$ or so on. It is not possible for two factors to both divide $53$ since it is prime. Therefore, it must be unique.

$\endgroup$
  • 3
    $\begingroup$ Nice! Why use base 100 though? Just give the value of ABCDE in base 53, this should have only 9 digits in base 10. $\endgroup$ – ffao Oct 20 '16 at 22:25
  • $\begingroup$ @ffao True, it is a good idea! My focus was mostly breaking the current record :-D $\endgroup$ – Carl Löndahl Oct 20 '16 at 22:28
  • $\begingroup$ Could you provide an example? I don't follow the value of x. $\endgroup$ – paparazzo Oct 20 '16 at 23:32
  • $\begingroup$ If I understood well, to compute the modulus, you are not limiting yourself to the four basic operations +-*/. You need some kind of loop, or at least some kind of conditional (the loop can be removed by unrolling it enough times). As Gareth McCaughan said, the goal is to compute the result using a rational function of the IDs. Or at least that's my understanding. $\endgroup$ – Georges Dupéron Oct 21 '16 at 2:20
  • $\begingroup$ @CarlLöndahl Regarding my previous comment, it is actually possible to implement the modulus using the basic operations and no loops, as long as there is a bound on the maximum value of which you need to take the modus, see my second answer for the general idea: puzzling.stackexchange.com/a/44680/31235 $\endgroup$ – Georges Dupéron Oct 21 '16 at 6:15
4
$\begingroup$

Even though the (arbitrary) constraint in the question that IDs must be 3 digits long only allows the multiplication solution, if we relax that constraint we can actually get an addition solution of the same order of magnitude as the multiplication solution (using 12 digits at most).

The fundamental theorem of arithmetic guarantees that multiplications of prime powers can only be recomposed in a single way, but there is no simple equivalent for addition. Therefore, let's use the multiplication result!

It's known that multiplication modulo a prime is in fact equivalent to addition: let $g$ be a primitive root $\mod P$, and let $f(x)$ be the smallest non-negative integer such that $g^{f(x)} \equiv x \pmod P$. Then we have that $f(a) + f(b) \equiv f(ab) \pmod P$. That is, we have made a multiplication of two integers turn into an addition!

We can use this to construct a list of IDs. Let's start by taking a list of integers for which any subset of 5 of them has a different multiplication result. Well, that has already been done, it's the multiplication solution taking prime powers:

1 2 3 4 5 7 9 11 13 16 17 19 23 25 29 31 37 41 43 47 49 53 59 61 67 71 73 79 81 83 89 97 101 103 107 109 113 121 127 128 131 137 139 149 151 157 163 167 169 173 179 181

Now let's choose a suitably high prime $P$ and a primitive root $g$ (I chose $P=158190677081$ and $g=6$), and make a list of the values of $f(x)$ for each $x$ in the list above:

0, 16445962636, 141744714445, 32891925272, 41469257188, 88706945715, 125298751810, 119801768315, 45645348677, 65783850544, 10559933910, 6498069647, 28871758692, 82938514376, 43945311014, 129559740004, 139964773214, 46143833772, 72119606038, 15722902759, 19223214350, 109129913342, 32569452357, 2621065874, 103451019890, 36836348907, 94873027927, 36431071505, 92406826540, 44034197223, 49620088406, 47432217884, 15767897478, 144952506326, 139187300538, 16588813376, 77370272961, 81412859550, 46599081569, 115121738452, 23970003234, 156223722913, 104797449260, 38709422671, 28274542857, 55950793132, 52934160773, 38218075031, 91290697354, 128401995698, 143534473790, 51946670652

From the fact that each 5-element subset of our original set has a distinct multiplication result, the addition results for the second set above must also be distinct, as they represent the same multiplications under the finite field.

The sum of the cards with the five highest IDs is 726420190688. Subtracting the sum of the five smallest IDs, we get a maximum hand of 691018218499.


We can see that the highest number used by the solution is around $5P$, therefore it makes sense to try to minimize the value of $P$ used. The actual condition on $P$ is that it must not divide any of the pairwise differences between the multiplication results; the $P$ I chose obviously satisfies this condition because it is greater than all of them, but there probably is a smaller prime.

I was tempted to check for the smallest prime possible, but the number of pairwise differences is around $3.3 \times 10^{12}$, so it would take some time for my slowish computer to handle them...

$\endgroup$
2
$\begingroup$

Brute-force using only multiplication

I used a brute-force technique with multiplication, implemented with the Racket language. Below is an attempt to use brute-force with addition (addition produces results which are more than 12 digits). Note that in both cases, not all possible sets of ids are attempted, rather the program tries to add numbers to the set, and rejects those which are incompatible with the existing numbers. This means that the solutions are far from being optimal.

The results are:

1 2 3 4 5 7 9 11 13 16 17 19 23 25 29 31 37 41 43 47 49 53 59 61 67 71 73 79 81 83 89 97 101 103 107 109 113 121 127 128 131 137 139 149 151 157 163 167 169 173 179 181

This is very similar to the answer by Gareth McCaughan, except that the last id is removed from the list, and instead another one is used in the middle of the list:

128

The reason that this is allowed follows:

Gareth McCaughan allowed primes of the form $p^1$, $p^2$, $p^4$, $p^8$, … However, the desired property is weaker. Let's represent the IDs as products of the form $(p_1)^{a_1} × (p_2)^{a_2} × ⋯$, where each $p_i$ is the $i$-th prime number (so $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, $p_4 = 7$ …). The $a_i$ are natural numbers, and can be $0$. The condition is then that for any 5 such IDs, whose prime powers are noted respectively $a_i$, $b_i$, $c_i$, $d_i$, $e_i$, the tuple $(a_1+b_1+c_1+d_1+e_1, a_2+b_2+c_2+d_2+e_2, a_3+b_3+c_3+d_3+e_3, …)$ must be unique.

I was unable to devise an algorithm which exploits the above property, however.

Since the minimum value for a product of five numbers is $1×2×3×4×5 = 120$, we can subtract $120$ from each sum (and still get unique sums, since we subtract a constant), meaning that the maximum result is:

$167 × 169 × 173 × 179 × 181 - 120 = 158190676901$, with $12$ digits.

I then tried to do the brute-force in the other way round, starting with the last two known good values, and working my way back. The result is:

1 19 45 90 97 101 103 107 109 113 121 122 127 128 131 134 137 139 141 142 146 147 148 149 151 155 156 157 158 159 160 161 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 191

Notice that it starts from a much higher value. The minimum product then becomes $7464150$, which gives us, when applying the subtraction trick, a slightly lower maximum result of:

$167 × 169 × 173 × 179 × 181 - 7464150 = 158183212871$, still with $12$ digits.

#lang racket
;; attempt at a solution for http://puzzling.stackexchange.com/q/44629/31235

;; Use unsafe fixnum operations: we know the values are small enough to not
;; overflow, and these operations are somewhat faster.
(require racket/unsafe/ops)

(define (check)
  (define check-clobbered (make-hash))
  ;; Could be sped up by using unsafe-fx* and unsafe-fx=
  (for* ([id1 (in-list ids)]
         #:when (displayln (format "Checking sets containing ~a…" id1))
         [id2 (in-list ids)]
         #:unless (= id1 id2)
         [id3 (in-list ids)]
         #:unless (or (= id1 id3) (= id2 id3))
         [id4 (in-list ids)]
         #:unless (or (= id1 id4) (= id2 id4) (= id3 id4))
         [id5 (in-list ids)]
         #:unless (or (= id1 id5) (= id2 id5) (= id3 id5) (= id4 id5)))
    (let* ([result (* id1 id2 id3 id4 id5)]
           [ref (hash-ref check-clobbered result #f)])
      (if ref
          (unless (equal? ref (sort (list id1 id2 id3 id4 id5) <))
            (error (format "~a*~a*~a*~a*~a = ~a is already the result of ~a"
                           id1 id2 id3 id4 id5 result ref)))
          (hash-set! check-clobbered
                     result
                     (sort (list id1 id2 id3 id4 id5) <))))))

;; Computed with my brute-force algorithm below
(define ids (list 1 2))

;; check the hardcoded values (copied from previous runs, to allow the
;; computation to be restarted
(begin
  (check)
  (displayln "Initial hardcoded values checked!"))

;; Compute more values by increasing the "20" in the definition of
;; compute-sequence just below:
(begin
  (define (compute-sequence)
    (for ([card (in-range (length ids) 52)]) ;; 20 cards
      (define newid (for/first ([id (in-naturals)]
                                #:unless (clobbered? id))
                      id))
      (set! ids (cons newid ids))
      (clobber! newid)
      (displayln (list card newid))))

  (define clobbered2 (mutable-set))
  (define clobbered3 (mutable-set))
  (define clobbered4 (mutable-set))
  (define clobbered5 (mutable-set))

  ;; returns #t if i*x₂, i*x₂*x₃, i*x₂*x₃*x₄ or i*x₂*x₃*x₅ have already been
  ;; seen (i.e. recorded by clobber! below).
  (define (clobbered? i)
    (or (member i ids)
        (= i 0)
        (for*/or ([id1 (in-value i)]
                  [id2 (in-list ids)]
                  #:unless (unsafe-fx= id1 id2))
          (let ([result2 (unsafe-fx* id1 id2)])
            (or (set-member? clobbered2 result2)
                (for*/or ([id3 (in-list ids)]
                          #:unless (or (unsafe-fx= id1 id3)
                                       (unsafe-fx= id2 id3)))
                  (let ([result3 (unsafe-fx* result2 id3)])
                    (or (set-member? clobbered3 result3)
                        (for*/or ([id4 (in-list ids)]
                                  #:unless (or (unsafe-fx= id1 id4)
                                               (unsafe-fx= id2 id4)
                                               (unsafe-fx= id3 id4)))
                          (let ([result4 (unsafe-fx* result3 id4)])
                            (or (set-member? clobbered4 result4)
                                (for*/or ([id5 (in-list ids)]
                                          #:unless (or (unsafe-fx= id1 id5)
                                                       (unsafe-fx= id2 id5)
                                                       (unsafe-fx= id3 id5)
                                                       (unsafe-fx= id4 id5)))
                                  (let ([result5 (unsafe-fx* result4 id5)])
                                    (set-member? clobbered5 result5))))))))))))))

  ; Records all the values for i*x₂, i*x₂*x₃, i*x₂*x₃*x₄ or i*x₂*x₃*x₅ as seen
  (define (clobber! i)
    (for* ([id1 (in-value i)]
           [id2 (in-list ids)]
           #:unless (unsafe-fx= id1 id2))
      (let ([result2 (unsafe-fx* id1 id2)])
        (set-add! clobbered2 result2)
        (for* ([id3 (in-list ids)]
               #:unless (or (unsafe-fx= id1 id3)
                            (unsafe-fx= id2 id3)))
          (let ([result3 (unsafe-fx* result2 id3)])
            (set-add! clobbered3 result3)
            (for* ([id4 (in-list ids)]
                   #:unless (or (unsafe-fx= id1 id4)
                                (unsafe-fx= id2 id4)
                                (unsafe-fx= id3 id4)))
              (let ([result4 (unsafe-fx* result3 id4)])
                (set-add! clobbered4 result4)
                (for* ([id5 (in-list ids)]
                       #:unless (or (unsafe-fx= id1 id5)
                                    (unsafe-fx= id2 id5)
                                    (unsafe-fx= id3 id5)
                                    (unsafe-fx= id4 id5)))
                  (let ([result5 (unsafe-fx* result4 id5)])
                    (set-add! clobbered5 result5))))))))))

  ;; initialize the clobbered lists
  (for-each clobber! ids)

  (compute-sequence)

  ids
  (check))

Brute-force using addition

I used a brute-force technique with addition, implemented with the Racket language. Unfortunately, the result has 16 digits, instead of the required 12.

Don't scroll through the code if you want to avoid spoilers, the first elements are hardcoded.

#lang racket
;; attempt at a solution for http://puzzling.stackexchange.com/q/44629/31235

;; Use unsafe fixnum operations: we know the values are small enough to not
;; overflow, and these operations are somewhat faster.
(require racket/unsafe/ops)

(define (check)
  (define check-clobbered (make-hash))
  ;; Could be sped up by using unsafe-fx+ and unsafe-fx=
  (for* ([id1 (in-list ids)]
         #:when (displayln (format "Checking sets containing ~a…" id1))
         [id2 (in-list ids)]
         #:unless (= id1 id2)
         [id3 (in-list ids)]
         #:unless (or (= id1 id3) (= id2 id3))
         [id4 (in-list ids)]
         #:unless (or (= id1 id4) (= id2 id4) (= id3 id4))
         [id5 (in-list ids)]
         #:unless (or (= id1 id5) (= id2 id5) (= id3 id5) (= id4 id5)))
    (let* ([result (+ id1 id2 id3 id4 id5)]
           [ref (hash-ref check-clobbered result #f)])
      (if ref
          (unless (equal? ref (sort (list id1 id2 id3 id4 id5) <))
            (error (format "~a+~a+~a+~a+~a = ~a is already the result of ~a"
                           id1 id2 id3 id4 id5 result ref)))
          (hash-set! check-clobbered
                     result
                     (sort (list id1 id2 id3 id4 id5) <))))))

;; Computed with my brute-force algorithm below
(define ids (list 0   1   2    4    7    13   24    44    84    161
                  309 594 1164 2284 4426 8543 16492 30700 56982 98817))
;; Sequence from https://oeis.org/A005318
(define A005318 (list 0 1 2 4 7 13 24 44 84 161
                      309 594 1164 2284 4484 8807 17305 34301 68008 134852))

;; check the hardcoded values (copied from previous runs, to allow the
;; computation to be restarted
(begin
  (check)
  (displayln "Initial hardcoded values checked!"))

;; Plot the difference between the "any subset of size 5 must have a unique sum"
;; and the https://oeis.org/A005318 sequence
(begin
  (require plot)
  (parameterize ([plot-y-transform log-transform]
                 [plot-y-ticks (log-ticks)])
    (plot (list (lines-interval
                 (for/list ([x (in-naturals 1)]
                            [y (cdr ids)])
                   (list x (exact->inexact y)))
                 (for/list ([x (in-naturals 1)]
                            [y (cdr A005318)])
                   (list (exact->inexact x) (exact->inexact y))))))))

;; Compute more values by increasing the "20" in the definition of
;; compute-sequence just below:
(begin
  (define (compute-sequence)
    (for ([card (in-range (length ids) 20)]) ;; 20 cards
      (define newid (for/first ([id (in-naturals)]
                                #:unless (clobbered? id))
                      id))
      (set! ids (cons newid ids))
      (clobber! newid)
      (displayln (list card newid))))

  (define clobbered2 (mutable-set))
  (define clobbered3 (mutable-set))
  (define clobbered4 (mutable-set))
  (define clobbered5 (mutable-set))

  ;; returns #t if i+x₂, i+x₂+x₃, i+x₂+x₃+x₄ or i+x₂+x₃+x₅ have already been
  ;; seen (i.e. recorded by clobber! below).
  (define (clobbered? i)
    (or (member i ids)
        (for*/or ([id1 (in-value i)]
                  [id2 (in-list ids)]
                  #:unless (unsafe-fx= id1 id2))
          (let ([result2 (unsafe-fx+ id1 id2)])
            (or (set-member? clobbered2 result2)
                (for*/or ([id3 (in-list ids)]
                          #:unless (or (unsafe-fx= id1 id3)
                                       (unsafe-fx= id2 id3)))
                  (let ([result3 (unsafe-fx+ result2 id3)])
                    (or (set-member? clobbered3 result3)
                        (for*/or ([id4 (in-list ids)]
                                  #:unless (or (unsafe-fx= id1 id4)
                                               (unsafe-fx= id2 id4)
                                               (unsafe-fx= id3 id4)))
                          (let ([result4 (unsafe-fx+ result3 id4)])
                            (or (set-member? clobbered4 result4)
                                (for*/or ([id5 (in-list ids)]
                                          #:unless (or (unsafe-fx= id1 id5)
                                                       (unsafe-fx= id2 id5)
                                                       (unsafe-fx= id3 id5)
                                                       (unsafe-fx= id4 id5)))
                                  (let ([result5 (unsafe-fx+ result4 id5)])
                                    (set-member? clobbered5 result5))))))))))))))

  ; Records all the values for i+x₂, i+x₂+x₃, i+x₂+x₃+x₄ or i+x₂+x₃+x₅ as seen
  (define (clobber! i)
    (for* ([id1 (in-value i)]
           [id2 (in-list ids)]
           #:unless (unsafe-fx= id1 id2))
      (let ([result2 (unsafe-fx+ id1 id2)])
        (set-add! clobbered2 result2)
        (for* ([id3 (in-list ids)]
               #:unless (or (unsafe-fx= id1 id3)
                            (unsafe-fx= id2 id3)))
          (let ([result3 (unsafe-fx+ result2 id3)])
            (set-add! clobbered3 result3)
            (for* ([id4 (in-list ids)]
                   #:unless (or (unsafe-fx= id1 id4)
                                (unsafe-fx= id2 id4)
                                (unsafe-fx= id3 id4)))
              (let ([result4 (unsafe-fx+ result3 id4)])
                (set-add! clobbered4 result4)
                (for* ([id5 (in-list ids)]
                       #:unless (or (unsafe-fx= id1 id5)
                                    (unsafe-fx= id2 id5)
                                    (unsafe-fx= id3 id5)
                                    (unsafe-fx= id4 id5)))
                  (let ([result5 (unsafe-fx+ result4 id5)])
                    (set-add! clobbered5 result5))))))))))

  ;; initialize the clobbered lists
  (for-each clobber! ids)

  (compute-sequence)

  ids
  (check))

The 20 first terms that my algorithm gives are:

0 1 2 4 7 13 24 44 84 161 309 594 1164 2284 4426 8543 16492 30700 56982 98817

Since the computation times start getting really high at that point (my code could use a LOT of improvement speed-wise), I plugged the results into oeis.org, and found this series:

Conway-Guy sequence: a(n + 1) = 2a(n) - a(n - floor( 1/2 + sqrt(2n) ))

The first 52 values of the series are:

0 1 2 4 7 13 24 44 84 161 309 594 1164 2284 4484 8807 17305 34301 68008 134852 267420 530356 1051905 2095003 4172701 8311101 16554194 32973536 65679652 130828948 261127540 521203175 1040311347 2076449993 4144588885 8272623576 16512273616 32958867580 65852055508 131573282068 262885436596 525249670017 1049459028687 2096841607381 4189538625877 8370804628178 16725096982740 33433681691864 66834404516148 133602956976788 267074340671508 533885795906420

A small excerpt from the description:

Conway and Guy conjecture that the set of $k$ numbers $\{s_i = a(k) - a(k-i) : 1 <= i <= k\}$ has the property that all its subsets have distinct sums

This is not exactly the property we are looking for, but it seems to fit the job.

The following script computes and checks the values (don't look too close, spoilers inside):

#lang racket

(define ids '(1 0))

(for ([i (in-range 1 51)])
  (set! ids
        (cons
         ;; a(i+1)
         (- (* 2 (list-ref (reverse ids) i))
            (list-ref (reverse ids)
                      (- i (inexact->exact
                            (floor (+ 1/2 (sqrt (* 2 i))))))))
         ids)))

(define (check)
  (define check-clobbered (make-hash))
  (for* ([id1 (in-list ids)]
         #:when (displayln (format "Checking sets containing ~a…" id1))
         [id2 (in-list ids)]
         #:unless (= id1 id2)
         [id3 (in-list ids)]
         #:unless (or (= id1 id3) (= id2 id3))
         [id4 (in-list ids)]
         #:unless (or (= id1 id4) (= id2 id4) (= id3 id4))
         [id5 (in-list ids)]
         #:unless (or (= id1 id5) (= id2 id5) (= id3 id5) (= id4 id5)))
    (let* ([result (+ id1 id2 id3 id4 id5)]
           [ref (hash-ref check-clobbered result #f)])
      (if ref
          (unless (equal? ref (sort (list id1 id2 id3 id4 id5) <))
            (error (format "~a+~a+~a+~a+~a = ~a is already the result of ~a"
                           id1 id2 id3 id4 id5 result ref)))
          (hash-set! check-clobbered
                     result
                     (sort (list id1 id2 id3 id4 id5) <)))))
  #;(hash->list check-clobbered))

(reverse ids)
(displayln (format "maximum value for a hand of 5 cards: ~a"
                   (apply + (take ids 5))))
(check)

The terms are the same at the beginning, but start diverging at the 15th card (my sequence gives smaller IDs):

My results:

0 1 2 4 7 13 24 44 84 161 309 594 1164 2284 4426 8543 16492 30700 56982 98817

OEIS sequence:

0 1 2 4 7 13 24 44 84 161 309 594 1164 2284 4484 8807 17305 34301 68008 134852

I think the reason the sequences diverge is:

My sequence ensures that any subset of five or less elements has a unique sum for that subset size, whereas the Conway-Guy sequence conjectures that any two subset of any size (possibly two sets with different sizes) have a different sum. My sequence is therefore more permissive.

Here is a logarithmic plot of the difference between the two sequences, for the first 20 elements:

Logarithmic plot of the difference between the two sequence, ending at the 20th element, which is about 10^5 for both. The difference is tiny (several orders of magnitude smaller than the element)

As can be seen, the difference is tiny, so my sequence won't improve enough on the OEIS one to pass the 12-digit limit.

$\endgroup$
  • $\begingroup$ cannot use 128 = 2 x 4 x 16 $\endgroup$ – paparazzo Oct 22 '16 at 19:51
  • $\begingroup$ @Paparazzi : You can use 128: if you have two hands $128×a×b×c×d$ and $2×4×16×e×f$, they won't collide unless there are four distinct numbers $a,b,c,d$ and two distinct numbers $e,f$ such that $a×b×c×d=e×f$. This is not the case in the sequences I gave, so 128 is valid (I used the code I gave in the answer to check automatically that all combinations of 5 elements of the set have a distinct product). $\endgroup$ – Georges Dupéron Oct 23 '16 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.