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
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 ...
6k views

### Calculate Phi (not Pi)

No, I don't mean ϕ = 1.618... and π = 3.14159.... I mean the functions. φ(x) is the number of integers less than or equal to <...
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 ...
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), ...
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 ...
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 ...
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: ...
5k 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 ...
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 ...
2k views

### Divisor skyline

For any positive integer k, let d(k) denote the number of divisors of k. For example, ...
7k views

### Theoretically output Graham's number

Graham's number G is defined in this way: ...
5k 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 ...
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 ...
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: ...
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 ...
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'...
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 ...
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 ...
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 ...
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 ...
6k 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. ...
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 ...
3k 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 ...
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....
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 ...
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, ...
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 ...
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 ...
3k views

### Is this number Loeschian?

A positive integer k is a Loeschian number if k can be expressed as i*i + j*j + i*j for <...
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 nth prime such that the prime - 1 is divisible by n. Explanation Here is an example so you understand the question, this is not necessarily the ...
954 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 ...
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 ...
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....
684 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 <...
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.de16 would represent ...
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 ...
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 ...
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 ...
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, ...
9k views

### Am I not good enough for you?

Background: The current Perfect Numbers challenge is rather flawed and complicated, since it asks you to output in a complex format involving the factors of the number. This is a purely decision-...
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 ...
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 ...
2k views

### Generate Keyboard Friendly Numbers

Most common computer keyboard layouts have the decimal digit keys 1234567890 running along at their top, above the keys for letters. Let a decimal digit's neighborhood be the set of digits from ...
1k 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 ...
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 ...
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, ...
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. ...