# Questions tagged [number-theory]

Number theory involves properties and relationships of numbers, primarily positive integers.

182 questions
Filter by
Sorted by
Tagged with
66k views

### Is this number a prime?

Believe it or not, we do not yet have a code golf challenge for a simple primality test. While it may not be the most interesting challenge, particularly for "usual" languages, it can be nontrivial in ...
• 210k
25k views

### Is this even or odd?

Note: There is not been a vanilla parity test challenge yet (There is a C/C++ one but that disallows the ability to use languages other than C/C++, and other non-vanilla ones are mostly closed too), ...
• 5,347
8k views

### Catalan Numbers

The Catalan numbers (OEIS) are a sequence of natural numbers often appearing in combinatorics. The nth Catalan number is the number of Dyck words (balanced strings of parenthesis or brackets such as <...
• 11.2k
8k views

### Greatest Common Divisor

Your task is to compute the greatest common divisor (GCD) of two given integers in as few bytes of code as possible. You may write a program or function, taking input and returning output via any of ...
• 717
4k views

### Least Common Multiple

The least common multiple of a set of positive integers A is the smallest postive integer B such that, for each ...
3k views

### Find the prime factors

In this task, you have to write a program, that computes the prime factors of a number. The input is a natural number 1 < n < 2^32. The output is a list of the prime factors of the number in the ...
• 10.1k
2k views

### Base Conversion With Strings

Introduction We've have a few base conversion challenges here in the past, but not many designed to tackle arbitrary length numbers (that is to say, numbers that are long enough that they overflow the ...
• 3,572
14k views

### Find the Smoothest Number

Your challenge is to find the smoothest number over a given range. In other words, find the number whose greatest prime factor is the smallest. A smooth number is one whose largest prime factor is ...
• 42k
1k views

### Find a Rocco number

I was asked this question in an interview but I was unable to figure out any solution. I don't know whether the question was right or not. I tried a lot but couldn't reach any solution. Honestly ...
• 231
5k views

### Calculate Euler's totient function

Background Euler's totient function φ(n) is defined as the number of whole numbers less than or equal to n that are relatively ...
• 2,272
8k views

### Find the smallest number that doesn't divide N

This challenge is simple enough that it's basically all in the title: you're given a positive integer N and you should return the smallest positive integer which is not a divisor of N. An example: the ...
• 197k
4k views

### Count sums of two squares

Given a non-negative number n, output the number of ways to express n as the sum of two squares of integers ...
• 145k
3k views

### List all multiplicative partitions of n

Given a positive number n, output all distinct multiplicative partitions of n in any convenient format. A multiplicative partition of n is a set of integers, all greater than one, such that their ...
• 39.1k
4k views

### Four Squares Together

Lagrange's four square theorem tells us any natural number can be represented as the sum of four square numbers. Your task is to write a program that does this. Input: A natural number (below 1 ...
• 12.1k
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 ...
• 59.3k
2k views

### Discrete Convolution or Polynomial Multiplication

Given two non empty lists of integers, your submission should calculate and return the discrete convolution of the two. Interestingly, if you consider the list elements as coefficients of polynomials, ...
• 43.8k
2k views

### Mixed Base Conversion

Background Most people on here should be familiar with several base systems: decimal, binary, hexadecimal, octal. E.g. in the hexadecimal system, the number 1234516 would represent ...
• 197k
9k views

### Coprimes up to N

Given a number n >= 2, output all the positive integers less than n where gcd(n, k) == 1 (...
• 7,850
3k views

### Pseudofactorial

There is a rather curious number which shows up sometimes in math problems or riddles. The pseudofactorial(N) is the least (i.e. lowest) common multiple of the numbers 1 through N; in other words, it'...
• 761
8k views

### Theoretically output Graham's number

Graham's number $G$ is defined in this way: \begin{align*} u(3,n,1) & = 3^n \\ u(3,1,m) & = 3 \\ u(3,n,m) & = u(3,u(3,n-1,m),m-1) \end{align*} Then, \begin{align*} g_1 & = u(3,3,4) \\...
• 49.8k
5k views

### Generate Recamán's sequence

Recamán's sequence (A005132) is a mathematical sequence, defined as such: A(0) = 0 A(n) = A(n-1) - n if A(n-1) - n > 0 and is new, else A(n) = A(n-1) + n A ...
• 2,073
6k views

### Count the divisors of a number

Introduction This is a very simple challenge: simply count the divisors of a number. We've had a similar but more complicated challenge before, but I'm intending this one to be entry-level. The ...
• 2,272
4k views

### Am I perfect (number)?

This is my first challenge! Background Perfect number is a positive integer, that is equal to the sum of all its divisors, except itself. So 6 is perfect number, ...
• 1,183
10k views

### List Prime Numbers [duplicate]

Introduction Prime numbers are simple, right? Well, now you get your chance to find out! Challenge You must write a program or function that takes an input n and ...
• 454
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 ...
• 105k
19k views

### Is this number evil?

Introduction In number theory, a number is considered evil if there are an even number of 1's in its binary representation. In today's challenge, you will be identifying whether or not a given number ...
• 1,642
5k views

### Hamming numbers

Hamming numbers are numbers which evenly divide a power of 60. Equivalently, their prime factors are all $\le 5$. Given a positive integer, print that many Hamming numbers, in order. Rules: Input ...
• 1,297
2k views

### Find largest prime which is still a prime after digit deletion

Over at https://math.stackexchange.com/questions/33094/deleting-any-digit-yields-a-prime-is-there-a-name-for-this the following question is asked. How many primes are there that remain prime after you ...
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 ...
655 views

### Perfect powers in more than one way?

Challenge Your task is to write a program or function which, given a positive integer $N$, finds all positive integers less than or equal to $N$ that can be expressed as a perfect power in more ...
• 4,577
1k views

### Generate all 4-perfect numbers

Your program or function should output all the 36 4-perfect numbers in increasing order separated by newlines. An n positive integer is a ...
• 20.9k
15k views

### Calculate the number of primes up to n

π(n) is the number of primes less than or equal to n. Input: a natural number, n. Output: π(n). Scoring: This is a fastest-code challenge. Score will be the sum of times for the score cases. I ...
• 3,215
7k views

### Calculate Phi (not Pi)

No, I don't mean $\phi = 1.618...$ and $π = 3.14159...$. I mean the functions. $\phi(x)$ is the number of integers less than or equal to $x$ that are relatively prime to $x$. $π(x)$ is ...
4k views

• 20.9k
3k views

### Shamir's Secret Sharing

Given n (the number of players), t (the threshold value), and s (the secret), output the <...
2k views

In Gödel, Escher, Bach, Douglas Hofstadter introduces an integer sequence which is commonly referred to as the figure-figure sequence: ...
• 197k
1k views

### Find the shortest Golomb rulers

Golomb rulers are sets of non-negative integers such that no two pairs of integers in the set are the same distance apart. For example, [0, 1, 4, 6] is a Golomb ...
• 38.8k