Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

Questions tagged [integer-partitions]

For challenges related to the different ways of expressing an integer as a sum of positive integers.

Filter by
Sorted by
Tagged with
14 votes
23 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 ...
user avatar
  • 18.7k
3 votes
7 answers
380 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 - ...
user avatar
10 votes
6 answers
474 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 ...
user avatar
  • 4,163
19 votes
10 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 ...
user avatar
  • 166k
15 votes
10 answers
779 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 ...
user avatar
  • 62.1k
20 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 ...
user avatar
  • 62.1k
15 votes
5 answers
927 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: ...
user avatar
28 votes
27 answers
2k 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, ...
user avatar
22 votes
16 answers
1k 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 ...
user avatar
  • 323
16 votes
16 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 ...
user avatar
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 ...
user avatar
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\$ ...
user avatar
7 votes
11 answers
486 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 ...
user avatar
18 votes
13 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,\...
user avatar
  • 62.1k
8 votes
3 answers
246 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 ...
user avatar
  • 8,097
21 votes
12 answers
2k 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 ...
user avatar
4 votes
5 answers
224 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 ...
user avatar
  • 969
17 votes
3 answers
495 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 ...
user avatar
  • 16.4k
18 votes
7 answers
633 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 ...
user avatar
  • 166k
33 votes
24 answers
4k 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, ...
user avatar
  • 137k
10 votes
17 answers
983 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: ...
user avatar
  • 209
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 ...
user avatar
  • 4,920
19 votes
37 answers
2k 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 ...
user avatar
7 votes
6 answers
362 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 ...
user avatar
69 votes
25 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 ...
user avatar
  • 99.4k
16 votes
16 answers
2k 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 ...
user avatar
12 votes
11 answers
875 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 ...
user avatar
8 votes
16 answers
814 views

Restricted Integer Partitions

Pk(n) means the amount of partitions of n into exactly k parts. Given n and ...
user avatar
  • 5,271
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 ...
user avatar
  • 269
39 votes
18 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 ...
user avatar
  • 166k
4 votes
0 answers
73 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 ...
user avatar
  • 201
21 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 ...
user avatar
23 votes
27 answers
2k 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 ...
user avatar
  • 451
21 votes
15 answers
1k 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 ...
user avatar
16 votes
11 answers
2k 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 ...
user avatar
  • 21.2k
37 votes
28 answers
3k 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 ...
user avatar
  • 28.4k
21 votes
6 answers
405 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 ...
user avatar
  • 38.7k
30 votes
22 answers
3k 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, ...
user avatar
  • 7,129
16 votes
11 answers
1k 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 ...
user avatar
18 votes
13 answers
640 views

Find the sets of sums

I've enjoyed reading this site; this is my first question. Edits are welcome. Given positive integers \$n\$ and \$m\$, compute all ordered partitions of \$m\$ into exactly \$n\$ positive integer parts,...
user avatar
27 votes
10 answers
1k views

Hook length product

A Young diagram is an arrangement of boxes in left-justified rows and top-justified columns. For each box, all the spaces above it and to its left are occupied. ...
user avatar
  • 137k
49 votes
14 answers
4k views

Fissile Numbers

I found this sequence while working on Evolution of OEIS, but never got around to posting it as an answer. After writing a reference implementation in Mathematica, I thought this is a fun exercise to ...
user avatar
17 votes
4 answers
3k views

Build an ASCII Fibonacci Clock

Someone built a really fancy clock using Fibonacci numbers, which looks really nice but is fairly unusable. Just the way we like it! Let's recreate this. The clock is made up of 5 sections ...
user avatar
19 votes
11 answers
2k views

Random Golf of the Day #3: Integer Partitions

About the Series First off, you may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges. You ...
user avatar
13 votes
4 answers
566 views

Nearest partition numbers

The number of partitions of an integer is the number of ways that integer can be represented as a sum of positive integers. For example: ...
user avatar
  • 2,181
12 votes
6 answers
1k views

Darts meets Codegolf

I think everyone is familiar with the game of darts. For those that don't understand the scores, here is a useful link. The board A dartboard can be compared to a pie cut in 20 pieces. Each piece is ...
user avatar
  • 2,609
2 votes
8 answers
1k views

Compute the number of ways how you can express a number as a sum [closed]

For a given natural number n, compute the number of ways how one can express n as a sum of positive natural numbers. For example,...
user avatar
  • 4,352
19 votes
15 answers
3k views

The minimum fibonacci challenge!

Challenge In this task you would be given an integer N (less than 106), find the minimum way in which you could sum to N using only Fibonacci numbers - this partition is called Zeckendorf ...
user avatar
  • 2,289
4 votes
9 answers
3k views

Partition of a positive integer N [closed]

Find the number of partitions of a positive integer n. Hope someone uses the explicit finite formula for the partition function defined in Jan Hendrik Brunier and Ken Ono paper here. ...
user avatar
  • 4,463