Questions tagged [number-theory]

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

Filter by
Sorted by
Tagged with
15
votes
12answers
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} = ...
17
votes
12answers
809 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: ...
12
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
919 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
5k 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
640 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
925 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]{...
33
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
526 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
501 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
881 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
703 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
197 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
383 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 ...
26
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
10answers
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 | ...
13
votes
2answers
360 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
462 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
675 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., ...

1
2 3 4 5
8