The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [number-theory]

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

Filter by
Sorted by
Tagged with
24
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 ...
17
votes
8answers
1k views

Dividing Divisive Divisors

Given a positive integer \$n\$ you can always find a tuple \$(k_1,k_2,...,k_m)\$ of integers \$k_i \geqslant 2\$ such that \$k_1 \cdot k_2 \cdot ... \cdot k_m = n\$ and $$k_1 | k_2 \text{ , } k_2 | ...
10
votes
1answer
213 views

Interpreter for number theory, modulo n

A sentence of number theory (for our purposes) is a sequence of the following symbols: 0 and ' (successor) - successor means <...
13
votes
12answers
401 views

Find all \$k\$-smooth pairs

Introduction In number theory, we say a number is \$k\$-smooth when its prime factors are all at most \$k\$. For example, 2940 is 7-smooth because \$2940=2^2\cdot3\cdot5\cdot7^2\$. Here, we define a ...
11
votes
12answers
1k views

Magical Modulo Squares

I'm a big fan of number theory. A big thing in number theory is modular arithmetic; the definition being \$a\equiv b\mod m\$ if and only if \$m\mid a-b\$. A fun thing to do is raising to powers: ...
21
votes
5answers
487 views

Congruent Numbers

Definitions: A triangle is considered a right triangle if one of the inner angles is exactly 90 degrees. A number is considered rational if it can be represented by a ratio of integers, i.e., ...
28
votes
26answers
2k views

Fundamental Solution of the Pell Equation

Given some positive integer \$n\$ that is not a square, find the fundamental solution \$(x,y)\$ of the associated Pell equation $$x^2 - n\cdot y^2 = 1$$ Details The fundamental \$(x,y)\$ is a pair ...
17
votes
16answers
2k views

Do I have a twin with permutated remainders?

We define \$R_n\$ as the list of remainders of the Euclidean division of \$n\$ by \$2\$, \$3\$, \$5\$ and \$7\$. Given an integer \$n\ge0\$, you have to figure out if there exists an integer \$0<k&...
29
votes
45answers
9k views

Am I not good enough for you?

Background: The current Perfect Numbers challenge is rather flawed and complicated, since it asks you to output in a complex format involving the factors of the number. This is a purely decision-...
7
votes
7answers
541 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: ...
12
votes
18answers
819 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 ...
16
votes
23answers
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 ...
22
votes
13answers
3k views

Eight coins for the fair king

This is a "counterpart" of another puzzle, Eight coins for the fair king on Puzzling.SE. You can read the above puzzle for the background. The details about this puzzle are as follows. A set of 8 ...
17
votes
19answers
3k views

Is this number a hill number?

A hill number is a number that has the same digit in the first & the last, but that's not all. In a hill number the first digits are strictly increasing, and the last digits are strictly ...
19
votes
13answers
1k views

Dirichlet Convolution

The Dirichlet convolution is a special kind of convolution that appears as a very useful tool in number theory. It operates on the set of arithmetic functions. Challenge Given two arithmetic ...
14
votes
6answers
1k 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 ...
15
votes
11answers
879 views

Generate some rough numbers

Background A number n can be described as B-rough if all of the prime factors of n strictly ...
19
votes
10answers
2k views

Repeat this GCD operation

Problem A3 from the 2008 Putnam competition says: Start with a finite sequence \$a_1, a_2, \dots, a_n\$ of positive integers. If possible, choose two indices \$j < k\$ such that \$a_j\$ does not ...
18
votes
26answers
3k views

Is the word coprime?

Given a word, treat every letter as it's number in English alphabet (so a becomes 1, b becomes 2, ...
13
votes
10answers
1k views

Quadratic residues are so much fun!

Definitions Quadratic residues An integer \$r\$ is called a quadratic residue modulo \$n\$ if there exists an integer \$x\$ such that: $$x^2\equiv r \pmod n$$ The set of quadratic residues modulo \...
14
votes
2answers
374 views

Impatient divisibility test

Your task is to write a program or function that determines whether a number is divisible by another. The catch is that it should give an answer as soon as possible, even if not all digits of the ...
13
votes
7answers
674 views

Make the biggest and smallest numbers

Inspired by this post over on Puzzling. Spoilers for that puzzle are below. Given three positive integers as input, (x, y, z), construct the inclusive range ...
15
votes
16answers
2k views

The number of ways a number is a sum of consecutive primes

Given an integer greater than 1, output the number of ways it can be expressed as the sum of one or more consecutive primes. Order of summands doesn't matter. A sum can consist of a single number (...
12
votes
17answers
511 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'\$ ...
17
votes
7answers
602 views

Split the bits!

