Questions tagged [number-theory]

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

Filter by
Sorted by
Tagged with
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

Theoretically output Graham's number

Graham's number G is defined in this way: ...
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 ...

1
2 3 4 5
8