Questions tagged [integer-partitions]
For challenges related to the different ways of expressing an integer as a sum of positive integers.
61 questions
13
votes
9
answers
2k
views
Pennies to Dollars
Over on Puzzling a couple years ago, Hermant Agarwal proposed the following question:
In a certain country the following coins are in circulation: 1 cent, 2 cents, 5 cents, 10 cents, 20 cents, 50 ...
- 50.9k
15
votes
9
answers
1k
views
How many chains?
Given a positive integer \$n\$, a partition of \$n\$ is an ascending sequence of numbers that sum to \$n\$.
Given two partitions \$a\$ and \$b\$, \$a\$ is a refinement of \$b\$ iff \$b\$ can be ...
- 103k
21
votes
11
answers
1k
views
Superimposed triangles
Because \$k^2\$ is the sum of the \$k\$ first odd positive integers, squared numbers can be represented as ASCII-art triangles of height \$k\$ as follows:
...
- 206k
2
votes
2
answers
279
views
Binary expansion and partition numbers [closed]
Not sure if it's correct to ask such a question on this site, but let's try.
Let a(n) be a sequence of positive integer such that a(1) = 1. To reproduce the sequence a(n) through itself, use the ...
user104951
21
votes
4
answers
2k
views
Write a number as a sum of Fibonacci numbers
In 2009, Hannah Alpert described the "far-difference" representation, a novel way of representing integers as sums and differences of Fibonacci numbers according to the following rules:
...
- 8,145
16
votes
1
answer
400
views
Best partitioning set
Given an array of \$n\$ positive integers we will say its self-sum order is the number of ways to add elements from it to make \$n\$. We will count ways as distinct up to associativity. So \$1+(2+3)\$...
- 103k
13
votes
18
answers
791
views
Count the number of compositions of \$n\$ in which the greatest part is odd
A composition of an integer \$n\$ is a representation of \$n\$ as a sum of positive integers. For example the eight compositions of 4 are as follows:
...
user108721
6
votes
14
answers
1k
views
Number of ways to make an amount with coins
This is not a duplicate of Sum of combinations with repetition. This question considers 1+2 to be the same as 2+1. The other ...
- 18.7k
10
votes
18
answers
1k
views
Sum of partition numbers
The partition function:
In number theory, the partition function p(n) represents the number of possible partitions of a positive integer n into positive integers
For instance, p(4) = 5 because the ...
- 18.7k
16
votes
3
answers
460
views
Help me design an unfair laundry machine
There's a payment machine for laundry in my building which does a few frustrating things. The ones relevant to this challenge are:
It doesn't make change. So if you pay over the amount then you are ...
- 103k
15
votes
28
answers
2k
views
There's more than one way to skin a set
Given a set of positive integers \$ S \$, output the set of all positive integers \$ n \$ such that \$ n \$ can be made by summing a subset of \$ S \$ in more than one different way, i.e., that are ...
- 25.3k
3
votes
8
answers
499
views
Split given integer into a given number of integers, each within given bounds
Input variables:
(Names are just examples, they don't need to be named like this)
GrandTotal - integer to divide
SplitCount - ...
- 157
10
votes
6
answers
608
views
Mirror an integer... in NDos' way
NDos' Numeral System
NDos' numeral system is a numeral system invented by me. It represents every nonnegative integer by a binary tree. Given a nonnegative integer \$n\$:
If \$n=0\$, it is ...
- 7,371
20
votes
11
answers
2k
views
1 bit, 2 bits, 3 bits, …
Given a positive integer \$n\$, your task is to find out the number of partitions \$a_1+a_2+\dots+a_k=n\$ where each \$a_j\$ has exactly \$j\$ bits set.
For instance, there are \$6\$ such partitions ...
- 206k
15
votes
10
answers
901
views
AoCG2021 Day 14: Adjusting dancing program's period
Part of Advent of Code Golf 2021 event. See the linked meta post for details.
Related to AoC2017 Day 16. I'm using the wording from my Puzzling SE puzzle based on the same AoC challenge instead of the ...
- 79.3k
21
votes
12
answers
1k
views
Minimally prepend numbers to get a symmetric Young diagram
Background
A Young diagram is a diagram that represents a nonincreasing sequence of positive integers using left-justified rows of squares. As an example, 5, 4, 1 ...
- 79.3k
16
votes
5
answers
1k
views
Non-sums of distinct positive powers
There are 31 positive integers that cannot be expressed as the sum of 1 or more distinct positive squares:
...
- 50.9k
31
votes
30
answers
3k
views
Display a number in Toki Pona
Toki Pona is a constructed language with 137ish words, designed to constrain the speaker to expressing ideas in a simple and straightforward manner, reducing ideas to more essential forms.
Often, ...
- 411
22
votes
16
answers
2k
views
List array elements which can be summed from other elements
Consider an array of unique integers, with an arbitrary length greater than 2. It is sometimes possible to express elements of the array as the sum of at least two other elements. For example, if our ...
- 323
17
votes
17
answers
3k
views
Number of coins needed to make change
Relatable scenario: I'm going to the store to buy a single item, but only have a $100k bill. As a result, I need exactly $99,979 in change, and in the fewest coins/bills possible because I'm quite ...
- 19.3k
26
votes
9
answers
1k
views
Minimally Making Change
This problem is an extension of what happens to me on a regular basis: I have to have $1.00 in coins and have to be able to give change to somebody. I discovered rather quickly that the ideal coins to ...
- 363
13
votes
4
answers
1k
views
I ain't no Fortunate sum
The primorial \$p_n\#\$ is the product of the first \$n\$ primes. The sequence begins \$2, 6, 30, 210, 2310\$.
A Fortunate number, \$F_n\$, is the smallest integer \$m > 1\$ such that \$p_n\# + m\$ ...
- 50.9k
7
votes
11
answers
586
views
Constrained integer partition
Challenge
In this challenge, all numbers are in \$\mathbb{N}_0\$.
Create a function or program that, when given a number \$N\$ and a tuple of \$k\$ numbers \$(n_i)\$ (all ≤ \$N\$), returns the number ...
- 785
18
votes
14
answers
3k
views
Landau logarithm
Related: Landau's function (OEIS A000793)
Background
Landau's function \$g(n)\$ is defined as the largest order of permutation of \$n\$ elements, which is equal to \$\max(\operatorname{lcm}(a_1,a_2,\...
- 79.3k
11
votes
4
answers
367
views
Multigraphs with a given degree sequence
This challenge will give you an input of a degree sequence in the form of a partition of an even number. Your goal will be to write a program that will output the number of loop-free labeled ...
- 8,145
21
votes
12
answers
3k
views
Calculate Landau's function
Landau's function \$g(n)\$ (OEIS A000793) gives the maximum order of an element of the symmetric group \$S_n\$. Here, the order of a permutation \$\pi\$ is the smallest positive integer \$k\$ such ...
- 1,441
4
votes
5
answers
310
views
Is there are exactly one partition, given length of partition and maximum number?
It is Restricted Integer Partitions, but with maximum number.
Question
Three positive integers are given. First number is number to divide, second number is length of partition, and third number is ...
- 979
16
votes
3
answers
587
views
Optimize my wings order
This tweet lists the possible orders for Wings of a Chinese restaurant1:
When ordering Pizza I usually calculate what size gives me the best Pizza-price ratio which is a simple calculation. However ...
- 17k
18
votes
7
answers
692
views
Split the bits!
We define \$V(x)\$ as the list of distinct powers of \$2\$ that sum to \$x\$. For instance, \$V(35)=[32,2,1]\$.
By convention, powers are sorted here from highest to lowest. But it does not affect ...
- 206k
33
votes
24
answers
5k
views
Sum of five cubes
Given an integer, output five perfect cubes whose sum is that integer. Note that cubes can be positive, negative, or zero. For example,
...
- 150k
13
votes
22
answers
2k
views
Sum of combinations with repetition
Write the shortest code you can solving the following problem:
Input:
An integer X with 2 <= X and X <= 100
Output:
...
- 239
24
votes
12
answers
2k
views
Write numbers as a difference of Nth powers
Challenge
There are many numbers which can be expressed as the difference of two squares, or as the difference of two cubes, or maybe even higher powers. Talking about squares, there are various ways ...
- 5,350
20
votes
37
answers
3k
views
Find the largest number of distinct integers that sum to n
The Task
Given an input positive integer n (from 1 to your language's limit, inclusively), return or output the maximum number of distinct positive integers that ...
- 11.3k
8
votes
6
answers
498
views
Count of relatively prime partitions
The partitions of an integer N are all the combinations of integers smaller than or equal to N and higher than 0 which sum up to N.
A relatively prime partition is an integer partition, but whose ...
user74686
72
votes
26
answers
9k
views
Yo boy, must it sum
Every positive integer can be expressed as the sum of at most three palindromic positive integers in any base b≥5. Cilleruelo et al., 2017
A positive integer is palindromic in a given base if ...
- 107k
21
votes
23
answers
3k
views
How many partitions do I have?
The partition number of a positive integer is defined as the number of ways it can be expressed as a sum of positive integers. In other words, the number of integer partitions it has. For example, the ...
user70974
14
votes
11
answers
964
views
Self-summed numbers
Convert a number to a sum of digits
Not any sum: we need the shortest sum
Not any digits: you can use only digits of the number
Example
You will be given as input an integer ...
user73398
13
votes
19
answers
1k
views
Restricted Integer Partitions
\$P_k(n)\$ means the number of partitions of \$n\$ into exactly \$k\$ positive parts. Given \$n\$ and \$k\$, calculate \$P_k(n)\$.
Tip: \$P_k(n) = P_k(n−k) + P_{k−1}(n−1)\$, with initial values \$P_0(...
- 5,415
31
votes
30
answers
8k
views
Chicken McNugget Numbers
Description
Chicken McNugget numbers are numbers that can be expressed as a sum of \$6\$, \$9\$ or \$20\$ - the initial sizes of the famous Chicken McNuggets boxes sold by McDonald's. In that sum, a ...
- 1,103
16
votes
10
answers
2k
views
Fewest operations to 100
Overview
Given a list of digits, find the fewest operations to make 100
Input
A string of digits, which may or may not be in numerical order. The order of the digits cannot be changed, however plus ...
- 269
39
votes
19
answers
7k
views
11 = (1+2+3+4+5) - (1+2+3) + (6) - (4)
Given a positive integer N, your task is to return the number of steps required by the following algorithm to reach N:
Find the smallest triangular number Ti such that Ti ≥ N. Build the ...
- 206k
4
votes
0
answers
77
views
Code Golf - Print all unique ways of writing a number as a sum with a lexical order [duplicate]
I found about Code Golf after writing this program and decided to post the rules here so you can try it out too. I saw this, which is a less restrictive version of my question. I've got a bit more ...
- 201
22
votes
20
answers
6k
views
A penny saved is a penny
...counted!
You will pass your program a variable which represents a quantity of money in dollars and/or cents and an array of coin values. Your challenge is to output the number of possible ...
- 411
23
votes
27
answers
3k
views
List all ordered partitions of n
The challenge is to list all ordered partitions (composition (combinatorics)) of a given positive integer n. These are the lists of numbers from ...
- 461
23
votes
19
answers
2k
views
Calculate the partitions of N
Your challenge is simple: GIven an integer N, ouput every list of positive integers that sums to N. For example, if the input was 5, you should output
...
- 60.1k
17
votes
12
answers
3k
views
Strict partitions of a positive integer
OEIS A000009 counts the number of strict partitions of the integers. A strict partition of a nonnegative integer n is a set of positive integers (so no repetition ...
- 21.6k
38
votes
30
answers
4k
views
This Challenge Makes Cents
I know, the title cracks you up
Given an amount of money, output the fewest number of coins that make up that amount.
Examples
...
- 29.2k
22
votes
7
answers
494
views
Partitioning reciprocals
Given a number n > 77, write a program or function that finds a set of distinct positive integers such that the sum of the set equals n, and the sum of the reciprocals of the set equals 1.
Example ...
- 39.4k
39
votes
37
answers
4k
views
Sums of Consecutive Integers
Before anyone says anything, similar and similar. But this is not a dupe.
Some positive integers can be written as the sum of at least two consecutive positive integers. For example, ...
- 7,405
18
votes
11
answers
2k
views
Minimum number of numbers to sum to exactly n
First question here, don't yell at me if this is a duplicate or a bad challenge.
Introduction
I thought of this challenge myself, and it seems to be a good basic puzzle for beginner code-golfers. It ...
- 646