This week’s Fiddler is about the number 2025, in celebration of (almost) New Years!
First puzzle: What is the greatest number of distinct primes that add up to 2025?
Second puzzle: How can you assign a set of 20 distinct prime numbers to the 20 vertices of a dodecahedron, so that the numbers on the five vertices of each face add up to 2025?
My solution:
[Show Solution]
I solved these problems by modeling them as integer linear programs. There are sophisticated solvers that can be brought to bear on such problems, such as Gurobi. But to do this, the problem must be put in the correct form. Namely,
- The decision variables can be real numbers, integers, or binary numbers.
- The constraints must be linear equalities or inequalities of the decision variables.
- The objective we are trying to minimize or maximize must also be a linear function of the decision variables.
It may not be immediately obvious how to do this for the problems above, since they involves prime numbers… Here is how you do it:
First puzzle
Let $p$ be the list of prime numbers up to 2025. It turns out there are $n=306$ of them. We will treat $p$ as a column vector:
\[
p = \begin{bmatrix}2 \\ 3 \\ 5 \\ \vdots \\ 2017 \end{bmatrix}
\]Our decision variable will be $x \in \{0,1\}^n$, a vector of length $n$ that selects which primes we will use. In other words:
\[
x_k = \begin{cases}1 & \text{if we include prime }p_k \\
0 &\text{otherwise}
\end{cases}
\]The problem we want to solve is simply:
\begin{align*}
\underset{x \in \{0,1\}^n}{\text{maximize}} \qquad & \sum_{k=1}^n x_k \\
\text{subject to:} \qquad & \sum_{k=1}^n p_k x_k = 2025
\end{align*}
It turns out this problem is an example of a Knapsack Problem, which is one of the simplest integer linear programs.
I coded this up in Julia using the Gurobi solver. Here is my code:
using JuMP using Primes using Gurobi using LinearAlgebra # list of the primes we will use p = primes(2025) n = length(p) # Create a model with Gurobi as the optimizer m = Model(Gurobi.Optimizer) set_optimizer_attribute(m, "OutputFlag", 0) # Define decision variables @variable(m, x[1:n], Bin) # x selects which primes to use # Maximize the number of primes used @objective(m, Max, sum(x)) # Sum of primes equals 2025 @constraint(m, dot(p,x) == 2025) # Solve the model optimize!(m) # Check the status of the solution if termination_status(m) == MOI.OPTIMAL println("Optimal solution found using ", Int(objective_value(m)), " primes") println([Int(prime) for prime in p .* value.(x) if prime > 0]) else println("No optimal solution found. Status: ", termination_status(m)) end
The code executed in 0.17 seconds and found an optimal solution, which uses 32 primes:
\begin{multline*}
2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41\\
+ 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89\\
+ 97 + 101 + 103 + 107 + 109 + 173 + 181 + 191 = 2025
\end{multline*}
Second puzzle
This problem is more complex than the first one because we must not only select which primes to use, but also which vertices to assign them to. The first step is to label the vertices. We will use the following labeling:
Some labels are repeated because they correspond to vertices that are actually the same once the dodecahedron is folded back together.
To solve this problem, we again define $p$ to be a list of primes. This time, it’s not clear how many we will need, so we will let $p$ be the first $N$ primes, and adjust $N$ later as needed.
Next, we should identify which vertices belong to each of the faces. To this effect, we define the binary matrix $F\in \{0,1\}^{12\times 20}$:
\[
F_{ij} = \begin{cases} 1 & \text{if face $i$ uses vertex $j$} \\
0 & \text{otherwise}
\end{cases}
\]Finally, our decision variable is a binary selection matrix $X\in \{0,1\}^{20\times N}$:
\[
X_{jk} = \begin{cases} 1 & \text{if vertex $j$ is assigned to prime $p_k$} \\
0 & \text{otherwise}
\end{cases}
\]The optimization problem we want to solve is:
\begin{align*}
\underset{X \in \{0,1\}^{20\times N}}{\text{minimize}} \qquad & 0 \\
\text{subject to:}\qquad & \sum_{k=1}^N X_{jk} = 1 && \text{for }j=1,\dots,20 \\
& \sum_{j=1}^{20} X_{jk} \leq 1 && \text{for }k=1,\dots,N \\
& \sum_{j=1}^{20} \sum_{k=1}^N F_{ij}X_{jk}p_k = 2025 && \text{for }i=1,\dots,12
\end{align*}Some explanation is warranted:
- The objective is to “minimize zero” since we simply want to find any feasible assignment of primes. So the objective we use does not matter.
- The first constraint says that each of the $20$ vertices must be assigned to exactly one prime number.
- The second constraint says that each of the $N$ primes can be assigned to at most one vertex.
- The final constraint says that the primes assigned to the vertices that form each of the 12 faces must sum to $2025$.
Using more compact matrix notation, we can write the optimization problem more succinctly as:
\begin{align*}
\underset{X}{\text{minimize}} \qquad & 0 \\
\text{subject to:}\qquad & X \mathbf{1} = \mathbf{1} \\
& X^\mathsf{T} \mathbf{1} \leq \mathbf{1} \\
& F X p = 2025 \cdot \mathbf{1}
\end{align*}This problem is far more difficult to solve than the first one, since there are many more variables and constraints. As a comparison:
- The first problem had $n$ variables and $n$ constraints. We picked primes up to 2025, which led to $n=306$, but we could have chosen a much smaller $n$.
- The second problem has $20N$ variables and $N+32$ constraints. In this case, we need primes up to at least 405 (2025 divided by 5), which leads to $N\geq 80$, but it turns out a much larger $N$ is needed to find a feasible solution. I ended up picking primes up to 1000, which led to $N=168$.
Here is my code:
# list of the primes we will use p = primes(1000) N = length(p) # Create a model with Gurobi as the optimizer m = Model(Gurobi.Optimizer) set_optimizer_attribute(m, "OutputFlag", 0) # Define decision variables # X[i,j] = 1 if vertex i is assigned to prime j @variable(m, X[1:20,1:N], Bin) # Sum of primes in each face equals 2025. 12x20 matrix selecting the faces F = [ 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 0 ] @constraint(m, X * ones(N) .== 1) # assign exactly one prime to each face @constraint(m, X' * ones(20) .<= 1) # use each prime at most once @constraint(m, F * X * p .== 2025) # the primes on each face sum to 2025 # Solve the model optimize!(m) # Check the status of the solution if termination_status(m) == MOI.OPTIMAL println("Optimal solution found") X = Int.(value.(X)) for i in 1:20 for j in 1:N if X[i,j] == 1 println( "(", i, ",", p[j], ")" ) end end end else println("No optimal solution found. Status: ", termination_status(m)) end
In the code above, $N=168$ and a solution was found in about 30 seconds. Interestingly, there is a trade-off with runtime:
- picking a smaller $N$ means there are fewer variables and constraints, so the code should run faster.
- picking a smaller $N$ also means there are fewer feasible solutions (since we have fewer primes at our disposal), so solutions could take longer to find.
Case in point: picking primes less than $900$ ($N=154$) still finds a solution, but takes several minutes to do so!
Here is one solution found by my code:
Another way to display the solution is via a Schlegel diagram:
Note: This puzzle is similar to a a previous Riddler puzzle. In that other puzzle, I used a more logical/number-theoretic approach rather than a purely computational one.
Very nice work on a difficult 2nd problem. I took a look at the problem over the weekend and gave up, leading me to 3 questions. First, in choosing a diagram for display purposes, why go with the dodec. “net” instead of a platonic graph (also called a Schlegel graph)? The graph has 20 nodes for the 20 vertices, making the prime assignments a little more direct, I would think. Second, didn’t you previously analyze this question, or something similar, in February 2022, back when the Fiddler was the Riddler? That question was about assigning distinct primes to the vertices of cube so that each face had the same sum. The difference there, as I recall, was that you could choose the sum, rather than being forced to hit a target number. Which brings me to my third question. How much of your prior analysis in 2022 could still be applied to the dodecahedron primes with a target sum? Nothing against optimization solvers, but I am particularly interested in how to break down problems like this analytically, to the extent possible, before we all run to our computers.
Thank you for the comment! I had totally forgotten about that old Riddler problem… I updated my solution with a link to it and also a Schlegel diagram of the solution.
Regarding your question, I think that having a variable sum was a critical feature that made the previous Riddler problem amenable to an analytic approach. Namely, it relied on the Green-Tao Theorem on the existence of arithmetic progressions of primes. Forcing the primes to lie in arithmetic progressions makes it easy to find solutions, but they end up having very large sums… If we want the sums to be smaller, such as 2025, I think that we can no longer expect to find solutions that lie in arithmetic progressions.
In general, I think this is a challenging question because there are very few known results about the structure of prime numbers. Beyond arithmetic progressions, I’m not sure what sort of structure we can exploit.
In the spriit of Eugene Wigner (who allegedly once said “It’s nice to know that the computer understands the problem, but I would like to understand it too”), here is how we can see that the max number of primes that sum to 2025 is 32. First, add up the smallest primes until the sum exceeds 2025: this happens with 34 primes, with a sum of 2127. So the max number that sums to 2025 must be less than 34. Could it be 33? Only if 2 is excluded, otherwise the sum is even. But the sum of the 33 smallest odd primes is just the previous sum minus 2, or 2125: still too big. So the largest possible number of primes that sums to 2015 must be 32 or fewer. And then there are many solutions with 32 primes, including 56 in which we add the 35th prime (149) and drop three other smaller primes. Your solution uses primes up to the 43rd (191).
Happy holidays and especially Happy New Year!
*sigh* typos! spriit -> spirit, 2015 -> 2025