Questions tagged [number-theory]
Number theory involves properties and relationships of numbers, primarily positive integers.
378
questions
216
votes
310answers
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 ...
72
votes
28answers
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 ...
70
votes
230answers
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), ...
69
votes
13answers
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 ...
69
votes
23answers
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 ...
69
votes
25answers
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 ...
59
votes
41answers
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 ...
53
votes
88answers
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 ...
51
votes
43answers
7k views
Coprimes up to N
Given a number n >= 2, output all the positive integers less than n where gcd(n, k) == 1 (...
51
votes
11answers
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 ...
50
votes
47answers
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 ...
48
votes
32answers
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 \...
48
votes
16answers
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 ...
44
votes
34answers
3k 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, ...
43
votes
104answers
15k 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 ...
43
votes
19answers
7k views
41
votes
69answers
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 ...
41
votes
72answers
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:
<...
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 ...
38
votes
29answers
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'...
38
votes
14answers
4k views
Incrementing Gray Codes
Introduction
A Gray Code is an alternative to binary representation in which a number is incremented by toggling only one bit, rather than a variable amount of bits. Here are some gray codes along ...
37
votes
34answers
3k views
Replace twos with threes
Given a positive integer n write some code to take its prime factorization and replace all of its factors of 2 with 3.
For ...
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 ...
36
votes
49answers
6k 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 ...
36
votes
23answers
3k views
Abandon all squares, ye who divide me
Definitions
A perfect square is an integer which can be expressed as the square of another integer. For example, 36 is a perfect square because ...
36
votes
20answers
7k views
Compute the Carmichael function
Task description
In number theory, the Carmichael function λ takes a positive integer n and returns the least positive integer k so that the k-th power of each integer coprime to n equals 1 modulo n.
...
36
votes
23answers
2k views
Sum the powers that be
A simple but hopefully not quite trivial challenge:
Write a program or function that adds up the kth powers dividing a number n....
35
votes
6answers
2k views
Can you reach this number by doubling and rearranging?
Inspired by this question on Math.SE.
Starting with 1 you can repeatedly perform one of the following two operations:
Double the number.
or
Rearrange its digits ...
34
votes
45answers
3k views
(RGS 1/5) Binary multiples
A binary multiple of a positive integer k is a positive integer n such that n is written ...
34
votes
35answers
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 ...
34
votes
31answers
2k views
Sum of Modulo Sums
Given an integer n > 9, for each possible insertion between digits in that integer, insert an addition + and evaluate. Then, ...
34
votes
15answers
2k views
One-zero dividend
Challenge description
For every positive integer n there exists a number having the form of 111...10...000 that is divisible by ...
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 ...
33
votes
60answers
4k views
GET your dubs together
On 4chan, a popular game is get. Every post on the site gets a sequential post ID. Since you can't influence or determine them, people try to guess (at least a part of) their own post number, usually ...
33
votes
22answers
3k views
Narcissistic loop lengths
A narcissistic number is a natural number which is equal to the sum of its digits when each digit is taken to the power of the number digits. For example \$8208 = 8^4 + 2^4 + 0^4 + 8^4\$, so is ...
33
votes
20answers
2k views
Finding The nth Prime such that the prime - 1 is divisible by n
Problem
The goal is as the title says to find the \$n\$th prime such that \$\text{the prime}-1\$ is divisible by \$n\$.
Explanation
Here is an example so you understand the question, this is not ...
33
votes
8answers
965 views
Can square tree rings be generated from primes?
Apparently yes! In three easy steps.
Step 1
Let f(n) denote the prime-counting function (number of primes less than or equal to n).
Define the integer sequence s(n) as follows. For each positive ...
32
votes
6answers
2k views
1, 2, 3, 14… or is it 15?
A well known song by the Irish rock band U2 starts with the singer Bono saying "1, 2, 3, 14" in Spanish ("uno, dos, tres, catorce").
There are various theories as to the significance of those numbers....
32
votes
6answers
690 views
Score Tarzan's Olympic Vine-Swinging Routine
Olympic vine-swingers perform their routines in standard trees. In particular, Standard Tree n has vertices for 0 up through <...
32
votes
2answers
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\...
31
votes
38answers
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 ...
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 ...
31
votes
9answers
5k views
Make 1s using a bunch of 1s
Your task is to form an expression equaling \$ 11111111111 \text{ (11 ones)} \$ using only the following characters: 1+(). Keep in mind that the result is in base ...
31
votes
14answers
2k views
Array Escape - get out of there
One day you awake only to find yourself caught in an array. You try to just walk out of there, taking one index at the time, but it seems there are other rules:
The array is completely filled with ...
31
votes
12answers
3k views
That's a prime… almost
If you've ever learned about primes in math class, you've probably have had to, at one point, determine if a number is prime. You've probably messed up while you were still learning them, for example, ...
31
votes
10answers
1k views
Find the dot product of Rationals
I was at a friend's house for dinner and they suggested the idea of a "Prime-factor vector space". In this space the positive integers are expressed as a vector such that the nth element in the ...
30
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.
...
30
votes
13answers
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 ...
30
votes
6answers
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 ...
30
votes
2answers
2k views
Addition on Elliptic Curves
Disclaimer: This does not do any justice on the rich topic of elliptic curves. It is simplified a lot. As elliptic curves recently got a lot of media attention in the context of encryption, I wanted ...
