Questions tagged [number-theory]

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

Filter by
Sorted by
Tagged with
36
votes
20answers
7k views

Compute the Carmichael function

Task description In number theory, the Carmichael function λ takes a positive integer n and returns the least positive integer k so that the k-th power of each integer coprime to n equals 1 modulo n. ...
9
votes
6answers
314 views

Misconstrued Monomials

There exists an equation, assuming n and x are positive, that expresses the relationship between two monomials, one being a ...
10
votes
6answers
543 views

Constructible n-gons

A constructible \$n\$-gon is a regular polygon with n sides that you can construct with only a compass and an unmarked ruler. As stated by Gauss, the only \$n\$ for which a \$n\$-gon is constructible ...
29
votes
28answers
3k 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, ...
18
votes
23answers
1k views

Excessive Integers

For a positive integer n with the prime factorization n = p1^e1 * p2^e2 * ... pk^ek where ...
32
votes
6answers
690 views

Score Tarzan's Olympic Vine-Swinging Routine

Olympic vine-swingers perform their routines in standard trees. In particular, Standard Tree n has vertices for 0 up through <...
8
votes
1answer
188 views

Compute the polyomino capacity of a rectangle

Write a program or function that takes as input three positive integers x, y, and a and ...
13
votes
9answers
395 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 ...
10
votes
8answers
538 views

Smallest positive integer which is coprime to the last two predecessors and has not yet appeared; a(1)=1, a(2)=2

Definition Two integers are coprime if they share no positive common divisors other than 1. a(1) = 1 ...
6
votes
2answers
169 views

The infinitely admissable sequence

In this challenge we'll compute an infinite minimal admissible sequence. The sequence for this challenge starts with a(1) = 1. We continue this sequence by ...
13
votes
7answers
1k views

Testing for admissible sequences

Executive summary: test whether an input sequence of integers is "admissible", meaning that it doesn't cover all residue classes for any modulus. What is an "admissible" sequence? Given an integer m ...
26
votes
11answers
843 views

Numbers of purity

Today we'll look at a sequence \$a\$, related to the Collatz function \$f\$: $$f = \begin{cases} n/2 & \text{if } n \equiv 0 \text{ (mod }2) \\ 3n+1 & \text{if } n \equiv 1 \text{ (mod }2) \\ ...
37
votes
28answers
4k views

Is it a Proth number?

A Proth number, named after François Proth, is a number that can be expressed as N = k * 2^n + 1 Where k is an odd positive ...
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, ...
19
votes
38answers
3k views

Hofstadter H-sequence

Definition \$a(0) = 0\$ \$a(n) = n-a(a(a(n-1)))\$ for integer \$n > 0\$ Task Given non-negative integer \$n\$, output \$a(n)\$. Testcases ...
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...
14
votes
14answers
684 views

Verify Wolstenholme's theorem

Definition Wolstenholme's theorem states that: where a and b are positive integers and p ...
23
votes
6answers
861 views

Partial factorisations of a positive integer

A collection of positive integers d_1 d_2 ... d_k is a factorisation of a positive integer n if ...
31
votes
14answers
2k views

Array Escape - get out of there

One day you awake only to find yourself caught in an array. You try to just walk out of there, taking one index at the time, but it seems there are other rules: The array is completely filled with ...
7
votes
1answer
403 views

Help the poor Cryptographers - DLP Edition

Introduction and Motivation I'm mainly active on Cryptography.SE and as such have already stumbled across the question: "How the hell am I supposed tools like cado-nfs to do stuff!?". They ...
16
votes
9answers
1k views

Find numbers within the Copeland–Erdős constant

Background The Copeland–Erdős constant is the concatenation of "0." with the base 10 representations of the prime numbers in order. Its value is ...
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 ...
17
votes
12answers
2k views

Shamir's Secret Sharing

Given n (the number of players), t (the threshold value), and s (the secret), output the <...
1
vote
1answer
115 views

Sequence avoiding near collision [closed]

Task Find a sequence of all numbers between min and max where every number differs from every other number in the sequence by at least "d" digits. Example of sub-sequence For min = 0, max = 1000 ...
20
votes
25answers
1k views

Reverse odd runs

Inspiration. Task Reverse runs of odd numbers in a given list of 2 to 215 non-negative integers. Examples 0 1 → 0 1 ...
21
votes
15answers
1k views

Calculate the partitions of N

