Questions tagged [number-theory]
Number theory involves properties and relationships of numbers, primarily positive integers.
371
questions
32
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 ...
14
votes
14answers
448 views
Repetend length in 1/n
This problem is based on non-terminating, repeating decimal points.
Let \$n\$ be any positive integer \$(n > 1 \text{ and } n < 10000)\$, say \$7\$. Then, \$1/n = 1/7 = 0.142857142857142857...\$
...
21
votes
9answers
1k views
Count the Collatz survivors mod 2^n
Introduction
We have 22 Collatz conjecture-related challenges as of October 2020, but none of which cares about the restrictions on counter-examples, if any exists, to the conjecture.
Considering a ...
21
votes
12answers
2k views
Find a divisibility pattern
Background
Sometimes when I'm golfing a program, I'm presented with the following situation: I have an integer value \$x\$ on some fixed interval \$[a, b]\$, and I'd like to test whether it's in some ...
15
votes
26answers
436 views
\$n\$-perfect numbers
A positive integer \$x\$ is an \$n\$-perfect number if \$\sigma(x) = nx\$, where \$\sigma(x)\$ is the divisor sum function. For example, \$120\$ is a \$3\$-perfect number because its divisors sum to \$...
26
votes
19answers
3k views
Legendre's (Unsolved) Conjecture
Legendre's Conjecture is an unproven statement regarding the distribution of prime numbers; it asserts there is at least one prime number in the interval \$(n^2,(n+1)^2)\$ for all natural \$n\$.
The ...
19
votes
16answers
2k views
Find the discrete logarithm
Task
Write a program/function that when given 3 positive integers \$a, b\$ and \$m\$ as input outputs a positive integer \$x\$ such that \$a^x\equiv b\ (\text{mod}\ m)\$ or that no such \$x\$ exists.
...
14
votes
4answers
2k views
Archimedes's cattle problem
Compute, O friend, the number of the cattle of the sun which once grazed upon the plains of Sicily, divided according to color into four herds, one milk-white, one black, one dappled and one yellow. ...
23
votes
9answers
1k views
Split pythagorean triples into two sets
Task
Write a program/function that when given a positive integer \$n\$ splits the numbers from \$1\$ to \$n\$ into two sets, so that no integers \$a, b, c\$, satisfying \$a^2 + b^2 = c^2\$ are all in ...
19
votes
22answers
2k views
Zero the byte (eventually)
Given an infinite arithmetically-progressive¹ sequence, compute the minimum length of a prefix with a product divisible by 2^8.
Sample cases & reference implementation
Here is a reference ...
12
votes
10answers
865 views
Find all Belphegor primes
A Belphegor number is a number of the form \$(10^{n+3}+666)*10^{n+1}+1\$ (1{n zeroes}666{n zeroes}1) where \$n\$ is an non-negative integer. A Belphegor prime is a ...
15
votes
7answers
1k views
Generate *all* coprime tuples
Given integers k and n, generate a sequence of n unique k-tuples of pairwise coprime ...
15
votes
8answers
698 views
Multiple, Lit Plume, Mute Pill and so on
We say two positive integers are anagrams of each other if the digits in one of them (in decimal representation) can be rearranged to form the other. Leading zeros don't count. For example, 110020222 ...
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 ...
19
votes
16answers
1k views
(RGS 4/5) Inverting matrices modulo m
Task
Given an integer matrix M and a modulus m, find an inverse of M modulo ...
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 ...
10
votes
5answers
192 views
Count switches in a smallest square root sequence mod \$2^n\$
Definition
For any \$a\equiv1\ (\text{mod }8)\$ and \$n\ge3\$, there are exactly 4 roots to the equation \$x^2\equiv a\ (\text{mod }2^n)\$. Now, let \$x_k(a)\$ be the smallest root to the equation \$...
14
votes
18answers
1k views
Find the Inverse Neighbor Pairs
Definition
We say a pair of integers \$(a,b)\$, where \$0<a<b<N\$ and \$N\$ is an integer larger than 4, is an inverse neighbor pair respect to \$N\$ if \$ab\equiv1\text{ }(\text{mod }N)\$ ...
8
votes
4answers
378 views
Dirichlet Convolution Inverse
If \$f,g\colon \mathbb{Z}_{\geq 1} \to \mathbb{R}\$, the Dirichlet convolution of \$f\$ and \$g\$ is defined by
\$ \qquad\qquad\qquad \displaystyle (f*g)(n) = \sum_{d|n}f(d)g(n/d).\$
This ...
29
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.
...
27
votes
13answers
3k views
Who's next to me in the queue?
Problem 4 in the 2019 BMO, Round 1 describes the following setup:
There are \$2019\$ penguins waddling towards their favourite restaurant. As
the penguins arrive, they are handed tickets numbered ...
25
votes
12answers
2k views
Next Shared Totient
The totient function \$\phi(n)\$, also called Euler's totient function, is defined as the number of positive integers \$\le n\$ that are relatively prime to (i.e., do not contain any factor in common ...
28
votes
18answers
4k views
Fermat's Last Theorem, mod n
Fermat's Last Theorem, mod n
It is a well known fact that for all integers \$p>2\$, there exist no integers \$x, y, z>0\$ such that \$x^p+y^p=z^p\$. However, this statement is not true in ...
24
votes
10answers
2k views
Fermat's polygonal number theorem
Fermat's polygonal number theorem states that every positive integer can be expressed as the sum of at most \$n\$ \$n\$-gonal numbers. This means that every positive integer can be expressed as the ...
19
votes
9answers
1k views
Dividing Divisive Divisors
Given a positive integer \$n\$ you can always find a tuple \$(k_1,k_2,...,k_m)\$ of integers \$k_i \geqslant 2\$ such that \$k_1 \cdot k_2 \cdot ... \cdot k_m = n\$ and $$k_1 | k_2 \text{ , } k_2 | ...
12
votes
2answers
353 views
Interpreter for number theory, modulo n
A sentence of number theory (for our purposes) is a sequence of the following symbols:
0 and ' (successor) - successor means <...
13
votes
12answers
452 views
Find all \$k\$-smooth pairs
Introduction
In number theory, we say a number is \$k\$-smooth when its prime factors are all at most \$k\$. For example, 2940 is 7-smooth because \$2940=2^2\cdot3\cdot5\cdot7^2\$.
Here, we define a \$...
11
votes
12answers
1k views
Magical Modulo Squares
I'm a big fan of number theory. A big thing in number theory is modular arithmetic; the definition being \$a\equiv b\mod m\$ if and only if \$m\mid a-b\$. A fun thing to do is raising to powers: ...
23
votes
6answers
656 views
Congruent Numbers
Definitions:
A triangle is considered a right triangle if one of the inner angles is exactly 90 degrees.
A number is considered rational if it can be represented by a ratio of integers, i.e., ...
28
votes
26answers
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 of ...
17
votes
16answers
2k views
Do I have a twin with permutated remainders?
We define \$R_n\$ as the list of remainders of the Euclidean division of \$n\$ by \$2\$, \$3\$, \$5\$ and \$7\$.
Given an integer \$n\ge0\$, you have to figure out if there exists an integer \$0<k&...
29
votes
45answers
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-...
10
votes
10answers
649 views
Check type of an integer
You will receive an integer less than 2000000000 and bigger than -2000000000 and you have to test what type(s) of number this is out of:
...
12
votes
19answers
872 views
Find a Rocco number
I was asked this question in an interview but I was unable to figure out any solution. I don't know whether the question was right or not. I tried a lot but couldn't reach any solution. Honestly ...
16
votes
23answers
2k views
Find if a list is an ABC-triple
Three positive integers A, B, C are ABC-triple if they are coprime,
with A < B and satisfying the relation : A + B = C
Examples :
1, 8, 9 is an ABC-triple since ...
22
votes
13answers
3k views
Eight coins for the fair king
This is a "counterpart" of another puzzle, Eight coins for the fair king on Puzzling.SE.
You can read the above puzzle for the background. The details about this puzzle are as follows.
A set of 8 ...
18
votes
20answers
3k views
Is this number a hill number?
A hill number is a number that has the same digit in the first & the last, but that's not all. In a hill number the first digits are strictly increasing until the largest digit, and after the ...
21
votes
14answers
1k views
Dirichlet Convolution
The Dirichlet convolution is a special kind of convolution that appears as a very useful tool in number theory. It operates on the set of arithmetic functions.
Challenge
Given two arithmetic ...
13
votes
6answers
1k views
Ryley's Theorem
S. Ryley proved following theorem in 1825:
Every rational number can be expressed as a sum of three rational cubes.
Challenge
Given some rational number \$r \in \mathbb Q \$ find three rational ...
15
votes
11answers
902 views
Generate some rough numbers
Background
A number n can be described as B-rough if all of the prime factors of n strictly ...
19
votes
10answers
2k views
Repeat this GCD operation
Problem A3 from the 2008 Putnam competition says:
Start with a finite sequence \$a_1, a_2, \dots, a_n\$ of positive integers. If possible, choose two indices \$j < k\$ such that \$a_j\$ does not ...
18
votes
26answers
3k views
Is the word coprime?
Given a word, treat every letter as it's number in English alphabet (so a becomes 1, b becomes 2, ...
14
votes
10answers
1k views
Quadratic residues are so much fun!
Definitions
Quadratic residues
An integer \$r\$ is called a quadratic residue modulo \$n\$ if there exists an integer \$x\$ such that:
$$x^2\equiv r \pmod n$$
The set of quadratic residues modulo \$n\$...
15
votes
2answers
404 views
Impatient divisibility test
Your task is to write a program or function
that determines whether a number is divisible by another.
The catch is that it should give an answer as soon as possible,
even if not all digits of the ...
13
votes
7answers
762 views
Make the biggest and smallest numbers
Inspired by this post over on Puzzling. Spoilers for that puzzle are below.
Given three positive integers as input, (x, y, z), construct the inclusive range ...
15
votes
16answers
2k views
The number of ways a number is a sum of consecutive primes
Given an integer greater than 1, output the number of ways it can be expressed as the sum of one or more consecutive primes.
Order of summands doesn't matter. A sum can consist of a single number (...
12
votes
17answers
658 views
Compute the minimum \$a(n)>a(n-1)\$ such that \$a(1)+a(2)+\dots+a(n)\$ is prime (OEIS A051935)
Background
Consider the following sequence (A051935 in OEIS):
Start with the term \$2\$.
Find the lowest integer \$n\$ greater than \$2\$ such that \$2+n\$ is prime.
Find the lowest integer \$n'\$ ...
18
votes
7answers
625 views
Split the bits!
We define \$V(x)\$ as the list of distinct powers of \$2\$ that sum to \$x\$. For instance, \$V(35)=[32,2,1]\$.
By convention, powers are sorted here from highest to lowest. But it does not affect ...
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 ...
24
votes
13answers
3k views
Find the 10-adic cube root of 3
I like to think of a 10-adic number as a number that goes infinitely to the left, or an integer modulo a very very large power of 10.
Things carry infinitely to the left and vanish. To see what I ...
