Questions tagged [number-theory]

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

Filter by
Sorted by
Tagged with
192
votes
287answers
44k 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 ...
72
votes
28answers
6k views

Calculate Phi (not Pi)

No, I don't mean ϕ = 1.618... and π = 3.14159.... I mean the functions. φ(x) is the number of integers less than or equal to <...
70
votes
23answers
7k views

Well that's odd… no wait, that's even!

Preamble Integers are always either even or odd. Even integers are divisible by two, odd integers are not. When you add two integers you can infer whether the result will be even or odd based on ...
64
votes
21answers
8k 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 ...
63
votes
196answers
19k views

Is this even or odd?

Note: There is not been a vanilla parity test challenge yet (There is a C/C++ one but that disallows the ability to use languages other than C/C++, and other non-vanilla ones are mostly closed too), ...
63
votes
13answers
9k views

Calculate the number of primes up to n

π(n) is the number of primes less than or equal to n. Input: a natural number, n. Output: π(n). Scoring: This is a fastest-code challenge. Score will be the sum of times for the score cases. I ...
58
votes
39answers
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 ...
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 ...
50
votes
79answers
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: ...
50
votes
43answers
5k views

Coprimes up to N

Given a number n >= 2, output all the positive integers less than n where gcd(n, k) == 1 (...
44
votes
42answers
3k views

Count sums of two squares

Given a non-negative number n, output the number of ways to express n as the sum of two squares of integers ...
44
votes
19answers
7k views

Theoretically output Graham's number

Graham's number G is defined in this way: ...
44
votes
26answers
2k views

Divisor skyline

For any positive integer k, let d(k) denote the number of divisors of k. For example, ...
42
votes
12answers
5k 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 ...
39
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'...
38
votes
62answers
5k 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 ...
38
votes
7answers
2k views

Sharing (characters) is Caring!

Overview Consider the following task: Given a positive integer n > 0, output its integer root. The integer root of a number n is the largest value of x where x2 ≤ n, usually expressed with the ...
37
votes
23answers
3k views

Abandon all squares, ye who divide me

Definitions A perfect square is an integer which can be expressed as the square of another integer. For example, 36 is a perfect square because ...
37
votes
64answers
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: ...
36
votes
34answers
3k views

Replace twos with threes

Given a positive integer n write some code to take its prime factorization and replace all of its factors of 2 with 3. For ...
36
votes
47answers
6k views

Catalan Numbers

The Catalan numbers (OEIS) are a sequence of natural numbers often appearing in combinatorics. The nth Catalan number is the number of Dyck words (balanced strings of parenthesis or brackets such as ...
36
votes
20answers
5k 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. ...
36
votes
14answers
4k views

Incrementing Gray Codes

Introduction A Gray Code is an alternative to binary representation in which a number is incremented by toggling only one bit, rather than a variable amount of bits. Here are some gray codes along ...
35
votes
25answers
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 ...
35
votes
34answers
3k views

Is it a Mersenne Prime?

A number is a Mersenne Prime if it is both prime and can be written in the form 2n-1, where n is a positive integer. Your task is to, given any positive integer, determine whether or not it is a ...
35
votes
20answers
2k views

Sum the powers that be

A simple but hopefully not quite trivial challenge: Write a program or function that adds up the kth powers dividing a number n....
34
votes
31answers
2k views

Sum of Modulo Sums

Given an integer n > 9, for each possible insertion between digits in that integer, insert an addition + and evaluate. Then, ...
34
votes
21answers
2k views

The Arithmetic Derivative

The derivative of a function is a cornerstone of mathematics, engineering, physics, biology, chemistry, and a large number of other sciences as well. Today we're going to be calculating something only ...
33
votes
86answers
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 ...
33
votes
24answers
3k views

Is this number Loeschian?

A positive integer k is a Loeschian number if k can be expressed as i*i + j*j + i*j for <...
33
votes
19answers
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 nth prime such that the prime - 1 is divisible by n. Explanation Here is an example so you understand the question, this is not necessarily the ...
33
votes
8answers
925 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 ...
33
votes
6answers
2k views

Can you reach this number by doubling and rearranging?

Inspired by this question on Math.SE. Starting with 1 you can repeatedly perform one of the following two operations: Double the number. or Rearrange its digits ...
32
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 ...
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....
32
votes
6answers
663 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 <...
32
votes
2answers
2k views

Standardise a Phinary Number

Background Most people on here should be familiar with a few integer base systems: decimal, binary, hexadecimal, octal. E.g. in the hexadecimal system, a number abc.de16 would represent ...
31
votes
42answers
2k views

Least Common Multiple

The least common multiple of a set of positive integers A is the smallest postive integer B such that, for each ...
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 ...
31
votes
6answers
1k views

Are you lost yet?

Your task is to implement integer sequence A130826: an is the smallest positive integer such that an - n is an entire multiple of 3 and twice the number of divisors of (an - n) / 3 gives the nth ...
30
votes
12answers
3k views

That's a prime… almost

If you've ever learned about primes in math class, you've probably have had to, at one point, determine if a number is prime. You've probably messed up while you were still learning them, for example, ...
29
votes
45answers
8k 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-...
29
votes
16answers
2k views

Primitive Pythagorean Triples

(related) A Pythagorean Triple is a list (a, b, c) that satisfies the equation a2 + b2 = c2. A Primitive Pythagorean Triple (PPT) is one where ...
29
votes
13answers
1k views

Pascal's Column Sums

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 ...
29
votes
13answers
2k views

Generate Keyboard Friendly Numbers

Most common computer keyboard layouts have the decimal digit keys 1234567890 running along at their top, above the keys for letters. Let a decimal digit's neighborhood be the set of digits from ...
29
votes
2answers
853 views

Addition on Elliptic Curves

Addition on Elliptic Curves Disclaimer: This does not do any justice on the rich topic of elliptic curves. It is simplified a lot. As elliptic curves recently got a lot of media attention in the ...
28
votes
26answers
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, ...
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 ...
28
votes
12answers
2k views

One-zero dividend

Challenge description For every positive integer n there exists a number having the form of 111...10...000 that is divisible by ...
28
votes
8answers
2k views

Visualize the greatest common divisor

Background The greatest common divisor (gcd for short) is a convenient mathematical function, since it has many useful properties. One of them is Bézout's identity: if ...