Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [number-theory]

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

Filter by
Sorted by
Tagged with
16 votes
6 answers
956 views

Golfing the complexity with subtraction

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
12 votes
10 answers
749 views

*Trivial* near-repdigit perfect powers

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
  • 76.8k
10 votes
4 answers
2k views

Output a 1-2-3-5-7... sequence

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
  • 2,083
21 votes
15 answers
2k views

Output a 1-2-3 sequence

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
  • 2,083
15 votes
16 answers
1k views

Pretty Palintiples

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
  • 487
18 votes
26 answers
2k views

Is it a tetrate of two?

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 ...
isaacg's user avatar
  • 42k
11 votes
10 answers
1k views

Egyptian fraction representations of 1 without prime denominators

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 Muller's user avatar
4 votes
5 answers
399 views

Generate a sequence of \$n\$ consecutive composite numbers

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,163
12 votes
20 answers
1k views

Modular Equivalence

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
  • 4,045
7 votes
10 answers
962 views

Make 1's and 2's composite

Input An integer k composed of 1 and 2, with at least 3 digits and at most 200 digits. ...
Sny's user avatar
  • 429
4 votes
25 answers
2k views

Consecutive Composite Numbers

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,163
17 votes
19 answers
1k views

Ellipse Lattice Point Counter

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,163
16 votes
2 answers
587 views

Construct this point

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 coinheringaahin g's user avatar
3 votes
2 answers
343 views

Visualise the Euclidean GCD [duplicate]

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
  • 38.4k
9 votes
5 answers
2k views

Random factorized numbers

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
  • 2,926
6 votes
4 answers
565 views

Sums of Euler's totient function in sublinear time

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
20 votes
11 answers
2k views

Sums of sum of divisors in sublinear time

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
11 votes
12 answers
1k views

The all-high powerful numbers

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 coinheringaahin g's user avatar
23 votes
31 answers
3k views

Is this a powerful number?

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
  • 48.2k
1 vote
0 answers
111 views

Print all semimagic squares [closed]

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

Sophie Safe primes

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 ...
Aitzaz Imtiaz's user avatar
15 votes
16 answers
2k views

Imtiaz Germain Primes

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 ...
Aitzaz Imtiaz's user avatar
18 votes
24 answers
2k views

Shortest code to generate all Pythagorean triples up to a given limit

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 ...
Aitzaz Imtiaz's user avatar
13 votes
25 answers
999 views

Find the Prime Signature

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
6 votes
9 answers
1k views

Implement the Riemann R function

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
  • 2,926
20 votes
4 answers
2k views

Write a number as a sum of Fibonacci numbers

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,689
24 votes
20 answers
2k views

"Prime" pyramid

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
  • 24.2k
13 votes
22 answers
1k views

Even and Odd kinds

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 coinheringaahin g's user avatar
13 votes
15 answers
2k views

Advanced Binary Number System

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
  • 145
14 votes
10 answers
1k views

IMO Question Six with a difference

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
15 votes
14 answers
5k views

The "Fly straight, dammit" sequence

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.1k
16 votes
14 answers
2k views

Persistence of a number

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 coinheringaahin g's user avatar
10 votes
18 answers
863 views

Sum of partition numbers

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.1k
21 votes
22 answers
2k views

The second even sublime number

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
  • 76.8k
17 votes
8 answers
3k views

An algorithm to find even sublime numbers

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
  • 76.8k
5 votes
2 answers
276 views

Generate a Kirkman triple system

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
  • 3,737
24 votes
34 answers
3k views

Anti-divisors of a number

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
  • 76.8k
2 votes
0 answers
369 views

Decompose number N into the sum of three triangular numbers [closed]

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
15 votes
3 answers
398 views

Help me design an unfair laundry machine

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
  • 98.8k
3 votes
11 answers
507 views

Divide by an odd number, 2-adically

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
21 votes
24 answers
3k views

Consecutive coin flips

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
  • 22.7k
15 votes
13 answers
1k views

Count alternating permutations

An alternating permutation is a permutation of the first \$ n \$ integers \$ \{ 1 ... n \} \$, such that adjacent pairs of values in the permutation alternate between increasing and decreasing (or ...
pxeger's user avatar
  • 23.7k
24 votes
19 answers
4k views

What's the best die to roll?

The "standard" polyhedral game dice have 4, 6, 8, 10, 12 and 20 sides. (Yes, I know that there are two 10-sided dice which together make a d100, but we're ignoring that right now.) If I want ...
Wheat Wizard's user avatar
  • 98.8k
7 votes
12 answers
577 views

Calculate the Lowest Even-Harmonic of the Values in a List

PROBLEM For a list of numbers, list: Find the lowest possible integer, x, which is optimally close to the whole number even-...
Austin Prater's user avatar
18 votes
12 answers
1k views

In between fractions

Given two positive integer fractions \$x\$ and \$y\$ such that \$x < y\$, give the fraction \$z\$ with the smallest positive integer denominator such that it is between \$x\$ and \$y\$. For example ...
Wheat Wizard's user avatar
  • 98.8k
1 vote
1 answer
523 views

Best performance on x/(y+z) + y/(x+z) + z/(x+y) = N

Consider the equation $$\frac x {y+z} + \frac y {x+z} + \frac z {x+y} = n$$ for positive integers \$x, y, z\$ and \$n \ge 4\$. Your code will receive \$n\$ as an input, and output three integers \$x, ...
Number Basher's user avatar
19 votes
17 answers
3k views

Join my exclusive friendly club!

Two or more positive integers are said to be "friendly" if they have the same "abundancy". The abundancy of an positive integer \$n\$ is defined as $$\frac {\sigma(n)} n,$$ where \$...
caird coinheringaahin g's user avatar
16 votes
15 answers
1k views

Average-ignorant sets of integers

Recently a friend of mine posed the following: What subset of the integers satisfies the condition if distinct a and b are in the subset, their average is not in the subset? I know the set of non-0 ...
Binary198's user avatar
  • 515
14 votes
2 answers
1k views

Find the magic numbers to divide a number without division

An integer \$x\in[0,2^{32}-1]\$ divided by an integer \$d\in{[1,2^{31}]}\$ will produce an integral quotient \$q\$ and a remainder \$r\$, so that \$x=d\times q+r\$. Any \$q\$, in fact, can be ...
xiver77's user avatar
  • 2,365
25 votes
16 answers
3k views

Convert to base i - 1

Given \$ i = \sqrt{-1} \$, a base-\$ (i - 1) \$ binary number \$ N \$ with \$ n \$ binary digits from \$ d_{0} \$ to \$ d_{n - 1} \$ satisfies the following equation. $$ N = d_{n - 1} (i - 1) ^ {n - 1}...
xiver77's user avatar
  • 2,365

1
2 3 4 5
10