A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [number-theory]

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

Filter by
Sorted by
Tagged with
46
votes
44answers
3k 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 ...
198
votes
295answers
46k 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 ...
27
votes
25answers
2k views

Which Day of Christmas is it?

Preface In the well known carol, The Twelve Days of Christmas, the narrator is presented with several gifts each day. The song is cumulative - in each verse, a new gift is added, with a quantity one ...
67
votes
212answers
20k 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), ...
7
votes
4answers
363 views

Dirichlet Convolution Inverse

If \$f,g\colon \mathbb{Z}_{\geq 1} \to \mathbb{R}\$, the Dirichlet convolution of \$f\$ and \$g\$ is defined by \$ \qquad\qquad\qquad \displaystyle (f*g)(n) = \sum_{d|n}f(d)g(n/d).\$ This ...
20
votes
14answers
1k views

Dirichlet Convolution

The Dirichlet convolution is a special kind of convolution that appears as a very useful tool in number theory. It operates on the set of arithmetic functions. Challenge Given two arithmetic ...
25
votes
13answers
3k views

Who's next to me in the queue?

Problem 4 in the 2019 BMO, Round 1 describes the following setup: There are \$2019\$ penguins waddling towards their favourite restaurant. As the penguins arrive, they are handed tickets numbered ...
20
votes
9answers
3k views

Hamming numbers

Given a positive integer, print that many hamming numbers, in order. Rules: Input will be a positive integer \$n \le 1,000,000 \$ Output should be the first n terms of https://oeis.org/A051037 ...
28
votes
5answers
2k views

Longest Prime Sums

Sandbox There are special sets S of primes such that \$\sum\limits_{p\in S}\frac1{p-1}=1\$. In this challenge, your goal is to find the largest possible set of primes that satisfies this condition. ...
15
votes
16answers
2k views

The number of ways a number is a sum of consecutive primes

Given an integer greater than 1, output the number of ways it can be expressed as the sum of one or more consecutive primes. Order of summands doesn't matter. A sum can consist of a single number (...
26
votes
59answers
3k 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 ...
22
votes
12answers
2k views

Next Shared Totient

The totient function \$\phi(n)\$, also called Euler's totient function, is defined as the number of positive integers \$\le n\$ that are relatively prime to (i.e., do not contain any factor in common ...
27
votes
35answers
4k 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 ...
11
votes
23answers
1k views

Find the positive divisors!

Definition A number is positive if it is greater than zero. A number (A) is the divisor of another number (B) if ...
27
votes
18answers
4k views

Fermat's Last Theorem, mod n

Fermat's Last Theorem, mod n It is a well known fact that for all integers \$p>2\$, there exist no integers \$x, y, z>0\$ such that \$x^p+y^p=z^p\$. However, this statement is not true in ...
28
votes
14answers
1k 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 ...
66
votes
13answers
10k 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 ...
19
votes
2answers
727 views

Write it into number theory style

