Questions tagged [number-theory]

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

Filter by
Sorted by
Tagged with
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 ...
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 ...

1
2 3 4 5
8