Questions tagged [number-theory]
Number theory involves properties and relationships of numbers, primarily positive integers.
455
questions
6
votes
4
answers
367
views
Sums of Euler's totient function in sublinear time
Related.
Given a number \$n\$, Euler's totient function, \$\varphi(n)\$ is the number of integers up to \$n\$ which are coprime to \$n\$. That is, no number bigger than \$1\$ divides both of them.
For ...
- 7,698
20
votes
12
answers
1k
views
Sums of sum of divisors in sublinear time
Given a number \$n\$, we have its sum of divisors, \$\sigma(n)\ = \sum_{d | n} {d}\$, that is, the sum of all numbers which divide \$n\$ (including \$1\$ and \$n\$). For example, \$\sigma(28) = 1 + 2 +...
- 7,698
11
votes
12
answers
1k
views
The all-high powerful numbers
We've had powerful numbers, yes, but what about highly powerful numbers?
Highly powerful numbers
Let \$n\$ be a positive integer in the form
$$n = p_1^{e_{p_1}(n)}p_2^{e_{p_2}(n)}\cdots p_k^{e_{p_k}(n)...
- 49.3k
17
votes
25
answers
3k
views
Is this a powerful number?
A powerful number is a positive integer \$n\$ such that for every prime \$p\$ that divides \$n\$, \$p^2\$ also divides \$n\$. Or equivalently, \$n\$ is powerful if and only if it can be written in the ...
- 45.6k
1
vote
0
answers
109
views
Print all semimagic squares [closed]
I am working on a code to print all semimagic squares [1] of a given size. I am working with the following definition:
An \$n\times n\$ consists of numbers \$1,2,\cdots, n^2\$.
All numbers must be ...
- 111
15
votes
18
answers
2k
views
Sophie Safe primes
Description
Write a program or function that takes in a positive integer \$n\$ as input and outputs all Sophie Germain primes that are safe primes less than or equal to \$n\$. A prime number \$p\$ is ...
- 1,732
15
votes
16
answers
1k
views
Imtiaz Germain Primes
Description
"Imtiaz Germain primes" is not a technical name in Mathematics, but my weird creation, in the memoir of the famous mathematician Sophie Germain. These primes can be generated by ...
- 1,732
18
votes
24
answers
2k
views
Shortest code to generate all Pythagorean triples up to a given limit
Generate the shortest possible code in any programming language that can generate all Pythagorean triples with all values not exceeding a given integer limit. A Pythagorean triple is a set of three ...
- 1,732
13
votes
25
answers
990
views
Find the Prime Signature
The Prime Signature of a number is the list of the exponents of the prime factors of a number, sorted in descending order (exponents of 0 are ignored). Inspired by ...
- 495
5
votes
7
answers
1k
views
Implement the Riemann R function
The Riemann R function is as follows:
$$R (x)=\sum _{n=1}^{\infty } \frac{\mu (n) \text{li}\left(x^{1/n}\right)}{n}.$$
This uses the Möbius function as well as the logarithmic integral.
From Wikipedia,...
- 1,545
20
votes
4
answers
2k
views
Write a number as a sum of Fibonacci numbers
In 2009, Hannah Alpert described the "far-difference" representation, a novel way of representing integers as sums and differences of Fibonacci numbers according to the following rules:
...
- 8,649
24
votes
20
answers
2k
views
"Prime" pyramid
The pyramid begins with the row 1 1. We'll call this row 1. For each subsequent row, start with the previous row and insert the current row number between every ...
- 21k
13
votes
22
answers
1k
views
Even and Odd kinds
Let \$n\$ be some positive integer. We say that \$n\$ is of even kind if the prime factorisation of \$n\$ (counting duplicates) has an even number of integers. For example, \$6 = 2 \times 3\$ is of ...
- 49.3k
13
votes
15
answers
2k
views
Advanced Binary Number System
Your task is to write a program that calculates the amount of different ways to display any given whole positive number using the following rules:
Meet the 'advanced binary system':
Any whole positive ...
- 147
14
votes
10
answers
1k
views
IMO Question Six with a difference
In 1988, the International Mathematical Olympiad (IMO) featured this as its final question, Question Six:
Let \$a\$ and \$b\$ be positive integers such that \$ab + 1\$ divides \$a^2 + b^2\$. Show ...
- 102k
15
votes
14
answers
5k
views
The "Fly straight, dammit" sequence
Background
"Fly straight, dammit" (OEIS A133058) is a sequence of integers, which has these rules:
\$a_0 = a_1 = 1\$
\$a_n = a_{n-1}+n+1\$ if \$gcd(a_{n-1}, n) = 1\$
Otherwise, \$a_n = \...
- 17.6k
16
votes
14
answers
2k
views
Persistence of a number
The persistence of a number \$x = d_1d_2d_3...d_n\$, with \$d_1 \ne 0\$, under some function \$f : \mathbb N_0 \times \mathbb N_0 \to \mathbb N_0\$ is defined as the number of applications of \$f\$ to ...
- 49.3k
10
votes
18
answers
828
views
Sum of partition numbers
The partition function:
In number theory, the partition function p(n) represents the number of possible partitions of a positive integer n into positive integers
For instance, p(4) = 5 because the ...
- 17.6k
21
votes
22
answers
2k
views
The second even sublime number
easy mode of my previous challenge
A perfect number is a positive integer whose sum of divisors (except itself) is equal to itself. E.g. 6 (1 + 2 + 3 = 6) and 28 (1 + 2 + 4 + 7 + 14 = 28) are perfect.
...
- 73.2k
17
votes
8
answers
3k
views
An algorithm to find even sublime numbers
A perfect number is a positive integer whose sum of divisors (except itself) is equal to itself. E.g. 6 (1 + 2 + 3 = 6) and 28 (1 + 2 + 4 + 7 + 14 = 28) are perfect.
A sublime number (OEIS A081357) is ...
- 73.2k
5
votes
2
answers
257
views
Generate a Kirkman triple system
Given a universe of \$v\$ elements, a Kirkman triple system is a set of \$(v-1)/2\$ classes each having \$v/3\$ blocks each having three elements, so that
every pair of elements appears in exactly ...
- 3,707
24
votes
33
answers
3k
views
Anti-divisors of a number
Given a positive integer n, output all of its anti-divisors in any order.
From OEIS A006272:
Anti-divisors are the numbers that do not divide a number by the ...
- 73.2k
2
votes
0
answers
346
views
Decompose number N into the sum of three triangular numbers [closed]
It is known that any natural number can be decomposed into the sum of three triangular numbers (assuming 0 is triangular), according to Fermat's Polygonal Number Theorem. Your task is to come up with ...
- 45
15
votes
3
answers
395
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 ...
- 95.7k
3
votes
11
answers
465
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,717
21
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 \$ ...
- 22.2k
15
votes
13
answers
894
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 ...
- 23.2k
24
votes
19
answers
4k
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 ...
- 95.7k
7
votes
12
answers
574
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 ...
- 95.7k
1
vote
1
answer
501
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,532
19
votes
17
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 \$...
- 49.3k
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 ...
- 523
14
votes
2
answers
863
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,325
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,325
23
votes
34
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\$.
...
- 4,956
34
votes
19
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] ...
- 23.2k
11
votes
6
answers
1k
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,325
6
votes
2
answers
748
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,325
4
votes
3
answers
226
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 ...
- 49.3k
8
votes
10
answers
943
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 ...
- 23.2k
10
votes
10
answers
579
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 ...
- 49.3k
12
votes
7
answers
290
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\$. ...
- 49.3k
15
votes
10
answers
794
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 ...
- 73.2k
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,125
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,...
- 31.7k
20
votes
1
answer
617
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:
...
- 22.2k
16
votes
21
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 ...
- 49.3k
10
votes
1
answer
304
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,451
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