# Tagged Questions

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

2k 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 prime to n, that is, the number of possible values of x in 0 < x <=...
446 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 n is the number of digits of the number. For example, ...
826 views
+200

### Fibonacci Factorization

Fibonacci Numbers Fibonacci Numbers start with f(1) = 1 and f(2) = 1 (some includes f(0) = 0 but this is irrelevant to this challenge. Then, for n > 2, f(n) = f(n-1) + f(n-2). The challenge Your ...
936 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 x co-prime to x) applied n times. Testcases n x result 1 10 4 2 10 ...
171 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 7 are twin primes. Let's define the twin number of some set of numbers as the number of twin ...
1k 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 “...
245 views

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, ...
330 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 number in the memory starts at 0. Each consecutive press of + or - will ...
449 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 ...
733 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 ...
137 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 ...
178 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 ...
728 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, ...
281 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 ...
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, the second number because of the second digit, etc. Example Given this ...
351 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 seven can be written 1+1+1+1+1+1+1=7, but it can also be written as 11-1-1-...
371 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 8 7 ...
310 views

### Polygonal numbers

A polygonal number is the number of dots in a k-gon of size n. You will be given n and k, and your task is to write a program/function that outputs/prints the corresponding number. Scoring This is ...
917 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/function that ...
299 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 A can divide B with no remainder. For example, 2 is a divisor of 6 because 2 can ...
285 views

### Find the repetend of the decimal representation!

In this challenge 2 years ago, we found the period of a unit fraction (1/n where n is a natural number). Now, your task is to write a program/function to find the repetend of a unit fraction. The ...
334 views

### m-nomial coefficient

While binomial coefficient is the coefficient of (1+x)**n, m-nomial coefficient is the coefficient of (1+x+x**2+...+x**(m-1))**n. For example, m(3,5,6) is the coefficient of x**6 in the expansion of (...
882 views

### Generate the minimal remainder sequence

Every number can be represented using an infinitely long remainder sequence. For example, if we take the number 7, and perform 7mod2, then 7mod3, then 7mod4, and so on, we get 1,1,3,2,1,0,7,7,7,7,.......
1k views

### Is it really a comcoin?

Very interesting background Comcoins are a currency like any other. The residents of Multibaseania (an economically robust system of city-states with very few residents in a galaxy far, far away) use ...
161 views

### Ponderous primality testing [closed]

One of my favorite algorithms was posted on Stack Overflow as an answer to What is the fastest way to generate prime number recursively?. In pseudocode: Nathan's algorithm bool isPrime(int n): ...
2k 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 ...
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 ...
264 views

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 ...
851 views

### Highly composite numbers

A highly composite number is a positive integer that has more divisors than any smaller positive integer has. This is OEIS sequence A002182. Its first 20 terms are 1, 2, 4, 6, 12, 24, 36, 48, 60, 120,...
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 n i.e. a decimal number that starts with all 1's and ends with all 0's. ...
2k 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 ...
1k views

### Generate lazy values

Related: Program my microwave oven. Inspired by Generate lazy microwave input. The lazy value of the non-negative integer N is the smallest of the integers that are closest to N while all their ...
2k 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, ...
1k views

### Output the juggler sequence

The juggler sequence is described as follows. Beginning with an input a1, the next term is defined by the recurrence relation The sequence terminates when it reaches 1, as all subsequent terms ...
3k 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. ...
45 views

### Quotient in base 31 numeral system [closed]

You're given two numbers a and b in base 31 numeral system and number k with no more than 10000 decimal digits. It is known that b is divisor of a. The task is to find last k 31-based-digits of ...
212 views

### Residue Number System

In the vein of large number challenges I thought this one might be interesting. In this challenge, we will be using the Residue Number System (RNS) to perform addition, subtraction, and ...
400 views

### Print the Super Collatz numbers

The Collatz Sequence (also called the 3x + 1 problem) is where you start with any positive integer, for this example we will use 10, and apply this set of steps to it: if n is even: Divide it by ...
1k views

### Split, flip and recombine integers

Background It's well known in mathematics that integers can be put into a one-to-one correspondence with pairs of integers. There are many possible ways of doing this, and in this challenge, you'll ...
7k views

### List Prime Numbers [duplicate]

Introduction Prime numbers are simple, right? Well, now you get your chance to find out! Challenge You must write a program or function that takes an input n and outputs the first n prime numbers. ...
2k views

### The Möbius Function

The Möbius Function The Möbius function is an important number theoretic function. Your submission should accept a positive integer n and return the value of the Möbius function evaluated at n. ...
271 views

### Bézout's Identity

Introduction to Bézout's identity The GCD of two integers A, B is the largest positive integer that divides both of them leaving no remainder. Now because of Euclid's property that each integer N can ...
276 views

### Primitive Roots of Unity

Let z be a complex number. z is an nth primitive root of unity if for a certain positive integer n and for any positive integer k < n . Challenge Write a full program or function that, given a ...
171 views

### Calculate the Number, Divisors Edition

Inspired by this question over on Math. Let the prime factorization of a number, n, be represented as P(n) = 2a x 3b x 5c x .... (Using x as the multiplication symbol.) Then the number of divisors of ...
397 views

### Base Conversion With Strings

Introduction We've have a few base conversion challenges here in the past, but not many designed to tackle arbitrary length numbers (that is to say, numbers that are long enough that they overflow ...
240 views

### Partitioning reciprocals

Given a number n > 77, write a program or function that finds a set of distinct positive integers such that the sum of the set equals n, and the sum of the reciprocals of the set equals 1. Example ...
957 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 d = gcd(a, b), then there exist ...
3k views

### What's a half on the clock?

In my room, I have this geeky clock (click for full size): Most of these are not difficult to figure out, but the one for 4-o-clock is particularly tricky: Normally, a fraction like 1/2 doesn't ...