# Questions tagged [number-theory]

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

455 questions
Filter by
Sorted by
Tagged with
367 views

### Sums of Euler's totient function in sublinear time

Related. Given a number $n$, Euler's totient function, $\varphi(n)$ is the number of integers up to $n$ which are coprime to $n$. That is, no number bigger than $1$ divides both of them. For ...
1k views

2k views

### Persistence of a number

The persistence of a number $x = d_1d_2d_3...d_n$, with $d_1 \ne 0$, under some function $f : \mathbb N_0 \times \mathbb N_0 \to \mathbb N_0$ is defined as the number of applications of $f$ to ...
828 views

### Sum of partition numbers

The partition function: In number theory, the partition function p(n) represents the number of possible partitions of a positive integer n into positive integers For instance, p(4) = 5 because the ...
2k views

### The second even sublime number

easy mode of my previous challenge A perfect number is a positive integer whose sum of divisors (except itself) is equal to itself. E.g. 6 (1 + 2 + 3 = 6) and 28 (1 + 2 + 4 + 7 + 14 = 28) are perfect. ...
3k views

### An algorithm to find even sublime numbers

A perfect number is a positive integer whose sum of divisors (except itself) is equal to itself. E.g. 6 (1 + 2 + 3 = 6) and 28 (1 + 2 + 4 + 7 + 14 = 28) are perfect. A sublime number (OEIS A081357) is ...
257 views

### Generate a Kirkman triple system

Given a universe of $v$ elements, a Kirkman triple system is a set of $(v-1)/2$ classes each having $v/3$ blocks each having three elements, so that every pair of elements appears in exactly ...
3k views

### Anti-divisors of a number

Given a positive integer n, output all of its anti-divisors in any order. From OEIS A006272: Anti-divisors are the numbers that do not divide a number by the ...
346 views

### Decompose number N into the sum of three triangular numbers [closed]

It is known that any natural number can be decomposed into the sum of three triangular numbers (assuming 0 is triangular), according to Fermat's Polygonal Number Theorem. Your task is to come up with ...
395 views

### Help me design an unfair laundry machine

There's a payment machine for laundry in my building which does a few frustrating things. The ones relevant to this challenge are: It doesn't make change. So if you pay over the amount then you are ...
465 views

3k views

290 views

### Multiplicity of Shared Totients

Euler's totient function, $\varphi(n)$, counts the number of integers $1 \le k \le n$ such that $\gcd(k, n) = 1$. For example, $\varphi(9) = 6$ as $1,2,4,5,7,8$ are all coprime to $9$. ...
794 views

### AoCG2021 Day 14: Adjusting dancing program's period

Part of Advent of Code Golf 2021 event. See the linked meta post for details. Related to AoC2017 Day 16. I'm using the wording from my Puzzling SE puzzle based on the same AoC challenge instead of the ...
2k views

### Sum powers to n

Each natural number (including 0) can be written as a sum of distinct powers of integers (with a minimum exponent of 2). Your task is to output the smallest power required to represent $n$. For ...
2k views

### AoCG2021 Day 4: Infinite Elves and infinite houses 2

Part of Advent of Code Golf 2021 event. See the linked meta post for details. Related to AoC2015 Day 20, Part 1. Here's why I'm posting instead of Bubbler and why not emanresuA To keep the Elves busy,...
617 views

### How to solve the LCM in 50 bytes of Python

I've recently stumbled upon a Russian site called acmp.ru, in which one of the tasks, HOK, asks us to find the LCM of two positive integers. The full statement, translated to English is as follows: ...
2k views

### Harmonic divisor numbers

Consider the $4$ divisors of $6$: $1, 2, 3, 6$. We can calculate the harmonic mean of these numbers as \frac 4 {\frac 1 1 + \frac 1 2 + \frac 1 3 + \frac 1 6} = \frac 4 {\frac {12} 6} = \frac ...
Gobar primes (A347476) are numbers which give a prime number when 0's and 1's are interchanged in their binary representation. For example, $10 = 1010_2$, and if we flip the bits, we get \\$0101_2 = ...