Skip to main content
Code Golf

Questions tagged [number-theory]

Ask Question

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

479 questions
Newest Active Bountied Unanswered
Filter by
Sorted by
Tagged with
14 votes
6 answers
706 views

Background In 1796, 18-year-old Carl Friedrich Gauss proved that a regular 17-gon can be constructed with compass and straightedge — the first such discovery in over 2,000 years. The stonemason tasked ...
Jan Popelka's user avatar
  • 151
-1 votes
1 answer
139 views

You have to code in python, and the number generated by your code must be bigger than all other current submissions. You need to make your code as small as possible, it has to terminate but you can ...
IAmNotLarry's user avatar
  • 1
15 votes
17 answers
2k views

Problem 4 of the 2025 International Mathematical Olympiad asked (paraphrased): Let \$f(n)\$ be the sum of the largest three proper divisors of \$n\$, that is divisors excluding \$n\$ itself. For ...
xnor's user avatar
  • 150k
24 votes
6 answers
3k views

Objective Compute \$\pi\$ using nothing but \$i\$ (\$\sqrt{-1}\$). Guidelines ONLY exponentiation and multiplication may be used (i.e. \$i^i\$ or \$ii\$) No additional symbols may be used (so no ...
WarpPrime's user avatar
  • 521
8 votes
18 answers
4k views

Related, but not dupe (Asking about the n-th k-smooth number whereas I'm only asking if a certain number is 5-smooth.)Source: Partially inspired by Leetcode's 5-smooth Number problem, but partially ...
CrSb0001's user avatar
  • 867
21 votes
28 answers
4k views

Challenge Write a program (function) that given a nonnegative integer input, output whether the number can be represented as the sum of 3 square numbers. That is, the program should, given nonnegative ...
Shieru Asakoto's user avatar
  • 6,478
11 votes
7 answers
2k views

Definitions: A sparse ruler, or simply a ruler, is a strict increasing finite sequence of nonnegative integers starting from 0, called marks. A ruler is complete if the set of all distances it can ...
Sophia Antipolis's user avatar
  • 1,742
11 votes
13 answers
1k views

For prime p, the factorization tree is a single vertex in just one way so that a(p) = 1. For composite n, the two subtrees at n are a split of n into two factors n = d * (n/d), without order, so that $...
Sophia Antipolis's user avatar
  • 1,742
14 votes
5 answers
754 views

Output a grid of characters visualizing the decomposition of a number into a sum of four perfect squares. Challenge Given a nonnegative integer \$0 \le n \le 2^{30}\$, output a \$2^k \times 2^k\$ ...
bb94's user avatar
  • 3,898
16 votes
6 answers
1k views

The Mahler-Popken complexity, \$C(N)\$, of a positive integer, \$N\$, is the smallest number of ones (\$1\$) that can be used to form \$N\$ in a mathematical expression using only the integer* \$1\$ ...
Jonathan Allan's user avatar
  • 115k
14 votes
13 answers
1k views

Task Output the sequence that precisely consists of the following integers in increasing order: the 2nd and higher powers of 10 (\$10^i\$ where \$i \ge 2\$), the squares of powers of 10 times 2 or 3 (...
Bubbler's user avatar
  • 79.3k
11 votes
4 answers
2k views

Follow-up of my previous challenge, inspired by @emanresu A's question, and proven possible by @att (Mathematica solution linked) For the purposes of this challenge, a 1-2-3-5-7... sequence is an ...
Tbw's user avatar
  • 3,053
22 votes
15 answers
2k views

For the purposes of this challenge, a 1-2-3 sequence is an infinite sequence of increasing positive integers such that for any positive integer \$n\$, exactly one of \$n, 2n,\$ and \$3n\$ appears in ...
Tbw's user avatar
  • 3,053
15 votes
16 answers
1k views

Imagine you have a positive integer number \$n\$. Let \$m\$ be the number obtained by reversing \$n\$'s digits. If \$m\$ is a whole multiple of \$n\$, then \$n\$ is said to be a reverse divisible ...
Trivaxy's user avatar
  • 697
19 votes
26 answers
2k views

The tetration operation consists of repeated exponentiation, and it is written ↑↑. For instance, 3↑↑3 =3 ^(3^3) = 3^27 = 7,625,597,484,987 A tetrate of two is an ...
izzyg's user avatar
  • 42.3k
11 votes
10 answers
2k views

Background As noted in this question, for all positive integers \$n>2\$ there exists at least one Egyptian fraction representation (EFR) of \$n\$ distinct positive integers \$a_{1} < a_{2} < \...
Max Lonysa Muller's user avatar
  • 211
4 votes
5 answers
498 views

Definitions The common methods to generate consecutive composites are $$\overbrace{(n+1)! + 2, \ (n+1)! + 3, \ \ldots, \ (n+1)! + (n+1)}^{\text{n composites}}$$ $$\overbrace{n!+2,n!+3,...,n!+n}^{\text{...
vengy's user avatar
  • 2,309
13 votes
20 answers
1k views

Given two numbers \$x,y > 2, x≠y \$ output all integers \$m\$ such that $$ x + y \equiv x \cdot y \pmod m $$ $$ x \cdot y > m > 2 $$ Input Two integers Output A list of integers Test cases <...
pacman256's user avatar
  • 5,405
9 votes
13 answers
1k views

Input An integer k composed of 1 and 2, with at least 3 digits and at most 200 digits. ...
Sunny's user avatar
  • 2,004
3 votes
28 answers
2k views

Challenge Generate \$n-1\$ consecutive composite numbers using this prime gap formula $$n!+2,n!+3,...,n!+n$$ Input An integer \$n\$ such that \$3 \leq n \leq 50 \$. Output Sequence of \$n-1\$ ...
vengy's user avatar
  • 2,309
17 votes
20 answers
2k views

Challenge Determine how many integer lattice points there are in an ellipse $$\frac{x^2}{a^2} + \frac{y^2}{b^2} \leq 1$$ centered at the origin with width \$2a\$ and height \$2b\$ where integers \$a, ...
vengy's user avatar
  • 2,309
17 votes
2 answers
691 views

Given a constructible point \$(x, y) \in \mathbb R^2\$, output the steps required to construct \$(x, y)\$ Constructing a point Consider the following "construction" of a point \$(\alpha, \...
caird coinheringaahing's user avatar
  • 50.9k
3 votes
2 answers
386 views

The Euclidean GCD Algorithm is an algorithm that efficiently computes the GCD of two positive integers, by repeatedly subtracting the smaller number from the larger number until they become equal. It ...
emanresu A's user avatar
  • 46.2k
10 votes
5 answers
2k views

Input The code should take an integer \$n\$ between 1 and 1000. Output The code should output positive integers with \$n\$ bits. Accompanying each integer should be its full factorization. Each ...
Simd's user avatar
  • 3,167
7 votes
4 answers
873 views

Related. Given a number \$n\$, Euler's totient function, \$\varphi(n)\$ is the number of integers up to \$n\$ which are coprime to \$n\$. That is, no number bigger than \$1\$ divides both of them. For ...
Command Master's user avatar
  • 10.9k
21 votes
11 answers
2k views

Given a number \$n\$, we have its sum of divisors, \$\sigma(n)\ = \sum_{d | n} {d}\$, that is, the sum of all numbers which divide \$n\$ (including \$1\$ and \$n\$). For example, \$\sigma(28) = 1 + 2 +...
Command Master's user avatar
  • 10.9k
11 votes
12 answers
1k views

We've had powerful numbers, yes, but what about highly powerful numbers? Highly powerful numbers Let \$n\$ be a positive integer in the form $$n = p_1^{e_{p_1}(n)}p_2^{e_{p_2}(n)}\cdots p_k^{e_{p_k}(n)...
caird coinheringaahing's user avatar
  • 50.9k
23 votes
31 answers
3k views

A powerful number is a positive integer \$n\$ such that for every prime \$p\$ that divides \$n\$, \$p^2\$ also divides \$n\$. Or equivalently, \$n\$ is powerful if and only if it can be written in the ...
alephalpha's user avatar
  • 51.9k
1 vote
0 answers
140 views

I am working on a code to print all semimagic squares [1] of a given size. I am working with the following definition: An \$n\times n\$ consists of numbers \$1,2,\cdots, n^2\$. All numbers must be ...
ananta's user avatar
  • 111
15 votes
19 answers
2k views

Description Write a program or function that takes in a positive integer \$n\$ as input and outputs all Sophie Germain primes that are safe primes less than or equal to \$n\$. A prime number \$p\$ is ...
aitzazisstuffed's user avatar
  • 1,970
15 votes
16 answers
2k views

Description "Imtiaz Germain primes" is not a technical name in Mathematics, but my weird creation, in the memoir of the famous mathematician Sophie Germain. These primes can be generated by ...
aitzazisstuffed's user avatar
  • 1,970
20 votes
26 answers
2k views

Generate the shortest possible code in any programming language that can generate all Pythagorean triples with all values not exceeding a given integer limit. A Pythagorean triple is a set of three ...
aitzazisstuffed's user avatar
  • 1,970
13 votes
25 answers
1k views

The Prime Signature of a number is the list of the exponents of the prime factors of a number, sorted in descending order (exponents of 0 are ignored). Inspired by ...
Samathingamajig's user avatar
  • 525
8 votes
9 answers
2k views

The Riemann R function is as follows: $$R (x)=\sum _{n=1}^{\infty } \frac{\mu (n) \text{li}\left(x^{1/n}\right)}{n}.$$ This uses the Möbius function as well as the logarithmic integral. From Wikipedia,...
Simd's user avatar
  • 3,167
21 votes
4 answers
2k views

In 2009, Hannah Alpert described the "far-difference" representation, a novel way of representing integers as sums and differences of Fibonacci numbers according to the following rules: ...
Peter Kagey's user avatar
  • 8,175
24 votes
20 answers
2k views

The pyramid begins with the row 1 1. We'll call this row 1. For each subsequent row, start with the previous row and insert the current row number between every ...
chunes's user avatar
  • 27.9k
13 votes
22 answers
1k views

Let \$n\$ be some positive integer. We say that \$n\$ is of even kind if the prime factorisation of \$n\$ (counting duplicates) has an even number of integers. For example, \$6 = 2 \times 3\$ is of ...
caird coinheringaahing's user avatar
  • 50.9k
13 votes
15 answers
2k views

Your task is to write a program that calculates the amount of different ways to display any given whole positive number using the following rules: Meet the 'advanced binary system': Any whole positive ...
Squareoot's user avatar
  • 163
14 votes
10 answers
2k views

In 1988, the International Mathematical Olympiad (IMO) featured this as its final question, Question Six: Let \$a\$ and \$b\$ be positive integers such that \$ab + 1\$ divides \$a^2 + b^2\$. Show ...
Jonathan Allan's user avatar
  • 115k
15 votes
14 answers
5k views

Background "Fly straight, dammit" (OEIS A133058) is a sequence of integers, which has these rules: \$a_0 = a_1 = 1\$ \$a_n = a_{n-1}+n+1\$ if \$gcd(a_{n-1}, n) = 1\$ Otherwise, \$a_n = \...
The Thonnu's user avatar
  • 18.7k
16 votes
14 answers
2k views

The persistence of a number \$x = d_1d_2d_3...d_n\$, with \$d_1 \ne 0\$, under some function \$f : \mathbb N_0 \times \mathbb N_0 \to \mathbb N_0\$ is defined as the number of applications of \$f\$ to ...
caird coinheringaahing's user avatar
  • 50.9k
10 votes
18 answers
1k views

The partition function: In number theory, the partition function p(n) represents the number of possible partitions of a positive integer n into positive integers For instance, p(4) = 5 because the ...
The Thonnu's user avatar
  • 18.7k
22 votes
23 answers
2k views

easy mode of my previous challenge A perfect number is a positive integer whose sum of divisors (except itself) is equal to itself. E.g. 6 (1 + 2 + 3 = 6) and 28 (1 + 2 + 4 + 7 + 14 = 28) are perfect. ...
Bubbler's user avatar
  • 79.3k
17 votes
8 answers
3k views

A perfect number is a positive integer whose sum of divisors (except itself) is equal to itself. E.g. 6 (1 + 2 + 3 = 6) and 28 (1 + 2 + 4 + 7 + 14 = 28) are perfect. A sublime number (OEIS A081357) is ...
Bubbler's user avatar
  • 79.3k
5 votes
2 answers
366 views

Given a universe of \$v\$ elements, a Kirkman triple system is a set of \$(v-1)/2\$ classes each having \$v/3\$ blocks each having three elements, so that every pair of elements appears in exactly ...
Parcly Taxel's user avatar
  • 4,749
27 votes
35 answers
3k views

Given a positive integer n, output all of its anti-divisors in any order. From OEIS A006272: Anti-divisors are the numbers that do not divide a number by the ...
Bubbler's user avatar
  • 79.3k
2 votes
0 answers
439 views

It is known that any natural number can be decomposed into the sum of three triangular numbers (assuming 0 is triangular), according to Fermat's Polygonal Number Theorem. Your task is to come up with ...
Study's user avatar
  • 45
16 votes
3 answers
461 views

There's a payment machine for laundry in my building which does a few frustrating things. The ones relevant to this challenge are: It doesn't make change. So if you pay over the amount then you are ...
Wheat Wizard's user avatar
  • 103k
3 votes
11 answers
621 views

Given \$a\$ and \$b\$, both odd \$n+1\$-bit integers, compute \$a/b\$ to a precision of \$n+1\$ bits in the 2-adic integers. That is, compute \$c\$ such that \$a = bc\, (\mathop{\rm mod} 2^{n+1})\$. \$...
NoLongerBreathedIn's user avatar
  • 1,897
21 votes
24 answers
3k views

This is a cross-post of a problem I posted to anarchy golf: http://golf.shinh.org/p.rb?tails Given two integers \$ n \$ and \$ k \$ \$ (0 \le k \le n) \$, count the number of combinations of \$ n \$ ...
dingledooper's user avatar
  • 23.4k

1
2 3 4 5
…
10