Questions tagged [number-theory]
Number theory involves properties and relationships of numbers, primarily positive integers.
416
questions
7
votes
4answers
460 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 ...
5
votes
2answers
378 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 ...
8
votes
10answers
896 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 ...
8
votes
8answers
493 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 ...
asked Dec 19 '21 at 18:30
caird coinheringaahing
45.8k9 gold badges95 silver badges311 bronze badges
10
votes
7answers
206 views
Multiplicity of Shared Totients
Euler's totient function, \$\varphi(n)\$, counts the number of integers \$1 \le k \le n\$ such that \$\gcd(k, n) = 1\$. For example, \$\varphi(9) = 6\$ as \$1,2,4,5,7,8\$ are all coprime to \$9\$. ...
asked Dec 18 '21 at 18:25
caird coinheringaahing
45.8k9 gold badges95 silver badges311 bronze badges
14
votes
10answers
766 views
AoCG2021 Day 14: Adjusting dancing program's period
Part of Advent of Code Golf 2021 event. See the linked meta post for details.
Related to AoC2017 Day 16. I'm using the wording from my Puzzling SE puzzle based on the same AoC challenge instead of the ...
26
votes
10answers
2k views
Sum powers to n
Each natural number (including 0) can be written as a sum of distinct powers of integers (with a minimum exponent of 2). Your task is to output the smallest power required to represent \$n\$.
For ...
25
votes
17answers
2k views
AoCG2021 Day 4: Infinite Elves and infinite houses 2
Part of Advent of Code Golf 2021 event. See the linked meta post for details.
Related to AoC2015 Day 20, Part 1.
Here's why I'm posting instead of Bubbler and why not emanresuA
To keep the Elves busy,...
19
votes
1answer
406 views
How to solve the LCM in 50 bytes of Python
I've recently stumbled upon a Russian site called acmp.ru, in which one of the tasks, HOK, asks us to find the LCM of two positive integers. The full statement, translated to English is as follows:
...
14
votes
19answers
2k views
Harmonic divisor numbers
Consider the \$4\$ divisors of \$6\$: \$1, 2, 3, 6\$. We can calculate the harmonic mean of these numbers as
$$\frac 4 {\frac 1 1 + \frac 1 2 + \frac 1 3 + \frac 1 6} = \frac 4 {\frac {12} 6} = \frac ...
9
votes
1answer
237 views
Concatenation Coincidence
This code-golf challenge (and test cases) are inspired by the work of Project Euler users amagri, Cees.Duivenvoorde, and oozk, and Project Euler Problem 751. (And no, this isn't on OEIS). Sandbox
A ...
14
votes
15answers
2k views
Print Gobar Primes
Gobar primes (A347476) are numbers which give a prime number when 0's and 1's are interchanged in their binary representation.
For example, \$10 = 1010_2\$, and if we flip the bits, we get \$0101_2 = ...
15
votes
25answers
1k views
Count occurrences in Pascal's Triangle
Pascal's triangle is a triangular diagram where the values of two numbers added together produce the one below them.
This is the start of it:
...
20
votes
22answers
3k views
Is it a row of Pascal's triangle?
Pascal's triangle is a triangular diagram where the values of two numbers added together produce the one below them.
This is the start of it:
...
17
votes
15answers
2k views
Euler's numerus idoneus
Euler's numerus idoneus, or idoneal numbers, are a finite set of numbers whose exact number is unknown, as it depends on whether or not the Generalized Riemann hypothesis holds or not. If it does, ...
17
votes
10answers
1k views
How many iterations to reach the sequence?
Let's define a function \$f\$ which, given a positive integer \$x\$, returns the sum of:
\$x\$
the smallest digit in the decimal representation of \$x\$
the highest digit in the decimal ...
12
votes
2answers
273 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
3k 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 ...
asked Jun 25 '21 at 23:52
caird coinheringaahing
45.8k9 gold badges95 silver badges311 bronze badges
28
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
143 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 ...
asked May 31 '21 at 3:48
ta Radvylf srik su shilani
14.8k2 gold badges53 silver badges137 bronze badges
20
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} = ...
asked Apr 25 '21 at 20:21
caird coinheringaahing
45.8k9 gold badges95 silver badges311 bronze badges
19
votes
13answers
870 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 ...
asked Apr 16 '21 at 21:21
caird coinheringaahing
45.8k9 gold badges95 silver badges311 bronze badges
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
937 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 ...
asked Mar 11 '21 at 17:07
caird coinheringaahing
45.8k9 gold badges95 silver badges311 bronze badges
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 ...
18
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, ...\$ ...
asked Feb 22 '21 at 19:53
caird coinheringaahing
45.8k9 gold badges95 silver badges311 bronze badges
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
654 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 ...
asked Dec 28 '20 at 20:33
caird coinheringaahing
45.8k9 gold badges95 silver badges311 bronze badges
16
votes
4answers
964 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 ...
asked Dec 17 '20 at 21:49
caird coinheringaahing
45.8k9 gold badges95 silver badges311 bronze badges
23
votes
28answers
3k views
"Factorise" a quadratic [duplicate]
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)(...
asked Dec 12 '20 at 22:33
caird coinheringaahing
45.8k9 gold badges95 silver badges311 bronze badges
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
557 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...\$
...
23
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
526 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 \$...
asked Sep 13 '20 at 21:41
caird coinheringaahing
45.8k9 gold badges95 silver badges311 bronze badges
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.
...
