Questions tagged [number-theory]
Number theory involves properties and relationships of numbers, primarily positive integers.
400
questions
11
votes
2answers
261 views
Number of distinct shadow transforms
Background
Shadow transform of a 0-based integer sequence \$a(n)\$ is another 0-based integer sequence \$s(n)\$ defined with the following equation:
$$
s(n) = \sum_{i=0}^{n-1}{(1 \text{ if } n \text{ ...
15
votes
10answers
2k views
Project Euler 1: Multiples in constant time
The purpose of this challenge is to solve the original first Project Euler problem, but as the title suggests in constant time (with respect to the size of the interval).
Find the sum of all the ...
22
votes
14answers
2k views
Find the Erdős–Woods origin
Consider, for a given positive integer \$k\$, the sequence \$(a, a+1, a+2, ..., a+k)\$, where \$a\$ is some positive integer. Is there ever a pair \$a, k\$ such that for each element \$a+i\$ in the ...
27
votes
33answers
2k views
Mr. Binary Counterman
Mr. Binary Counterman, son of Mr. Boolean Masker & Mrs. Even Oddify, follows in his parents’ footsteps and has a peculiar way of keeping track of the digits.
When given a list of booleans, he ...
0
votes
4answers
106 views
Prime Factorization [duplicate]
Although there was a prime factors challenge posted ten years ago, it has tedious I/O and restricted time. In this challenge, your task is to write a program or function which takes an integer \$n \ge ...
18
votes
20answers
2k views
Gödel numbering of a string
Background
Gödel numbers are a way of encoding any string with a unique positive integer, using prime factorisations:
First, each symbol in the alphabet is assigned a predetermined integer code.
Then, ...
15
votes
13answers
2k views
Restricted-source, take this!
a.k.a. You Can Output Anything With Labyrinth Or Hexagony™
Challenge
In a recent restricted-source challenge, I could print any character with only half of the allowed digits with very small character ...
15
votes
17answers
1k views
Wolstenholme numbers
The generalised harmonic number of order \$m\$ of \$n\$ is
$$H_{n,m} = \sum^n_{k=1} \frac 1 {k^m}$$
In this challenge, we'll be considering the generalised harmonic numbers of order \$2\$:
$$H_{n,2} = ...
18
votes
13answers
851 views
Duplicates in “n × hamming weight of n” sequence
Background
The sequence in the title is A245788 "n times the number of 1's in the binary expansion of n" ("times" here means multiplication), which starts like this:
...
13
votes
25answers
1k views
Non-Hamming numbers
Hamming number (also known as regular number) is a number that evenly divides powers of 60.
We already have a task to do something with it.
This time we are going to do the opposite.
I define non-...
17
votes
16answers
2k views
How hyperperfect am I?
A \$k\$-hyperperfect number is a natural number \$n \ge 1\$ such that
$$n = 1 + k(\sigma(n) − n − 1)$$
where \$\sigma(n)\$ is the sum of the divisors of \$n\$. Note that \$\sigma(n) - n\$ is the ...
23
votes
19answers
1k views
Calculate Home Primes
The Home Prime of an integer \$n\$ is the value obtained by repeatedly factoring and concatenating \$n\$'s prime factors (in ascending order, including repeats) until reaching a fixed point (a prime). ...
18
votes
17answers
1k views
The meeker number sequence
The Meeker numbers are a 7 digit number in form of \$abcdefg\$, where \$a×b=10c+d\$ and \$d×e=10f+g\$. As an example \$6742612\$ is a meeker number, here \$6×7=10×4+2\$ and \$2×6=10×1+2\$, so it is a ...
18
votes
12answers
926 views
Sociable sequences
Sociable numbers are a generalisation of both perfect and amicable numbers. They are numbers whose proper divisor sums form cycles beginning and ending at the same number. A number is \$n\$-sociable ...
23
votes
27answers
2k views
Reconstruct an integer from its prime exponents
All integers \$n > 0\$ can be expressed in the form
$$n = \prod_{\text{prime } p} p^e = 2^{e_2} 3^{e_3} 5^{e_5} 7^{e_7} \cdots$$
This form is also known as it's prime factorisation or prime ...
29
votes
24answers
2k views
First sequence with no square differences
Consider the sequence \$(a_n)\$ defined in the following way.
\$a_0=0\$
For all \$n=1, 2, 3, \dots\$, define \$a_n\$ to be the smallest positive integer such that \$a_n-a_i\$ is not a square number, ...
16
votes
15answers
1k views
Generalise perfect numbers
Let \$\sigma(n)\$ represent the divisor sum of \$n\$ and \$\sigma^m(n)\$ represent the repeated application of the divisor function \$m\$ times.
Perfect numbers are numbers whose divisor sum equals ...
19
votes
7answers
1k views
Square root multiples
This code-challenge is based on OEIS sequence A261865.
\$A261865(n)\$ is the least integer \$k\$ such that some multiple of \$\sqrt{k}\$ is in the interval \$(n,n+1)\$.
The goal of this challenge is ...
19
votes
11answers
2k views
What's next, Achilles?
Powerful numbers are positive integers such that, when expressed as a prime factorisation:
$$a = p_1^{e_1} \times p_2^{e_2} \times p_3^{e_3} \cdots \times p_k^{e_k}$$
all exponents \$e_1, e_2, ...\$ ...
14
votes
21answers
1k views
N-dimensional pyramid numbers [duplicate]
Given two inputs, a number n and a dimension d, generate the nth d-dimensional pyramid number.
That was confusing, let me try again.
For d = 1, the numbers start 1,2,3,4,5 and is the number of points ...
24
votes
13answers
5k views
Is it a vampire number?
Repost and improvement of this challenge from 2011
A vampire number is a positive integer \$v\$ with an even number of digits that can be split into 2 smaller integers \$x, y\$ consisting of the ...
32
votes
16answers
6k views
Is it a lobster number?
Introduction
A "lobster number", by my own designation, is a number that contains within itself all of its prime factors. The "lobster" description was inspired by the recent ...
17
votes
13answers
3k views
Landau logarithm
Related: Landau's function (OEIS A000793)
Background
Landau's function \$g(n)\$ is defined as the largest order of permutation of \$n\$ elements, which is equal to \$\max(\operatorname{lcm}(a_1,a_2,\...
12
votes
7answers
646 views
Generalised Taxicab Numbers
\$\newcommand{T}[1]{\text{Ta}(#1)} \newcommand{Ta}[3]{\text{Ta}_{#2}^{#3}(#1)} \T n\$ is a function which returns the smallest positive integer which can be expressed as the sum of 2 positive integer ...
16
votes
4answers
938 views
(Almost) Solve Fermat's Last Theorem
It's a well-known fact that Fermat's Last Theorem is true. More specifically, that for any integer \$n \gt 2\$, there are no three integers \$a, b, c\$ such that
$$a^n + b^n = c^n$$
However, there are ...
23
votes
28answers
2k views
“Factorise” a quadratic
When learning to factorise quadratics in the form \$x^2 + ax + b\$, a common technique is to find two numbers, \$p, q\$ such that
$$pq = b \\
p + q = a$$
as, for such numbers, \$x^2 + ax + b = (x + p)(...
21
votes
27answers
2k views
Perfect radicals
Given a positive integer number \$n\$ output its perfect radical.
Definition
A perfect radical \$r\$ of a positive integer \$n\$ is the lowest integer root of \$n\$ of any index \$i\$:
$$r = \sqrt[i]{...
34
votes
23answers
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 ...
16
votes
15answers
537 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...\$
...
22
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 ...
22
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 ...
17
votes
27answers
513 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 \$...
27
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.
...
15
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
23answers
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
888 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 ...
16
votes
8answers
707 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 ...
37
votes
49answers
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 ...
11
votes
5answers
201 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)\$ ...
9
votes
4answers
385 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 ...
30
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.
...
28
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 ...
26
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 ...
