I have to find algorithm which find prime number less than $n$ which is sum of the largest amount of unique primes, for example for $n=81$, the answer is $79 = 3 + 5 + 7 + 11 + 13 + 17 + 23$. I have read about partitions and Goldbach's conjecture but it seems unhelpful.
2026-03-25 23:38:35.1774481915
How to turn number into sum of unique primes?
1.3k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
There are 1 best solutions below
Related Questions in ALGORITHMS
- Least Absolute Deviation (LAD) Line Fitting / Regression
- Do these special substring sets form a matroid?
- Modified conjugate gradient method to minimise quadratic functional restricted to positive solutions
- Correct way to prove Big O statement
- Product of sums of all subsets mod $k$?
- (logn)^(logn) = n^(log10+logn). WHY?
- Clarificaiton on barycentric coordinates
- Minimum number of moves to make all elements of the sequence zero.
- Translation of the work of Gauss where the fast Fourier transform algorithm first appeared
- sources about SVD complexity
Related Questions in INTEGER-PARTITIONS
- What form does the Law of Total Probability take if the partition you use is generated by the random variable Y?
- Permutation induced by a partition
- Number of positive integral solutions of $a+b+c+d+e=20$ such that $a<b<c<d<e$ and $(a,b,c,d,e)$ is distinct
- On a theorem (1.7) in Macdonald's Symmetric Functions and Hall Polynomials
- Asymptotic behavior of the number of ways a real plane curve of degree $n$ can intersect a real line
- Sum of the hook-lengths of a partition $\lambda$
- On an example in Macdonald's Symmetric Functions and Hall Polynomials on Paritions and their Frobenius Notation
- To show that $\sum_{x \in \lambda}(h(x)^2 - c(x)^2)=|\lambda|^2$, $h(x)$ is hook-length & $c(x)$ content of $x$, a block in the diagram of $\lambda$
- Decompose the permutation module $M^{(2, 2)}$ into irreducible representations.
- What does s(n) = s(n) mean?
Related Questions in GOLDBACHS-CONJECTURE
- Landau's comment on validity of Goldbach's conjecture
- Goldbach's Conjecture and 1-1 correspondence
- Calculating probability of being $m$ and $(n-m)$ both prime in Goldbach conjecture
- Are there any counterexamples to a generalized Goldbach conjecture?
- Why Goldbach Conjecture is difficult to solve in $\mathbb{R}[x]$ and $\mathbb{C}[x]$?
- Decomposition $2^k$ into a sum of primes
- Lower bound for $g(n)$, the number of decompositions of 2n into ordered sums of two odd primes
- $O(1)$ algorithm for Goldbach partitions, assuming $\pi(n)$ is known for all $0<n<2n$?
- Why can't we prove Goldbach's conjecture with this method?
- Every integer greater than $0$ can be expressed as a sum of $a$'s and $b$'s, if and only if $a$ and $b$ have no common factor
Trending Questions
- Induction on the number of equations
- How to convince a math teacher of this simple and obvious fact?
- Find $E[XY|Y+Z=1 ]$
- Refuting the Anti-Cantor Cranks
- What are imaginary numbers?
- Determine the adjoint of $\tilde Q(x)$ for $\tilde Q(x)u:=(Qu)(x)$ where $Q:U→L^2(Ω,ℝ^d$ is a Hilbert-Schmidt operator and $U$ is a Hilbert space
- Why does this innovative method of subtraction from a third grader always work?
- How do we know that the number $1$ is not equal to the number $-1$?
- What are the Implications of having VΩ as a model for a theory?
- Defining a Galois Field based on primitive element versus polynomial?
- Can't find the relationship between two columns of numbers. Please Help
- Is computer science a branch of mathematics?
- Is there a bijection of $\mathbb{R}^n$ with itself such that the forward map is connected but the inverse is not?
- Identification of a quadrilateral as a trapezoid, rectangle, or square
- Generator of inertia group in function field extension
Popular # Hahtags
second-order-logic
numerical-methods
puzzle
logic
probability
number-theory
winding-number
real-analysis
integration
calculus
complex-analysis
sequences-and-series
proof-writing
set-theory
functions
homotopy-theory
elementary-number-theory
ordinary-differential-equations
circles
derivatives
game-theory
definite-integrals
elementary-set-theory
limits
multivariable-calculus
geometry
algebraic-number-theory
proof-verification
partial-derivative
algebra-precalculus
Popular Questions
- What is the integral of 1/x?
- How many squares actually ARE in this picture? Is this a trick question with no right answer?
- Is a matrix multiplied with its transpose something special?
- What is the difference between independent and mutually exclusive events?
- Visually stunning math concepts which are easy to explain
- taylor series of $\ln(1+x)$?
- How to tell if a set of vectors spans a space?
- Calculus question taking derivative to find horizontal tangent line
- How to determine if a function is one-to-one?
- Determine if vectors are linearly independent
- What does it mean to have a determinant equal to zero?
- Is this Batman equation for real?
- How to find perpendicular vector to another vector?
- How to find mean and median from histogram
- How many sides does a circle have?
Some thoughts
After the first split of $n$ into two or three unique primes, the problem becomes splitting larger primes into a list of smaller primes which is the problem I discuss below.
The minimum number of unique primes a larger prime can be split into is $2$ smaller primes, where $2$ is one of those unique primes e.g. $31=29+2$. If $2$ is not used the minimum number of primes a larger prime can be split into is $3$ primes e.g.
$$31=(23+5+3)=(19+7+5)=(17+11+3)=(13+11+7)$$
user477343 was playing with this idea here
We can now look at how to generate new primes by making the split into $3$ other primes and so on. The split into $2$ primes using $2$ can only be used once.
e.g. the smaller primes above split as follows
$$29=(19+7+3)=(17+7+5)=(13+11+5)$$ $$23=(13+7+3)=(11+7+5)$$ $$19=(17+2)=(11+5+3)$$ $$13=(11+2)$$ $$7=(5+2)$$
In the example of $31$ I first split this into 2 primes because that gives the largest available prime, that is $31=29+2$
I then use the split $29=(19+7+3)$ giving
$$31=19+7+3+2$$
The question is:
Is this "greedy prime" algorithm (taking the largest primes you can get from any recursive split into 2 or mainly 3 primes) always going to get you to a sum with the largest number of unique primes?
[Which includes the constraint to always decompose the largest prime in the new list first (the new list being generated immediately after a previous split).]