Questions tagged [number-theory]
Number theory involves properties and relationships of numbers, primarily positive integers.
431
questions
15
votes
3
answers
299
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 ...
- 88.3k
1
vote
10
answers
330
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})\$. \$...
- 1,281
19
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 \$ ...
- 17.6k
13
votes
12
answers
702
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 ...
- 21.4k
23
votes
18
answers
3k
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 ...
- 88.3k
7
votes
12
answers
547
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-...
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 ...
- 88.3k
1
vote
1
answer
404
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, ...
- 1,252
18
votes
15
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 \$...
- 47.2k
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 ...
- 513
14
votes
2
answers
536
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 ...
- 2,213
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}...
- 2,213
21
votes
33
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\$.
...
- 3,941
32
votes
18
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] ...
- 21.4k
11
votes
6
answers
895
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 ...
- 2,213
6
votes
2
answers
464
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 ...
- 2,213
4
votes
2
answers
142
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 ...
- 47.2k
8
votes
10
answers
919
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 ...
- 21.4k
10
votes
10
answers
558
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 ...
- 47.2k
12
votes
7
answers
219
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\$. ...
- 47.2k
15
votes
10
answers
780
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 ...
- 62.8k
28
votes
10
answers
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 ...
- 2,005
26
votes
17
answers
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,...
- 22.1k
20
votes
1
answer
487
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:
...
- 17.6k
16
votes
19
answers
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 ...
- 47.2k
10
votes
1
answer
270
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 ...
- 2,431
16
votes
15
answers
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 = ...
- 193
15
votes
25
answers
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:
...
- 30.5k
24
votes
23
answers
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:
...
- 30.5k
19
votes
15
answers
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, ...
- 47.2k
17
votes
10
answers
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 ...
- 168k
13
votes
2
answers
276
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{ ...
- 62.8k
15
votes
10
answers
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 ...
- 679
23
votes
14
answers
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 ...
- 47.2k
29
votes
33
answers
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 ...
- 1,921
0
votes
4
answers
158
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 ...
- 17.4k
21
votes
20
answers
3k
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, ...
- 21.4k
15
votes
13
answers
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 ...
- 62.8k
15
votes
17
answers
2k
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} = ...
- 47.2k
20
votes
13
answers
895
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:
...
- 62.8k
13
votes
25
answers
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-...
user100411
17
votes
16
answers
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 ...
- 47.2k
24
votes
19
answers
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). ...
- 47.2k
18
votes
17
answers
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 ...
- 11.9k
18
votes
12
answers
945
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 ...
- 47.2k
24
votes
27
answers
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 ...
- 47.2k
30
votes
24
answers
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, ...
- 2,949
16
votes
15
answers
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 ...
- 47.2k
18
votes
7
answers
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 ...
- 8,107
19
votes
11
answers
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, ...\$ ...
- 47.2k