Questions tagged [number-theory]

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

Filter by
Sorted by
Tagged with
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 ...
Command Master's user avatar
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 +...
Command Master's user avatar
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)...
caird coinheringaahin g's user avatar
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 ...
alephalpha's user avatar
  • 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 ...
ananta's user avatar
  • 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 ...
Aitzaz Imtiaz's user avatar
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 ...
Aitzaz Imtiaz's user avatar
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 ...
Aitzaz Imtiaz's user avatar
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 ...
Samathingamajig's user avatar
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,...
Simd's user avatar
  • 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: ...
Peter Kagey's user avatar
  • 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 ...
chunes's user avatar
  • 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 ...
caird coinheringaahin g's user avatar
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 ...
Squareoot's user avatar
  • 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 ...
Jonathan Allan's user avatar
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 = \...
The Thonnu's user avatar
  • 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 ...
caird coinheringaahin g's user avatar
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 ...
The Thonnu's user avatar
  • 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. ...
Bubbler's user avatar
  • 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 ...
Bubbler's user avatar
  • 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 ...
Parcly Taxel's user avatar
  • 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 ...
Bubbler's user avatar
  • 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 ...
Study's user avatar
  • 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 ...
Wheat Wizard's user avatar
  • 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})\$. \$...
NoLongerBreathedIn's user avatar
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 \$ ...
dingledooper's user avatar
  • 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 ...
pxeger's user avatar
  • 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 ...
Wheat Wizard's user avatar
  • 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-...
Austin Prater's user avatar
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 ...
Wheat Wizard's user avatar
  • 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, ...
Number Basher's user avatar
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 \$...
caird coinheringaahin g's user avatar
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 ...
Binary198's user avatar
  • 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 ...
xiver77's user avatar
  • 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}...
xiver77's user avatar
  • 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\$. ...
hakr14's user avatar
  • 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] ...
pxeger's user avatar
  • 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 ...
xiver77's user avatar
  • 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 ...
xiver77's user avatar
  • 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 ...
caird coinheringaahin g's user avatar
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 ...
pxeger's user avatar
  • 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 ...
caird coinheringaahin g's user avatar
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\$. ...
caird coinheringaahin g's user avatar
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 ...
Bubbler's user avatar
  • 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 ...
Spitemaster's user avatar
  • 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,...
lyxal's user avatar
  • 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: ...
dingledooper's user avatar
  • 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 ...
caird coinheringaahin g's user avatar
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 ...
Rushabh Mehta's user avatar
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 = ...
Ha'Penny's user avatar
  • 193

1
2 3 4 5
10