# Questions tagged [number-theory]

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

378 questions
Filter by
Sorted by
Tagged with
51k 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 ...
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 ...
22k 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), ...
12k 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 ...
7k views

### Well that's odd… no wait, that's even!

Preamble Integers are always either even or odd. Even integers are divisible by two, odd integers are not. When you add two integers you can infer whether the result will be even or odd based on ...
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 ...
12k 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 ...
6k 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 ...
7k views

### Coprimes up to N

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

### Bringing a pair of integers to equality

This was inspired by a math problem I saw somewhere on the internet but do not remember where (UPDATE: The original problem was found on the math riddles subreddit with a proof provided that it is ...
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 ...
2k views

### Divisor skyline

For any positive integer $k$, let $d(k)$ denote the number of divisors of $k$. For example, $d(6)$ is $4$, because $6$ has $4$ divisors (namely $1, 2, 3, 6$). Given a positive integer \...
6k views

### A naturally occurring prime generator

There are quite a large number of prime generating functions. Pretty much all of them are constructed and are based on the sieve of Eratosthenes, the Möbius function or the Wilson's theorem and are ...
3k views

1k views

### Pascal's Column Sums

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

### Are you lost yet?

Your task is to implement integer sequence A130826: an is the smallest positive integer such that an - n is an entire multiple of 3 and twice the number of divisors of (an - n) / 3 gives the nth ...
2k views