Questions tagged [number-theory]
Number theory involves properties and relationships of numbers, primarily positive integers.
378
questions
25
votes
13answers
3k 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 ...
7
votes
5answers
1k views
Build a Primitive Root Diffuser
Introduction
When a room has bare, parallel walls, it can create unpleasant repeating acoustic reflections (echoes). A diffuser is a device mounted on a wall which creates a blocky surface of many ...
18
votes
12answers
806 views
Compute modular inverse
Given two positive numbers \$x\$ and \$n\$ with \$x<2^n\$, write the shortest possible function to compute \$x^{-1} \mod 2^n\$. In other words, find \$y\$ such that \$xy=1 \mod 2^n\$.
Your ...
33
votes
20answers
2k views
Finding The nth Prime such that the prime - 1 is divisible by n
Problem
The goal is as the title says to find the \$n\$th prime such that \$\text{the prime}-1\$ is divisible by \$n\$.
Explanation
Here is an example so you understand the question, this is not ...
21
votes
14answers
2k views
Is this a truncated triangular number?
Related OEIS sequence: A008867
Truncated triangular number
A common property of triangular numbers is that they can be arranged in a triangle. For instance, take 21 and arrange into a triangle of <...
48
votes
32answers
2k views
Divisor skyline
For any positive integer \$k\$, let \$d(k)\$ denote the number of divisors of \$k\$. For example, \$d(6)\$ is \$4\$, because \$6\$ has \$4\$ divisors (namely \$1, 2, 3, 6\$).
Given a positive integer \...
41
votes
72answers
5k views
Am I divisible by double the sum of my digits?
Given a positive integer as input, your task is to output a truthy value if the number is divisible by the double of the sum of its digits, and a falsy value otherwise (OEIS A134516). In other words:
<...
33
votes
60answers
4k views
GET your dubs together
On 4chan, a popular game is get. Every post on the site gets a sequential post ID. Since you can't influence or determine them, people try to guess (at least a part of) their own post number, usually ...
21
votes
12answers
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 ...
11
votes
18answers
1k views
Do we share the prime cluster?
The prime cluster of an integer N higher than 2 is defined as the pair formed by the highest prime strictly lower than N and the lowest prime strictly higher than N.
Note that following the definition ...
21
votes
26answers
2k views
“Factorise” a quadratic
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)(...
44
votes
34answers
3k views
Is this number Loeschian?
A positive integer \$k\$ is a Loeschian number if
\$k\$ can be expressed as \$i^2 + j^2 + i\times j\$ for \$i\$, \$j\$ integers.
For example, the first positive Loeschian numbers are: \$1\$ (\$i=1, ...
17
votes
13answers
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,\...
48
votes
16answers
6k views
A naturally occurring prime generator
There are quite a large number of prime generating functions. Pretty much all of them are constructed and are based on the sieve of Eratosthenes, the Mƶbius function or the Wilson's theorem and are ...
216
votes
310answers
51k 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 ...
13
votes
7answers
619 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 ...
25
votes
36answers
2k 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 ...
27
votes
25answers
2k views
The Add-Multiply-Add Sequence
(Related)
Given an integer n > 1,
1) Construct the range of numbers n, n-1, n-2, ... 3, 2, 1 and calculate the sum
2) Take ...
7
votes
7answers
977 views
Count how many numbers are divisible by perfect numbers in a given range
Given two arbitrary integers \$a\$ and \$b\$, count how many numbers are divisible by perfect numbers in that given range (\$a\$ and \$b\$ both are inclusive).
In mathematics, a perfect number is a ...
22
votes
38answers
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 ...
21
votes
27answers
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]{...
21
votes
12answers
1k views
Hilbert Primes Golf
Hilbert numbers are defined as positive integers of the form 4n + 1 for n >= 0. The first few Hilbert numbers are:
...
14
votes
6answers
792 views
HardyāRamanujan number generalization
\$1729\$, known as the HardyāRamanujan number, is the smallest positive integer that can be expressed as the sum of two cubes of positive integers in two ways (\$12^3+1^3=10^3+9^3=1729\$). Given an ...
caird coinheringaahing
22.5k5 gold badges53 silver badges159 bronze badges
24
votes
42answers
2k views
Product of Divisors
Challenge
Given a positive integer, return the product of its divisors, including itself.
This is sequence A007955 in the OEIS.
Test Cases
1: 1
2: 2
3: 3
4: 8
5: 5
6: 36
7: 7
8: 64
9: 27
10: 100
...
15
votes
4answers
902 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 ...
20
votes
18answers
846 views
(KevinC's) Triangular DeciDigits Sequence
Input:
A positive integer n which is 1 <= n <= 25000.
Output:
In this sequence we start with the decimal number 1/n.
Then we take the sum of digits up ...
53
votes
88answers
6k views
Find the smallest number that doesn't divide N
This challenge is simple enough that it's basically all in the title: you're given a positive integer N and you should return the smallest positive integer which is not a divisor of N.
An example: the ...
69
votes
25answers
9k views
Yo boy, must it sum
Every positive integer can be expressed as the sum of at most three palindromic positive integers in any base bā„5. Cilleruelo et al., 2017
A positive integer is palindromic in a given base if ...
19
votes
23answers
2k views
Zero the byte (eventually)
Given an infinite arithmetically-progressiveĀ¹ sequence, compute the minimum length of a prefix with a product divisible by 2^8.
Sample cases & reference implementation
Here is a reference ...
26
votes
10answers
2k views
Fermat's polygonal number theorem
Fermat's polygonal number theorem states that every positive integer can be expressed as the sum of at most \$n\$ \$n\$-gonal numbers. This means that every positive integer can be expressed as the ...
15
votes
6answers
996 views
The Untouchables
Untouchable NumbersĪ±
An untouchable number is a positive integer that cannot be expressed as the sum of all the proper divisors of any positive integer (including the untouchable number itself).
...
33
votes
22answers
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 ...
22
votes
5answers
454 views
Swap program halves to test divisors
Four integer sequences
In this challenge, you will test four different properties of a positive integer, given by the following sequences.
A positive integer N is
perfect (OEIS A000396), if the sum ...
59
votes
41answers
12k views
Find the Smoothest Number
Your challenge is to find the smoothest number over a given range. In other words, find the number whose greatest prime factor is the smallest.
A smooth number is one whose largest prime factor is ...
10
votes
10answers
661 views
Check type of an integer
You will receive an integer less than 2000000000 and bigger than -2000000000 and you have to test what type(s) of number this is out of:
...
21
votes
9answers
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 ...
11
votes
9answers
962 views
Compute the Lambert W function
Your challenge is to compute the Lambert W function. \$W(x)\$ is defined to be the real value(s) \$y\$ such that
$$y = W(x) \text{ if } x = ye^y$$
where \$e = 2.718281828...\$ is Euler's number.
...
26
votes
19answers
3k views
Legendre's (Unsolved) Conjecture
Legendre's Conjecture is an unproven statement regarding the distribution of prime numbers; it asserts there is at least one prime number in the interval \$(n^2,(n+1)^2)\$ for all natural \$n\$.
The ...
14
votes
13answers
1k views
Generate Linus Sequence
Definition
From the description on OEIS A006345:
To find a(n), consider either a 1 or a 2...
19
votes
13answers
1k views
Return the nth digit of the sequence of aliquot series
0. DEFINITIONS
A sequence is a list of numbers.
A series is the sum of a list of numbers.
The set of natural numbers contains all "non-negative integers greater than zero".
A divisor (in this ...
13
votes
32answers
3k views
N numbers closest to zero staying balanced
Objective: Given a positive integer n:
If n is odd, output the list of n numbers closest to ...
15
votes
10answers
476 views
Reachable numbers
Definitions
Euler Phi Function (AKA totient function): a function which takes in a positive number and returns the number of positive numbers less than the given number which are co-prime with given ...
20
votes
26answers
2k views
Find the nearest biquadratic number
A biquadratic number is a number that is the fourth power of another integer, for example: 3^4 = 3*3*3*3 = 81
Given an integer as input, output the closest ...
41
votes
69answers
6k views
Greatest Common Divisor
Your task is to compute the greatest common divisor (GCD) of two given integers in as few bytes of code as possible.
You may write a program or function, taking input and returning output via any of ...
27
votes
14answers
1k views
Palindromic Residue
Today, as I'm writing this, is March 31st. In the US, this is 3/31. I was playing around with 331 as a number to come up with a ...
22
votes
31answers
4k views
Sum the First n Even Fibonacci Numbers
There seems not to be a contest for this one yet.
The task is simple. Add the first n numbers of the Fibonacci sequence that are even and output the result.
This ...
16
votes
13answers
1k views
Seidel Triangle
The Seidel Triangle is a mathematical construction similar to Pascal's Triangle, and is known for it's connection to the Bernoulli numbers.
The first few rows are:
...
12
votes
19answers
872 views
Find a Rocco number
I was asked this question in an interview but I was unable to figure out any solution. I don't know whether the question was right or not. I tried a lot but couldn't reach any solution. Honestly ...
26
votes
24answers
4k views
Implement the divisibility-by-7 rule
To check whether a decimal number is divisible by 7:
Erase the last digit. Multiply it by 2 and subtract from what is left. If the result is divisible by 7, the original number is divisible by 7.
(...
25
votes
12answers
2k views
Print all 3 by 3 sturdy squares
A sturdy square (akin to a magic square) is an arrangement of the integers 1 to \$N^2\$ on an \$N\$ by \$N\$ grid such that every 2 by 2 subgrid has the same sum.
For example, for \$N = 3\$ one sturdy ...
