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
26 votes
6 answers
2k views

The Coin Problem

Background The official currency of the imaginary nation of Golfenistan is the foo, and there are only three kinds of coins in circulation: 3 foos, 7 foos and 8 foos. One can see that it's not ...
user avatar
  • 42.2k
22 votes
18 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 ...
user avatar
  • 57.4k
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,342
71 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 ...
user avatar
  • 100k
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
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
34 votes
25 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,219
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,299
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
37 votes
29 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
19 votes
21 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
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 ...
user avatar
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
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
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,\...
user avatar
  • 64.8k
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
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
  • 461
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
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
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
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
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
12 votes
19 answers
964 views

Restricted Integer Partitions

Pk(n) means the number of partitions of n into exactly k parts. Given n and ...
user avatar
  • 5,321
11 votes
19 answers
1k 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
  • 219