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.

350 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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), ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 (...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
2k views

### Divisor skyline

For any positive integer k, let d(k) denote the number of divisors of k. For example, ...
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 ...
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 ...
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: ...
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 ...
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 ...
1k views

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 ...
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: ...
2k views

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 ...
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. ...
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 ...