Questions tagged [number-theory]

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

Filter by
Sorted by
Tagged with
3 votes
5 answers
350 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
  • 1,603
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
  • 3,300
7 votes
10 answers
921 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 Smartie's user avatar
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
  • 1,603
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
  • 1,603
15 votes
2 answers
567 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
338 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
  • 37.1k
9 votes
5 answers
1k 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,760
6 votes
4 answers
551 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
22 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
  • 47.5k
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
996 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
8 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,760
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,659
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
  • 23.4k
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
  • 17.9k
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
847 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
  • 17.9k
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
  • 74.9k
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
  • 74.9k
5 votes
2 answers
270 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,717
24 votes
33 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
  • 74.9k
2 votes
0 answers
357 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
396 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
  • 97.6k
3 votes
11 answers
495 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.6k
15 votes
13 answers
956 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.5k
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
  • 97.6k
7 votes
12 answers
576 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
  • 97.6k
1 vote
1 answer
515 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
990 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,355
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,355
23 votes
34 answers
3k views

Sum of two squares

Given a nonnegative integer \$n\$, determine whether \$n\$ can be expressed as the sum of two square numbers, that is \$\exists a,b\in\mathbb Z\$ such that \$n=a^2+b^2\$. ...
hakr14's user avatar
  • 4,974
35 votes
19 answers
3k views

Egyptian fraction representations of 1

An Egyptian fraction is a representation of a rational number using the sum of distinct unit fractions (a unit fraction is of the form \$ \frac 1 x \$ where \$ x \$ is a positive integer). For all[1] ...
pxeger's user avatar
  • 23.5k
12 votes
6 answers
1k views

High throughput prime numbers

This challenge is inspired by the High throughput Fizz Buzz challenge. The goal Generate a list of prime numbers up to 10,000,000,000,000,000. The output of primes should be in decimal digits followed ...
xiver77's user avatar
  • 2,355
6 votes
2 answers
790 views

Write the most optimized assembly program to detect a prime number (from a bigger range!)

This is the second version of the task. The original task had a defect that the given range of integers was too small. This was pointed out by @harold that other methods couldn't defeat the way of ...
xiver77's user avatar
  • 2,355
4 votes
3 answers
237 views

Order of an algebraic number

Consider some arbitrary polynomial with integer coefficients, $$a_n x^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0 = 0$$ We'll assume that \$a_n \ne 0\$ and \$a_0 \ne 0\$. The solutions to this polynomial ...
caird coinheringaahin g's user avatar
8 votes
10 answers
943 views

AoCG2021 Day 24: Is the bus company cheating?

Part of Advent of Code Golf 2021 event. See the linked meta post for details. Related to AoC2020 Day 13, Part 2. Why Bubbler isn't posting this; Why Riker isn't posting this A shuttle bus service ...
pxeger's user avatar
  • 23.5k
10 votes
10 answers
582 views

Primes dividing consecutive composites

Grimm's conjecture states that, for any set of consecutive composite numbers \$n+1, n+2, ..., n+k\$, there exist \$k\$ distinct primes \$p_i\$, such that \$p_i\$ divides \$n+i\$ for each \$1 \le i \le ...
caird coinheringaahin g's user avatar

1
2 3 4 5
10