Skip to main content

Questions tagged [number-theory]

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

Filter by
Sorted by
Tagged with
236 votes
370 answers
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 ...
Dennis's user avatar
  • 210k
79 votes
261 answers
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), ...
Matthew Roh's user avatar
  • 5,347
43 votes
57 answers
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 <...
a spaghetto's user avatar
  • 11.2k
47 votes
85 answers
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 ...
Mike Shlanta's user avatar
36 votes
49 answers
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 ...
user avatar
24 votes
26 answers
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 ...
FUZxxl's user avatar
  • 10.1k
16 votes
9 answers
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 ...
Mwr247's user avatar
  • 3,572
62 votes
44 answers
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 ...
isaacg's user avatar
  • 42k
12 votes
19 answers
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 ...
vijayscode's user avatar
35 votes
44 answers
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 ...
jqkul's user avatar
  • 2,272
59 votes
100 answers
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 ...
Martin Ender's user avatar
51 votes
48 answers
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 ...
xnor's user avatar
  • 145k
31 votes
15 answers
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 ...
orlp's user avatar
  • 39.1k
22 votes
16 answers
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 ...
qwr's user avatar
  • 12.1k
22 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 ...
DJMcMayhem's user avatar
  • 59.3k
21 votes
16 answers
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, ...
flawr's user avatar
  • 43.8k
13 votes
7 answers
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 ...
Martin Ender's user avatar
55 votes
50 answers
9k views

Coprimes up to N

Given a number n >= 2, output all the positive integers less than n where gcd(n, k) == 1 (...
Riker's user avatar
  • 7,850
46 votes
44 answers
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'...
Tony Ruth's user avatar
  • 761
45 votes
20 answers
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) \\...
Leaky Nun's user avatar
  • 49.8k
34 votes
49 answers
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 ...
James Williams's user avatar
33 votes
68 answers
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 ...
jqkul's user avatar
  • 2,272
27 votes
20 answers
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, ...
Zereges's user avatar
  • 1,183
22 votes
26 answers
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 ...
Elliot A.'s user avatar
  • 454
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 ...
Luis Mendo's user avatar
  • 105k
57 votes
136 answers
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 ...
Amphibological's user avatar
26 votes
14 answers
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 ...
grokus's user avatar
  • 1,297
23 votes
4 answers
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 ...
user avatar
19 votes
23 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
13 votes
5 answers
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 ...
fR0DDY's user avatar
  • 4,577
5 votes
6 answers
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 ...
randomra's user avatar
  • 20.9k
74 votes
16 answers
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 ...
Liam's user avatar
  • 3,215
72 votes
28 answers
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 ...
El'endia Starman's user avatar
45 votes
36 answers
4k views

Is this number Loeschian?

A positive integer \$k\$ is a Loeschian number if \$k\$ can be expressed as \$i^2 + j^2 + i\times j\$ for \$i\$, \$j\$ integers. For example, the first positive Loeschian numbers are: \$1\$ (\$i=1, ...
Luis Mendo's user avatar
  • 105k
40 votes
32 answers
5k views

Is it a Proth number?

A Proth number, named after François Proth, is a number that can be expressed as $$N = k \times 2^n + 1$$ Where \$k\$ is an odd positive integer and \$n\$ is a positive integer such that \$2^n > k\$...
DJMcMayhem's user avatar
  • 59.3k
38 votes
53 answers
3k views

(RGS 1/5) Binary multiples [duplicate]

A binary multiple of a positive integer k is a positive integer n such that n is written ...
RGS's user avatar
  • 14.1k
36 votes
41 answers
4k views

Is it a Mersenne Prime?

A number is a Mersenne Prime if it is both prime and can be written in the form 2n-1, where n is a positive integer. Your task is to, given any positive integer, determine whether or not it is a ...
FlipTack's user avatar
  • 14.7k
33 votes
2 answers
2k views

Standardise a Phinary Number

Background Most people on here should be familiar with a few integer base systems: decimal, binary, hexadecimal, octal. E.g. in the hexadecimal system, a number \$abc.de_{16}\$ would represent $$a\...
Martin Ender's user avatar
33 votes
17 answers
6k views

Is it a lobster number?

Introduction A "lobster number", by my own designation, is a number that contains within itself all of its prime factors. The "lobster" description was inspired by the recent ...
IronEagle's user avatar
  • 439
27 votes
22 answers
2k views

Co-primality and the number pi

Introduction Number theory is full of wonders, in the form of unexpected connections. Here's one of them. Two integers are co-prime if they have no factors in common other than 1. Given a number \$N\$,...
Luis Mendo's user avatar
  • 105k
24 votes
28 answers
5k views

The Möbius Function

The Möbius function is an important number theoretic function. Your submission should accept a positive integer \$n\$ and return the value of the Möbius function evaluated at \$n\$. Definition The ...
flawr's user avatar
  • 43.8k
23 votes
11 answers
3k views

Highly composite numbers

A highly composite number is a positive integer that has more divisors than any smaller positive integer has. This is OEIS sequence A002182. Its first 20 terms are ...
Luis Mendo's user avatar
  • 105k
23 votes
6 answers
5k views

Chinese Remainder Theorem

The Chinese Remainder Theorem tells us that we can always find a number that produces any required remainders under different prime moduli. Your goal is to write code to output such a number in ...
xnor's user avatar
  • 145k
22 votes
19 answers
2k views

Is this a consecutive-prime/constant-exponent number?

A while ago, I had a look at the prime factorization of 27000: 27000 = 23 × 33 × 53 There are two special things about that: consecutive-prime: The primes are consecutive: 2 is the 1st prime, 3 is ...
wastl's user avatar
  • 3,903
20 votes
11 answers
1k views

Period of the decimal representation

Write a function which takes a single positive integer n and returns the period of the decimal representation of 1/n. Test cases: ...
Howard's user avatar
  • 23.5k
19 votes
12 answers
892 views

Compute modular inverse

Given two positive numbers \$x\$ and \$n\$ with \$x<2^n\$, write the shortest possible function to compute \$x^{-1} \mod 2^n\$. In other words, find \$y\$ such that \$xy=1 \mod 2^n\$. Your ...
Keith Randall's user avatar
17 votes
14 answers
3k views

Shamir's Secret Sharing

Given n (the number of players), t (the threshold value), and s (the secret), output the <...
user avatar
17 votes
9 answers
2k views

Generate Hofstadter's Figure-Figure Sequence

In Gödel, Escher, Bach, Douglas Hofstadter introduces an integer sequence which is commonly referred to as the figure-figure sequence: ...
Martin Ender's user avatar
15 votes
3 answers
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 ...
Fatalize's user avatar
  • 38.8k
13 votes
9 answers
1k views

Find the repetend of the decimal representation!

In this challenge 2 years ago, we found the period of a unit fraction (1/n where n is a natural number). Now, your task is to write a program/function to find the ...
Leaky Nun's user avatar
  • 49.8k