Write a mathematical statement, using the symbols: There exists at least one non-negative integer (written as E, existential ...
37
votes
28answers
4k views

Is it a Proth number?

A Proth number, named after François Proth, is a number that can be expressed as N = k * 2^n + 1 Where k is an odd positive ...
24
votes
10answers
2k views

Fermat's polygonal number theorem

Fermat's polygonal number theorem states that every positive integer can be expressed as the sum of at most \$n\$ \$n\$-gonal numbers. This means that every positive integer can be expressed as the ...
34
votes
88answers
14k 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 ...
40
votes
65answers
6k 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 ...
46
votes
27answers
2k views

Divisor skyline

For any positive integer k, let d(k) denote the number of divisors of k. For example, ...
67
votes
23answers
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 ...
40
votes
7answers
2k views

Sharing (characters) is Caring!

Overview Consider the following task: Given a positive integer n > 0, output its integer square root. The integer square root of a number n is the largest value of x where x2 ≤ n, usually ...
40
votes
68answers
5k views

Am I divisible by double the sum of my digits?

Given a positive integer as input, your task is to output a truthy value if the number is divisible by the double of the sum of its digits, and a falsy value otherwise (OEIS A134516). In other words: ...
24
votes
22answers
3k views

Bertrand's Primes

Bertrand's Postulate states that for every integer n ≥ 1 there is at least one prime p such that n < p ≤ 2n. In order to verify this theorem for n < 4000 ...
24
votes
29answers
2k views

Pascal's Triangle (Sort of)

Most everyone here is familiar with Pascal's Triangle. It's formed by successive rows, where each element is the sum of its two upper-left and upper-right neighbors. Here are the first ...
17
votes
8answers
1k views

Dividing Divisive Divisors

Given a positive integer \$n\$ you can always find a tuple \$(k_1,k_2,...,k_m)\$ of integers \$k_i \geqslant 2\$ such that \$k_1 \cdot k_2 \cdot ... \cdot k_m = n\$ and $$k_1 | k_2 \text{ , } k_2 | ...
11
votes
12answers
1k views

Magical Modulo Squares

I'm a big fan of number theory. A big thing in number theory is modular arithmetic; the definition being \$a\equiv b\mod m\$ if and only if \$m\mid a-b\$. A fun thing to do is raising to powers: ...
26
votes
3answers
2k views

Residue Number System

In the vein of large number challenges I thought this one might be interesting. In this challenge, we will be using the Residue Number System (RNS) to perform addition, subtraction, and ...
10
votes
1answer
224 views

Interpreter for number theory, modulo n

A sentence of number theory (for our purposes) is a sequence of the following symbols: 0 and ' (successor) - successor means <...
16
votes
9answers
863 views

Last k digits of Powers of 2

For any integer \$r\$, there exists a power of 2 each of whose last \$r\$ digits are either 1 or 2. Given \$r\$, find the smallest \$x\$ such that \$2^x\bmod{10^r}\$ consists of only 1 or 2. For ...
29
votes
16answers
2k views

Primitive Pythagorean Triples

(related) A Pythagorean Triple is a list (a, b, c) that satisfies the equation a2 + b2 = c2. A Primitive Pythagorean Triple (PPT) is one where ...
20
votes
39answers
4k 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 ...
28
votes
26answers
2k views

Fundamental Solution of the Pell Equation

Given some positive integer \$n\$ that is not a square, find the fundamental solution \$(x,y)\$ of the associated Pell equation $$x^2 - n\cdot y^2 = 1$$ Details The fundamental \$(x,y)\$ is a pair ...
14
votes
15answers
1k views

Am I a Pillai prime?

A Pillai prime is a prime number \$p\$ for which there exists some positive \$m\$ such that \$(m! + 1) \equiv 0 \:(\text{mod } p)\$ and \$p \not\equiv 1\:(\text{mod }m)\$. In other words, an ...
20
votes
11answers
1k views

Find the Emirps!

An emirp is a non-palindromic prime which, when reversed, is also prime. The list of base 10 emirps can be found on OEIS. The first six are: ...
17
votes
16answers
2k views

Do I have a twin with permutated remainders?

We define \$R_n\$ as the list of remainders of the Euclidean division of \$n\$ by \$2\$, \$3\$, \$5\$ and \$7\$. Given an integer \$n\ge0\$, you have to figure out if there exists an integer \$0<k&...
7
votes
14answers
720 views

Another amicable number problem

Two numbers are said to be 'amicable' or 'friends' if the sum of the proper divisors of the first is equal to the second, and viceversa. For example, the proper divisors of 220 are: 1, 2, 4, 5, 10, ...
16
votes
14answers
998 views

Sum Chain Sequence

Sequence: We start at 1. We first add the current 1-indexed value to the previous number in the sequence. Then we apply the following mathematical operations in ...
28
votes
26answers
3k views

Is this a Smith number?

Challenge description A Smith number is a composite number whose sum of digits is equal to the sum of sums of digits of its prime factors. Given an integer N, ...
18
votes
37answers
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 ...
23
votes
23answers
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 ...
13
votes
12answers
410 views

Find all \$k\$-smooth pairs

Introduction In number theory, we say a number is \$k\$-smooth when its prime factors are all at most \$k\$. For example, 2940 is 7-smooth because \$2940=2^2\cdot3\cdot5\cdot7^2\$. Here, we define a ...
31
votes
42answers
3k 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 ...
23
votes
6answers
485 views

Factorize a Gaussian integer

A Gaussian integer is a complex number whose real and imaginary parts are integers. Gaussian integers, like ordinary integers, can be represented as a product of Gaussian primes, in a unique manner. ...
18
votes
13answers
719 views

Goldbach partitions

The Goldbach conjecture states that every even number greater than two can be expressed as the sum of two primes. For example, 4 = 2 + 2 6 = 3 + 3 8 = 5 + 3 ...
21
votes
5answers
514 views

Congruent Numbers

Definitions: A triangle is considered a right triangle if one of the inner angles is exactly 90 degrees. A number is considered rational if it can be represented by a ratio of integers, i.e., ...
34
votes
21answers
3k views

The Arithmetic Derivative

The derivative of a function is a cornerstone of mathematics, engineering, physics, biology, chemistry, and a large number of other sciences as well. Today we're going to be calculating something only ...