Skip to main content

Questions tagged [number-theory]

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

Filter by
Sorted by
Tagged with
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,974
37 votes
20 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.9k
12 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,365
6 votes
2 answers
853 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,365
5 votes
3 answers
283 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
944 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.9k
10 votes
10 answers
584 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
298 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
799 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
  • 77.1k
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,135
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
  • 33.6k
20 votes
1 answer
660 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.7k
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
315 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
17 votes
28 answers
2k 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: ...
emanresu A's user avatar
  • 38.8k
23 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: ...
emanresu A's user avatar
  • 38.8k
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, ...
caird coinheringaahin g's user avatar
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 ...
Arnauld's user avatar
  • 193k
13 votes
2 answers
277 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{ ...
Bubbler's user avatar
  • 77.1k
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 ...
N3buchadnezzar's user avatar
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 ...
caird coinheringaahin g's user avatar
31 votes
35 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 ...
AviFS's user avatar
  • 2,111
0 votes
4 answers
209 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 ...
Rydwolf Programs's user avatar
22 votes
21 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, ...
pxeger's user avatar
  • 23.9k
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 ...
Bubbler's user avatar
  • 77.1k
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} = ...
caird coinheringaahin g's user avatar
20 votes
13 answers
932 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: ...
Bubbler's user avatar
  • 77.1k
14 votes
27 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-...
user avatar
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 ...
caird coinheringaahin g's user avatar
26 votes
25 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). ...
caird coinheringaahin g's user avatar
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 ...
Wasif's user avatar
  • 12.3k
19 votes
12 answers
998 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 ...
caird coinheringaahin g's user avatar
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 ...
caird coinheringaahin g's user avatar
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, ...
79037662's user avatar
  • 2,999
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 ...
caird coinheringaahin g's user avatar
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 ...
Peter Kagey's user avatar
  • 8,689
20 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, ...\$ ...
caird coinheringaahin g's user avatar
14 votes
21 answers
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 ...
emanresu A's user avatar
  • 38.8k
27 votes
13 answers
6k 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 ...
caird coinheringaahin g's user avatar
33 votes
17 answers
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 ...
IronEagle's user avatar
  • 439
18 votes
14 answers
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,\...
Bubbler's user avatar
  • 77.1k
12 votes
7 answers
664 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 ...
caird coinheringaahin g's user avatar
16 votes
4 answers
1k 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 ...
caird coinheringaahin g's user avatar
23 votes
28 answers
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)(...
caird coinheringaahin g's user avatar
23 votes
27 answers
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]{...
AZTECCO's user avatar
  • 10.8k
34 votes
23 answers
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 ...
caird coinheringaahin g's user avatar
16 votes
15 answers
660 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...\$ ...
vrintle's user avatar
  • 2,990
23 votes
9 answers
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 ...
Shieru Asakoto's user avatar
22 votes
12 answers
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 ...
Zgarb's user avatar
  • 42.7k

1
2
3 4 5
10