Questions tagged [number-theory]
Number theory involves properties and relationships of numbers, primarily positive integers.
468
questions
24
votes
61
answers
3k
views
Subtract my odds from my evens
Given a non-negative integer, return the absolute difference between the sum of its even digits and the sum of its odd digits.
Default Rules
Standard Loopholes apply.
You can take input and provide ...
- 14.9k
19
votes
15
answers
2k
views
+200
Output a 1-2-3 sequence
For the purposes of this challenge, a 1-2-3 sequence is an infinite sequence of increasing positive integers such that for any positive integer \$n\$, exactly one of \$n, 2n,\$ and \$3n\$ appears in ...
- 10.6k
11
votes
4
answers
1k
views
Output a 1-2-3-5-7... sequence
Follow-up of my previous challenge, inspired by @emanresu A's question, and proven possible by @att (Mathematica solution linked)
For the purposes of this challenge, a 1-2-3-5-7... sequence is an ...
- 4,257
39
votes
27
answers
2k
views
Sum the powers that be
A simple but hopefully not quite trivial challenge:
Write a program or function that adds up the kth powers dividing a number n....
- 1,805
19
votes
7
answers
1k
views
Fastest tweetable integer factorizer
The task is to find a non-trivial factor of a composite number.
Write code that finds a non-trivial factor of a composite number as quickly as possible subject to your code being no more than 140 ...
- 331
23
votes
11
answers
3k
views
Highly composite numbers
A highly composite number is a positive integer that has more divisors than any smaller positive integer has. This is OEIS sequence A002182. Its first 20 terms are
...
- 33.3k
57
votes
136
answers
18k
views
Is this number evil?
Introduction
In number theory, a number is considered evil if there are an even number of 1's in its binary representation. In today's challenge, you will be identifying whether or not a given number ...
- 399
235
votes
368
answers
65k
views
Is this number a prime?
Believe it or not, we do not yet have a code golf challenge for a simple primality test. While it may not be the most interesting challenge, particularly for "usual" languages, it can be nontrivial in ...
- 399
18
votes
26
answers
2k
views
Is it a tetrate of two?
The tetration operation consists of repeated exponentiation, and it is written ↑↑. For instance,
3↑↑3 =3 ^(3^3) = 3^27 = 7,625,597,484,987
A tetrate of two is an ...
- 399
81
votes
31
answers
8k
views
Well that's odd... no wait, that's even!
Preamble
Integers are always either even or odd. Even integers are divisible by two, odd integers are not.
When you add two integers you can infer whether the result will be even or odd based on ...
- 979
15
votes
16
answers
1k
views
Pretty Palintiples
Imagine you have a positive integer number \$n\$. Let \$m\$ be the number obtained by reversing \$n\$'s digits. If \$m\$ is a whole multiple of \$n\$, then \$n\$ is said to be a reverse divisible ...
- 126k
27
votes
19
answers
5k
views
Last non-zero digit of n!
Given an integer 1 ≤ N ≤ 1,000,000 as input, output the last non-zero digit of N!, where ! is the factorial (the product of all numbers from 1 to N, inclusive). This is OEIS sequence A008904.
Your ...
- 1,473
15
votes
13
answers
2k
views
Print n weird numbers
A weird number is a number that the sum of proper divisors is greater than the number itself and no subset of proper divisors sum to that number.
Examples:
70 is a weird number because its proper ...
- 131
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] ...
- 331
11
votes
10
answers
1k
views
Egyptian fraction representations of 1 without prime denominators
Background
As noted in this question, for all positive integers \$n>2\$ there exists at least one Egyptian fraction representation (EFR) of \$n\$ distinct positive integers \$a_{1} < a_{2} < \...
- 331
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). ...
- 20.2k
6
votes
9
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,...
- 331
4
votes
5
answers
390
views
Generate a sequence of \$n\$ consecutive composite numbers
Definitions
The common methods to generate consecutive composites are
$$\overbrace{(n+1)! + 2, \ (n+1)! + 3, \ \ldots, \ (n+1)! + (n+1)}^{\text{n composites}}$$
$$\overbrace{n!+2,n!+3,...,n!+n}^{\text{...
- 106k
12
votes
20
answers
1k
views
Modular Equivalence
Given two numbers \$x,y > 2, x≠y \$ output all integers \$m\$ such that
$$
x + y \equiv x \cdot y \pmod m
$$
$$
x \cdot y > m > 2
$$
Input
Two integers
Output
A list of integers
Test cases
<...
- 3,847
26
votes
14
answers
5k
views
Hamming numbers
Hamming numbers are numbers which evenly divide a power of 60. Equivalently, their prime factors are all \$ \le 5 \$.
Given a positive integer, print that many Hamming numbers, in order.
Rules:
Input ...
- 1,223
4
votes
25
answers
2k
views
Consecutive Composite Numbers
Challenge
Generate \$n-1\$ consecutive composite numbers using this prime gap formula
$$n!+2,n!+3,...,n!+n$$
Input
An integer \$n\$ such that \$3 \leq n \leq 50 \$.
Output
Sequence of \$n-1\$ ...
- 501
23
votes
31
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 ...
- 24k
17
votes
19
answers
1k
views
Ellipse Lattice Point Counter
Challenge
Determine how many integer lattice points there are in an ellipse
$$\frac{x^2}{a^2} + \frac{y^2}{b^2} \leq 1$$
centered at the origin with width \$2a\$ and height \$2b\$ where integers \$a, ...
- 8,366
7
votes
10
answers
960
views
Make 1's and 2's composite
Input
An integer k composed of 1 and 2, with at least 3 digits and at most 200 digits.
...
- 126k
15
votes
16
answers
2k
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 ...
- 126k
15
votes
19
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 ...
- 126k
31
votes
14
answers
3k
views
That's a prime... almost
If you've ever learned about primes in math class, you've probably have had to, at one point, determine if a number is prime. You've probably messed up while you were still learning them, for example, ...
- 51
16
votes
2
answers
584
views
Construct this point
Given a constructible point \$(x, y) \in \mathbb R^2\$, output the steps required to construct \$(x, y)\$
Constructing a point
Consider the following "construction" of a point \$(\alpha, \...
- 23.9k
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:
...
3
votes
11
answers
501
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,757
13
votes
19
answers
982
views
Compute the minimum \$a(n)>a(n-1)\$ such that \$a(1)+a(2)+\dots+a(n)\$ is prime (OEIS A051935)
Background
Consider the following sequence (A051935 in OEIS):
Start with the term \$2\$.
Find the lowest integer \$n\$ greater than \$2\$ such that \$2+n\$ is prime.
Find the lowest integer \$n'\$ ...
- 41
20
votes
11
answers
2k
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 +...
- 411
13
votes
10
answers
1k
views
Repeated Digit Primes
Another sequence, another challenge.*
Definition
A prime p is in this sequence, let's call it A, iff for every digit ...
- 3,760
23
votes
41
answers
1k
views
Proper Divisor mash-up
A proper divisor is a divisor of a number n, which is not n itself. For example, the proper divisors of 12 are 1, 2, 3, 4 and 6.
You will be given an integer x, x ≥ 2, x ≤ 1000. Your task is to sum ...
- 5,903
30
votes
44
answers
3k
views
How does the square end?
In base-10, all perfect squares end in \$0\$, \$1\$, \$4\$, \$5\$, \$6\$, or \$9\$.
In base-16, all perfect squares end in \$0\$, \$1\$, \$4\$, or \$9\$.
Nilknarf describes why this is and how to work ...
- 5,903
21
votes
16
answers
2k
views
Discrete Convolution or Polynomial Multiplication
Given two non empty lists of integers, your submission should calculate and return the discrete convolution of the two. Interestingly, if you consider the list elements as coefficients of polynomials, ...
- 5,741
31
votes
29
answers
4k
views
Is this a Smith number?
Challenge description
A Smith number is a composite number whose sum of digits is equal to the sum of sums of digits of its prime factors. Given an integer N, ...
- 3,760
9
votes
5
answers
1k
views
Random factorized numbers
Input
The code should take an integer \$n\$ between 1 and 1000.
Output
The code should output positive integers with \$n\$ bits. Accompanying each integer should be its full factorization. Each ...
- 10.5k
9
votes
15
answers
826
views
Find the largest value of power.
Some numbers can be represented as perfect powers of other numbers. A number x can be represented as x = base^power for some integer base and power.
Given an integer x you have to find the largest ...
- 34.7k
3
votes
2
answers
342
views
Visualise the Euclidean GCD [duplicate]
The Euclidean GCD Algorithm is an algorithm that efficiently computes the GCD of two positive integers, by repeatedly subtracting the smaller number from the larger number until they become equal. It ...
- 23.9k
13
votes
10
answers
476
views
Dense Number Sequence
OEIS: A167171
A dense number is a number that has exactly as many prime divisors as non-prime divisors (including 1 and itself as divisors). Equivalently, it is either a prime or a product of two ...
- 3,760
14
votes
11
answers
1k
views
Find all Belphegor primes
A Belphegor number is a number of the form \$(10^{n+3}+666)*10^{n+1}+1\$ (1{n zeroes}666{n zeroes}1) where \$n\$ is an non-negative integer. A Belphegor prime is a ...
- 126k
17
votes
24
answers
2k
views
Find if a list is an ABC-triple
Three positive integers A, B, C are ABC-triple if they are coprime,
with A < B and satisfying the relation : A + B = C
Examples :
1, 8, 9 is an ABC-triple since ...
- 3,760
30
votes
15
answers
2k
views
Generate Keyboard Friendly Numbers
Most common computer keyboard layouts have the decimal digit keys
1234567890
running along at their top, above the keys for letters.
Let a decimal digit's neighborhood be the set of digits from ...
- 23.9k
20
votes
20
answers
2k
views
Finite Cantor's Diagonal
Given a list of N integers, each with N digits, output a number which differs from the first number because of the first digit, ...
- 3,760
5
votes
2
answers
275
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 ...
- 5,741
12
votes
2
answers
641
views
Find a number which generates all the integers mod q
Consider the integers modulo q where q is prime, a generator is any integer 1 < x < q ...
- 5,741
6
votes
4
answers
562
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 ...
- 5,741
35
votes
44
answers
5k
views
Calculate Euler's totient function
Background
Euler's totient
function φ(n) is defined as the number of whole numbers less than or equal to n that are relatively ...
- 48k
13
votes
7
answers
2k
views
Ryley's Theorem
S. Ryley proved following theorem in 1825:
Every rational number can be expressed as a sum of three rational cubes.
Challenge
Given some rational number \$r \in \mathbb Q \$ find three rational ...
- 48k