Questions tagged [number-theory]
Number theory involves properties and relationships of numbers, primarily positive integers.
335 questions
15
votes
22answers
1k 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 ...
21
votes
12answers
2k 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
860 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
364 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
647 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
494 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
591 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 ...
28
votes
77answers
13k 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 ...
19
votes
16answers
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 ...
11
votes
11answers
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 ...
7
votes
2answers
189 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
701 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
360 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 ...
17
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, ...
27
votes
4answers
1k 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
189 views
19
votes
3answers
366 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
975 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
825 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 ...
11
votes
5answers
617 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
267 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
486 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
128 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-...
22
votes
20answers
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 ...
14
votes
9answers
678 views
Verify Cyclic Difference Sets
A cyclic difference set is a set of positive integers with a unique property:
Let n be the largest integer in the set.
Let r be ...
23
votes
29answers
2k views
Pascal's Triangle (Sort of)
Most everyone here is familiar with Pascal's Triangle. It's formed by successive rows, where each element is the sum of its two upper-left and upper-right neighbors. Here are the first ...
15
votes
15answers
1k views
The modulo parity party
You are given an array A of n strictly positive integers, with n ≥ 2.
Your task is to map each entry Ai to:
1 if Aj mod Ai is odd for each j such that 1 ≤ j ≤ n and j ≠ i
2 if Aj mod Ai is even for ...
15
votes
19answers
1k views
Make Zero From First 'n' Numbers
Challenge
The challenge is to write a code that takes a positive integer 'n' as an input and displays all the possible ways in which the numbers from 1 - n can be written, with either positive or ...
33
votes
8answers
884 views
Can square tree rings be generated from primes?
Apparently yes! In three easy steps.
Step 1
Let f(n) denote the prime-counting function (number of primes less than or equal to n).
Define the integer sequence s(n) as follows. For each positive ...
26
votes
22answers
2k views
Diluted Integer Sums
A positive integer can be diluted by inserting a 0 between two bits in its binary expansion. This means that an n-bit number has ...
24
votes
12answers
2k views
Write numbers as a difference of Nth powers
Challenge
There are many numbers which can be expressed as the difference of two squares, or as the difference of two cubes, or maybe even higher powers. Talking about squares, there are various ways ...
12
votes
14answers
1k views
Minimise the count of prime factors through insertion
Given two positive integers A and B, return the position p that minimises the number of prime factors (counting multiplicities) of the resulting integer, when B is inserted in A at p.
For example, ...
8
votes
20answers
988 views
Prime numbers between n and 2n [duplicate]
Bertrand's postulate states that there is always at least 1 prime number between n and 2n for all n greater than 1.
Challenge
Your task is to take a positive integer n greater than 1 and find all of ...
21
votes
16answers
2k views
Recursive Collatz Conjecture
The Collatz conjecture postulates that if you take any positive integer, then repeat the following algorithm enough times:
...
16
votes
33answers
2k views
Find the largest number of distinct integers that sum to n
The Task
Given an input positive integer n (from 1 to your language's limit, inclusively), return or output the maximum number of distinct positive integers that ...