Your challenge is simple: GIven an integer N, ouput every list of positive integers that sums to N. For example, if the input was 5, you should output ...
22
votes
20answers
2k views

Reverse and subtract

Challenge description Let's take a positive integer n, reverse its digits to get rev(n) and get the absolute value of the ...
43
votes
19answers
7k views

Theoretically output Graham's number

Graham's number G is defined in this way: ...
31
votes
38answers
4k 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 ...
12
votes
3answers
1k views

All Armstrong numbers

An Armstrong number (AKA Plus Perfect number, or narcissistic number) is a number which is equal to its sum of n-th power of the digits, where ...
20
votes
10answers
1k views

Fibonacci Factorization

Fibonacci Numbers Fibonacci Numbers start with f(1) = 1 and f(2) = 1 (some includes f(0) = 0...
8
votes
14answers
1k views

Golf the repeated totient function

You will take two positive integers n and x as input, and output Euler's totient function (number of positive integers less than ...
2
votes
4answers
235 views

OMG! We're Twinning! [duplicate]

Introduction We define twin primes as two natural numbers p,p+2 which both are prime. Example: 5 and ...
38
votes
29answers
3k views

Pseudofactorial

There is a rather curious number which shows up sometimes in math problems or riddles. The pseudofactorial(N) is the least (i.e. lowest) common multiple of the numbers 1 through N; in other words, it'...
26
votes
22answers
2k views

Swap bits with their neighbours

Task description Given an integer, swap its (2k–1)-th and 2k-th least significant bits for all integers k > 0. This is sequence A057300 in the OEIS. (The number is assumed to have “...
10
votes
12answers
336 views

N-uniquely additive sets

Remember that a set is unordered without duplicates. Definition An N-uniquely additive set S whose length is K is a set such that all N-length subsets in S sum to different numbers. In other words, ...
13
votes
4answers
467 views

My “keybore” is key-boring me! Help me find a minimal keystrokes

Credits to @Agawa001 for coming up with this question. Explanation My new "keybore" only has 2 buttons, namely + and -. The ...
13
votes
8answers
977 views

Longest arithmetic subsequence

Given a non empty finite sequence of integers, return an arithmetic subsequence of maximal length. If there are multiple of the same maximal length, any of them can be returned. Definitions: An ...
2
votes
9answers
809 views

Generate an infinite group of infinite galaxies [closed]

Here is the challenge as proposed by @trichoplax thanks to him for consolidating my post and standarizing it to PPCG common-rules. A galaxy is a group of numbers where each one is mapped to another ...
3
votes
0answers
263 views

What's so great about 1729? [closed]

This is not a duplicate of this question. This is asking for the nth number that can be represented as the sum of two cubes in two different ways, while that is asking for the n-th number that can be ...
6
votes
3answers
792 views

Surjective, Injective, Bijective, or Nothing?

Given a mapping from the integers from 1 to N to the integers from 1 to N, determine if the mapping is surjective, injective, bijective, or nothing. You may choose any character/digit for the four ...
19
votes
14answers
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, ...
15
votes
4answers
373 views

Shortest paths in a divisor graph

Introduction In this challenge, we will be dealing with a certain infinite undirected graph, which I call the high divisor graph. Its nodes are the integers starting from 2. There is an edge between ...
19
votes
19answers
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, ...
11
votes
3answers
426 views

Minimize Those Ones [closed]

Your task is to build a natural number using the fewest number of ones and only the operators + or -. For example, the number ...
11
votes
8answers
484 views

Draw a phi triangle

Clarification: Basically, you need to make this Euler's totient function has the name phi. Let's try to calculate phi(8) First, list all numbers 8 and under backwards, not including 0 or under <...
12
votes
25answers
863 views

Polygonal numbers

A polygonal number is the number of dots in a k-gon of size n. You will be given n and <...
18
votes
20answers
2k views

Find the n-th perfect power!

A perfect power is a number of the form \$a^b\$, where \$a>0\$ and \$b>1\$. For example, \$125\$ is a perfect power because it can be expressed as \$5^3\$. Goal Your task is to write a program/...
12
votes
23answers
1k views

Find the positive divisors!

Definition A number is positive if it is greater than zero. A number (A) is the divisor of another number (B) if ...
15
votes
20answers
903 views

Decompose a number!

Your task is to decompose a number using the format below. This is similar to base conversion, except that instead of listing the digits in the base, you list the <...

1
4
5
6 7 8