All Questions
17
questions
3
votes
0
answers
86
views
Given $n\in\mathbb{N}_{\geqslant 2}$, find the partition $(a_1,...,a_k)\in\mathbb{N}^k:\sum_{i=1}^k a_i=n$ of $n$ that maximizes $\prod_{i=1}^k a_i$
I am a solving programming question in Leetcode in which, given a number $n \in \mathbb{N}_{\geqslant 2}$, I have to find $(a_1, ..., a_k) \in \mathbb{N}^k$ such that $k \in \mathbb{N}$, $2 \leqslant ...
1
vote
0
answers
295
views
An algorithm to generate all unique combinations of addends for a sum, from a range of small addends which are greater than 1?
I'm looking for an algorithm to generate all unique combinations of addends for a given sum, within a certain given range of addends. The size of the sum could range from two digits to five digits, ...
7
votes
2
answers
126
views
A sum of partitions
A friend of mine presented a problem I found interesting:
Compute the following: $$\sum_{n=0}^\infty\left(\prod_{k=1}^j(1+x^k)\right)[x^{mn}]$$ where $P(x)[x^n]$ denotes the $x^n$ coefficient of $P$...
-6
votes
1
answer
517
views
list partitions (python) - why is the index out of range? [closed]
General problem: Using the elements of some list of length $m* n$, create a list with $m$ sub-lists, each of length $n$.
In my case, $m= 10 > n=3$.
The final output should be a list ("lis1&...
-1
votes
1
answer
1k
views
Represent $N$ as the sum of exactly $K$ distinct positive integers
You are given two integers $N$ and $K$. Find all ways to represent $N$ as the sum of exactly $K$ distinct positive integers $x_1,x_2, \ldots,x_K$ — in other words.
$xi_>0$ for each valid $i$;
...
5
votes
1
answer
103
views
Sharing a pie evenly among an unknown number of people. [duplicate]
This is a question inspired by the question "Nine gangsters and a gold bar" on the Puzzling Stack Exchange.
Suppose you're throwing a party, and you know that either 7, 8, or 9 people will arrive. ...
0
votes
2
answers
119
views
Fastest algorithm for splitting an integer
I have a number $n$ in the range $1$ - $255$. What I'm trying to do is split $n$ into the shortest list of numbers $1$ -$16$ that add up to $n$. For example, let's say $n$ is $32$. Then, we could ...
1
vote
4
answers
668
views
Is there any Algorithm to Write a Number $N$ as a Sum of $M$ Natural Numbers?
I have a number $N$ (for example $N=64$).
Is there any algorithm to find all the feasible ways for writing the number $N$ as a sum of $M$ positive numbers?
(For example $M=16$) --- Repetition is ...
3
votes
0
answers
1k
views
How to make a canonical coin system so that greedy solution is the only optimal solution for change-making problem
Related to the paper: http://arxiv.org/PS_cache/arxiv/pdf/0809/0809.0400v1.pdf and coin-change problem in general.
We say that a coin system of coins canonical if the greedy algorithm to the coin ...
1
vote
1
answer
55
views
What is the name of the transform which finds the number of ways to make partitions of the given sizes?
I'm looking for the name of a transform which takes a sequence giving the number of 'prime' elements of a given size to the number of ways to make a number out of a sum of 'prime' elements, up to ...
4
votes
0
answers
93
views
Counting the number of partitions that are a distance d away from a fixed partition.
Given a positive integer $N \in \mathbb{Z}^{\geq 0}$ let $Partitions(N)$ denote the set of all partitions of $N$, where a tuple $\left(f_1,\ldots,f_N \right)$ is a partition of $N$ if $\sum_{i=1}^N ...
1
vote
1
answer
972
views
Find all Combinations of 1 and 2 which sums up to k.
I have two numbers $1$ and $2$. I have to print all ordered combinations which sums up to $k$.
For example:
$k=1$ Its only $1$.
$k=2$ It's ${1,1},{2}$.
$k=3$ Its ${1,1,1},{1,2},{2,1}$
What ...
2
votes
0
answers
127
views
Integer partitions without rotated solutions?
I'm searching for an algorithm to determine a list of all integer partitions of a number $n$ into a fixed number $m$ of summands (say $n=6$ and $m=4$), for instance to be stored into a list of (...
14
votes
2
answers
5k
views
For what coinage systems does a greedy algorithm not work in providing change?
For the United States coinage system, a greedy algorithm nicely allows for an algorithm that provides change in the least amount of coins.
However, for a coinage system with 12 cent coins, a greedy ...
6
votes
2
answers
2k
views
How can I reduce a number?
I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...