We define \$V(x)\$ as the list of distinct powers of \$2\$ that sum to \$x\$. For instance, \$V(35)=[32,2,1]\$. By convention, powers are sorted here from highest to lowest. But it does not affect ...
34
votes
88answers
14k 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 ...
24
votes
13answers
3k views

Find the 10-adic cube root of 3

I like to think of a 10-adic number as a number that goes infinitely to the left, or an integer modulo a very very large power of 10. Things carry infinitely to the left and vanish. To see what I ...
22
votes
19answers
2k views

Is this a consecutive-prime/constant-exponent number?

A while ago, I had a look at the prime factorization of 27000: 27000 = 23 × 33 × 53 There are two special things about that: consecutive-prime: The primes are consecutive: 2 is the ...
27
votes
24answers
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 ...
51
votes
11answers
3k views

Bringing a pair of integers to equality

This was inspired by a math problem I saw somewhere on the internet but do not remember where (UPDATE: The original problem was found on the math riddles subreddit with a proof provided that it is ...
14
votes
15answers
1k views

Am I a Pillai prime?

A Pillai prime is a prime number \$p\$ for which there exists some positive \$m\$ such that \$(m! + 1) \equiv 0 \:(\text{mod } p)\$ and \$p \not\equiv 1\:(\text{mod }m)\$. In other words, an ...
6
votes
2answers
219 views

Minimal Triangles

Make an upside down triangle of positive integers. Every number in the triangle must be distinct. Each number is the summation of its two parents (similar to how Pascal's triangle is constructed, but ...
22
votes
11answers
721 views

Digit Product Sequences

Here's an interesting sequence discovered by Paul Loomis, a mathematician at Bloomsburg University. From his page on this sequence: Define ...
5
votes
27answers
1k views

Simple Factorial Challenge [duplicate]

In light of today's date... A factorial of a number n, is the product of all the numbers from 1 to n inclusive. The Challenge Given an integer n where 0 <= n <= 420, find the sum of the ...
18
votes
13answers
2k views

Conway's Prime Game

Specifically, Conway's PRIMEGAME. This is an algorithm devised by John H. Conway to generate primes using a sequence of 14 rational numbers: ...
14
votes
9answers
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: ...
9
votes
5answers
369 views

Four Spiraling Axes

Take the numbers 0, 1, 2, 3, 4, ... and arrange them in a clockwise spiral, starting downward, writing each digit in its own separate square. Then, given one of ...
18
votes
26answers
1k views

Rotational Average

Given an input integer n >= 10, output the average of all deduplicated rotations of the integer. For example, for input 123, ...
32
votes
6answers
2k views

1, 2, 3, 14… or is it 15?

A well known song by the Irish rock band U2 starts with the singer Bono saying "1, 2, 3, 14" in Spanish ("uno, dos, tres, catorce"). There are various theories as to the significance of those numbers....
3
votes
3answers
223 views

unRSA: solve the private key

Given positive integer n and e, knowing that e<n and that ...
19
votes
3answers
380 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 ...
11
votes
10answers
1k views

Some Lonely Primes

I know, I know, yet another primes challenge... Related A lonely (or isolated) prime is a prime number p such that p-2, ...
20
votes
14answers
1k 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 <...
11
votes
3answers
844 views

Crazy but Rational Bases

We have many challenges based on base 10, base 2, base 36, or even base -10, but what about all the other rational bases? Task Given an integer in base 10 and a rational base, return the integer in ...
12
votes
5answers
630 views

Sparse Protractor

Given some positive integer n, design a protractor with the fewest number of marks that lets you measure all angles that are an integral multiple of ...
31
votes
10answers
1k views

Find the dot product of Rationals

I was at a friend's house for dinner and they suggested the idea of a "Prime-factor vector space". In this space the positive integers are expressed as a vector such that the nth element in the ...
10
votes
4answers
292 views

Continued Fraction of Digit-wise Sum of Square Roots

Introduction Your task is to generate the first 1000 terms in the continued fraction representation of digit-wise sum of square root of 2 and square root of 3. In other words, produce exactly the ...
14
votes
1answer
578 views

Regex for multiples of 9

It is easy to describe a finite state machine that recognizes multiples of 9: keep track of the digit sum (mod 9) and add whatever digit is accepted next. Such a FSM has only 9 states, very simple! By ...
-4
votes
1answer
137 views

Find prime factors of sum of non-composite Fibonacci numbers up to n

The Challenge Given a number, find the sum of the non-composite numbers in the Fibonacci sequence up to that number, and find the prime factors of the sum. For example, if you were given 8, the non-...
24
votes
22answers
3k views

Bertrand's Primes

Bertrand's Postulate states that for every integer n ≥ 1 there is at least one prime p such that n < p ≤ 2n. In order to verify this theorem for n < 4000 ...