A Project Euler heatmap with cleaner browsing.
The archive now starts with a dense clickable problem board, then a compact result list below it. Use search when you know what you want, or scan the heatmap when you do not.
Every solved problem in one board
Filtered entries
Multiples of 3 and 5
Find the sum of all the multiples of 3 or 5 below 1000. That is, compute S = sum_(1 <= k < 1000, 3 | k or 5 | k) k.
Even Fibonacci Numbers
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms. That is, compute S = sum_(F_n <= 4,000,000, 2 | F_n) F_n where F_1...
Largest Prime Factor
What is the largest prime factor of the number 600,851,475,143?
Largest Palindrome Product
Find the largest palindrome made from the product of two 3-digit numbers. That is, determine M = maxbigl{xy: 100 <= x,y <= 999, xy is a palindrome in base 10bigr}.
Smallest Multiple
Determine the smallest positive integer divisible by every integer from 1 to 20. Formally, compute L = lcm(1, 2, 3,..., 20).
Sum Square Difference
Compute the difference between the square of the sum and the sum of the squares of the first 100 natural numbers: D(100) = (sum_(i=1)^100 i)^2 - sum_(i=1)^100 i^2.
10001st Prime
Determine the 10001st prime number, where primes are indexed as p_1 = 2, p_2 = 3, p_3 = 5,...
Largest Product in a Series
Given a 1000-digit number D = d_0 d_1... d_999 (where each d_i in {0, 1,..., 9}), find the maximum product of 13 consecutive digits: M = max_(0 <= i <= 987) prod_(j=0)^12 d_(i+j).
Special Pythagorean Triplet
A Pythagorean triplet is a tuple of positive integers (a, b, c) with a < b < c and a^2 + b^2 = c^2. Find the unique such triplet satisfying a + b + c = 1000, and compute the product abc.
Summation of Primes
Compute sum_(p prime, p < 2,000,000) p.
Largest Product in a Grid
Let G = (g_(i,j))_(0 <= i,j <= 19) be a 20 x 20 matrix of non-negative integers (given below). Find the greatest product of four adjacent entries along any horizontal, vertical, or diagonal line.
Highly Divisible Triangular Number
The n -th triangular number is T_n = (n(n+1))/(2). Find the smallest T_n with tau(T_n) > 500, where tau(m) denotes the number of positive divisors of m.
Large Sum
Given N = 100 positive integers, each having exactly D = 50 decimal digits, compute the first 10 digits of their sum S = sum_(i=1)^N a_i.
Longest Collatz Sequence
Define the Collatz map C: Z^+ -> Z^+ by C(n) = n/2 & if 2 | n, 3n + 1 & if 2 nmid n. The Collatz sequence from n_0 is (n_0, C(n_0), C^2(n_0),...). The chain length L(n) is the number of terms in th...
Lattice Paths
Starting at the top-left corner of a 20 x 20 grid, how many routes exist to the bottom-right corner if only rightward and downward moves are permitted? Formally: count the number of monotone lattic...
Power Digit Sum
Let S(m) denote the sum of the decimal digits of a positive integer m. Compute S(2^1000).
Number Letter Counts
Let ell(n) denote the number of letters (excluding spaces and hyphens) in the British English representation of the positive integer n. Compute sum_(n=1)^1000 ell(n). Convention. British English us...
Maximum Path Sum I
Let T be a triangular array of 15 rows. A path from the apex to the base selects one entry per row such that each successive entry is adjacent (directly below or below-right) to its predecessor. Fi...
Counting Sundays
Given that 1 January 1900 was a Monday, determine the number of Sundays that fell on the first of the month during the period 1 January 1901 to 31 December 2000 (inclusive).
Factorial Digit Sum
Let S(m) denote the sum of the decimal digits of a positive integer m. Compute S(100!).
Amicable Numbers
Let d(n) denote the sum of proper divisors of n (i.e., divisors strictly less than n). If d(a) = b and d(b) = a with a!= b, then a and b form an amicable pair. Compute the sum of all amicable numbe...
Names Scores
Given a text file of over five thousand first names, sort the names into lexicographic (alphabetical) order. Define the alphabetical value of a name as the sum of the positional values of its lette...
Non-Abundant Sums
A positive integer n is perfect if s(n) = n, deficient if s(n) < n, and abundant if s(n) > n, where s(n) = sigma_1(n) - n is the sum of proper divisors. It is known that every integer greater than...
Lexicographic Permutations
A permutation is an ordered arrangement of objects. The lexicographic permutations of {0, 1, 2} are: 012, 021, 102, 120, 201, 210. What is the millionth lexicographic permutation of the digits {0,...
1000-Digit Fibonacci Number
The Fibonacci sequence is defined by F_1 = 1, F_2 = 1, and F_n = F_(n-1) + F_(n-2) for n >= 3. Determine the index of the first term to contain 1000 digits.
Reciprocal Cycles
Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.
Quadratic Primes
Considering quadratics of the form n^2 + an + b where |a| < 1000 and |b| <= 1000, find the product of the coefficients a and b that produces the maximum number of primes for consecutive values of n...
Number Spiral Diagonals
Starting with the number 1 at the center and spiraling clockwise, a number spiral is formed. Find the sum of the numbers on the diagonals of a 1001 x 1001 spiral.
Distinct Powers
Consider all integer combinations of a^b for 2 <= a <= 100 and 2 <= b <= 100. How many distinct terms are in the sequence?
Digit Fifth Powers
Find the sum of all numbers that can be written as the sum of fifth powers of their digits. (By convention, 1 = 1^5 is excluded since it is not a "sum.")
Coin Sums
In England the currency is made up of pound and pence. There are eight coins in general circulation: 1p, 2p, 5p, 10p, 20p, 50p, 100p (£1), and 200p (£2) How many different ways can £2 (200p) be mad...
Pandigital Products
We say that an n -digit number is pandigital if it uses all the digits 1 to n exactly once. Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through...
Digit Cancelling Fractions
The fraction 49/98 is a curious fraction, because an inexperienced mathematician might incorrectly simplify it by cancelling the 9s, obtaining 49/98 = 4/8, which happens to be correct. We shall con...
Digit Factorials
145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145. Find the sum of all numbers which are equal to the sum of the factorial of their digits. Note: As 1! = 1 and 2! = 2 are not sums, they...
Circular Primes
The number 197 is called a circular prime because all rotations of its digits are prime: 197, 971, and 719. How many circular primes are there below one million?
Double-base Palindromes
Find the sum of all natural numbers less than 10^6 that are palindromic in both base 10 and base 2. Leading zeros are not permitted in either representation.
Truncatable Primes
Find the sum of the only eleven primes that are both truncatable from left to right and right to left. Single-digit primes (2, 3, 5, 7) are excluded.
Pandigital Multiples
For a fixed positive integer x, form the concatenated product of x with (1, 2,..., n) for some n > 1. What is the largest 1-to-9 pandigital 9-digit number achievable?
Integer Right Triangles
For which value of p <= 1000 is the number of integer-sided right triangles with perimeter p maximized?
Champernowne's Constant
An irrational decimal fraction is created by concatenating the positive integers: 0.123456789101112131415161718192021... If d_n represents the n -th digit of the fractional part, find the value of:...
Pandigital Prime
We say that an n -digit number is pandigital if it uses each of the digits 1, 2,..., n exactly once. Find the largest n -digit pandigital number that is also prime.
Coded Triangle Numbers
The n -th triangle number is T_n = (n(n+1))/(2). By converting each letter in a word to its alphabetical position (A=1, B=2,..., Z=26) and summing, we obtain a word value. A word is a triangle word...
Sub-string Divisibility
Let d_1 d_2 d_3... d_10 be a 0 -to- 9 pandigital number (a permutation of the digits {0,1,...,9}). We require the following sub-string divisibility conditions: | Substring | Divisor | |-----------|...
Pentagon Numbers
Pentagonal numbers are generated by P_n = (n(3n-1))/(2) for n >= 1. Find the pair of pentagonal numbers P_j and P_k (with j < k) for which both their sum P_j + P_k and difference P_k - P_j are pent...
Triangular, Pentagonal, and Hexagonal
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae: | Type | Formula | Sequence | |------------|----------------------------|-----------------------| | Triangle | T...
Goldbach's Other Conjecture
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square. It turns out that the conjecture was false. What is the smallest odd c...
Distinct Primes Factors
Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?
Self Powers
The series 1^1 + 2^2 + 3^3 +... + 10^10 = 10,405,071,317. Find the last ten digits of the series 1^1 + 2^2 + 3^3 +... + 1000^1000.
Prime Permutations
The arithmetic sequence 1487, 4817, 8147, in which each term increases by 3330, is unusual in two ways: (i) each of the three terms is prime, and (ii) each of the three 4-digit numbers are permutat...
Consecutive Prime Sum
Which prime, below one million, can be written as the sum of the most consecutive primes?
Prime Digit Replacements
By replacing the 1st digit of the 2-digit number \3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime. By replacing the 3rd and 4th digits of 56\\3 with...
Permuted Multiples
Find the smallest positive integer x such that 2x, 3x, 4x, 5x, and 6x contain the same digits as x.
Combinatoric Selections
How many values of C(n, r) for 1 <= n <= 100 and 0 <= r <= n are greater than one million?
Poker Hands
The file poker.txt contains one-thousand random hands dealt to two players. Each line contains ten cards (separated by spaces): the first five are Player 1's hand and the last five are Player 2's h...
Lychrel Numbers
A Lychrel number is a number that never forms a palindrome through the reverse-and-add process. Working with the assumption that a number is Lychrel if it has not produced a palindrome within 50 it...
Powerful Digit Sum
A digital sum (or digit sum) of a natural number is the sum of its decimal digits. Considering natural numbers of the form a^b, where a, b < 100, find the maximum digital sum.
Square Root Convergents
The square root of 2 can be expressed as the infinite continued fraction sqrt(2) = 1 + cfrac12 + cfrac12 + cfrac12 +... By expanding this for the first one thousand iterations, one obtains successi...
Spiral Primes
Starting with 1 and spiralling anticlockwise, a square spiral with side length s is formed. The diagonals of this spiral contain certain values. What is the side length of the square spiral for whi...
XOR Decryption
A text file has been encrypted by XOR-ing each byte with a repeating key of three lowercase ASCII characters. Given the ciphertext (as a sequence of ASCII codes), decrypt the message and find the s...
Prime Pair Sets
Define two primes p and q to be a prime pair if both concatenations p \| q and q \| p are themselves prime. Find the smallest sum of a set of five primes in which every pair of distinct elements fo...
Cyclical Figurate Numbers
Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers generated by: | Type | Formula | Sequence | |------|---------|----------| | Triangle...
Cubic Permutations
The cube 41063625 = 345^3 can be obtained by permuting the digits of 56623104 = 384^3. Find the smallest cube for which exactly five permutations of its digits are also cubes.
Powerful Digit Counts
How many n -digit positive integers exist which are also an n -th power?
Odd Period Square Roots
How many continued fractions for sqrt(N), N <= 10000 (where N is not a perfect square), have an odd period?
Convergents of e
Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.
Diophantine Equation
Consider quadratic Diophantine equations of the form: x^2 - Dy^2 = 1 For example, when D = 13, the minimal solution in x is 649^2 - 13 x 180^2 = 1. It can be assumed that there are no solutions in...
Maximum Path Sum II
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23. That is, 3 + 7 + 4 + 9 = 23. Find the maximum total from to...
Magic 5-gon Ring
Consider a "magic" 5-gon ring, filled with the numbers 1 to 10. Working clockwise, and starting from the group of three with the numerically lowest external node, each solution can be described by...
Totient Maximum
Euler's totient function, varphi(n), counts the number of integers k with 1 <= k <= n that are relatively prime to n. Find the value of n <= 1,000,000 for which n / varphi(n) is a maximum.
Totient Permutation
Find the value of n, 1 < n < 10^7, for which varphi(n) is a permutation of the digits of n and the ratio n/varphi(n) is minimized.
Ordered Fractions
By listing the set of reduced proper fractions n/d (with gcd(n,d) = 1 and 0 < n < d) for d <= 1,000,000 in ascending order, find the numerator of the fraction immediately to the left of 3/7.
Counting Fractions
Consider the fraction n/d, where n and d are positive integers. If n < d and gcd(n, d) = 1, it is called a reduced proper fraction. How many elements are in the set of reduced proper fractions for...
Counting Fractions in a Range
How many reduced proper fractions n/d with gcd(n, d) = 1 lie strictly between 1/3 and 1/2 for d <= 12,000?
Digit Factorial Chains
Define the digit factorial function by replacing a number with the sum of the factorials of its digits. Starting from any positive integer, repeated application forms a chain that eventually cycles...
Singular Integer Right Triangles
Given that L is the perimeter of a right triangle with integer sides, for how many values of L <= 1,500,000 can exactly one integer-sided right triangle be formed?
Counting Summations
It is possible to write five as a sum in exactly six different ways: How many different ways can one hundred be written as a sum of at least two positive integers?
Prime Summations
It is possible to write ten as the sum of primes in exactly five different ways: What is the first value which can be written as the sum of primes in over five thousand different ways?
Coin Partitions
Let p(n) represent the number of different ways in which n coins can be separated into piles. Find the least value of n for which p(n) is divisible by one million.
Passcode Derivation
A common security method for online banking is to ask the user for three random characters from a passcode. Given 50 successful login attempts where each attempt reveals a 3-character subsequence o...
Square Root Digital Expansion
For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all irrational square roots.
Path Sum: Two Ways
In the 80x80 matrix below, find the minimal path sum from the top-left to the bottom-right by only moving right and down. The matrix is provided as a text file from Project Euler.
Path Sum: Three Ways
In the same 80x80 matrix, find the minimal path sum from any cell in the left column to any cell in the right column, where at each step you may move right, up, or down (but not left).
Path Sum: Four Ways
In the same 80x80 matrix, find the minimal path sum from the top-left to the bottom-right, where you may move up, down, left, or right at each step.
Monopoly Odds
In a simplified Monopoly game with two 4-sided dice, find the three most visited squares. Express the answer as a six-digit string of their two-digit square numbers (in descending order of frequency).
Counting Rectangles
By counting carefully, it can be verified that a rectangular grid that is 3 by 2 contains 18 rectangles. Find the area of the grid with the nearest number of rectangles to two million (T = 2,000,000).
Cuboid Route
A spider is located at one corner of a cuboid room with dimensions a x b x c, and a fly is at the diagonally opposite corner. By travelling on the surfaces of the room, find the shortest "straight...
Prime Power Triples
How many numbers below 50,000,000 can be expressed as the sum of a prime square, prime cube, and prime fourth power? n = p^2 + q^3 + r^4 where p, q, r are primes.
Product-sum Numbers
A natural number N can be written as both the sum and product of a set of at least two natural numbers {a_1, a_2,..., a_k}: N = a_1 + a_2 +... + a_k = a_1 x a_2 x... x a_k For a given k, the smalle...
Roman Numerals
The Project Euler data file contains one thousand Roman numerals written in valid (but not necessarily minimal) form. Find the number of characters saved by rewriting each numeral in its minimal form.
Cube Digit Pairs
Two cubes each have 6 faces with a distinct digit (0-9) on each face. By placing the two cubes side by side, we can form two-digit square numbers: 01, 04, 09, 16, 25, 36, 49, 64, 81. The digit 6 an...
Right Triangles with Integer Coordinates
Let O=(0,0), P=(x_1,y_1), Q=(x_2,y_2), with all coordinates integers in [0,50]. We ask for the number of right triangles OPQ.
Square Digit Chains
Define f(n)=sum of the squares of the decimal digits of n. Starting from a positive integer n, repeatedly apply f. Every chain eventually enters a cycle. We must count how many starting numbers n<1...
Arithmetic Expressions
Choose four distinct digits {a,b,c,d}subset{1,2,...,9}, a<b<c<d. Using each digit exactly once, together with the operations +,-,x,/ and arbitrary parentheses, we obtain a set of values. We seek th...
Almost Equilateral Triangles
An almost equilateral triangle is a triangle with sides (a, a, a +/- 1) where a >= 2. Find the sum of the perimeters of all almost equilateral triangles with integral area whose perimeters do not e...
Amicable Chains
Define s(n) = sigma(n) - n, the sum of proper divisors of n. An amicable chain of length k is a cycle n_1 -> n_2 ->... -> n_k -> n_1 under the map s, where all n_i are distinct. Find the smallest e...
Su Doku
A Sudoku puzzle requires filling a 9 x 9 grid so that each row, each column, and each of the nine 3 x 3 sub-boxes contains every digit from 1 to 9 exactly once. Given fifty Su Doku puzzles, solve a...
Large Non-Mersenne Prime
In 2004, a massive non-Mersenne prime was discovered: N = 28433 x 2^7830457 + 1. Find the last ten digits of N.
Anagramic Squares
An anagram pair consists of two distinct words that are permutations of the same multiset of letters. A square anagram word pair is an anagram pair (w_1, w_2) admitting an injective mapping varphi...
Largest Exponential
Given a file containing 1000 lines, each with a base/exponent pair (a_i, b_i), determine which line number has the greatest value a_i^(b_i).
Arranged Probability
A box contains n coloured discs, of which b are blue. When two discs are drawn at random without replacement, the probability of drawing two blue discs is exactly 1/2: (b)/(n) * (b-1)/(n-1) = (1)/(...
Optimum Polynomial
If we are given the first k terms of a sequence, it is not always possible to determine the generating function. For example, consider the sequence of cube numbers: 1, 8, 27, 64, 125, 216,... If we...
Triangle Containment
Three distinct points are plotted at random on a Cartesian plane, for which -1000 <= x, y <= 1000, such that a triangle is formed. Given a file containing the coordinates of one thousand triangles,...
Special Subset Sums: Optimum
Let S(A) denote the sum of elements in a set A of positive integers. We call A a special sum set if for any two non-empty disjoint subsets B, C subseteq A: 1. S(B)!= S(C) (distinct subset sums). 2....
Pandigital Fibonacci Ends
The Fibonacci sequence is defined by F_1 = F_2 = 1 and F_n = F_(n-1) + F_(n-2) for n >= 3. Find the smallest index k such that both the first 9 digits and the last 9 digits of F_k are 1--9 pandigit...
Special Subset Sums: Testing
Let S(A) denote the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty, disjoint subsets B and C, the following properties hold: 1. S(B)!= S(C); that is...
Special Subset Sums: Meta-testing
Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true: 1. S(B)!= S(C);...
Minimal Network
Given an undirected weighted network represented as a 40-vertex adjacency matrix, find the maximum saving which can be achieved by removing redundant edges whilst ensuring that the network remains...
Diophantine Reciprocals I
Find the least value of n such that the number of distinct solutions of (1)/(x) + (1)/(y) = (1)/(n) exceeds 1000.
Darts
In the game of darts, a player throws a dart at a target to score points. The board provides the following possible scores per dart: Singles: 1-20 and 25 (bull's eye outer) Doubles: D1-D20 and D25...
Diophantine Reciprocals II
Find the least value of n such that the number of distinct solutions of (1)/(x) + (1)/(y) = (1)/(n) exceeds four million (4,000,000).
Primes with Runs
For n -digit primes, define: M(n, d): the maximum number of repeated occurrences of digit d in an n -digit prime, N(n, d): the count of n -digit primes achieving M(n, d) repetitions of d, S(n, d):...
Bouncy Numbers
A positive integer is increasing if its digits form a non-decreasing sequence from left to right, decreasing if they form a non-increasing sequence, and bouncy if it is neither. Find the least posi...
Non-bouncy Numbers
A positive integer is increasing if its digits are non-decreasing from left to right, decreasing if non-increasing, and bouncy otherwise. How many numbers below a googol (10^100) are not bouncy?
Counting Block Combinations I
A row of length n is filled with red blocks of minimum length 3 and black unit squares, subject to the constraint that any two red blocks are separated by at least one black square. For n = 7 there...
Counting Block Combinations II
A row measuring n units in length has red blocks with a minimum length of m units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least on...
Red, Green or Blue Tiles
A row of five black square tiles needs to have a number of its tiles replaced with coloured oblong tiles chosen from: red tiles (length 2), green tiles (length 3), or blue tiles (length 4). If red...
Red, Green, and Blue Tiles
Using a combination of grey squares (length 1), red tiles (length 2), green tiles (length 3), and blue tiles (length 4), in how many ways can a row measuring fifty units in length be tiled? Note: T...
Pandigital Prime Sets
Using all of the digits 1 through 9 exactly once, and concatenating them to form individual numbers, how many distinct sets of primes can be formed?
Digit Power Sum
The number 512 is interesting because it is equal to the sum of its digits raised to some power: 5 + 1 + 2 = 8, and 8^3 = 512. Another example is 614656 = 28^4. We define a_n as the n -th term of t...
Square Remainders
Let r be the remainder when (a-1)^n + (a+1)^n is divided by a^2. For 3 <= a <= 1000, find sum r_max, where r_max is the maximum value of r over all positive integers n.
Disc Game Prize Fund
A bag contains one red disc and one blue disc. In a game of chance, the player pays $1 to play and the following procedure is repeated each turn: A red disc is added to the bag. A disc is randomly...
Efficient Exponentiation
The most efficient way to compute x^n uses the minimum number of multiplications, where each multiplication computes x^(a_i + a_j) from previously computed powers x^(a_i) and x^(a_j). This minimum...
Prime Square Remainders
Let p_n denote the n -th prime (p_1 = 2, p_2 = 3, p_3 = 5, etc.). Define r_n = [(p_n - 1)^n + (p_n + 1)^n] mod p_n^2. Find the least value of n for which r_n first exceeds 10^10.
Ordered Radicals
The radical of n, denoted rad(n), is the product of the distinct prime factors of n. For example, rad(504) = 2 x 3 x 7 = 42. By convention, rad(1) = 1. Sort the integers 1 <= n <= 100,000 by the pa...
Palindromic Sums
Find the sum of all positive integers less than 10^8 that are both palindromic (in base 10) and expressible as the sum of consecutive positive squares with at least two terms.
Cuboid Layers
The minimum number of cubes to cover every visible face on a cuboid measuring 3 x 2 x 1 is twenty-two. If we then add a second layer to this solid it would require forty-six cubes, the third layer...
abc-hits
The radical of n, rad(n), is the product of the distinct prime factors of n. A triple (a, b, c) is an abc-hit if: 1. gcd(a, b) = 1 2. a < b 3. a + b = c 4. rad(abc) < c Find sum c for all abc-hits...
Hexagonal Tile Differences
Hexagonal tiles are arranged in concentric rings around tile 1. For each tile n, define PD(n) as the count of differences between n and its six neighbors that are prime. Find the 2000th tile for wh...
Repunit Divisibility
A number consisting entirely of ones is called a repunit. Define R(k) = underbrace11ldots1_k. Given that n is a positive integer and gcd(n, 10) = 1, there always exists k such that n | R(k). Let A(...
Composites with Prime Repunit Property
Define R(k) as the repunit of length k and A(n) as the least k such that n | R(k). For all primes p > 5, it is known that A(p) | (p-1). Find the sum of the first 25 composite values of n for which...
Prime Cube Partnership
There are some primes p for which there exists a positive integer n such that the expression n^3 + n^2 p is a perfect cube. How many primes below one million satisfy this property?
Large Repunit Factors
A number consisting entirely of ones is called a repunit: R(k) = underbrace11ldots1_k = (10^k - 1)/(9). Find the sum of the first forty prime factors of R(10^9).
Repunit Nonfactors
A repunit R(k) = (10^k - 1)/(9). Find the sum of all primes below 100,000 that will never be a factor of R(10^n) for any positive integer n.
Prime Pair Connection
For consecutive primes p_1 and p_2 where 5 <= p_1 and p_2 <= 1,000,003, find S(p_1, p_2), the smallest positive integer whose last digits equal p_1 and which is divisible by p_2. Find sum S(p_1, p_...
Same Differences
Given the positive integers x, y, z are consecutive terms of an arithmetic progression, how many values of n less than one million have exactly ten solutions to x^2 - y^2 - z^2 = n?
Singleton Difference
The positive integers x, y, and z are consecutive terms of an arithmetic progression. Given that n is a positive integer, the equation x^2 - y^2 - z^2 = n has exactly one solution for how many valu...
Fibonacci Golden Nuggets
Consider the infinite polynomial series A_F(x) = xF_1 + x^2F_2 + x^3F_3 +..., where F_k is the k -th term in the Fibonacci sequence: 1, 1, 2, 3, 5, 8,.... Find the 15th golden nugget, where a golde...
Special Isosceles Triangles
Consider an isosceles triangle with base b, equal legs of length L, and height h (from the apex perpendicular to the base). The constraint is |b - h| = 1 (the base and height differ by exactly 1),...
Pythagorean Tiles
Given a right triangle with integer sides (a, b, c) (a Pythagorean triple, a^2 + b^2 = c^2) and perimeter at most 100,000,000, how many such triples allow the square on the hypotenuse to be perfect...
Modified Fibonacci Golden Nuggets
Consider the modified Fibonacci-like sequence defined by G_1 = 1, G_2 = 4, G_k = G_(k-1) + G_(k-2). The generating function is: A_G(x) = xG_1 + x^2 G_2 + x^3 G_3 +... = (x + 3x^2)/(1 - x - x^2) A "...
Investigating Progressive Numbers
A positive integer n is called progressive if, when dividing n by some positive integer d, the quotient q and remainder r satisfy: q, d, r form a geometric sequence (in that order) with q > d > r >...
Perfect Square Collection
Find the smallest x + y + z with x > y > z > 0 such that all six quantities x+y, x-y, x+z, x-z, y+z, y-z are perfect squares.
Investigating the Torricelli Point of a Triangle
Let ABC be a triangle with all interior angles less than 120 degrees. Let T be the Torricelli (Fermat) point of the triangle, and let p = |AT|, q = |BT|, r = |CT|. It can be shown that p, q, r sati...
Investigating Multiple Reflections of a Laser Beam
A laser beam enters a white cell (an ellipse defined by 4x^2 + y^2 = 100) at the point (0, 10.1) and first hits the mirror at (1.4, -9.6). Each time the beam hits the surface, it is reflected accor...
How Many Reversible Numbers Are There Below One Billion
Some positive integers n have the property that n + reverse(n) consists entirely of odd digits. Such numbers are called reversible. Leading zeros are not allowed, so n must not end with 0 (and thus...
Investigating a Prime Pattern
The smallest positive integer n for which the numbers n^2+1, n^2+3, n^2+7, n^2+9, n^2+13, and n^2+27 are consecutive primes is 10. Find the sum of all integers n, 0 < n < 150,000,000, such that n^2...
Rectangles in Cross-hatched Grids
In a cross-hatched grid (a grid with both horizontal/vertical lines and diagonal lines through each cell), rectangles can be placed either aligned with the grid axes or tilted at 45 degrees along t...
Exploring Pascal's Triangle
How many entries in the first 10^9 rows of Pascal's triangle are not divisible by 7? (Rows are numbered starting from row 0 at the top.)
Searching for a Maximum-sum Subsequence
Find the greatest sum of any contiguous subsequence in any direction (horizontal, vertical, diagonal, anti-diagonal) in a 2000 x 2000 table generated by a lagged Fibonacci generator.
Searching a Triangular Array for a Sub-triangle Having the Minimum-sum
In a triangular array with 1000 rows, the entries are generated by a linear congruential generator: t_k = (615949 * t_(k-1) + 797807) mod 2^20, t_0 = 0 s_k = t_k - 2^19 Row r (0-indexed) has r+1 en...
Paper Sheets of Standard Sizes
A printing shop runs 16 batches per job. For each batch, they take one sheet of paper at random from an envelope. At the beginning, the envelope contains a single A1 sheet. Whenever an A n sheet (w...
Writing 1/2 as a Sum of Inverse Squares
Find the number of distinct subsets S subseteq {2, 3,..., 80} such that sum_(k in S) (1)/(k^2) = (1)/(2).
Investigating Gaussian Integers
For 1 <= n <= N = 10^8, find sum_(n=1)^N R(n), where R(n) is the sum of the real parts of all Gaussian integer divisors of n that have positive real part. A Gaussian integer g = a + bi (with a, b i...
Exploring Pascal's Triangle
How many entries C(200000, i,j,k) = (200000!)/(i! j! k!) with i + j + k = 200000 are divisible by 10^12?
Counting Capacitor Circuits
Using up to 18 unit capacitors (each of capacitance 1) connected in series and/or parallel combinations, how many distinct capacitance values can be obtained? Let D(n) be the set of distinct capaci...
Counting Digits
For each digit d from 1 to 9, define f(n, d) as the number of times digit d appears when writing all integers from 1 to n. Find the sum of all n satisfying f(n, d) = n, summed over all digits d fro...
Solving the Equation 1/a + 1/b = p / 10^n
For each n from 1 to 9, count the number of solutions (a, b, p) where a, b, p are positive integers with a <= b, satisfying: (1)/(a) + (1)/(b) = (p)/(10^n) Sum the counts over n = 1, 2,..., 9.
Exploring Strings for Which Only One Character Comes Lexicographically After Its Neighbour to the Left
Taking three different letters from the 26 letters of the alphabet, characters strings of length 3 can be formed. For each length n where 1 <= n <= 26, let p(n) be the number of strings of length n...
Digital Root Sums of Factorisations
The digital root of a number is found by repeatedly summing its digits until a single digit remains. For example, dr(627) = dr(15) = 6. For a composite number n, a "digital root sum" (drs) of a fac...
Factorial Trailing Digits
Find the last 5 non-trailing-zero digits of N! where N = 10^12. In other words, find f(N) = N! / 10^(v_5(N!)) (mod 10^5), where v_5(N!) is the 5-adic valuation of N!.
Triominoes
A triomino is a shape consisting of three unit squares joined edge-to-edge. There are exactly two combinatorial types: the I-triomino (three collinear squares) and the L-triomino (three squares for...
Hexadecimal Numbers
In the hexadecimal number system, numbers are represented using 16 digits: 0, 1, 2,..., 9, A, B, C, D, E, F. How many hexadecimal numbers containing at most sixteen hexadecimal digits exist with al...
Cross-hatched Triangles
Consider an equilateral triangle of side length n subdivided by a triangular grid (lines parallel to each side at unit spacing) and further cross-hatched by lines from each vertex through equally-s...
Numbers for Which No Three Consecutive Digits Have a Sum Greater Than a Given Value
How many 20-digit numbers n (without any leading zeros) exist such that no three consecutive digits of n have a sum greater than 9?
Intersections
A segment is uniquely defined by its two endpoints. By considering two line segments in plane geometry there are three possibilities: the segments have zero points, exactly one point, or infinitely...
Criss Cross
A 4 x 4 grid is filled with digits d (0 <= d <= 9), and we require that every row, every column, and both main diagonals all share the same sum S. How many such grids exist?
Investigating Ulam Sequences
For 2 <= n <= 10, find U(2, 2n+1)(10^11) -- the (10^11) -th term of the Ulam sequence U(2, 2n+1) -- and compute the sum of these values. An Ulam sequence U(a, b) with a < b starts with a, b and the...
Number Rotations
Find all integers n with 10 <= n < 10^100 such that moving the last digit of n to the front produces a number that is an exact multiple of n. Sum the last 5 digits of all such n.
Exploring the Number of Different Ways a Number Can Be Expressed as a Sum of Powers of 2
Define f(n) as the number of ways to express n as a sum of powers of 2, where each power of 2 is used at most twice. Find f(10^25).
Find the Largest 0 to 9 Pandigital That Can Be Formed by Concatenating Products
Take the number 6 and multiply it by each of 1273 and 9854: 6 x 1273 = 7638 6 x 9854 = 59124 By concatenating these products we get the 1 to 9 pandigital 763859124. Notice that the concatenation of...
Finding Numbers for Which the Sum of the Squares of the Digits Is a Perfect Square
For a positive integer n, let f(n) denote the sum of the squares of the digits of n in base 10. Find the last nine digits of sum_(0 < n < 10^(20 f(n) is a perfect square)) n.
Investigating Numbers with Few Repeated Digits
How many 18-digit numbers n (without leading zeros) are there such that no digit occurs more than three times in n?
Using Up to One Million Tiles How Many Different "Hollow" Square Laminae Can Be Formed?
A hollow square lamina is formed by removing a smaller concentric square hole from a larger square. Using up to N = 10^6 unit-square tiles, how many distinct hollow square laminae can be formed?
Counting the Number of "Hollow" Square Laminae That Can Form One, Two, Three, ... Distinct Arrangements
Define N(t) as the number of hollow square laminae that can be formed using exactly t tiles. How many values of t <= 10^6 satisfy 1 <= N(t) <= 10?
Fractions Involving the Number of Different Ways a Number Can Be Expressed as a Sum of Powers of 2
Define f(n) as the number of ways to write n as a sum of powers of 2, where each power is used at most twice. The ratio f(n)/f(n-1) enumerates every positive rational exactly once via the Calkin-Wi...
Right-angled Triangles That Share a Cathetus
The four right triangles with sides (9,12,15), (12,16,20), (5,12,13), and (12,35,37) all share a cathetus (leg) of length 12. It can be shown that no other integer right triangle exists with 12 as...
Integer Angled Quadrilaterals
Let ABCD be a convex quadrilateral with diagonals AC and BD. At each vertex, the diagonal makes an angle with each of the two sides, creating eight corner angles. How many non-similar convex quadri...
Step Numbers
Consider the number 45656. It can be seen that each pair of consecutive digits differs by one (|4-5| = |5-6| = |6-5| = |5-6| = 1). A number where each pair of consecutive digits differs by exactly...
Consecutive Positive Divisors
Find the number of integers n, 1 < n < 10^7, for which d(n) = d(n+1), where d(n) denotes the number of positive divisors of n.
Rational Zeros of a Function of Three Variables
For any integer n, consider three functions: f_(1,n)(x,y,z) = x^(n+1) + y^(n+1) - z^(n+1) f_(2,n)(x,y,z) = (xyz)^n(x+y-z) f_(3,n)(x,y,z) = xyz^n(x^(n-1)+y^(n-1)-z^(n-1)) for n!= 1 and f(x,y,z) = f_...
Investigating in How Many Ways Objects of Two Different Colours Can Be Grouped
How many ways can 60 black objects and 40 white objects be grouped into non-empty groups, where the order of groups does not matter and each group is characterized by the pair (b, w) denoting the n...
RSA Encryption
Given distinct primes p = 1009 and q = 3643, let n = pq and lambda(n) = lcm(p-1, q-1). Find the sum of all values of e with 1 < e < lambda(n) and gcd(e, lambda(n)) = 1 that minimize the number of u...
Maximum Product of Parts
For a positive integer N, partition N into k equal real-valued parts of size N/k, yielding product (N/k)^k. Let M(N) be the maximum of (N/k)^k over all positive integers k. Define D(N) = -N & if M(...
Triangles Containing the Origin
Consider all lattice points (integer coordinates) strictly inside or on the circle of radius 105 centered at the origin. How many triangles formed by three such points strictly contain the origin?
Number Mind
A game similar to Mastermind: the player tries to guess a secret 16-digit number. After each guess, the player is told how many digits are in the correct position. Given the following clues, find t...
Connectedness of a Network
Here are the records from a busy telephone system with one million users: The telephone number of the caller and the called number in record n are generated by a "Lagged Fibonacci Generator": For 1...
Semiprimes
A composite number is called a semiprime if it is the product of exactly two prime factors (not necessarily distinct). The first few semiprimes are: 4, 6, 9, 10, 14, 15, 21, 22,... How many composi...
The Hyperexponentiation of a Number
The hyperexponentiation (or tetration) of a number a by a positive integer b is recursively defined: a uparrowuparrow b = a & if b = 1 a^(a uparrowuparrow (b-1)) & if b > 1 Find 1777 uparrowuparrow...
Tri-colouring a Triangular Grid
Consider the following configuration of 64 triangles: A triangular grid of side 8 is divided into small triangles (both upward-pointing and downward-pointing). We need to colour each small triangle...
Maximising a Weighted Product
Let S_m = {(x_1, x_2,..., x_m): x_i > 0, sum_(i=1)^m x_i = m}. Let P_m = max_(S_m) prod_(i=1)^m x_i^i. Find sum_(m=2)^15 floor(P_m).
Prize Strings
A particular school offers cash prizes to children with good attendance and punctuality. If they are absent for three consecutive days or late on more than one day, their prize is forfeited. Over a...
Best Approximations
For each non-perfect-square integer d with 2 <= d <= 100000, find the best rational approximation p/q to sqrt(d) with q <= 10^12. Here "best" means no other fraction with denominator at most 10^12...
Squarefree Numbers
How many squarefree numbers are there below 2^50? A number is squarefree if it is not divisible by any perfect square other than 1.
Coloured Configurations
Consider a graph formed by taking two complete graphs K_a and K_b that share exactly one common edge. Count the number of valid n -colourings of this graph, for (a, b, n) = (25, 75, 1984). Give the...
Inscribed Circles of Triangles with One Angle of 60 Degrees
How many triangles with integer sides having one angle of exactly 60 degrees have an inscribed circle (incircle) with radius not exceeding 10^5?
Prime Triplets
Build a triangle of positive integers: Row n contains n numbers. Two numbers are neighbours if they occupy adjacent positions in the triangle (up to 6 neighbours per position: left, right, and up t...
Investigating the Behaviour of a Recursively Defined Sequence
Given the function: f(x) = floor(2^(30.403243784 - x^2)) * 10^(-9) and the sequence u_0 = -1, u_(n+1) = f(u_n), find floor((u_n + u_(n+1)) x 10^9) for sufficiently large n (written as x.xxxxxxxxx).
Ambiguous Numbers
A best rational approximation to a real number x for denominator bound d is a fraction r/s (fully reduced, s <= d) such that |x - r/s| < |x - p/q| for every p/q with q <= d and q ne s. A real numbe...
Iterative Circle Packing
Three unit circles are packed inside a larger circle such that each is tangent to the other two and to the outer circle. In the first iteration, we fill each of the initial curvilinear triangular g...
Find the 200th Prime-proof Sqube Containing "200"
A sqube is a number of the form p^2 q^3 or p^3 q^2 where p and q are distinct primes. A number is prime-proof if no single digit substitution (replacing exactly one digit with a different digit) pr...
Subsets with a Unique Sum
For any set A of numbers, let sum(A) denote the sum of the elements of A. Consider the set S = {1^2, 2^2, 3^2,..., 100^2}. Let U be the set of all integers v such that exactly one 50-element subset...
Laserbeam
Three mirrors are arranged in the shape of an equilateral triangle, with their reflective surfaces pointing inwards. There is an infinitesimal gap at each vertex through which a laser beam may pass...
Squarefree Binomial Coefficients
Find the sum of all distinct squarefree numbers in the first 51 rows (rows 0 through 50) of Pascal's triangle.
Generalised Hamming Numbers
A Hamming number is a positive integer which has no prime factor larger than 5. We define a type- t generalised Hamming number as a positive integer which has no prime factor larger than t. How man...
Dice Game
Peter has nine four-sided (pyramidal) dice, each with faces numbered 1 to 4. Colin has six six-sided (cubic) dice, each with faces numbered 1 to 6. Peter and Colin roll their dice and compare total...
Concealed Square
Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0, where each underscore represents a single digit.
Integer Partition Equations
For the equation 4^t = 2^t + k, if we set x = 2^t, then k = x(x-1). For each integer x >= 2, this gives a distinct positive integer k and a corresponding real t = log_2 x. Each such (k, t) pair is...
Robot Walks
A robot moves on a plane, taking steps that are each an arc of 1/5 of a circle. At each step, the robot can turn either left (L) or right (R). After 70 steps, how many distinct closed paths return...
Circular Logic
A 6-input binary truth table tau(a,b,c,d,e,f) must satisfy: tau(a,b,c,d,e,f) wedge tau(b,c,d,e,f, a + (b wedge c)) = 0 for all inputs (a,b,c,d,e,f) in {0,1}^6. How many such truth tables exist?
Obtuse Angled Triangles
Consider the set S(r) of points (x, y) with integer coordinates satisfying |x| + |y| <= r. Let O = (0, 0) and C = (r/4, r/4). Let N(r) be the number of points B in S(r) such that triangle OBC has a...
Divisor Square Sum
For a positive integer n, let sigma_2(n) denote the sum of the squares of the divisors of n: sigma_2(n) = sum_(d | n) d^2 For example, sigma_2(10) = 1^2 + 2^2 + 5^2 + 10^2 = 130. Find the sum of al...
Combined Volume of Cuboids
An axis-aligned cuboid with parameters {(x_0, y_0, z_0), (delta x, delta y, delta z)} consists of all points (X, Y, Z) with x_0 <= X <= x_0 + delta x, y_0 <= Y <= y_0 + delta y, z_0 <= Z <= z_0 + d...
Flea Circus
A 30 x 30 grid starts with exactly one flea on each square. Each round, every flea independently jumps to a uniformly random adjacent square (up, down, left, right). Corner fleas have 2 choices, ed...
Totient Chains
Let phi denote Euler's totient function. The totient chain of n is: n -> phi(n) -> phi(phi(n)) ->... -> 1 The length of the chain is the number of elements (including n and 1). For example, the cha...
Crack-free Walls
Consider building a wall that is 32 units wide and 10 units tall using bricks of width 2 and width 3 (all height 1). A wall is crack-free if there is no vertical line running through the entire hei...
Investigating the Primality of $2n^2 - 1$
Consider the sequence t(n) = 2n^2 - 1 for n >= 1: 1, 7, 17, 31, 49, 71, 97, 127, 161, 199,... How many values of t(n) are prime for 2 <= n <= 50,000,000?
Balanced Numbers
A positive integer with k digits (base 10) is balanced if the sum of the first floor(k/2) digits equals the sum of the last floor(k/2) digits. For odd k, the middle digit is ignored. All 1-digit nu...
Perfect Right-angled Triangles
A right-angled triangle with sides a, b, and hypotenuse c is called perfect if: 1. (a, b, c) is a primitive Pythagorean triple (a^2 + b^2 = c^2, gcd(a, b) = 1). 2. The hypotenuse c is a perfect squ...
Skew-cost Coding
Build a prefix-free binary code for N = 10^9 symbols. Each codeword is a binary string. A 0 bit costs 1 and a 1 bit costs 4. The cost of a codeword is the sum of costs of its bits. The total cost i...
Heighway Dragon
The Heighway Dragon curve is defined by the Lindenmayer system: Axiom: F_a Rules: F_a -> F_a R F_b, F_b -> F_a L F_b where F_a and F_b mean "draw forward", R means "turn right 90 degrees", and L me...
Alexandrian Integers
We call a positive integer A an Alexandrian integer if there exist integers p, q, r such that A = p q r and (1)/(A) = (1)/(p) + (1)/(q) + (1)/(r). Find the 150000th Alexandrian integer (in sorted o...
Sphere Packing
What is the minimum length of a tube of internal radius R = 50 mm that can contain 21 spheres of radii r = 30, 31,..., 50 mm? Give the answer in micrometers (mu m), rounded to the nearest integer.
Almost Right-angled Triangles I
How many ordered triples (a, b, c) with a <= b <= c satisfy a^2 + b^2 = c^2 + 1 and a + b + c <= 25,000,000?
Almost Right-angled Triangles II
How many ordered triples (a, b, c) with a <= b <= c satisfy a^2 + b^2 = c^2 - 1 and a + b + c <= 75,000,000?
Tribonacci Non-divisors
The Tribonacci sequence T_n is defined by T_1 = T_2 = T_3 = 1 and T_n = T_(n-1) + T_(n-2) + T_(n-3) for n > 3. Find the 124th odd number that does not divide any Tribonacci number.
A Scoop of Blancmange
The Blancmange curve (Takagi curve) is defined by blanc(x) = sum_(n=0)^infinity (s(2^n x))/(2^n) where s(x) = min_(k in Z) |x - k| is the distance from x to the nearest integer. Consider the circle...
The Chase
"The Chase" is a game played by two players on a circular board of 100 spaces. The two players start at diametrically opposite positions (50 spaces apart). Each turn, both players simultaneously ro...
Minkowski Sums
Let S_n denote a regular n -sided polygon. Find the number of sides of the Minkowski sum T = S_2 + S_3 + S_4 +... + S_1864.
Four Representations Using Squares
Find the count of integers n <= 2 x 10^9 that can simultaneously be represented in all four forms: 1. n = a^2 + b^2 2. n = a^2 + 7c^2 3. n = a^2 + 11d^2 4. n = a^2 + 13e^2 where a, b, c, d, e are n...
Fibonacci Words
For any two strings of digits A and B, define the Fibonacci word sequence: F(1) = A F(2) = B F(n) = F(n-2) F(n-1) for n > 2 (concatenation) Let D(k) denote the k -th digit of the first term in the...
The Prime Factorisation of Binomial Coefficients
The binomial coefficient C(10, 3) = 120 has prime factorisation 2^3 x 3 x 5, so the sum of the terms in its prime factorisation is 2^3 + 3 + 5 = 16. Find the sum of the terms in the prime factorisa...
The Race
Two players alternate turns in a race to 100 points (Player 1 goes first). Player 1's turn: Flip one fair coin. Heads scores 1 point; tails scores nothing. Player 2's turn: Choose a positive intege...
Lattice Points on a Circle
Let f(n) be the number of lattice points on the circle x^2 + y^2 = n^2. Find the sum of all positive integers n <= 10^11 such that f(n) = 420.
Semidivisible Numbers
For an integer n, define lps(n) as the largest prime <= sqrt(n) and ups(n) as the smallest prime >= sqrt(n). A number n is semidivisible if exactly one of lps(n) or ups(n) divides it. Find the sum...
An Arithmetic Geometric Sequence
Given u(k) = (900 - 3k) r^(k-1), let s(r) = sum_(k=1)^5000 u(k). Find the value of r for which s(r) = -600,000,000,000, correct to 12 decimal places.
Luxury Hampers
Suppliers A and B each provided 18885 products across five types: | Product | A | B | |---------|------|------| | Beluga Caviar | 5248 | 640 | | Christmas Cake | 1312 | 1888 | | Gammon Joint | 2624...
Tours on a 4 x n Playing Board
Let T(n) be the number of tours on a 4 x n playing board such that: The tour visits every square exactly once. The tour starts at the top-left corner and ends at the bottom-left corner. Movement is...
Infinite String Tour
Define the Blum Blum Shub (BBS) sequence: s_0 = 14025256, s_(n+1) = s_n^2 mod 20300713. Concatenate all s_n to form the infinite string w = "14025256741014958...". For a positive integer k, define:...
Twenty-two Foolish Primes
A permutation of {1, 2,..., 100} is chosen uniformly at random. What is the probability that exactly 22 of the 25 prime numbers among 1 - 100 are NOT in their natural position (i.e., exactly 3 prim...
Top Dice
In how many ways can 20 twelve-sided dice (sides numbered 1 to 12) be rolled so that the top 10 values sum to 70? For reference: there are 1111 ways for 5 six-sided dice where the top 3 sum to 15.
Perfection Quotients
For a positive integer n, let sigma(n) denote the sum of all positive divisors of n. The perfection quotient of n is defined as p(n) = sigma(n)/n. A positive integer n is called a half-integer perf...
Odd Triplets
Define f(N) as the number of triplets (a, b, c) with 0 < a <= b <= c, a + b + c <= N, and a + b + c = 0 (where + denotes bitwise XOR). Find f(10^12) mod 10^9.
Resilience
For a denominator d > 1, the resilience is defined as R(d) = (phi(d))/(d - 1) where phi is Euler's totient function. Find the smallest d such that R(d) < dfrac1549994744.
Sliders
A sliding puzzle on a 4 x 4 grid contains Red (R), Blue (B), and one White/empty (W) tile arranged in a specific starting configuration. Tiles adjacent to the empty space may slide into it. Each mo...
Coresilience
For n > 1, define the coresilience: C(n) = (n - phi(n) - 1)/(n - 1). Find the sum of all composite numbers 1 < n <= 10^10 for which C(n) is a unit fraction, i.e., C(n) = 1/k for some positive integ...
Tangents to an Ellipse
Given points M(-2000, 1500) and G(8000, 1500) and a circle c centred at M with radius 15000, the locus of points equidistant from G and from c forms an ellipse e. From an external point P, two tang...
Squares Under a Hyperbola
Consider the region {(x,y): x >= 1, 0 <= y <= 1/x}. Squares are placed greedily (largest first) into this region. Each square S_n receives an index (a, b): a counts how many squares lie to its left...
Numbers for which Euler's Totient Function Equals 13!
Find the 150,000 -th number n (in ascending order) for which varphi(n) = 13! = 6,227,020,800.
Prime Subset Sums
Let S = {2, 3, 5, 7, 11, ldots} be the set of all primes less than 5000. Find the number of subsets of S whose elements sum to a prime number. Give the last 16 digits (i.e., the answer modulo 10^16).
250250
Find the number of non-empty subsets of {1^1, 2^2, 3^3,..., 250250^250250} whose element sum is divisible by 250. Give the answer modulo 10^16.
Cardano Triplets
A triplet of positive integers (a, b, c) is called a Cardano Triplet if it satisfies: sqrt[3]a + bsqrt(c) + sqrt[3]a - bsqrt(c) = 1. Find the number of Cardano Triplets such that a + b + c <= 110,0...
Convex Holes
Given 500 points in the plane generated by the linear congruential generator: s_0 = 290797 s_(n+1) = s_n^2 mod 50515093 t_n = (s_n mod 2000) - 1000 Points are P_k = (t_2k, t_(2k+1)) for k = 0, 1,.....
Tidying Up
A caterpillar of length n = 40 is a row of n cells. Cells are filled one at a time in uniformly random order (each of the n! permutations equally likely). After each placement, count the number of...
Sums of Digit Factorials
Define the following functions: f(n) = sum_(d in digits(n)) d! (sum of factorials of the digits of n). sf(n) = s(f(n)), where s(x) denotes the digit sum of x. g(i) = min{n in Z^+: sf(n) = i}. sg(i)...
Rounded Square Roots
Define the "rounded square root" algorithm for a positive integer n: 1. Let d be the number of digits of n. 2. If d is odd, set x_0 = 2 x 10^((d-1)/2). If d is even, set x_0 = 7 x 10^((d-2)/2). 3....
Tatami-Free Rooms
Tatami are rectangular 1 x 2 mats placed horizontally or vertically. A tiling of an n x m room with tatami (and possibly 1 x 1 monomers) is called tatami-free if no four tiles meet at any interior...
Angular Bisectors
Count the number of triangles with integer sides a <= b <= c and perimeter p = a + b + c <= 10^8 such that at least one angle bisector has integral length.
A Lagged Fibonacci Sequence
Define the sequence: g(k) = 1 for 0 <= k <= 1999, g(k) = g(k-2000) + g(k-1999) for k >= 2000. Find g(10^18) mod 20092010.
Reachable Numbers
Consider the digit string "123456789." By partitioning these digits into contiguous groups (forming multi-digit numbers by concatenation), inserting binary operators +, -, x, / between groups, and...
Stone Game
A game is played with three piles of stones. On each turn, a player may: 1. Remove any positive number of stones from one pile, or 2. Remove an equal positive number of stones from any two piles. T...
Pivotal Square Sums
A positive integer k is called a square-pivot if there exist integers m > 0 and n >= k such that the sum of (m+1) consecutive squares ending at k equals the sum of m consecutive squares starting at...
Mountain Range
The elevation at point (x, y) is given by h(x,y) = (5000 - 0.005(x^2 + y^2 + xy) + 12.5(x+y)) * e^(-|0.000001(x^2+y^2) - 0.0015(x+y) + 0.7|). A mosquito wants to fly from A = (200, 200) to B = (140...
An Engineers' Dream Come True
Define n to be an engineer's paradise if: 1. (n-9, n-3, n+3, n+9) are four consecutive primes (a "triple-pair" of sexy primes, each consecutive pair differing by exactly 6). 2. n-8, n-4, n, n+4, n+...
Triangle Centres
Consider all non-degenerate triangles ABC with: All vertices at lattice points (integer coordinates). Circumcenter at the origin O = (0, 0), so all vertices lie on a circle x^2 + y^2 = R^2. Orthoce...
Binary Circles
2^N binary digits can be placed in a circle so that all N -bit clockwise subsequences are distinct. For N = 3, the sequence 00010111 works: the 8 three-bit subsequences 000, 001, 010, 101, 011, 111...
Pseudo Square Root
The largest divisor of n that does not exceed sqrt(n) is called the pseudo square root (PSR) of n. Let P = prod_(p < 190, p prime) p be the product of the 42 primes below 190. Find the last 16 digi...
Billionaire
You have 1 and want to become a billionaire (10^9). You flip a biased coin repeatedly (probability 1/2 heads, 1/2 tails). Before each flip, you choose a fixed fraction f (0 < f < 1) of your current...
Counting Numbers with at Least Four Distinct Prime Factors Less Than 100
How many numbers below 10^16 are divisible by at least four distinct primes less than 100?
Polynomials with at Least One Integer Root
A 9-digit positive integer n = a_9 10^9 + a_8 10^8 +... + a_1 10 + a_0 (with a_9!= 0, and 0 <= a_i <= 9) defines a polynomial: f_n(x) = a_9 x^9 + a_8 x^8 +... + a_1 x + a_0 How many 9-digit positiv...
Cutting Squares
A square piece of paper is cut into triangles by making straight cuts that connect points on the boundary. We want to cut the square into exactly 15 triangles by connecting boundary points (vertice...
Modular Cubes, Part 1
Let N = 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 x 37 x 41 x 43 = 13082761331670030. Find the sum of all n with 0 < n < N such that n^3 equiv 1 (mod N).
Modular Cubes, Part 2
For a positive integer n, define C(n) as the number of integers x with 1 < x < n such that x^3 equiv 1 (mod n). Find the sum of all positive integers n <= 10^11 for which C(n) = 242.
Sum of Squares
Consider equations of the form a^2 + b^2 = n with 0 <= a <= b and a, b, n integers. Let P = {p prime: p equiv 1 (mod 4), p < 150}. For each squarefree N that is a product of a non-empty subset of P...
Divisibility Multipliers
For each integer p > 1 coprime to 10, define the divisibility multiplier m(p) as the smallest positive integer m < p such that the function f(n) = floor(n/10) + (n mod 10) * m preserves divisibilit...
Balanced Sculptures
A balanced sculpture of order n consists of a plinth at position (0, 0) and n unit-square blocks at integer coordinates with y >= 1, forming a connected polyomino (adjacency via shared edges; holes...
Primitive Triangles
Consider the triangles with integer sides a, b and c with a <= b <= c. An integer sided triangle (a, b, c) is called primitive if gcd(a, b, c) = 1. How many primitive triangles exist with a perimet...
A Modified Collatz Sequence
A modified Collatz sequence of integers is obtained from a starting value a_1 in the following way: a_(n+1) = a_n / 3 & if a_n equiv 0 (mod 3) (denoted 'D' for down) (4a_n + 2) / 3 & if a_n equiv 1...
Linear Combinations of Semiprimes
Given three distinct primes p < q < r, define: f(p,q,r) = 2pqr - pq - qr - rp This is the largest positive integer that cannot be represented as ap + bq + cr for non-negative integers a, b, c (a ge...
Triangles with Integral Sides and an Integral Angle
How many triangles are there with integer sides and perimeter not exceeding 10^8 that have at least one angle that is an integer number of degrees?
Ant and Seeds
A 5x5 grid has seeds in each cell of the top row (y=0). An ant starts at the center (2,2) and performs a random walk (moving to a uniformly random adjacent cell at each step, staying within the gri...
Pizza Toppings
A pizza (a perfect circle) is cut into m * n equal slices. Let f(m,n) denote the number of distinct distributions of m distinct toppings on the pizza, each topping covering exactly n consecutive sl...
The Ackermann Function
Define A(n) = ack(n, n) where ack is the Ackermann function: ack(0, m) = m + 1, ack(n, 0) = ack(n-1, 1) for n > 0, ack(n, m) = ack(n-1, ack(n, m-1)) for n, m > 0. Find sum_(n=0)^6 A(n) (mod 14^8).
Integer Sided Triangles for which Area/Perimeter Ratio is Integral
Find the sum of perimeters of all integer-sided triangles for which A/P = k is a positive integer with 1 <= k <= 1000, where A is the area and P is the perimeter.
Steady Squares
A steady square in base 14 is a positive integer n such that n^2 equiv n (mod 14^k), where k is the number of base-14 digits of n. Find the digit sum (in base 14) of all n -digit steady squares for...
Pythagorean Odds
Albert chooses a positive integer k, then picks two reals a, b uniformly from [0,1]. He computes sqrt((ka+1)^2 + (kb+1)^2) and rounds to the nearest integer. If the result equals k, he scores k poi...
Scoring Probabilities
Barbara shoots from distances x = 1, 2,..., 50 with success probability p_x = 1 - x/q for a real constant q > 50. The probability of scoring exactly 20 points (out of 50 shots) is exactly 2%. Find...
Quadtree Encoding
A 2^N x 2^N black-and-white image is encoded via a quadtree: Entirely black region: output 10 (2 bits). Entirely white region: output 11 (2 bits). Mixed region: output 0 followed by encodings of fo...
An Enormous Factorial
For a prime p, define N(p,q) = sum_(n=0)^q T_n * p^n where T_n is generated by S_0 = 290797, S_(n+1) = S_n^2 mod 50515093, T_n = S_n mod p. Let NF(p,q) = v_p(N(p,q)!) (the p -adic valuation of N(p,...
Eulerian Cycles
Let C(x,y) be a circle through lattice points (x,y), (x+1,y), (x,y+1), (x+1,y+1). For positive integers m, n, let E(m,n) be the graph of mn such circles for 0 <= x < m, 0 <= y < n. Let L(m,n) count...
Digital Signature
How many integers 0 <= n < 10^18 satisfy S(n) = S(137n), where S(k) denotes the digit sum of k?
Panaitopol Primes
A prime number p is called a Panaitopol prime if there exists a positive integer n such that p = (x^4 - y^4)/(x^3 + y^3) for some positive integers x > y. Equivalently, these are primes of the form...
Pythagorean Polygons
A Pythagorean polygon is a convex polygon where all vertices lie at lattice points and all edges have integer length. Two polygons differing only by translation are considered identical. Define P(n...
Pseudo-Fortunate Numbers
An integer n is admissible if n = 2^(a_1) 3^(a_2) 5^(a_3)... p_k^(a_k) where 2 = p_1 < p_2 = 3 <... < p_k are consecutive primes and all exponents a_i >= 1. For an admissible number n, the pseudo-F...
Sum of Digits -- Experience #23
For a positive integer k, let d(k) denote the digit sum of k. Define S(n) = #{k: 0 < k < 10^n, 23 | k, d(k) = 23}. Given: S(9) = 263626, S(42) = 6,377,168,878,570,056. Find S(11^12) mod 10^9.
Lenticular Holes
A lenticular hole is a convex region enclosed by two circles where: 1. Both circle centers are at lattice points. 2. The circles intersect at exactly two distinct lattice points. 3. The interior of...
Angular Bisector and Tangent
Given an integer-sided triangle ABC with BC <= AC <= AB, let: k be the angular bisector of angle ACB, m be the tangent at C to the circumscribed circle of ABC, n be the line through B parallel to m...
Zeckendorf Representation
Every positive integer has a unique Zeckendorf representation as a sum of non-consecutive Fibonacci numbers. Let z(n) denote the number of terms in this representation. For example, z(5) = 1, z(14)...
Selective Amnesia
Larry and Robin play a memory game. In each of 50 turns, a number is drawn uniformly at random from {1, 2,..., 10}. Each player maintains a memory of at most 5 numbers. If the called number is in m...
Three Similar Triangles
Four points A(a, 0), B(b, 0), C(0, c), D(0, d) with 0 < a < b and 0 < c < d have integer coordinates. Point P (integer coordinates) lies on line AC such that triangles ABP, CDP, and BDP are all sim...
Protein Folding
A protein of length n is a string over {H, P} (hydrophobic/polar). It folds as a self-avoiding walk (SAW) on the 2D square lattice. An H-H contact occurs when two H residues at non-consecutive sequ...
Nim
Nim is a two-player combinatorial game played with heaps of stones under the normal play convention: players alternate turns removing any positive number of stones from a single heap, and the playe...
Strong Achilles Numbers
A positive integer n is powerful if for every prime p dividing n, we have p^2 | n. An Achilles number is a powerful number that is not a perfect power (i.e., it cannot be expressed as m^k for integ...
Multiples with Small Digits
For a positive integer n, define f(n) as the smallest positive multiple of n whose decimal representation uses only the digits {0, 1, 2}. Compute sum_(n=1)^10000 (f(n))/(n).
Primonacci
Let p_i denote the i -th prime number. Define a(i) = F(p_(10^14+i)), where F(n) is the n -th Fibonacci number with F(1) = F(2) = 1. Find sum_(i=1)^100000 a(i) (mod 1234567891011).
Reflexive Position
Let S be the infinite Champernowne-like string formed by concatenating all positive integers in base 10: S = 123456789101112131415161718192021... Positions are 1-indexed. Define f(n) as the startin...
Paper-strip Game
Two players alternate turns on a strip of n white squares. Each turn, a player picks two contiguous white squares and paints them black. The first player unable to move loses (normal play conventio...
Chip Defects
k = 20,000 defects are randomly distributed amongst n = 1,000,000 integrated-circuit chips (each defect independently and uniformly at random). Let p(k,n) represent the probability that there is a...
An Amazing Prime-generating Automaton
Conway's PRIMEGAME is the FRACTRAN program: (17)/(91), (78)/(85), (19)/(51), (23)/(38), (29)/(33), (77)/(29), (95)/(23), (77)/(19), (1)/(17), (11)/(13), (13)/(11), (15)/(2), (1)/(7), (55)/(1) Start...
Integer Ladders
Two ladders of integer lengths x and y lean against opposite walls of a narrow street, crossing at height h. All four values x, y, h, and the street width w must be positive integers. For 0 < x < y...
Nim Square
Alice and Bob play Nim Square, which is like ordinary three-heap normal play Nim, but players may only remove a perfect square number of stones from a heap. A position (a, b, c) is losing for the n...
Biclinic Integral Quadrilaterals
A biclinic integral quadrilateral is a convex quadrilateral ABCD with integer side lengths such that both diagonals divide it into pairs of triangles each having integer area. Count the number of s...
Cyclic Paths in Sierpinski Graphs
Let S_n denote the Sierpinski graph of order n. Define C(n) as the number of Eulerian circuits in S_n. Compute: C(C(C(10000))) mod 61^8
Sliding Game
In a sliding puzzle on an m x n grid, a red counter occupies the top-left cell and the empty space occupies the bottom-right cell. A move slides any counter horizontally or vertically into the adja...
The Mouse on the Moon
A quarter-circle of radius r = 250,000 is drawn in the first quadrant, centered at the origin. A fence consisting of horizontal and vertical unit segments along lattice lines runs from (0, r) to (r...
Digital Root Clocks
Sam and Max have digital clocks with 7-segment displays. Starting from a number, they repeatedly compute the digit sum until a single digit remains (the digital root chain). Sam's clock turns off a...
Numbers in Decimal Expansions
Let p = p_1 p_2 p_3... be an infinite random decimal sequence where each digit is uniform on {0,..., 9}. For a positive integer n with d digits, let k be the smallest index such that p_k p_(k+1)......
Firecracker
A firecracker explodes at height h_0 = 100 m above flat ground, ejecting fragments in every direction at speed v_0 = 20 m/s. With gravity g = 9.81 m/s^2 and no air resistance, determine the volume...
2011 Nines
For integers 1 <= p < q with p + q <= 2011, let C(p,q,n) be the count of consecutive nines at the start of the fractional part of (sqrt(p) + sqrt(q))^2n. Let N(p,q) be the minimal n with C(p,q,n) >...
Bounded Sequences
Let t(n) denote the number of sequences (x_1,..., x_n) of positive integers such that there exists alpha in [2, 3) with x_i = floor(alpha^i) for all i. Given t(10) = 86195 and t(20) = 5227991891, f...
Factorials Divisible by a Huge Integer
Let N(i) be the smallest integer n such that n! is divisible by (i!)^1234567890. Define S(u) = sum_(i=10)^u N(i). Given: S(1000) = 614538266565663. Find S(1000000) mod 10^18.
Swapping Counters
A horizontal row comprises 2n+1 squares. A set of n red counters occupies the leftmost n squares and a set of n blue counters occupies the rightmost n squares, with a single empty square in the mid...
Binomial Coefficients Divisible by 10
Let T(m, n) denote the number of binomial coefficients C(i, n) that are divisible by 10, for n <= i < m (where i, m, n are positive integers). Given: T(10^9, 10^7 - 10) = 989697000. Find: T(10^18,...
Bitwise-OR Operations on Random Integers
Let y_0, y_1, y_2,... be a sequence of random unsigned 32-bit integers (each bit independently 0 or 1 with equal probability). Define x_0 = 0 and x_i = x_(i-1) mathbin| y_i for i >= 1. Let N be the...
Building a Tower
Let f(n) denote the number of ways to fill a 3 x 3 x n tower using 2 x 1 x 1 bricks. Find f(10^10000) mod (10^8 + 7).
Stone Game II
A game is played with two piles of stones. On each turn, a player removes k (smaller pile) stones from the larger pile, where k >= 1. The player who empties a pile wins. A position (a, b) with a <...
Modular Inverse of Power Tower
Let a uparrowuparrow b denote the power tower a^a^a^(...) of height b. Define N(a, b, m) equiv (a uparrowuparrow b)^(-1) (mod m) whenever the inverse exists. Compute the required value as specified...
Rooms of Doom
A series of N+1 rooms are connected in a line (rooms 0, 1,..., N). Room 0 has an unlimited supply of cards. Each door from room i to room i+1 consumes one card. You can carry at most R cards at a t...
Lowest-Cost Search
We play a number-guessing game. A number is chosen from {1, 2,..., n}. When we guess g, we pay g dollars and are told whether the hidden number is higher, lower, or equal. We want a strategy that m...
Prime Frog
A frog sits on one of the squares numbered 1 to 500, chosen uniformly at random. At each step, the frog jumps to an adjacent square with equal probability (from square 1 it must jump to 2; from squ...
Euler's Number
An infinite sequence a(n) is defined as follows. For every positive integer n: a(n) = sum_(k=1)^infinity (floor(n / k))/(k!) and the sequence begins a(1) = 1, a(2) = 1 + 1/2,... The function A(n) i...
Cross Flips
An N x N grid has each square colored black (1) or white (0). A cross flip at square (i,j) toggles every square sharing a row or column with (i,j). In F_2 arithmetic, the square (i,j) itself receiv...
Spherical Triangles
A spherical triangle is formed on the surface of a unit sphere by three great-circle arcs. Find the sum of the areas of all spherical triangles whose three sides have integer arc-lengths (in radian...
Special Partitions
A number of the form 2^a * 3^b with a, b >= 0 is called a 3-smooth power. A positive integer n has a special partition if it can be written as a sum of distinct 3-smooth powers. A prime p is called...
Spilling the Beans
A row of bowls contains beans. Beans are redistributed by adjacent transfers: if a bowl has more beans than its right neighbor, one bean moves right, and vice versa, simultaneously for all bowls in...
Gathering the Beans
In a circle of n bowls numbered 0, 1,..., n-1, bowl k initially contains k beans. We wish to gather all beans into a single bowl by moving one bean at a time to an adjacent bowl. Define M(n) as the...
Maximix Arrangements
A train is used to transport four different coloured combatant carriages to a town, and after being sorted into the order of their combatant number, they are uncoupled. The engine can only pull car...
Totient Stairstep Sequences
Let {a_1, a_2,..., a_k} be a totient stairstep sequence if: 1. phi(a_i) < phi(a_{i+1}) for 1 <= i < k (strictly increasing Euler totient values) 2. a_i divides a_{i+1} for 1 <= i < k (each term div...
Cutting Rectangular Grid Paper
A rectangular grid paper of size p x q can be cut along grid lines and rearranged (without overlap or gaps) to form a different rectangle a x b. Define f(p, q) as the number of such rectangles a x...
Peredur fab Efrawg
Define a recursive sequence based on the story of Peredur fab Efrawg. We have a function R(a, b, c) that generates a sequence of triples, and E(.) computes the expected value of a specific quantity...
Crazy Function
Define a function F(m, n, o) recursively: F(m, n, o) = o + 1 if m = 0 F(m, n, o) = F(m-1, n, o+1) if m > 0 and n = 0 and o = 0 (or similar base cases) The exact recursive definition creates a rapid...
Golomb's Self-Describing Sequence
The Golomb sequence {G(n)}_(n >= 1) is the unique non-decreasing sequence of positive integers satisfying the self-referential property: for every positive integer n, the value n appears exactly G(...
The Totient of a Square Is a Cube
Find the sum of all integers n with 1 < n < 10^10 such that varphi(n^2) is a perfect cube, where varphi denotes Euler's totient function.
Fractional Sequences
For any positive integer k, a finite sequence a_i of fractions x_i/y_i is defined by: a_1 = 1/k a_i = (x_(i-1)+1)/y_(i-1) when x_(i-1) > 0, reduced to lowest terms The sequence terminates when x_i...
Silver Dollar Game
In the Silver Dollar Game, coins are placed on a one-dimensional strip of n squares. Players alternate turns; on each turn a player moves one coin any number of squares to the left, without jumping...
Matrix Sum
Given the 15 x 15 matrix: Find max_sigma in S_15 sum_(i=1)^15 M_(i,sigma(i)), the maximum sum obtainable by selecting exactly one element from each row and each column.
Strong Repunits
A positive integer n is a repunit in base b if its base- b representation consists entirely of 1s, i.e., n = sum_(i=0)^(k-1) b^i for some k >= 2. A positive integer is a strong repunit if it is a r...
Largest Integer Divisible by Two Primes
For two distinct primes p and q, let M(p, q, N) be the largest positive integer <= N whose only prime factors are p and q (both must appear), or 0 if no such integer exists. Find sum M(p, q, 10^7)...
Sum of a Square and a Cube
Find the sum of the five smallest palindromic numbers that can each be expressed as the sum of a square and a cube (a^2 + b^3 with a >= 1, b >= 1) in exactly 4 different ways.
Langton's Ant
An ant moves on an infinite grid of squares, all initially white. At each step: On a white square: flip to black, turn right 90°, move forward one square. On a black square: flip to white, turn lef...
Constraining the Least Greatest and the Greatest Least
A list of size n is a sequence (a_1,..., a_n) of natural numbers. For a list L, define: f(L) = lcm(L), the least common multiple of all elements. g(L) = gcd(L), the greatest common divisor of all e...
Hexagonal Orchards
A hexagonal orchard of order n is a triangular lattice arranged in a regular hexagonal pattern with n concentric rings around a central point. A lattice point is visible from the center if no other...
Blood Tests
A population of N = 10,000 sheep each independently has probability p = 0.02 of carrying a rare blood disease. A blood test can detect the disease perfectly. Instead of testing each sheep individua...
Risky Moon
A spaceship travels on the surface of a sphere from the north pole to the south pole, hopping between lattice points. For a sphere of integer radius r, the lattice points are integer triples (a,b,c...
Distances in a Bee's Honeycomb
On a hexagonal lattice, define the Eisenstein norm of a point z = a + bomega (where omega = e^(2pi i/3)) as N(z) = a^2 - ab + b^2. Let C(n) be the number of Eisenstein integers of norm exactly n. F...
Maximal Coprime Subset
Define S_n as the maximal sum of a subset of {1, 2,..., n} in which no two elements share a common factor greater than 1 (i.e., all elements are pairwise coprime). Compute sum_(n=1)^N S_n for N = 1...
Largest Roots of Cubic Polynomials
Let a_n be the largest real root of the polynomial g(x) = x^3 - 2^n * x^2 + n. Find sum_(n=1)^30 floor(a_n^987654321) (mod 10^8).
Prime Generating Integers
Consider the divisors of 30: 1, 2, 3, 5, 6, 10, 15, 30. For every divisor d of 30, d + 30/d is prime: 1 + 30 = 31, 2 + 15 = 17, 3 + 10 = 13, 5 + 6 = 11 Find the sum of all positive integers n not e...
Cyclic Numbers
A cyclic number with n digits has the property that multiplying it by 1, 2, 3,..., n produces all cyclic permutations of itself. These arise from the decimal expansion of 1/p for full-reptend prime...
Hilbert's New Hotel
An infinite hotel has rooms arranged on floors. The hotel uses a specific procedure to assign rooms based on a function P(f, r) which gives the number of the guest in room r on floor f. The assignm...
Scared of Heights
Given an N -dimensional sphere of radius R, count the number of lattice points (points with all integer coordinates) that lie on or inside the sphere. Specifically, we need to find a function relat...
Subsequence of Thue-Morse Sequence
The Thue-Morse sequence {T(n)}_(n >= 0) is defined by T(n) = s_2(n) mod 2, where s_2(n) denotes the number of 1-bits in the binary representation of n (the "popcount"). Define the subsequence A(n)...
Squarefree Factors
Define f(n) as the largest squarefree divisor of n, i.e., the product of the distinct prime factors of n. Equivalently, if n = prod p_i^(a_i), then f(n) = prod p_i. Compute S(N) = sum_(n=1)^N f(n)...
Bezier Curves
A cubic Bezier curve is defined by four control points P_0, P_1, P_2, P_3. Find the cubic Bezier curve that best approximates a quarter circle (from (0,1) to (1,0) along the unit circle) in the min...
Comfortable Distance
A row of n seats is initially empty. People enter one at a time and always choose the seat that maximizes their minimum distance to any occupied seat (choosing the leftmost such seat in case of tie...
A Huge Binomial Coefficient
Let n = 10^18 and k = 10^9. For each triple of distinct primes (p_1, p_2, p_3) with 1000 < p_i < 5000, compute C(n, k) mod (p_1 p_2 p_3) using the Chinese Remainder Theorem. Find the sum of all suc...
Stone Game III
Two players play a stone game. There is a heap of stones at the start. The first player removes at least one stone but not all stones. Thereafter, each player must remove at least one stone but at...
Bozo Sort
Bozo sort works as follows on an array of n elements: 1. Pick two positions uniformly at random (possibly the same) and swap the elements. 2. Check if the array is sorted by comparing adjacent pair...
A Kempner-like Series
The Kempner series is a modification of the harmonic series where terms with a specific digit or substring are removed. In the original Kempner series, all terms containing the digit 9 are removed,...
Badugi
In the card game Badugi, a hand consists of 4 cards drawn from a standard 52-card deck. A Badugi hand is one where all four cards have different suits AND all four cards have different ranks. We ne...
Geometric Triangles
Let us define a geometric triangle as a triangle with sides a <= b <= c such that the sides form a geometric progression, i.e., b/a = c/b, which means b^2 = a*c. Given a perimeter limit L, count th...
Licence Plates
Oregon licence plates consist of three letters followed by a three-digit number (000 to 999). While driving to work you play a game: each plate you see gives you its three-digit number N; if you ha...
Pencils of Rays
Let R(M, N) denote the number of lattice points (x, y) with 0 < x <= M and 0 < y <= N such that gcd(x, y) = 1. A "pencil of rays" corresponds to a visible lattice point from the origin inside an M...
Circumscribed Circles
For a positive integer n, let L(n) denote the number of lattice points on the circle x^2 + y^2 = n (i.e., integer solutions to x^2 + y^2 = n). Every triple of distinct lattice points on such a circ...
Maximum Integer Partition Product
An integer partition of n is a way of writing n as a sum of positive integers (order irrelevant). For each positive integer n, define f(n) as the maximum product over all partitions of n (where a s...
Minimum of Subsequences
Define the pseudo-random sequence {S_n} by S_0 = 290797 and S_(n+1) = S_n^2 mod 50515093. Let A(i,j) = min(S_i, S_(i+1),..., S_j) for 1 <= i <= j. Compute: M(N) = sum_(1 <= i <= j <= N) A(i,j) for...
Nontransitive Sets of Dice
Consider the following set of dice with nonstandard pips: Die A: 1 1 1 1 1 1 Die B: 6 6 6 6 6 6 Die C: 2 2 2 2 2 2 This has the property: A beats C, C beats... nothing interesting here. But nontran...
Sum of Digits - Experience 13
Transfer matrix for digit-sum enumeration. Matrix exponentiation mod 10^9+7.
Triangle Triples
d(T(n)) for triangle numbers T(n). Count triples satisfying triangle inequality via sorting + two-pointer.
Least Common Multiple Count
f(n) = pairs with lcm=n. Sum f(n) for n=1..10^12 via Dirichlet hyperbola method.
Amazing Mazes!
Grid Laplacian, Matrix Tree Theorem, Kirchhoff effective resistance. Numerical to 10 decimals.
(prime-k) factorial
For a prime p, let S(p) = sum_(k=1)^5 (p-k)! mod p. Find sum S(p) for all primes 5 <= p < 10^8.
Generating Polygons
A polygon is called generating if its interior contains exactly one lattice point. Let T(n) be the number of generating polygons with perimeter not exceeding n, where the vertices are lattice point...
Divisibility Comparison between Factorials
Let f_5(n) denote the largest integer k such that 5^k divides n. Define D(N) = sum_(i=2)^N f_5(C(2i, i)). Find D(10^12). More generally, the problem asks about the p -adic valuation of central bino...
Rudin-Shapiro Sequence
Define r(n) = (-1)^(f(n)), where f(n) counts the number of occurrences of "11" in the binary representation of n (i.e., the number of positions i such that both bit i and bit i+1 of n are 1). Let s...
Ellipses Inside Triangles
Ellipses inscribed in lattice triangles via algebraic geometry and numerical computation.
Maximum Length of an Antichain
Dilworth's theorem on divisibility poset. Antichain via prime signature analysis.
Harshad Numbers
A Harshad number is a number divisible by the sum of its digits. A right truncatable Harshad number is a Harshad number such that recursively truncating the last digit always yields a Harshad numbe...
Distinct Lines through Lattice Points
Consider all lattice points (a, b, c) with 0 <= a, b, c <= N. From the origin O(0,0,0) a straight line is drawn to every point. Let D(N) be the number of distinct such lines. You are given that D(1...
Project Euler Problem 389: Platonic Dice
An unbiased single 4-sided die is thrown and its value, T, is noted. T unbiased 6-sided dice are thrown and their scores are added together. The sum, C, is noted. C unbiased 8-sided dice are thrown...
Project Euler Problem 390: Triangles with Non-Rational Sides and Integral Area
Consider the triangle with sides sqrt(5), sqrt(65), and sqrt(68). It can be shown that this triangle has area 9. S(n) is the sum of the areas of all triangles with sides sqrt(1+b^2), sqrt(1+c^2), a...
Hopping Game
Let s_k denote the cumulative popcount function: s_k = sum_(i=0)^k popcount(i), where popcount(i) counts the number of 1 -bits in the binary representation of i. The range of this function defines...
Enmeshed Unit Circle
A rectilinear grid is formed by (N+2) vertical and (N+2) horizontal lines, with outer boundaries at x = +/- 1 and y = +/- 1. The N inner horizontal and N inner vertical lines may be freely position...
Migrating Ants
An n x n grid of squares contains n^2 ants, one ant per square. All ants decide to move simultaneously to an adjacent square (up, down, left, or right). We define f(n) to be the number of ways this...
Project Euler Problem 394: Eating Pie
Project Euler Problem 394: Eating Pie
Project Euler Problem 395 -- Pythagorean Tree
The Pythagorean tree is a fractal constructed by starting with a unit square. On the top side, a right triangle is built with the hypotenuse coinciding with that side and legs a = 3/5, b = 4/5 (sat...
Weak Goodstein Sequence
For any positive integer n, the nth weak Goodstein sequence {g1, g2, g3,...} is defined as: g1 = n For k > 1, gk is obtained by writing g(k-1) in base k, interpreting it as a base (k+1) number, and...
Project Euler Problem 397 -- Triangle on Parabola
On the parabola y = x^2 / k (for a positive integer k), three points A(a, a^2/k), B(b, b^2/k), C(c, c^2/k) are chosen with integer x-coordinates satisfying 0 < a < b < c <= k. The area of triangle...
Project Euler Problem 398: Cutting Rope
Inside a rope of length n, n-1 points are placed with distance 1 from each other and from the endpoints. Among these n-1 points, we choose m-1 points at random and cut the rope at these points to c...
Project Euler Problem 399: Squarefree Fibonacci Numbers
The first 15 Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610. A Fibonacci number F(n) is squarefree if it is not divisible by any perfect square other than 1. Among...
Project Euler Problem 400: Fibonacci Tree Game
A Fibonacci tree is defined recursively: T(0) is the empty tree. T(1) is a single node. T(k) for k >= 2 consists of a root node with T(k-1) as left subtree and T(k-2) as right subtree. Two players...
Sum of Squares of Divisors
Let sigma_2(n) = sum_(d | n) d^2 denote the sum of the squares of the divisors of n. Define the summatory function Sigma_2(n) = sum_(i=1)^n sigma_2(i). The first six values are Sigma_2(1) = 1, Sigm...
Integer-valued Polynomials
The polynomial n^4 + 4n^3 + 2n^2 + 5n is a multiple of 6 for every integer n, and 6 is the largest such integer. Define M(a, b, c) as the maximum m such that n^4 + an^3 + bn^2 + cn is a multiple of...
Lattice Points Enclosed by Parabola and Line
For integers a and b, define D(a,b) = {(x,y) in R^2: x^2 <= y <= ax + b}. Let L(a,b) count the lattice points in D(a,b). Define S(N) = sum L(a,b) over all pairs (a,b) with |a|, |b| <= N such that A...
Project Euler Problem 404: Crisscross Ellipses
E_a is an ellipse with equation x^2 + 4y^2 = 4a^2. E_a' is the rotated image of E_a by theta degrees counterclockwise around the origin O(0,0) for 0° < theta < 90°. b is the distance to the origin...
Project Euler Problem 405: A Rectangular Tiling
We tile a rectangle whose length is twice its width using a recursive substitution rule. T(0) is the tiling consisting of a single 2x1 rectangle. For n > 0, T(n) is obtained from T(n-1) by replacin...
Project Euler Problem 406: Guessing Game
We are playing a guessing game where I choose a number from the set {1, 2,..., n}. You make guesses, and after each guess I tell you whether your guess is correct, too low, or too high. A guess tha...
Project Euler Problem 407: Idempotents
If we calculate a^2 mod 6 for 0 <= a <= 5 we get: 0, 1, 4, 3, 4, 1. The largest value of a such that a^2 = a (mod 6) is 4. Let M(n) be the largest value of a < n such that a^2 = a (mod n). Find: Su...
Project Euler Problem 408: Admissible Paths Through a Grid
A lattice point (x, y) is called inadmissible if x, y, and x + y are all positive perfect squares. For example, (9, 16) is inadmissible because 9 = 3^2, 16 = 4^2, and 9 + 16 = 25 = 5^2. A path from...
Project Euler Problem 409: Nim Extreme
Consider nim positions where: 1. There are n non-empty piles. 2. Each pile has size less than 2^n. 3. No two piles share the same size. Define W(n) as the number of winning positions (the first pla...
Circle and Tangent Line
Given a circle C centered at the origin with radius r, and an external point P = (a, 0) where a > r: 1. Find the two tangent lines from P to C. 2. Compute the tangent length (distance from P to eac...
Uphill Paths
Let n be a positive integer. Stations are placed at coordinates (x, y) = (2^i mod n, 3^i mod n), 0 <= i <= 2n. Stations at identical coordinates are identified. An uphill path from (0,0) to (n,n) i...
Gnomon Numbering
For integers m and n with 0 <= n < m, define L(m,n) as the L-shaped region (gnomon) formed by an m x m grid with the top-right n x n portion removed. Let LC(m,n) count the number of ways to fill th...
One-child Numbers
A d -digit positive number (no leading zeros) is a one-child number if exactly one of its substrings is divisible by d. Examples: 5671 is a 4-digit one-child number: among its substrings, only 56 i...
Project Euler Problem 414: Kaprekar Constant
The Kaprekar routine for a number works as follows: take a number, sort its digits in descending order, subtract the number formed by sorting digits in ascending order. Repeat. For 4-digit numbers...
Titanic Sets
A set of lattice points S is called a titanic set if there exists a line passing through exactly two points of S. Find the sum of all T(N) values for specific parameters, where T(N) counts the numb...
A Frog's Trip
A frog begins at the leftmost square of an n-square row and makes successive jumps of 1, 2, or 3 squares to the right to reach the rightmost square, then returns leftward using the same jumping rul...
Reciprocal Cycles II
A unit fraction contains 1 in the numerator. The decimal representation of unit fractions with denominators 2 to 10 are given: 1/2 = 0.5 1/3 = 0.(3) 1/4 = 0.25 1/5 = 0.2 1/6 = 0.1(6) 1/7 = 0.(14285...
Factorisation Triples
An integer triple (a, b, c) is called a factorisation triple of n if: 1 <= a <= b <= c a b c = n Define f(n) = a + b + c for the factorisation triple (a, b, c) of n which minimises c/a. This triple...
Look and Say Sequence
The look-and-say sequence goes 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211,... The sequence starts with 1 and all other members are obtained by describing the previous member in terms of...
2x2 Positive Integer Matrix
A 2x2 positive integer matrix is a 2x2 matrix whose elements are all positive integers. Some positive integer matrices can be expressed as the square of a positive integer matrix in two different w...
Prime Factors of $n^{15}+1$
Numbers of the form n^15+1 are composite for every integer n > 1. For positive integers n and m, let s(n,m) be the sum of the distinct prime factors of n^15+1 not exceeding m. Examples: 2^15+1 = 3^...
Sequence of Points on a Hyperbola
Let H be the hyperbola defined by 12x^2 + 7xy - 12y^2 = 625. Define X = (7, 1) (on H), P_1 = (13, 61/4), P_2 = (-43/6, -4). For i > 2, P_i is the unique point on H different from P_(i-1) such that...
Consecutive Die Throws
Let n consecutive die throws form a sequence. We count arrangements where specific consecutive patterns appear. Define F(n) as the number of valid sequences of length n. Find F(10^14) mod (10^9 + 7).
Kakuro
A Kakuro puzzle is a cross-sum puzzle on a grid where blank cells must be filled with digits 1 -- 9 such that each horizontal and vertical run of consecutive blank cells sums to a given clue, with...
Prime Connection
Two primes are connected if one can be transformed into the other by changing a single digit (preserving the number of digits and primality at each step). Let f(N) be the number of primes p <= N su...
Box-ball System
Consider the box-ball system (BBS), a cellular automaton on a row of boxes, each containing at most one ball. At each step, balls move according to a soliton rule. Find the state after 10^18 steps...
n-sequences
A sequence (a_1, a_2,..., a_n) is called an n-sequence if for all 1 <= i < j <= n, a_i <= a_j and a_j - a_i <= j - i. Find the number of n -sequences with values in {1,..., k} for given n, k.
Necklace of Circles
Consider a ring of circles packed inside an annular region between two concentric circles. Using Descartes' Circle Theorem and inversive geometry, find the sum of the curvatures of circles in speci...
Sum of Squares of Unitary Divisors
A unitary divisor d of a number n is a divisor such that gcd(d, n/d) = 1. The unitary divisors of 4! = 24 are 1, 3, 8, 24. The sum of their squares is 1^2 + 3^2 + 8^2 + 24^2 = 650. Let S(n) represe...
Range Flips
N disks are placed in a row, indexed 1 to N from left to right. Each disk has a black side and a white side. Initially all disks show their white side. At each turn, two integers A and B between 1...
Square Space Silo
Problem 431: Square Space Silo
Totient Stairstep Sequences
Define the iterated Euler totient function: phi^((0))(n) = n, phi^((k))(n) = phi(phi^((k-1))(n)). The sequence terminates at 1. Let f(n) be the number of steps to reach 1 (i.e., f(n) = min{k: phi^(...
Steps in Euclid's Algorithm
Let E(x, y) be the number of division steps in the Euclidean algorithm to compute gcd(x, y), defined by E(x, 0) = 0 and E(x, y) = 1 + E(y, x mod y) for y > 0. Define S(N) = sum_(1 <= x, y <= N) E(x...
Rigid Graphs
A graph G = (V, E) embedded in the plane is rigid if it cannot be continuously deformed while preserving edge lengths, other than by rigid motions (translations and rotations). Count the number of...
Polynomials of Fibonacci Numbers
Let F_n be the n -th Fibonacci number (F_0 = 0, F_1 = 1). Define P_k(x) = sum_(n=0)^k F_n x^n. Evaluate sum_(n=1)^N P_k(n) (mod p) for given k, N, and prime p.
Unfair Wager
Julie proposes a wager to her sister Louise. They use a generator of independent random numbers uniformly distributed on (0, 1). Starting with S = 0: Louise adds random numbers to S until S > 1, an...
Fibonacci Primitive Roots
A primitive root g of a prime p is a Fibonacci primitive root if g^n + g^(n+1) equiv g^(n+2) (mod p) for all n >= 0. Find the sum of all primes less than 10^8 that have at least one Fibonacci primi...
Integer Part of Polynomial Equation's Solutions
For an n -tuple of integers t = (a_1,..., a_n), let (x_1,..., x_n) be the real solutions of x^n + a_1 x^(n-1) + a_2 x^(n-2) +... + a_(n-1)x + a_n = 0, sorted in increasing order. Consider only tupl...
Sum of Sum of Divisors
Let sigma(k) denote the sum of divisors of k. Define S(N) = sum_(i=1)^N sum_(j=1)^N sigma(i * j). Given S(10^3) = 563576517282 and S(10^5) mod 10^9 = 215766508, find S(10^11) mod 10^9.
GCD and Tiling
Tile a board of length n and height 1 with either 1 x 2 blocks or 1 x 1 digit blocks (digits 0-9). Let T(n) be the number of tilings. Define S(L) = sum_(a=1)^L sum_(b=1)^L sum_(c=1)^L gcd (T(c^a),...
The Inverse Summation of Coprime Couples
For an integer M >= 2, define R(M) = sum_(1 <= p < q <= M, p + q >= M, gcd(p,q) = 1) (1)/(pq). Let S(N) = sum_(M=2)^N R(M). Given that S(2) = 1/2, S(10) approx 6.9147, and S(100) approx 58.2962, fi...
Eleven-free Integers
An integer is called eleven-free if its decimal expansion does not contain any substring representing a power of 11 (excluding 11^0 = 1). The forbidden substrings are 11, 121, 1331, 14641, 161051,....
GCD Sequence
Define the sequence g(n) by g(1) = 1 and g(n) = g(n-1) + gcd(n, g(n-1)) for n >= 2. Find g(10^15).
The Roundtable Lottery
A group of n people sit around a circular table, each holding a lottery ticket numbered 1 to n. The tickets are collected and randomly redistributed (uniformly at random among all n! permutations)....
Retractions A
For the group G = Z_n^k, a retraction is an idempotent group endomorphism r: G -> G satisfying r circ r = r. Let R(n, k) denote the number of retractions on Z_n^k. Find R(12^12) (mod 10^9 + 7).
Retractions B
For every integer n > 1, define the family of functions f_(n,a,b)(x) equiv ax + b (mod n) for 0 < a < n, 0 <= b < n, 0 <= x < n. The function f_(n,a,b) is a retraction if f_(n,a,b)(f_(n,a,b)(x)) eq...
Retractions C
An affine map f_(n,a,b)(x) = ax + b (mod n) with a, b in {0, 1,..., n-1} is a retraction if f circ f = f, i.e., f(f(x)) equiv f(x) (mod n) for all x. Let R(n) denote the number of retractions for n...
Average Least Common Multiple
Define the average LCM function: f(n) = (1)/(n) sum_(k=1)^n lcm(k, n). Compute S(N) = sum_(n=1)^N f(n) (mod 10^9 + 7) for N = 10^8.
Chocolate Covered Candy
A candy has the shape of a body of revolution formed by rotating an ellipse about its minor axis, then coated with a uniform chocolate layer of thickness t. Find the volume of chocolate for an elli...
Hypocycloid and Lattice Points
A hypocycloid is the curve traced by a point on a small circle rolling inside a larger circle. Find the number of lattice points (integer coordinate points) on or inside specific hypocycloids.
Modular Inverses
For a positive integer n, define I(n) as the largest positive integer m < n - 1 such that m^2 equiv 1 (mod n). If no such m exists, set I(n) = 1. Known values: I(7) = 1, I(15) = 11, I(100) = 51. Co...
Long Products
Define F(m, n) as the number of n -tuples (a_1, a_2,..., a_n) of positive integers for which the product does not exceed m: F(m, n) = |bigl{(a_1,..., a_n) in Z_(>0)^n: a_1 a_2... a_n <= mbigr}|. Gi...
Lattice Quadrilaterals
A simple quadrilateral is a polygon with four distinct vertices, no straight angles, and no self-intersections. Let Q(m, n) be the number of simple quadrilaterals whose vertices are lattice points...
Project Euler Problem 454: Diophantine Reciprocals III
In the equation 1/x + 1/y = 1/n, where x, y, and n are positive integers, define F(L) as the number of solutions satisfying x < y <= L. Checkpoints: F(15) = 4 F(1000) = 1069 Find F(10^12).
Project Euler Problem 455: Powers With Trailing Digits
Let f(n) be the largest positive integer x less than 10^9 such that the last 9 digits of n^x form the number x (including leading zeros), or 0 if no such x exists. Examples: f(4) = 411728896 (since...
Triangles Containing the Origin II
Define: x_n = (1248n mod 32323) - 16161 y_n = (8421n mod 30103) - 15051 P_n = {(x_1, y_1), (x_2, y_2),..., (x_n, y_n)} Let C(n) be the number of triangles whose vertices are in P_n which contain th...
Project Euler Problem 457: A Polynomial Modulo the Square of a Prime
Let f(n) = n^2 - 3n - 1. Let p be a prime. Let R(p) be the smallest positive integer n such that f(n) mod p^2 = 0, or R(p) = 0 if no such n exists. Let SR(L) = sum of R(p) for all primes p <= L. Fi...
Project Euler Problem 458: Permutations of Project
Consider the word "project" which has 7 distinct letters: {p, r, o, j, e, c, t}. Let T(n) be the number of strings of length n, formed using these 7 characters, that do NOT contain any permutation...
Flipping Game
The flipping game is a two-player game played on an N x N square board. Each square contains a disk with one side white and one side black. The game starts with all disks showing their white side....
An Ant on the Move
On the Euclidean plane, an ant travels from point A(0, 1) to point B(d, 1) for an integer d. In each step, the ant at point (x0, y0) chooses one of the lattice points (x1, y1) which satisfy x1 >= 0...
Almost Pi
Let f_n(k) = e^(k/n) - 1 for all non-negative integers k. Define g(n) = a^2 + b^2 + c^2 + d^2 for the unique tuple of non-negative integers (a, b, c, d) that minimizes |f_n(a) + f_n(b) + f_n(c) + f...
Permutation of 3-smooth Numbers
A 3-smooth number is an integer whose only prime factors are 2 and 3. For an integer N, let S(N) be the set of 3-smooth numbers <= N. Define F(N) as the number of permutations of S(N) in which each...
A Weird Recurrence Relation
Define f on positive integers by: f(1) = 1, f(3) = 3 f(2n) = f(n) f(4n+1) = 2f(2n+1) - f(n) f(4n+3) = 3f(2n+1) - 2f(n) Let S(n) = sum_(i=1)^n f(i). Given S(8) = 22 and S(100) = 3604, find S(3^37) m...
Mobius Function and Intervals
The Mobius function mu(n) equals (-1)^k if n is squarefree with k distinct prime factors, and 0 otherwise. Define: P(a,b) = |{n in [a,b]: mu(n) = 1}| N(a,b) = |{n in [a,b]: mu(n) = -1}| Let C(n) co...
Polar Polygons
A polar polygon is a polygon whose kernel (the set of interior points from which the entire boundary is visible) strictly contains the origin. Vertices have integer coordinates with |x|, |y| <= n....
Distinct Terms in a Multiplication Table
Let P(m, n) be the number of distinct terms in an m x n multiplication table (entry in row i, column j is i * j, for 1 <= i <= m, 1 <= j <= n). Given: P(64, 64) = 1263, P(12, 345) = 1998, P(32, 10^...
Superinteger
An integer s is a superinteger of another integer n if the digits of n form a subsequence of the digits of s. Let p(i) be the i -th prime, c(i) the i -th composite. Define sd(n) = 1 + (n-1) mod 9 (...
Smooth Divisors of Binomial Coefficients
An integer is B-smooth if none of its prime factors is greater than B. Define S_B(n) as the largest B-smooth divisor of n. Examples: S_1(10) = 1 S_4(2100) = 12 S_17(2496144) = 5712 Define: F(n) = s...
Empty Chairs
In a room, N chairs are placed around a circular table. Knights enter one by one and choose at random an available empty chair to sit in. A chair is available if both of its neighbors are empty (to...
Super Ramvok
Ramvok (Single Game) A player has a fair d-sided die (sides 1 to d, some possibly blank). Before playing, the player chooses a number of turns t and pays an upfront cost of c*t. On each turn i (1 <...
Triangle Inscribed in Ellipse
A triangle triangle ABC is inscribed in the ellipse (x^2)/(a^2) + (y^2)/(b^2) = 1, where 0 < 2b < a and a, b are positive integers. Let r(a, b) be the radius of the incircle of triangle ABC when th...
Comfortable Distance II
N seats are arranged in a row. People fill them according to these rules: 1. No person sits beside another (adjacent seats cannot both be occupied). 2. The first person may choose any seat. 3. Each...
Phigital Number Base
Let varphi = frac1+sqrt(5)2 be the golden ratio. Every positive integer has a unique representation as a sum of non-consecutive powers of varphi (a "phigital" representation using digits 0 and 1, w...
Last Digits of Divisors
For a positive integer n and digit count d, let f(n, d) be the number of divisors of n! whose last d digits equal the last d digits of n!. That is, f(n,d) = #{k | n!: k equiv n! (mod 10^d)}. Define...
Music Festival
A music festival has n stages, each running m acts sequentially with no gaps between acts on the same stage. A festival-goer wishes to attend exactly one complete act from each stage, with no two c...
Circle Packing II
Let R(a, b, c) be the maximum area covered by three non-overlapping circles inside a triangle with edge lengths a, b, and c. Let S(n) be the average value of R(a, b, c) over all integer triplets (a...
Number Sequence Game
Two players alternate turns removing either the first or last number from a sequence S. Each player tries to maximize their own score (sum of numbers taken). Player 1 goes first. The sequence S is...
Mixtures
Mixtures of three substances A, B, and C are described by ratios (a: b: c), where a mixture with ratio (2: 3: 5) contains 20% A, 30% B, and 50% C. For a positive integer n, suppose that for every t...
Roots on the Rise
Given the equation: 1/x = (k/x)^2 (k + x^2) - kx Let a_k, b_k, c_k represent its three solutions (real or complex). For k = 5, the solutions are approximately {5.727244, -0.363622+2.057397i, -0.363...
The Last Question
Consider all the words which can be formed by selecting letters, in any order, from the phrase: "thereisasyetinsufficientdataforameaningfulanswer" Suppose those with 15 letters or less are listed i...
Chef Showdown
A group of n chefs participate in a turn-based strategic cooking competition. On each chef's turn, he/she cooks a dish. Chef k has skill level S(k) = F_k / F_(n+1), where F_k is the k -th Fibonacci...
The Incenter of a Triangle
ABC is an integer-sided triangle with incenter I and perimeter p. The segments IA, IB, and IC all have integral length. Let L = p + |IA| + |IB| + |IC|. Let S(P) = sum L over all such triangles with...
Repeated Permutation
A permutation P of {1, 2,..., n} has order f(P) equal to the smallest positive integer m such that P^m is the identity. Let g(n) be the average of f(P)^2 over all n! permutations of {1,..., n}. Giv...
Arithmetic Derivative
The arithmetic derivative is defined by: p' = 1 for any prime p (ab)' = a'b + ab' (Leibniz product rule) 0' = 0, 1' = 0 Define ad(n) = n' as the arithmetic derivative of n. Compute sums of ad(n) ov...
Maximum Number of Divisors
Let d(i) be the number of divisors of i. Define M(n, k) = max(d(n), d(n+1),..., d(n+k-1)). Given that sum_(n=1)^100 M(n, 10) = 432, find sum_(n=1)^(10^8) M(n, 10^5).
Palindrome-Containing Strings
Let F_5(n) be the number of binary strings of length at most n that contain a palindromic substring of length at least 5. Given: F_5(4) = 0, F_5(5) = 8, F_5(6) = 42, F_5(11) = 3844. Let D(L) be the...
Sums of Power Sums
Define the power sum f_k(n) = sum_(i=1)^n i^k. Let S_k(p) = sum_(i=1)^(p-1) f_k(i) mod p where p is prime. Compute sums of S_k(p) for specified values of k and ranges of primes p.
Unbalanced Nim
Consider a Nim variant where from a heap of size h, a player may remove between 1 and floor(h/2) stones (leaving at least ceil(h/2) stones). The last player to move wins (normal play convention). A...
Common Factors Between Two Sequences
Let varphi(n) denote Euler's totient function and sigma(n) denote the sum-of-divisors function. Define G(n) = gcd(varphi(n), sigma(n)). Compute sum_(n=1)^N G(n) for a given large N.
Jumping Frog
A frog sits on stepping stones arranged in a line, numbered 0, 1, 2,..., n. Starting at stone 0, the frog wants to reach stone n. At each step, the frog can jump forward by 1, 2, or 3 stones. Count...
Double Pandigital Number Divisible by 11
We call a positive integer double pandigital if it uses all the digits 0 to 9 exactly twice (with no leading zero). How many double pandigital numbers are divisible by 11?
Totient Chains
Define the iterated Euler totient function by varphi^((0))(n) = n and varphi^((k))(n) = varphi(varphi^((k-1))(n)). The totient chain starting at n is the sequence n, varphi(n), varphi^((2))(n),......
Under the Rainbow
70 colored balls are placed in an urn, 10 for each of the seven rainbow colors. What is the expected number of distinct colors in 20 randomly picked balls? Give your answer with nine digits after t...
Collatz Prefix Families
The Collatz function is defined by c(n) = n/2 if n is even, and c(n) = 3n + 1 if n is odd. A Collatz prefix family of length k is the set of all starting values in [1, N] whose Collatz sequences sh...
Writing n as the Product of k Distinct Divisors
Let W(n, k) denote the number of ways to write n as the product of exactly k distinct integers, each greater than 1. Order does not matter. For example, W(12, 2) = 4: 12 = 2 x 6 = 3 x 4 = 2 x 6 = 1...
Incenter and Circumcenter of Triangle
For a triangle with integer side lengths a, b, c, the incenter I and circumcenter O are two classical triangle centers. The distance between them is given by Euler's formula: OI^2 = R^2 - 2Rr = R(R...
Drunken Tower of Hanoi
In the Drunken Tower of Hanoi, there are 3 pegs and n disks of distinct sizes initially stacked on peg 1 in decreasing order (largest at bottom). A move consists of selecting a legal move uniformly...
Remainder of Polynomial Division
For positive integers n and m, we define: F_n(x) = x^n G_m(x) = (x-1)^m Let R_(n,m)(x) be the remainder when dividing F_n(x) by G_m(x). Define C(n, m, d) as the absolute value of the coefficient of...
St. Petersburg Lottery
In the St. Petersburg game, a fair coin is flipped repeatedly until tails appears. If tails appears on the k -th flip, the payout is 2^k dollars. The classical paradox is that the expected payout i...
Problem 500!!!
The number of divisors of 120 is 16. In fact, 120 is the smallest number having 16 divisors. Find the smallest number with 2^500500 divisors. Give your answer modulo 500500507.
Eight Divisors
The eight divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24. The ten numbers not exceeding 100 having exactly eight divisors are 24, 30, 40, 42, 54, 56, 66, 70, 78, and 88. Let f(n) denote the count...
Counting Castles
We build "castles" on a w x h grid. A castle is defined by a row-by-row binary profile: each cell in the grid is either filled or empty, subject to the constraints that (1) the bottom row is comple...
Compromise or Persist
Alice is sitting in front of n bowls numbered 1 to n, each containing a single marble. She picks a random bowl, keeping the marble from it. She then continues picking random bowls; if the bowl stil...
Square on the Inside
Let ABCD be a quadrilateral whose vertices are lattice points lying on the coordinate axes: A(a, 0), B(0, b), C(-c, 0), D(0, -d) where 1 <= a, b, c, d <= m and a, b, c, d, m are integers. For m = 4...
Bidding Game
Alice and Bob play a bidding game. Each starts with n chips. In each round, both simultaneously bid some number of their chips (0 to their remaining total). The higher bidder wins the round (ties b...
Clock Sequence
Consider the infinite periodic digit stream 123432123432123432... and read it from left to right. Define v_n to be the shortest consecutive block of unread digits whose digit sum is exactly n. The...
Shortest Lattice Vector
Given a lattice defined by basis vectors in R^n, find the shortest non-zero lattice vector. This is the Shortest Vector Problem (SVP), fundamental to lattice-based cryptography and number theory. F...
Integers in Base i-1
Every Gaussian integer a + bi (where a, b in Z and i = sqrt(-1)) can be uniquely represented in base beta = i - 1 using digits {0, 1}: a + bi = sum_(k=0)^m d_k * (i-1)^k, d_k in {0, 1} Define f(a +...
Divisor Nim
Alice and Bob play a Nim variant called Divisor Nim. There is a single pile of n stones. On each turn, a player must remove d stones where d is a proper divisor of the current pile size (i.e., d |...
Tangent Circles
Consider three mutually externally tangent circles C_1, C_2, C_3 that are all internally tangent to a larger circle C_0. The radii of C_1, C_2, C_3 are a, b, c respectively. Given that the circles...
Sequences with Nice Divisibility Properties
Let S(n, k, m) denote the number of n -tuples (a_1, a_2,..., a_n) of positive integers satisfying: 1. 1 <= a_i <= m for all 1 <= i <= n. 2. a_1 + a_2 +... + a_n equiv 0 (mod k). Compute S(n, k, m)...
Sums of Totients of Powers
Let varphi denote Euler's totient function. Compute sum_(n=1)^N varphi(n^k) for given N and k. The specific instance asks for sum_(n=1)^(5 x 10^8) varphi(n) (i.e., k = 1).
Integral Median
A triangle has integer sides a <= b <= c. The median to side a has length m_a = (1)/(2)sqrt(2b^2 + 2c^2 - a^2). Let T(N) count the number of such triangles with a <= b <= c <= N for which m_a is a...
Geoboard Shapes
A geoboard is an n x n grid of pegs. A shape is formed by stretching a rubber band around some subset of pegs to form a simple closed polygon. Two shapes are considered the same if one can be trans...
Dissonant Numbers
For a positive integer n and base b >= 2, let ds_b(n) denote the digit sum of n in base b. Define D(b, s, N) as the count of integers 1 <= n <= N with ds_b(n) = s. Compute sum D(b_i, s_i, N_i) for...
5-Smooth Totients
A number is 5-smooth (or a Hamming number) if its largest prime factor does not exceed 5. Let S(L) be the sum of all positive integers n <= L such that varphi(n) is 5-smooth. Given S(100) = 3728, f...
A Real Recursion
For every real number a > 1, define the sequence g_a by: g_a(x) = 1 for x < a, g_a(x) = g_a(x-1) + g_a(x-a) for x >= a. Let G(n) = g_(sqrt(n))(n). Given G(90) = 7564511, find sum G(p) (mod 10^9 + 7...
Prime Triples and Geometric Sequences
Let S(n) be the sum of a + b + c over all triples (a, b, c) of prime numbers with a < b < c < n such that a + 1, b + 1, c + 1 form a geometric sequence. Given S(100) = 1035, find S(10^8).
Tricoloured Coin Fountains
A coin fountain is an arrangement of coins in rows where the bottom row is a contiguous block, and every coin in a higher row touches exactly two coins in the row below. Let f(n) count the number o...
Simbers
A positive integer is called a simber if every decimal digit that appears in its representation appears an even number of times. For example, 1221 is a simber (two 1s and two 2s), but 1231 is not (...
Smallest Prime Factor
Let smpf(n) denote the smallest prime factor of n for n >= 2. Define S(N) = sum_(n=2)^N smpf(n). Compute S(10^12) mod 10^9.
Hilbert's Blackout
Consider a 2^n x 2^n grid of lights indexed by an order- n Hilbert curve. A blackout operation turns off lights at positions along the curve satisfying specific arithmetic conditions. Determine the...
First Sort I
Consider the following sorting algorithm on a permutation sigma of {1, 2,..., n}: repeatedly scan from left to right, find the first element that is greater than its successor, remove it, and reins...
First Sort II
Using the "first sort" algorithm from Problem 523, let E(n) be the expected number of moves to sort a uniformly random permutation of {1,..., n}. Compute E(10^18) mod (10^9 + 7).
Rolling Ellipse
An ellipse with semi-major axis a and semi-minor axis b (a > b > 0) rolls without slipping along the x -axis. Compute the arc length of the path traced by the center of the ellipse over one complet...
Largest Prime Factors of Consecutive Numbers
Let f(n) be the largest prime factor of n. Define g(n) = sum_(i=0)^8 f(n+i) and h(n) = max_(2 <= k <= n) g(k). Given h(10^9) = 4896292593, find h(10^16).
Randomized Binary Search
A secret integer t is selected uniformly at random from {1, 2,..., n}. We make guesses and receive feedback (<, =, or >). Standard binary search B(n): always guess g = floor((L+H)/2). Randomized bi...
Constrained Sums
Let S(n, k, b) denote the number of solutions to x_1 + x_2 +... + x_k <= n where 0 <= x_m <= b^m for all 1 <= m <= k. Given: S(14, 3, 2) = 135 S(200, 5, 3) = 12949440 S(1000, 10, 5) mod (10^9 + 7)...
10-substrings
A 10-substring of a number is a contiguous subsequence of its digits whose digits sum to 10. A number is 10-substring-friendly if every one of its digits belongs to at least one 10-substring. Let T...
GCD of Divisors
Define f(n) = sum_(d | n) gcd(d, n/d) and F(k) = sum_(n=1)^k f(n). Given F(10) = 32 and F(1000) = 12776, find F(10^15).
Chinese Leftovers
Let g(a, n, b, m) denote the smallest non-negative integer x satisfying the simultaneous congruences x equiv a (mod n), x equiv b (mod m), or 0 if no such x exists. Define S = sum_(n=1,000,000)^(1,...
Nanoscale Strips
Horizontal strips of width W and unit height can be placed at continuous vertical positions on a W x H grid. Let f(W, H) count the number of distinct visible patterns. Compute f(10^7, 10^7) mod 999...
Minimum Values of the Carmichael Function
The Carmichael function lambda(n) is the smallest positive integer m such that a^m equiv 1 (mod n) for every integer a coprime to n. Define f(N) = |left{n: 1 <= n <= N, lambda(n) = lambda(n+1)right...
Weak Queens
A weak queen on a chessboard attacks only the 8 adjacent squares (like a king). Let f(n) be the number of ways to place n non-attacking weak queens on an n x n board with exactly one queen per row....
Fractal Sequence
Define the fractal sequence (Kimberling's sequence) a(n) as the lexicographically earliest sequence of positive integers such that removing the first occurrence of each value yields the original se...
Modulo Power Identity
Let S(n) be the sum of all positive integers m not exceeding n having the following property: a^(m+4) equiv a (mod m) for all integers a. The values of m <= 100 that satisfy this property are 1, 2,...
Counting Tuples
Count tuples of primes summing to n with specific constraints. The problem asks to compute a specific quantity related to generating functions.
Maximum Quadrilaterals
Find maximum area quadrilateral from point sets. The problem asks to compute a specific quantity related to convex hull + rotating calipers.
Odd Elimination
Alternating left-right elimination, find last survivor sum. The problem asks to compute a specific quantity related to Josephus variant with alternating direction.
Coprime Pythagorean Triples
A primitive Pythagorean triple (a, b, c) satisfies a^2 + b^2 = c^2 with gcd(a, b, c) = 1 and a < b < c. Count the number of such triples with c <= N for N = 3,141,592,653,589,793.
Divisibility of Harmonic Number Numerators
The n -th harmonic number H_n is defined as: H_n = sum_(k=1)^n (1)/(k) When expressed in lowest terms as H_n = (a_n)/(b_n), we define f(n) to be the number of integers k, 1 <= k <= n, such that the...
Geometric Progression with Maximum Sum
A geometric progression (GP) consists of terms a, ar, ar^2,..., ar^(k-1) where a is the first term, r is the common ratio, and k is the number of terms. We require all terms to be distinct positive...
Prime String Subsequences
Count subsequences of prime-digit string forming primes. The problem asks to compute a specific quantity related to DP over digit positions.
Chromatic Conundrum
Count proper k-colorings of a specific graph. The problem asks to compute a specific quantity related to chromatic polynomial.
Faulhaber's Formulas
Sum of denominators of leading coefficients of power sum polynomials. The problem asks to compute a specific quantity related to Bernoulli numbers.
Sum of Sum of Divisors
Iterated divisor sum functions evaluated at 10^10. The problem asks to compute a specific quantity related to Dirichlet convolution powers of zeta.
Distance of Random Points in Rectangles
Expected distance between random points in rectangles. The problem asks to compute a specific quantity related to geometric probability integral.
Gozinta Chains
Count chains in divisor lattice, sum over n <= N. The problem asks to compute a specific quantity related to multiplicative function.
Divisibility of Factorials
The smallest number m such that 10 divides m! is m = 5. The smallest number m such that 25 divides m! is m = 10. Let s(n) be the smallest number m such that n divides m!. So s(10) = 5 and s(25) = 1...
Divisor Game
Sprague-Grundy analysis of a divisor subtraction game.
Sum of Digit Sequence
Let a_0, a_1, a_2,... be an integer sequence defined by: a_0 = 1. a_n = a_(n-1) + s(a_(n-1)) for n >= 1, where s(m) denotes the sum of the base-10 digits of m. The first terms are 1, 2, 4, 8, 16, 2...
Chinese Leftovers II
Let p_1 < p_2 <... < p_k be the first k primes. For a positive integer n, define r_i(n) = n mod p_i, 1 <= i <= k. Define S(n, k) as the number of integers m with 1 <= m <= n such that r_i(m) >= r_i...
Power Sets of Power Sets
Compute last 8 digits of 2^{2^n} using modular tower exponentiation.
Centaurs on a Chess Board
Count placements of centaurs (combined knight+bishop movement) on a chessboard.
McCarthy 91 Variant
Analyze a generalized McCarthy function with nested recursive calls.
Squarefree Gaussian Integers
A Gaussian integer is a number z = a + bi where a, b are integers and i^2 = -1. A proper Gaussian integer satisfies a > 0 and b >= 0. A Gaussian integer is squarefree if its prime factorization doe...
Cutting Triangles
A triangle is cut into four pieces by two straight lines, each starting at one vertex and ending on the opposite edge. This results in forming three smaller triangles and one quadrilateral. If the...
Irrational Jumps
Count lattice walks with irrational step lengths reaching specific targets.
Permuted Matrices
Count permutation matrices with prescribed row/column sum properties.
Coprime Columns
Count matrices where column GCDs are all 1.
Divisor Pairs
Let Pairs(n) denote the number of ordered pairs (d_1, d_2) of positive divisors of n satisfying d_1 <= d_2 and d_1 * d_2 = n. Define S(N) = sum_(n=1)^N Pairs(n). We seek S(10^10).
Maximal Perimeter
Given an N x N grid of integer lattice points {0, 1,..., N}^2, find the triangle with three vertices on lattice points that has the maximum perimeter. Define f(N) as this maximum perimeter, rounded...
Robot Welders
A company has n robot welders on a production line. Each robot i has a fixed position p_i and a welding range [a_i, b_i] on the line. A weld job at position x can be performed by robot i if a_i <=...
Maximal Polygons
Find maximal area lattice polygons with given constraints.
Divisor Sum Divisors
Count n <= N where d | sigma(n) for specific d.
Cake Icing Puzzle
Adam plays a game with his birthday cake. He cuts a piece forming a circular sector of angle x degrees and flips the piece upside down, placing the icing on the bottom. He then rotates the cake by...
Cake Icing Puzzle
Minimize icing surface area on a multi-layer cake.
Reciprocal Circles
Apply Descartes circle theorem to find integer curvature circles.
Prime Mountain Range
Count mountain range sequences formed from prime digit sequences.
Snowflake Sequences
Count sequences with snowflake-like fractal self-similarity.
Super Pandigital Numbers
A positive number is pandigital in base b if it contains all digits from 0 to b-1 when written in base b. An n -super-pandigital number is a number that is simultaneously pandigital in all bases fr...
Idempotent Matrices
A matrix M is called idempotent if M^2 = M. Let I(n) be the number of idempotent 3 x 3 matrices whose entries are taken from {0, 1,..., n-1} and arithmetic is performed modulo n. Find sum_(n=2)^200...
Unfair Race
Expected number of runners who are ever in the lead during a race.
Verifying Primes
Sum verification costs for Pratt primality certificates.
Wandering Robots
Stationary distribution probability at target cell on grid with obstacles.
Irrational Jumps
Count points in arc after irrational jumps on a circle.
Counting Hexagons
An equilateral triangle with integer side length n >= 3 is divided into n^2 equilateral triangles with side length 1. The vertices of these triangles constitute a triangular lattice with ((n+1)(n+2...
Integers with Decreasing Prime Powers
Count integers n <= N with decreasing exponent sequence in factorization.
Lattice Points in Lattice Cubes
Count interior lattice points of all lattice cubes up to side N.
Squarefree Hilbert Numbers
Count Hilbert numbers (4k+1) not divisible by square of any Hilbert number > 1.
47-smooth Triangular Numbers
A positive integer m is called p -smooth if every prime factor of m is at most p. Let T(n) = tfracn(n+1)2 denote the n -th triangular number. Determine S = sum_(n >= 1, T(n) is 47-smooth) n.
Nearly Isosceles 120 Degree Triangles
A triangle is called nearly isosceles if two of its sides differ by no more than one unit. Find the sum of the perimeters of all nearly isosceles triangles with a 120° angle and integer sides. More...
Heron Envelopes
Find integer-sided triangles with integer area (Heronian triangles) with extra properties.
Birthday Problem Revisited
Variant of birthday problem with specific collision counting.
Nested Square Roots
Evaluate and count nested radical expressions equal to integers.
Binary Quadratic Forms
Count integers representable by ax^2 + bxy + cy^2.
Concave Triangle
A square is drawn around a circle as shown. We shall call the blue shaded region the "L-section". A line is drawn from the bottom left of the square to the top right, as shown in the diagram. The o...
Quintinomial Coefficients
The coefficients in the expansion of (x^4 + x^3 + x^2 + x + 1)^k are called quintinomial coefficients. For k = 3, out of the 13 quintinomial coefficients, 7 are odd: 1, 3, 1, 3, 3, 1, 3, 1... wait,...
Pouring Water
Sum of measurable volumes using two containers.
Sets with a Given LCM
Count subsets of {1,...,n} with LCM equal to n.
Best Approximations
Given a positive integer N, define a fraction (p)/(q) (with gcd(p,q)=1 and q > 0) to be a best approximation to the real number alpha if |p - qalpha| < |p' - q'alpha| for every fraction (p')/(q') w...
Factorial Trailing Digits
For a prime p and positive integer n, let g(p, n) denote the last non-zero digit of n! when written in base p. Define: S(N) = sum_(p <= N, p prime) sum_(n=1)^N g(p, n) Compute S(10^8).
Fleeting Medians
Define the sequence S_n for n >= 1 by: S_n = s_n mod 10007, where s_n = (prime(n))^2 mod 10007 (Here prime(n) is the n -th prime.) Let M(i, j) be the median of the subsequence S_i, S_(i+1),..., S_j...
Rhombus Tilings
A regular hexagon with side length n can be tiled by unit rhombi (each composed of two equilateral triangles). Let T(n) denote the number of such tilings. Compute T(n) for a specified n, giving the...
Incremental Random Sort
Consider an array of n distinct elements in random order. In each step, one element chosen uniformly at random is removed and re-inserted into its correct sorted position. Let E(n) denote the expec...
Number of Lattice Points in a Hyperball
Count integer points in a d-dimensional ball of radius r.
Torpids
Count valid orderings in bumps chart rowing competition.
Split Divisibilities
Count ways to split digits of n into groups dividing n.
Distinct Colourings of a Rubik's Cube
Consider a standard 3 x 3 x 3 Rubik's Cube with 54 visible facelets (9 per face). Each facelet can be colored in one of c colors. Two colorings are equivalent if one can be obtained from the other...
Integer Sided Equiangular Hexagons
An equiangular hexagon is a hexagon where all interior angles are equal (each 120°). The sides have integer lengths a, b, c, d, e, f (in order). Count the number of such hexagons with perimeter at...
Divisibility Streaks
For every positive integer n, define streak(n) = k as the smallest positive integer k such that n + k is not divisible by k + 1. Examples: streak(13) = 4 because 2 | 14, 3 | 15, 4 | 16, but 5 nmid...
Product of Head Counts
Problem 602: Product of Head Counts
Bonus on Primes
Problem 603: Bonus on Primes
Convex Path in Square
Let F(N) denote the number of lattice paths from (0,0) to (N,N) using unit steps right (R) or up (U) such that the path is convex -- meaning the path never goes above the line y = x and then return...
Pairwise Coin-Tossing Game
A set of n people play a round-robin coin-tossing tournament. Each pair plays exactly once: they flip a fair coin, and one person is declared the winner. Let W_i denote the number of wins for playe...
Gozinta Chains II
A gozinta chain for n is a sequence {1, a, b,..., n} where each element properly divides the next. For example, there are eight distinct gozinta chains for 12: {1,12},\ {1,2,12},\ {1,2,4,12},\ {1,2...
Marsh Crossing
Frodo and Sam need to travel exactly 100 leagues due East from point A to point B. On normal terrain they can cover 10 leagues per day. A marsh runs exactly South-West to North-East, 50 leagues wid...
Divisor Sums Modulo Prime
Compute sums of divisor functions modulo a prime.
Pi Sequences
Count sequences derived from the primality of successive values, building chains.
Roman Numerals II
Count valid representations in a modified Roman numeral system.
Hallway of Square Steps
Peter has a hallway of length n. Starting at position 0, he takes steps forward where each step length must be a perfect square (1, 4, 9, 16,...). Let f(n) denote the number of distinct ordered seq...
Friend Numbers
Let s(n) denote the sorted tuple of decimal digits of n. Two positive integers a and b are friend numbers if s(a) = s(b). Define f(n) as the number of positive integers m <= 10^n such that m has no...
Pythagorean Ant
An ant starts at a random point in a right triangle. Find the probability it reaches the hypotenuse first.
Special Partitions 2
Count integer partitions with special ordering and distinctness constraints.
The Millionth Number with at Least One Million Prime Factors
Define D(n) as the number of ways to write n as a product of powers of 2 alone — equivalently, D(n) = v_2(n) + 1 counts the choices 2^0, 2^1,..., 2^(v_2(n)). More precisely (per the actual Project...
Creative Numbers
Alice plays a game starting with a list L of integers. She can perform two operations: 1. Remove two elements a and b from L and add a^b to L. 2. If c = a^b is in L (with a, b > 1), remove c and ad...
Mirror Power Sequence
Find numbers whose digit reversal equals a power of the original.
Numbers with a Given Prime Factor Sum
Find numbers whose prime factors (with multiplicity) sum to a given value.
Square Subsets
Count subsets of {1,..., n} whose product is a perfect square.
Planetary Gears
Analyze gear ratios in a planetary gear system and find specific configurations.
Expressing an Integer as the Sum of Triangular Numbers
Let T(n) denote the number of ordered triples (a, b, c) of non-negative integers such that (a(a+1))/(2) + (b(b+1))/(2) + (c(c+1))/(2) = n. Find sum_i T(n_i) for specified values n_i (Project Euler...
Riffle Shuffles
A perfect (out-)riffle shuffle on a deck of 2n cards in positions 0, 1,..., 2n-1 maps position i to position 2i mod (2n-1) (with position 2n-1 fixed). Equivalently, working modulo m = 2n+1: positio...
Lambda Count
Let Lambda(n) count the number of permutations of {1, 2,..., n} that consist of exactly two disjoint cycles. Compute Lambda(n) mod p for given n and prime modulus p.
Two Heads Are Better Than One
A fair coin is flipped repeatedly. Let E_n denote the expected number of flips required to obtain n consecutive heads. Compute E_n and related quantities modulo a given prime.
GCDSUM
Define G(N) = sum_(j=1)^N sum_(i=1)^j gcd(i, j). Compute G(10^11) mod 998244353.
Counting Binary Matrices
A binary matrix is a matrix consisting entirely of 0s and 1s. Consider the following transformations that can be applied to a binary matrix: Swap any two rows Swap any two columns Flip all elements...
Counting Products
Let f(n) count the number of ordered factorizations of n into factors >= 2. For example, f(12) = 8 because 12 = 12 = 2 6 = 6 2 = 3 4 = 4 3 = 2 2 3 = 2 3 2 = 3 2 2. Define F(N) = sum_(n=2)^N f(n). C...
Open Chess Positions
Place n pawns on an n x n board so that each row and each column contains exactly one pawn. Let f(n) be the number of such positions for which a rook can start in the lower-left square, move only r...
Scatterstone Nim
In Scatterstone Nim, a player takes stones from one pile and may optionally distribute some of the removed stones to other existing piles (the total number of stones must strictly decrease). Determ...
Crossed Lines
Given N points generated by a pseudo-random sequence s_0 = 290797, s_(n+1) = s_n^2 mod 50515093, form line segments between consecutive pairs of points and count the number of pairs of segments tha...
Constrained Permutations
Let A be an n x n matrix with entries in {0, 1}, where A_ij = 1 indicates that element j is permitted in position i. Count the number of permutations sigma in S_n such that A_(i,sigma(i)) = 1 for a...
Sum of Divisors of Sum of Divisors
Let sigma(n) = sum_(d | n) d denote the sum-of-divisors function. Define S(N) = sum_(n=1)^N sigma(sigma(n)). Compute S(N) for large N.
Square Sum of Squares
Count integers n <= N that are representable as a sum of 2 squares, as a sum of 3 squares, or both, and compute the related counting functions.
Numbers of the Form $a^2 b^3$
A powerful number (squarefull number) is a positive integer n such that for every prime p | n, we have p^2 | n. Equivalently, n can be written as n = a^2 b^3 for positive integers a, b. Count the p...
Subset Sums
Given a multiset of integers, count the number of subsets whose elements sum to a specified target T. Compute this modulo a given prime.
Restricted Factorisations
Consider writing a natural number as a product of powers of natural numbers with given exponents, additionally requiring different base numbers for each power. For example, 256 can be written as a...
Flexible Digit Sum
Given any positive integer n, we can construct a new integer by inserting plus signs between some of the digits of the base B representation of n, and then carrying out the additions. For example,...
Weighted Lattice Paths
Let P_{a,b} denote a path in an a x b lattice grid from (0,0) to (a,b) using only unit moves right (R) or up (U). Define A(P_{a,b}) as the area under the path. Define G(P_{a,b}, k) = k^{A(P_{a,b})}...
Summing a Multiplicative Function
A multiplicative function f(x) satisfies f(1)=1 and f(ab)=f(a)f(b) for coprime a,b. For integer k, f_k(n) is a multiplicative function additionally satisfying f_k(p^e) = p^k for any prime p and int...
Shut the Box
Bob plays a single-player game using two standard 6-sided dice and twelve cards numbered 1 to 12, all initially face up. Each turn, Bob rolls both dice, getting numbers x and y (each in range 1-6)....
A Flea on a Chess Board
An infinite chessboard has cells of width W and height H, coloured in the standard alternating pattern: the cell containing point (x, y) is white if floor(x/W) + floor(y/H) is even, and black other...
Sum of Largest Prime Factors
Let lpf(n) denote the largest prime factor of n (with lpf(1) = 1). Compute S(N) = sum_(n=2)^N lpf(n).
2-Friendly Divisors
A divisor d of n is called unitary (or 2-friendly) if gcd(d, n/d) = 1. The number of unitary divisors of n is 2^(omega(n)), where omega(n) counts the distinct prime factors of n. Compute T(N) = sum...
Squares on the Line
n points are chosen independently and uniformly on [0, 1]. Compute expected geometric quantities related to their configuration (gaps, spacing, maximum gap).
Every Day is a Holiday
A year has n holidays uniformly distributed among 365 days. Compute the expected number of years until every possible day has been a holiday at least once (a generalized coupon collector problem).
Bounded Divisors
Count integers in [1, N] whose divisors satisfy specific bounding conditions (e.g., all divisors d satisfy d <= B or n/d <= B).
Linear Transformations of Polygonal Numbers
Find integers simultaneously representable as multiple types of polygonal numbers. The k -th s -gonal number is: P_s(k) = (k[(s-2)k - (s-4)])/(2) tag1
Skipping Squares
Define the sequence of non-square positive integers: 2, 3, 5, 6, 7, 8, 10, 11,... Find the N -th element.
Low-Prime Chessboard Nim
A Nim variant where moves are constrained to prime-length jumps (2, 3, 5, 7,...). Compute Grundy values for given positions.
Divisors of Binomial Product
Let B(n) = prod_(k=0)^n C(n, k), a product of binomial coefficients. Let D(n) = sum_(d | B(n)) d, the sum of the divisors of B(n). For example, B(5) = C(5, 0) x C(5, 1) x C(5, 2) x C(5, 3) x C(5, 4...
Patterned Cylinders
A cylinder is formed by a ring of n cells, each coloured with one of k colours. Two colourings are considered identical if one can be obtained from the other by rotation of the cylinder. Determine...
Distinct Values of a Proto-logarithmic Function
Define a completely additive arithmetic function f on positive integers by f(p^a) = g(a) for every prime p and positive integer a, where g is a fixed function (the "proto-logarithm"). Since f depen...
Frictionless Tube
n identical balls are placed in a frictionless one-dimensional tube at distinct positions x_1 < x_2 <... < x_n with velocities v_1, v_2,..., v_n. When two balls collide, they undergo a perfectly el...
Neighbourly Constraints
Count valid vertex-colourings of a graph (e.g., path or cycle) with k colours such that adjacent vertices have different colours. This is the chromatic polynomial.
Divisible Palindromes
Count the palindromes below 10^32 that are divisible by 10,000,019.
Palindromic Sequences
Given a non-square positive integer beta, let the continued fraction expansion of sqrt(beta) be [a_0; overlinea_1, a_2,..., a_p] where p is the period length. The partial quotients a_1, a_2,..., a_...
Incomplete Words
In the theory of formal languages, a word is any finite sequence of letters from a given alphabet, and a word is called incomplete if it does not contain every letter of that alphabet. For example,...
Incomplete Words II
Given an alphabet Sigma of alpha letters, I(alpha, n) is defined as the number of incomplete words over Sigma with length not exceeding n. A word is incomplete if it does not contain every letter o...
Largest Prime
Consider the sequence n^2 + k^2 for n = 1, 2, 3,... Define P(k) as the largest prime that divides any two successive terms of this sequence, i.e., the largest prime p such that p | gcd(n^2 + k^2, (...
Pandigital Triangles
Find integer-sided triangles (a, b, c) with a <= b <= c whose concatenated side lengths a \| b \| c form a pandigital string (containing each digit 0--9 exactly once).
A Long Chess Match
Two players A and B play an infinitely long chess match. In each game, A wins with probability p_A, B wins with probability p_B, and the game is drawn with probability 1 - p_A - p_B. After each gam...
Fibonacci Paths
Alice walks on a lattice grid. From point (a,b) she can step to (a+x, b+y) provided sqrt(x^2+y^2) is a Fibonacci number (1, 2, 3, 5, 8, 13,...), with x >= 0 and y >= 0. Let F(W,H) be the number of...
Sums of Subarrays
An array A_n of length n is initialized to all zeros. A pseudo-random sequence {t_i} generates updates: at step i, set A_n[t_(2i-2) mod n] mathrel+= 2(t_(2i-1) mod n) - n + 1. After each step i, de...
An Infinite Game
Peter plays a solitaire game on an infinite checkerboard. A dividing line separates left (initially all tokens) from right (initially empty). In each move, a token jumps over an adjacent token (whi...
Proportionate Nim
A variant of Nim where a player must remove a number of stones proportional to the pile size. The allowed moves from a pile of size n are to remove floor(n/k) stones for some allowed k. Determine w...
Polymorphic Bacteria
A species of bacteria S_(k,m) occurs in k types alpha_0,..., alpha_(k-1). The lifecycle rules for each bacterium of type alpha_i at each minute depend on a pseudo-random sequence r_n defined by r_0...
Moving Pentagon
Find the largest pentagonal table (by area) that can be moved through a unit-wide L-shaped corridor. The corridor consists of two unit-wide hallways meeting at a right angle. The pentagon must rema...
Square Root Smooth Numbers
A positive integer n is called square root smooth if all of its prime factors are strictly less than sqrt(n). Including the number 1, there are 29 square root smooth numbers not exceeding 100. How...
The King's Banquet
The Knights of the Order of Fibonacci are preparing for a feast. There are n knights numbered 1 to n sitting at a round table with the king. Two knights can sit adjacent only if their numbers sum t...
Colouring a Strip
Tiles of sizes 1x 1, 1x 2, and 1x 3 in four colours tile a 2 x n rectangle. Rules: (1) no four tiles meet at a point, (2) adjacent tiles differ in colour. Let F(n) be the count of valid tilings. Gi...
Colouring a Loop
Extend the tiling of Problem 670 to a 2 x n loop (cylinder). Let F_k(n) count the number of valid colourings of a 2 x n cylindrical grid using at most k colours, where adjacent cells must have diff...
One More One
Define a self-referential sequence as follows. Starting from a seed value a_0, each subsequent term a_(n+1) is obtained by counting certain digit occurrences in a_n according to a prescribed rule i...
Beds and Desks
At Euler University, n students each occupy a bed (in a dormitory) and a desk (in a classroom). Some beds are in single rooms and others in double rooms; similarly for desks. A reassignment is a pe...
Shared Splints
Count configurations of overlapping intervals (splints) on a line where splints are shared between objects. A splint of length k is an interval [a, a+k-1]. A shared splint appears in multiple objec...
$2^{\omega(n)}$
omega(n) is the number of distinct prime factors of n. Define: S(n) = sum_(d | n) 2^(omega(d)) and F(n) = sum_(i=2)^n S(i!). Given F(10) = 4821, find F(10^7) mod 1,000,000,087.
Matching Digit Sums
Let d(i, b) represent the digit sum of the number i in base b. For example, d(9, 2) = 2 since 9 = 1001_2. Define M(n, b_1, b_2) as the sum of all natural numbers i <= n for which d(i, b_1) = d(i, b...
Coloured Graphs
Count connected graphs on n nodes where nodes are coloured red, blue, or yellow, with degree constraints per colour: Red nodes: degree <= 4 Blue/yellow nodes: degree <= 3 Yellow nodes cannot be adj...
Fermat-like Equations
Count tuples (a, b, c, e, f) with a^e + b^e = c^f, 0 < a < b, e >= 2, f >= 3, c^f <= N. Given: F(10^3) = 7, F(10^5) = 53, F(10^7) = 287. Find F(10^18).
Freefarea
Let S = {A, E, F, R}. For n >= 0, let S^(n) denote the set of words of length n consisting of letters from S. The four keywords are: FREE, FARE, AREA, and REEF. Let f(n) be the number of words in S...
Yarra Gnisrever
Start with array A = (0, 1, 2,..., N-1). Perform K reversal operations, each reversing a subarray A[s_j... t_j]. The indices (s_j, t_j) are determined by a pseudo-random generator. Define R(N, K) =...
Maximal Area
For positive integers a <= b <= c <= d, let M(a,b,c,d) denote the maximum area of a quadrilateral with consecutive side lengths a, b, c, d. Define SP(n) = sum_(a <= b <= c <= d, M(a,b,c,d) in {1,.....
5-Smooth Pairs
A positive integer is 5-smooth (or a Hamming number) if its largest prime factor is at most 5. For a positive integer a, let Omega(a) denote the number of prime factors of a counted with multiplici...
The Chase II
n players sit around a circular table. Two dice are placed randomly with two distinct players. Each turn, both die-holders simultaneously roll a fair die: outcomes 1--2 pass the die left, 3--4 keep...
Inverse Digit Sum
Define s(n) as the smallest number that has a digit sum of n. For example, s(10) = 19. Let S(k) = sum_(n=1)^k s(n). We are given that S(20) = 1074. The Fibonacci sequence is defined as f_0 = 0, f_1...
Inverse Digit Sum II
f(n, m) is the m -th smallest positive integer with digit sum n. Define S(k) = sum_(i=1)^k f(i^3, i^4). Given: S(3) = 7128, S(10) equiv 32287064 (mod 10^9+7). Find S(10000) mod 10^9+7.
Powers of Two
Find p(123,678910), the 678910 -th smallest exponent j such that the decimal expansion of 2^j begins with the digits 123.
Shuffling Cards
52-card deck, rank is 'perfect' if no two same-rank cards adjacent. E[perfect ranks] = 4324/425. Find P(perfect count is prime) to 10 d.p.
Piles of Plates
Stack n plates into k distinct-sized piles. f(n,k) = max smallest pile. S(N) = sum F(n) for n=1..N. Find S(10^16) mod 10^9+7.
Binary Series
f(x) = sum d_i(x)/i^2 where d_i = i-th binary digit. Find P(f(x) > 0.5) for x uniform on [0,1). Answer to 8 d.p.
Tom and Jerry
Tom graph = graph where cop always catches robber. T(n) = count of n-vertex Tom graphs. Find T(2019) mod 10^9+7.
Long Substring with Many Repetitions
For a character string s, define L(k, s) as the length of the longest substring of s that appears at least k times. If no substring appears k times, set L(k, s) = 0. The string S_n is built via a F...
Siegbert and Jo
Siegbert and Jo play a Fibonacci Nim variant. Define: H(N) = the smallest Fibonacci number in the Zeckendorf representation of N. G(n) = sum_(k=1)^n H(k). Given that G(10) = 22 and G(1000) = 396673...
Finite Sequence Generator
a_{n+1} = a_n^2 mod n generates a sequence. g(x) = max orbit length for y<x. f(n) = max g(x) for x<=n. Find f(3000000).
Cube-full Divisors
Let s(n) be the number of cube-full divisors of n, where a positive integer is cube-full if every prime factor appears with exponent at least 3. Define S(N) = sum_(n=1)^N s(n). Find S(10^18).
Random Rectangles
3 random points in unit square define 3 axis-aligned rectangles. Find E[2nd largest area] to 10 d.p.
Mahjong
Count winning hands: 3t+2 tiles = t triples + 1 pair. DP over tile types with multiplicity constraints.
Randomly Decaying Sequence
A sequence of random numbers is generated by the rule: X_0 = c X_n = U_n * X_(n-1) for n > 0 where U_n is chosen uniformly at random from [0, 1], independently. Given that P(X_100 < 1) = 0.25 impli...
123 Numbers
Numbers using only digits {1,2,3}. Find F(111111111111222333) mod 123123123.
Triffle Numbers
sigma(n)/n has denominator 3^k (k>0) in lowest terms. Sum such n up to N.
Eulercoin
Leonhard Euler was born on 15 April 1707. Consider the sequence a_n = 1504170715041707 * n mod 4503599627370517. An element of this sequence is called an Eulercoin if it is strictly smaller than al...
Random Connected Graph
Consider the random process of successively adding edges to a graph on n labelled vertices, where each of the C(n, 2) possible edges is equally likely to be chosen at each step (with replacement of...
Jumping Flea
A regular hexagonal table of side length N is divided into equilateral unit triangles. A flea sits at the center of the table and can jump to the midpoint between its current position and any chose...
Circular Logic II
Define f: B^n -> B^n by f(b_1, b_2,..., b_n) = (c_1, c_2,..., c_n) where c_i = b_(i+1) for i < n and c_n = b_1 wedge (b_2 + b_3). Let S(n) be the number of Boolean functions T: B^n -> B satisfying...
Factors of Two in Binomial Coefficients
Define g(n, m) as the largest integer k such that 2^k | C(n, m). Let F(n) = max{g(n, m): 0 <= m <= n} and S(N) = sum_(n=1)^N F(n). Given F(10) = 3, F(100) = 6, S(100) = 389, S(10^7) = 203,222,840,...
Total Inversion Count of Digit Strings
For a digit string d_1 d_2... d_n with digits in {0, 1,..., 9}, the inversion count is #{(i,j): 1 <= i < j <= n, d_i > d_j}. Let T(n) be the sum of inversion counts over all 10^n digit strings of l...
3-Like Numbers
For a positive integer n, define f(n) as the number of non-empty substrings of n (in decimal) that are divisible by 3. Call n 3-like if f(n) equiv 0 (mod 3). Let F(d) count the d -digit 3-like numb...
Lights Out
Consider a w x h grid where each cell is either ON or OFF. Selecting a cell toggles it and all its edge-adjacent neighbors. A state is solvable if there exists a sequence of selections that turns a...
Twos Are All You Need
Define f(n) as the integer obtained by replacing each prime factor of n with 2 (i.e., if n = p_1^(a_1) p_2^(a_2)... p_k^(a_k), then f(n) = 2^(a_1 + a_2 +... + a_k) = 2^(Omega(n)), where Omega(n) is...
Even Stevens
Even Stevens flips a fair coin repeatedly. Starting with score 0, each flip adds 1 (heads, probability (1)/(2)) or 2 (tails, probability (1)/(2)) to his score. He stops when his score reaches or ex...
One Million Members
A palindromic partition of n is a multiset of positive integers that sums to n and, when listed in non-decreasing order, reads the same forwards and backwards. Equivalently, every part occurs an ev...
Binary Blackboard
Oscar and Eric play a game on a blackboard. They take turns writing binary digits (0 or 1). After all digits are written, the digits form a binary number whose value must not exceed 2n. Oscar wins...
Exponent Difference
For integers n >= 2 and m >= 1, let v_n(k) denote the n -adic valuation of k (the largest exponent e such that n^e | k). Define D(n, m) = sum_(1 <= i < j <= m) |v_n(i) - v_n(j)|. Compute sum_(p <=...
Turan's Water Heating System
A water heating system requires two working fuses connected in series (one for the house, one for the shed). There are N fuses in total, of which m are working (but we do not know which ones). Defi...
Duodigits
A positive integer is a duodigit if its decimal representation uses at most 2 distinct digits. For example, 12, 110, 33333 are duodigits, but 123 is not. Define d(n) as the smallest positive duodig...
Sextuplet Norms
Let f be a multiplicative function related to norms of algebraic integers in a sextic number field. Define G(n) = sum_(k=1)^n (f(k))/(k^2 * varphi(k)), where varphi is Euler's totient function. Giv...
Grid Graphs
For an H x W grid graph, let S(G) denote a graph-theoretic quantity (related to spanning subgraph counting) computed over all subgraphs G. Define C(H, W) = sum_G S(G) where the sum is over all subg...
Summation of a Modular Formula
For an odd prime p, define f(p) = floor(frac2^(2^p)p) mod 2^p. Let g(p) = f(p) and define G(N) = sum_(p < N, p odd prime) g(p). Given G(100) = 474 and G(10^4) = 2,819,236, find G(10^7).
Unreachable Numbers
Consider the set of integers that cannot be represented as a non-negative integer linear combination of certain values determined by a parameter p. Let G(p) denote the sum of all such unreachable (...
Number Splitting
We define an S-number to be a natural number n that is a perfect square and whose square root can be obtained by splitting the decimal representation of n into 2 or more numbers then adding them. F...
Unpredictable Permutations
A permutation P of {1, 2,..., N} is called unpredictable if there are no three indices i < j < k such that P(i), P(j), P(k) form an arithmetic progression (i.e., P(j) - P(i) = P(k) - P(j)). Let S(N...
High Powers of Irrational Numbers
Given a positive integer a that is not a perfect square, define f(a, n) = floor((ceil(sqrt(a)) + sqrt(a))^n) where floor() and ceil() denote the floor and ceiling functions. Compute G(N) = sum_(a=1...
Slowly Converging Series
For a non-negative integer k, define E_k(q) = sum_(n=1)^infinity sigma_k(n) q^n where sigma_k(n) = sum_(d | n) d^k is the divisor power sum. The series converges for 0 < q < 1. Given: E_1(1 - 2^(-4...
Pythagorean Quadrilaterals
A quadrilateral ABCD inscribed in a circle of radius r is called pythagorean if its sides a, b, c, d satisfy a^2 + b^2 + c^2 + d^2 = 8r^2. A pythagorean lattice grid quadrilateral additionally requ...
Drone Delivery
A depot manages n drones distributed along a straight road. Initially all drones are stationary and loaded. Every second, the depot selects a drone uniformly at random: If stationary, start moving...
Digit Sum Numbers
A number where one digit equals the sum of all other digits is called a digit sum number (DS-number). For example, 352, 3003, and 32812 are DS-numbers. Define S(n) as the sum of all DS-numbers with...
Falling Bottles
A stack of wine bottles is arranged in n layers, with the top layer containing 1 bottle and the bottom layer containing n bottles (triangular arrangement). When a bottle is removed, bottles above m...
Triangle of Circular Arcs
Three circles with radii r_a, r_b, r_c are mutually externally tangent, forming a "triangle of circular arcs" between their tangency points. Two special circles are defined: Circumcircle (passes th...
Circle of Coins
Consider n coins arranged in a circle, each showing heads (H) or tails (T). A move consists of flipping k consecutive coins. The goal is to reach the all-heads state. F(n, k) = the number of initia...
Range of Periodic Sequence
Consider the recurrence a_(n+1) = a_n - (1)/(a_n) for n >= 0. Certain starting values a_0 produce periodic sequences. The range of a periodic sequence is the difference between its maximum and mini...
Shifted Pythagorean Triples
For non-negative integer k, a triple (p, q, r) of positive integers is a k -shifted Pythagorean triple if p^2 + q^2 + k = r^2. It is primitive if gcd(p, q, r) = 1. Let P_k(n) count primitive k -shi...
A Stoneham Number
Define the Stoneham number: A = sum_(i=1)^infinity frac13^i * 10^(3^i). Let A(n) denote the 10 decimal digits starting from position n in the decimal expansion of A. Given: A(100) = 4938271604, A(1...
Standing on the Shoulders of Trolls
N trolls are trapped in a hole of depth D_N cm. Each troll n (0 <= n < N) has shoulder height h_n, arm length l_n, and IQ (Irascibility Quotient) q_n, generated by: r_n = [(5^n mod (10^9+7)) mod 10...
Ascending Subsequences
Define a_i = 153^i mod 10,000,019 for i >= 1. An ascending subsequence of length 4 within the first n terms is a tuple (a_(i_1), a_(i_2), a_(i_3), a_(i_4)) with i_1 < i_2 < i_3 < i_4 and a_(i_1) <...
A Bit of Prime
The bitwise-OR of integers performs logical OR on each pair of binary digits. Define T(n, k) as the number of k -tuples (x_1, x_2,..., x_k) where: Each x_i is prime and <= n x_1 mathbin| x_2 mathbi...
Divisors of 2n^2
Let f(n) be the number of divisors of 2n^2 that are no greater than n. For example, f(15) = 8 because the divisors of 2 * 15^2 = 450 that do not exceed 15 are: 1, 2, 3, 5, 6, 9, 10, 15. Define F(N)...
Paths to Equality
Two functions on lattice points: r(x,y) = (x+1, 2y) and s(x,y) = (2x, y+1). A path to equality of length n from (a,b) is a sequence starting at (a,b), applying r or s at each step, such that interm...
Coin Loops
Identical coins are stacked on a flat table around a perpendicular line. Each coin is placed horizontally atop the previous one while maintaining balance and contact with the line. When the n -th c...
Counting Ordered Factorisations
Let d(n, k) be the number of ways to write n as a product of k ordered integers: n = x_1 * x_2... x_k with 1 <= x_1 <= x_2 <=... <= x_k. Define D(N, K) = sum_(n=1)^N sum_(k=1)^K d(n, k). Given: D(1...
Summation of Summations
Take a sequence of length n. Discard the first term then make a sequence of the partial sums. Continue to do this over and over until we are left with a single term. We define this resulting value...
Secret Santa
In this Secret Santa variant, n people each write their name on two slips, creating 2n slips in a hat. Each person draws two slips, ensuring they don't draw their own name. The process fails if the...
Binary Grid Colouring
Let f(n) be the number of ways to colour an n x n binary grid such that each row and each column contains exactly two black cells. Let g(n) count such colourings up to the symmetries of the square...
Minimum Area Ellipse
A symmetrical convex grid polygon is a convex polygon whose vertices all have integer coordinates, all internal angles are strictly less than 180°, and it has both horizontal and vertical symmetry....
Window into a Matrix
Consider a 2 x n binary matrix where every 2 x k contiguous submatrix (window) has entry sum exactly k. Let A(k, n) count the number of such matrices. Given: A(3, 9) = 560, A(4, 20) = 1,060,870. Fi...
What? Where? When?
In a game show, there are 2n + 1 envelopes arranged in a circle: 2n contain questions and 1 contains a RED card. The envelopes are opened one by one in clockwise order, starting from a random posit...
Sum of Squares II
For a positive integer n, define g(n) to be the maximum perfect square that divides n. For example, g(18) = 9, g(19) = 1. Define S(N) = sum_(n=1)^N g(n). Given: S(10) = 24, S(100) = 767. Find S(10^...
A Messy Dinner
There are n families, each consisting of a father, mother, son, and daughter (4 people). They are seated at a circular table with 4n seats, alternating by gender (male-female-male-female-...). Let...
Triangular Pizza
Mamma Triangolo bakes a triangular pizza and cuts it into n equal-area triangular pieces by choosing an interior point P and making n straight cuts from P to the boundary of the triangle. Let psi(n...
Upside Down Diophantine
Find primitive solutions to (1)/(x^2) + (1)/(y^2) = (13)/(z^2) with gcd(x, y, z) = 1 and x <= y. Define S(N) = sum (x + y + z) over all such primitive solutions with 1 <= x, y, z <= N. Given: S(100...
Near Power Sums
A positive integer n is a near power sum if there exists a positive integer k such that the sum of the k -th powers of the digits of n equals either n + 1 or n - 1. Define S(d) as the sum of all ne...
Optimal Card Stacking
A deck of N cards labeled 1 to N is placed at positions defined by p(n) = 3^n mod (N + 1) for n = 1, 2,..., N. Card n starts at position p(n). We must merge the cards into a single ordered stack (c...
Concatenation Coincidence
A non-decreasing sequence of positive integers a_1, a_2, a_3,... is derived from a real number theta by the recurrence: b_1 = theta, b_n = floor(b_(n-1)) * (b_(n-1) - floor(b_(n-1)) + 1) for n >= 2...
Powers of $1 + \sqrt{7}$
Define alpha(n) and beta(n) by (1 + sqrt(7))^n = alpha(n) + beta(n)sqrt(7). Let g(x) be the smallest positive integer n such that alpha(n) equiv 1 (mod x) and beta(n) equiv 0 (mod x). Define G(N) =...
Fermat Quotients
For prime p, F(p) counts solutions to a^3+b^3equiv c^3 (mod p) with 1<= a,b,c<p. Given F(5)=12, F(7)=0. Find sum F(p) for primes p < 6x 10^6.
Product of Gauss Factorials
Gauss factorial: g(n) = prod_1<= k<= n, gcd(k,n)=1 k. G(n) = prod_i=1^n g(i). Given G(10)=23044331520000. Find G(10^8) mod 10^9+7.
Not Zeckendorf
f(n) = number of representations of n as sum of distinct Fibonacci numbers (allowing consecutive). S(n) = sum_k=0^n f(k). Given S(100)=415, S(10^4)=312807. Find S(10^13).
Approximating a Sum
Approximate S = sum_k=1^n f(k) using m random samples. E(Delta|f,n,m) = expected error. Find E(Delta|phi(k), 12345678, 12345) to 6 d.p.
Stealthy Numbers
A positive integer N is stealthy if there exist positive integers a, b, c, d such that a b = c d = N and a + b = c + d + 1. For example, 36 = 4 x 9 = 6 x 6 is stealthy since 4 + 9 = 13 = 6 + 6 + 1....
Buckets of Water
Three buckets: capacities a, b, a+b. Start: S= a, M= b, L=empty. Pour between buckets. P(a,b) = min pours to measure 1 liter. Find sum P(2^p^5-1, 2^q^5-1) for primes p<q<1000, mod 10^9+7.
A Squared Recurrence
f(1)=1, f(2n)=2f(n), f(2n+1)=2n+1+2f(n)+f(n)/n. S(n)=sum f(i)^2. Given S(10)=1530, S(100)=4798445. Find S(10^16) mod 10^9+7.
Problem 760
Problem 760
Runner and Swimmer
A student is swimming in a pool while a teacher runs around the perimeter trying to apprehend the student. The student's swimming speed is slower than the teacher's running speed by a factor of v....
Amoeba Colonies
Amoeba at (0,0) in 4-row infinite grid. Division: (x,y)-> (x+1,y) and (x+1,(y+1)mod 4) if empty. C(N) = distinct arrangements after N divisions. Find last 9 digits of C(100000).
Amoeba Colonies 3D
An amoeba at (0,0,0) divides into 3 offspring at (x+1,y,z), (x,y+1,z), (x,y,z+1) if those cells are empty. After N divisions, 2N+1 amoebas exist. Different division orders may give same arrangement...
Asymmetric Diophantine Equation
Find primitive solutions to 16x^2 + y^4 = z^2 with gcd(x,y,z) = 1. Compute S(N) = sum(x+y+z) over all solutions with 1 <= x,y,z <= N. Given S(10^2) = 81, S(10^4) = 112851, S(10^7) equiv 248876211 (...
Trillionaire
Start with 1g gold, 1000 rounds. Each round bet b<= x at 60/40 odds. Maximize probability of reaching 10^12 g. Find optimal probability to 10 d.p.
Sliding Block Puzzle
A sliding block puzzle is a puzzle where pieces are confined to a grid and by sliding the pieces a final configuration is reached. Pieces can only be slid in multiples of one unit in the directions...
Window into a Matrix II
Consider a 16 x n matrix with binary entries (0s and 1s). Define B(k, n) as the total number of these matrices such that the sum of the entries in every 2 x k window is exactly k. Given: B(2, 4) =...
Chandelier
A chandelier has a circular ring of n evenly spaced candleholders. We place m identical candles into some of these holders such that the chandelier remains perfectly balanced (center of gravity at...
Binary Quadratic Form
The binary quadratic form f(x,y) = x^2 + 5xy + 3y^2 with discriminant Delta = 25-12 = 13. A positive integer z has a primitive representation as z^2 = f(x,y) with gcd(x,y)=1, x,y > 0. C(N) counts a...
Delphi Flip
A starts with 1g gold. Each round, A picks x, B takes or gives x. n takes and n gives total. g(X) = smallest n for A to guarantee X grams. g(1.7)=10. Find g(1.9999).
Pseudo Geometric Sequences
A pseudo geometric sequence is a strictly increasing sequence of positive integers a_0 < a_1 <... < a_n with n >= 4 such that for every interior index 1 <= i <= n-1, |a_i^2 - a_(i-1) a_(i+1)| <= 2....
Balanceable $k$-bounded Partitions
A k -bounded partition of a positive integer N is a partition of N into parts each of size at most k. A partition is balanceable if its parts can be divided into two groups with equal sum (hence N...
Ruff Numbers
Let S_k = {2, 5} union {p_1, p_2,..., p_k} where p_1 < p_2 <... are the primes whose decimal representation ends in the digit 7 (i.e., p_1 = 7, p_2 = 17, p_3 = 37,...). A positive integer m is call...
Conjunctive Sequences
A sequence (x_1, x_2,..., x_n) of non-negative integers is called conjunctive if for every consecutive pair, x_i mathbin& x_(i+1) ne 0 (where & denotes bitwise AND). Let c(n, b) denote the number o...
Saving Paper
When wrapping n unit cubes individually, each cube requires 6 square units of paper (surface area of a unit cube). Alternatively, one can arrange the cubes into a rectangular box of dimensions a x...
Digit Sum Division
For a positive integer n, let d(n) be the sum of its decimal digits. Define F(N)=sum_(n=1)^N(n)/(d(n)). The given checks are: F(10)=19, F(123)approx 1.187764610390mathrm e3, F(12345)approx 4.855801...
Lissajous Curves
For coprime positive integers a and b, define the curve x=cos(at), y=cos (b(t-(pi)/(10))), 0 <= t <= 2pi. Let d(a,b) be the sum of x^2+y^2 over all self-intersection points of the curve, and let s(...
Problem 778
Problem 778
Problem 779
Problem 779
Problem 780
Problem 780
Feynman Path Integral
Consider a lattice path on Z^2 from (0,0) to (n,n) using steps (1,0) and (0,1). Define the area under a path as the number of unit squares below it. Let Z(n) = sum_(gamma) e^(ipi * area(gamma) / n^...
Distinct Rows and Columns
A binary matrix is distinct if all rows are different and all columns are different. Let D(n,m) be the number of distinct n x m binary matrices. Find sum_(m=1)^20 D(20, m) modulo 1,000,000,007.
Problem 783
Problem 783
Problem 784
Problem 784
Problem 785
Problem 785
Billiard
A billiard table is a quadrilateral with angles 120°, 90°, 60°, 90° at vertices A, B, C, D respectively, with AB = AD. A ball departs from A, bounces elastically off edges (never at corners), and r...
Bezout's Game
Two stone piles of coprime sizes (a, b). A player removes (c, d) stones with |ad - bc| = 1. First to empty a pile wins. Position (a,b) is winning if the next player can force a victory. H(N) counts...
Dominating Numbers
A positive integer with exactly n digits is called dominating if some digit appears more than n/2 times. Let D(N) be the number of dominating positive integers with at most N digits. Compute D(2022...
Minimal Pairing Modulo p
Pair numbers 1..p-1 (p prime) into (p-1)/2 pairs. Cost of pair (a,b) = ab mod p. Find optimal pairing minimizing total cost, then report cost product for p=2000000011.
Clock Grid
A 50515093 x 50515093 grid of 12-hour clocks, all starting at 12. Pseudorandom sequence S_0=290797, S_(t+1) = S_t^2 mod 50515093. Every 4 terms define a rectangle; all clocks in the rectangle advan...
Average and Variance
Find ordered quadruples (a,b,c,d) with 1 <= a <= b <= c <= d <= n where the arithmetic mean equals twice the variance. Define S(n) = sum (a+b+c+d) over all qualifying quadruples. Given S(5) = 48 an...
Too Many Twos
Define S(n) = sum_(k=1)^n (-2)^k C(2k, k). Let u(n) = v_2(3S(n) + 4) where v_2 denotes the 2-adic valuation. Define U(N) = sum_(n=1)^N u(n^3). Given u(4) = 7 (since 3S(4) + 4 = 2944 = 2^7 * 23) and...
Median of Products
Pseudorandom S_0=290797, S_(i+1)=S_i^2 mod 50515093. M(n) = median of all pairwise products S_iS_j for 0 <= i < j < n. Given M(3) = 3878983057768, M(103) = 492700616748525. Find M(1000003).
Seventeen Points
Choose real numbers x_1,..., x_n in [0,1) sequentially such that after step n, each subinterval [(k-1)/n, k/n) for k=1,...,n contains exactly one chosen number. F(n) = minimum sum x_1+...+x_n. Give...
Alternating GCD Sum
g(n) = sum_(i=1)^n (-1)^i gcd(n, i^2). G(N) = sum_(n=1)^N g(n). Given g(1234)=1233, G(1234)=2194708. Find G(12345678).
A Grand Shuffle
10 decks of 54 cards each (52 ranked + 2 jokers), total 540 cards. Draw without replacement. Find expected draws to get at least one card from every suit (4), every rank (13), and every deck design...
Cyclogenic Polynomials
A monic polynomial p(x) is n -cyclogenic if p(x)q(x) = x^n - 1 for some monic q(x) in Z[x], with n minimal. P_n(x) = sum of all n -cyclogenic polynomials. Q_N(x) = sum_(n=1)^N P_n(x). Given Q_10(2)...
Card Stacking Game
s suits, cards numbered 1 to n per suit. Some cards visible on table. Players place card X on visible card Y (same suit, X > Y). First unable to move loses. C(n,s) = number of initial visible confi...
Problem 799
Problem 799
Hybrid Integers
An integer of the form p^q q^p with prime numbers p!= q is called a hybrid-integer. For example, 800 = 2^5 * 5^2 is a hybrid-integer. We define C(n) to be the number of hybrid-integers less than or...
$x^y \equiv y^x \pmod{p}$
For a prime p, define f(p) = sum_(1 <= x < y < p, x^y equiv y^x (mod p)) (x + y). Compute sum_(p <= 10^6, p prime) f(p) (mod 10^9 + 7).
Iterated Composition
Let f(x) = x^2 - x + 1. Define f_1(x) = f(x) and f_(n+1)(x) = f(f_n(x)). Let g(n) be the number of real solutions to f_n(x) = x. Find sum_(n=1)^30 g(n).
Pseudorandom Sequence
Rand48 PRNG: a_n = (25214903917 a_(n-1) + 11) mod 2^48. Extract character: b_n = floor(a_n/2^16) mod 52 mapped to a-zA-Z. Given starting string 'PuzzleOne...', find position of 'LuckyText'.
Counting Binary Quadratic Representations
g(n) = number of integer solutions to x^2+xy+41y^2 = n. T(N) = sum_(n=1)^N g(n). Given T(10^3)=474, T(10^6)=492128. Find T(10^16).
Shifted Multiples
For a positive integer n with leading digit d_1 and remaining digits forming number m, define shift(n) = 10m + d_1 (cyclic left shift of digits). Let r(n) = n mod shift(n). Find S(N) = sum_(n=1)^N...
Problem 806
Problem 806
Loops of Ropes
Consider n ropes with 2n ends randomly paired. Let E(n) be the expected number of loops. Find floor(E(10^6)).
Reversible Prime Squares
Both 169 and 961 are the square of a prime. 169 is the reverse of 961. A number is called a reversible prime square if: 1. It is not a palindrome. 2. It is the square of a prime. 3. Its digit-rever...
Rational Recurrence
f(x): if x integer, f(x)=x; if x<1, f(x)=f(1/(1-x)); else f(x)=f(1/(ceil(x) - x) - 1 + f(x-1)). Given f(3/2)=3, f(1/6)=65533, f(13/10)=7625597484985. Find f(22/7) mod 10^15.
XOR-Primes
Define XOR-multiplication x via polynomial multiplication over GF(2). A number n > 1 is XOR-prime if it cannot be written as a x b with a,b > 1. Find the sum of all XOR-primes up to 5 x 10^6.
Bitwise Recursion
Define the function f:N_0 x N_0 -> N_0 by: f(n, k) = n & if k = 0, f(n + k, floor(k/2)) & if k > 0, where + denotes bitwise XOR. Let S(N) = sum_(k=0)^N sum_(n=0)^N f(n, k). Find S(10^18) mod (10^9...
Dynamical Polynomials
Let p be a prime and f(x) = x^2 + c for c in F_p. Define f^n as the n -th iterate of f. A point x in F_p is a periodic point of period n if f^n(x) = x and n is the minimal such positive integer. Le...
XOR Power
Define the XOR-product n x m as the "carryless multiplication" of n and m in base 2, i.e., polynomial multiplication in GF(2)[x] where n and m are interpreted as polynomials via their binary repres...
Seating Plan
At a circular table with n seats, n people must be seated so that no two people who are "enemies" sit adjacent. The enemy relation is defined by a specific constraint (e.g., people with consecutive...
Random Digit Sum
Choose k digits independently and uniformly at random from {0, 1,..., 9}. Let S be their sum. We seek to compute E[S^2] or the probability P(S = s) for specific parameters, or a related quantity in...
Shortest Distance Among Points
A sequence of points is defined using a pseudo-random number generator: s_0 = 290797 s_(n+1) = s_n^2 mod 50515093 P_n = (s_2n, s_(2n+1)) Let d(k) be the shortest Euclidean distance between any two...
Digits in Squares
Let f(n) count how many perfect squares m^2 have the property that n appears as a substring of the decimal digits of m^2. Alternatively, study digit patterns in n^2 mod 10^k. We consider the quadra...
SET (Triple Counting)
In the card game SET, each card has d attributes, each taking one of 3 values. A SET is a triple of cards (a, b, c) such that for each attribute, the three values are either all the same or all dif...
Iterative Sampling
Consider a random process on the set {1, 2,..., n}. At each step, we sample an element uniformly at random (with replacement). Let T be the number of steps until some stopping condition is met (e.g...
Nth Digit of Reciprocals
Let d_n(x) be the n -th decimal digit of the fractional part of x (or 0 if the fractional part has fewer than n digits). Examples: d_7(1/3) = 3 since 1/3 = 0.3333333333... d_7(1/6) = 6 since 1/6 =...
123-Separable
A positive integer n is called 123-separable if its decimal digit string can be partitioned into contiguous substrings whose numeric values satisfy a prescribed cyclic divisibility pattern by 1, 2,...
Square the Smallest
Start with the list [2,3,4,...,10000]. At each step, replace the smallest element by its square. If several elements are tied for the minimum, choosing any one of them gives the same multiset after...
Factor Shuffle
Define the factor shuffle operation: given n = p_1^(a_1) p_2^(a_2)... p_r^(a_r) with primes p_1 < p_2 <... < p_r, rearrange the exponents to produce sort(n) = p_1^a_(sigma(1)) p_2^a_(sigma(2))... p...
Antichain Counting
Consider the divisibility poset on {1, 2,..., n}, where a preceq b iff a | b. An antichain is a subset A such that no element divides another: for all a, b in A with a ne b, a nmid b and b nmid a....
Taxicab Variations
A taxicab number Ta(k) is the smallest number expressible as the sum of two positive cubes in k or more distinct ways. The famous Hardy-Ramanujan number is Ta(2) = 1729 = 1^3 + 12^3 = 9^3 + 10^3. G...
Birds on a Wire
Consider a wire of length 1 unit between two posts. Every morning n birds land on it randomly with every point on the wire equally likely to host a bird. The interval from each bird to its closest...
Gaussian Primes
A Gaussian integer is a complex number z = a + bi where a, b in Z. The norm is N(z) = a^2 + b^2. A Gaussian prime is a Gaussian integer whose only divisors are units (+/- 1, +/- i) and associates....
Numbers Challenge
Given a set of n numbers {a_1, a_2,..., a_n} and a target T, find a subset S whose elements combine (using +, -, x, /) to produce T, minimizing |S|. If multiple subsets of the same size work, choos...
Integral Remainders
Compute the sum of all remainders: R(n) = sum_(k=1)^n (n mod k) or a related quantity for large n, modulo 10^9+7.
Summing a Multiplicative Function
Let d(n) denote the number of decimal digits of n!, i.e., d(n) = floor(log_10(n!)) + 1, with the convention d(0) = d(1) = 1. Define the multiplicative function f(n) = prod_(p^a \| n) d(p^a) where t...
Triple Product
Given integer vectors a, b, c in Z^3, the scalar triple product is a * (b x c) = det[a|b|c]. This equals the signed volume of the parallelepiped spanned by the three vectors. Compute a sum or count...
Mex Sequence
The mex (minimum excludant) of a set S subseteq N_0 is the smallest non-negative integer not in S: mex(S) = min(N_0 setminus S). Define a sequence using mex operations and compute a sum or specific...
Square Triangular Numbers
A square triangular number is a positive integer that is both a perfect square and a triangular number. The k -th triangular number is T_n = n(n+1)/2, and a perfect square is m^2. We seek all n, m...
Sum of Concatenations
Define the concatenation n \| m as the number formed by writing n followed by m in decimal. For example, 12 \| 34 = 1234. Compute: S(N) = sum_(n=1)^N sum_(m=1)^N (n \| m) (mod 10^9+7).
Supernatural Triangles
A Heronian triangle is a triangle with integer sides and integer area. A supernatural triangle is a Heronian triangle satisfying additional structural constraints. Count or sum supernatural triangl...
A Bold Proposition
Let A be an affine plane over a radically integral local field F with residual characteristic p. We consider an open oriented line section U of A with normalized Haar measure m. Define f(m, p) as t...
Amidakuji
Amidakuji is a method for producing a random permutation using parallel vertical lines and horizontal rungs between adjacent lines. For three objects A, B, C, let a(m, n) count distinct Amidakujis...
Not Coprime
For a positive integer N, define C(N) as the number of pairs (a, b) with 1 <= a <= b <= N such that gcd(a, b) > 1 (i.e., a and b are not coprime). Compute C(10^7).
Beans in Bowls
Count the number of solutions to x_1 + x_2 +... + x_k = n with 0 <= x_i <= m for all i. Denote this B(n, k, m). Compute the answer modulo a prime p.
Sum of Products
Given a sequence {x_1, x_2,..., x_n} of positive integers, the k -th elementary symmetric polynomial is: e_k(x_1,..., x_n) = sum_(1 <= i_1 < i_2 <... < i_k <= n) x_(i_1) x_(i_2)... x_(i_k). Compute...
Regular Star Polygons
A regular star polygon {n/k} is formed by connecting every k -th point out of n equally spaced points on a circle of radius r. The star polygon is valid when 1 < k < n/2 and gcd(n, k) = 1. Compute...
Irregular Clocking
A Linear Congruential Generator (LCG) produces a sequence {x_n} via: x_(n+1) = (a * x_n + c) mod m Given parameters (a, c, m, x_0), determine the period rho, tail length tau, and values at large in...
Periodic Tilings
Count the number of ways to tile an m x n rectangular grid with dominoes (1 x 2 or 2 x 1 tiles). Denote this count by T(m, n). Compute T(m, n) for given dimensions, potentially modulo a prime.
k-Markov Sequences
A k -Markov sequence over an alphabet Sigma of size |Sigma| = sigma is a sequence where the probability of each symbol depends only on the preceding k symbols. Count the number of k -Markov sequenc...
Prime Pairs
A twin prime pair is a pair of primes (p, p+2). More generally, a prime pair with gap g is (p, p+g) where both are prime. Compute pi_2(N) = |{p <= N: p and p+2 are both prime}| for a given bound N.
Magic Bracelets
A bracelet is made by connecting at least three numbered beads in a circle. Each bead can display either 1, 2, or a number of the form p^k or 2p^k where p is an odd prime. A bracelet is called "mag...
Jack's Bean
Jack faces three plates containing beans. One bean is magical, and Jack must identify it through yes/no questions about whether subsets contain the magic bean. For plates with a, b, and c beans res...
Fraction Field
A continued fraction [a_0; a_1, a_2,..., a_n] represents the rational number: [a_0; a_1,..., a_n] = a_0 + cfrac1a_1 + cfrac1a_2 + cfrac1ddots + cfrac1a_n Given a rational number p/q, compute its co...
The Locked Box
Consider n locked boxes, each requiring a specific key. You have m available keys, and each key opens a specific subset of boxes. Determine the minimum number of keys needed to open all n boxes, or...
Frieze Patterns
A Conway-Coxeter frieze pattern of order n is an array of positive integers arranged in rows, where the top and bottom rows are all 1s, and every adjacent 2 x 2 submatrix a&b c&d satisfies the unim...
SOP and POS
A Boolean function f: {0,1}^n -> {0,1} can be represented in Sum of Products (SOP, or DNF) form: f = bigvee_i bigwedge_j l_ij where each l_ij is a literal (x_k or overlinex_k). The minimal SOP repr...
Coin Flipping Game
In a coin flipping game, a player starts with fortune k and plays until reaching 0 (ruin) or N (goal). At each step, the fortune increases by 1 with probability p and decreases by 1 with probabilit...
Pisano Periods
The Pisano period pi(m) is the period of the Fibonacci sequence modulo m: F_n mod m Compute sum_(m=2)^N pi(m) for a given bound N.
Dividing the Cake
Divide a cake (interval [0,1]) among n players, each with a valuation function v_i: [0,1] -> R_(>= 0) satisfying int_0^1 v_i(x) dx = 1. Find an envy-free allocation: a partition into n pieces where...
Power Sequence
Tetration (iterated exponentiation) is defined recursively: ^0 a = 1 and ^(n+1) a = a^^n a. Compute ^n a mod m for given a, n, m.
Waiting for a Pair
A standard 52-card deck contains 13 ranks across four suits. Cards are drawn without replacement from a shuffled deck until either two consecutive draws form a pair (same rank) or all 52 cards are...
Beautiful Graphs
A graph on n labeled vertices has the following edge types between any two distinct vertices: A red directed edge in one direction and a blue directed edge in the opposite direction, OR A green und...
Count Mates
This problem involves chess endgame checkmate counting. The central quantity is: sum_pos [checkmate]
Nimber Reciprocals
This problem involves nimber field arithmetic over F_(2^(2^n)). The central quantity is: a x a^(-1) = 1
Fermat Pseudoprimes
This problem involves Carmichael number enumeration. The central quantity is: a^(n-1) equiv 1 (mod n)
Divisor Nimbers
This problem involves XOR of divisor function bigoplus_(d|n) d. The central quantity is: bigoplus_(d|n) d
Digital Root Clocks
This problem involves digital root dr(n) = 1 + (n-1) mod 9. The central quantity is: dr(n) = 1 + (n-1) mod 9
Permutation Orbits
This problem involves cycle index Z(S_n) and orbit counting. The central quantity is: Z(S_n) = (1)/(n!)sum_(sigma)p_1^(c_1)... p_n^(c_n)
Matrix Trace Powers
This problem involves trace of matrix powers tr(A^n). The central quantity is: tr(A^n) = sum lambda_i^n
Consecutive Prime Sums
This problem involves primes as sums of consecutive primes. The central quantity is: p = p_a + p_(a+1) +... + p_b
Tidying Up B
A small child has a "number caterpillar" consisting of N jigsaw pieces, each with one number on it, which, when connected together in a line, reveal the numbers 1 to N in order. Every night, the ch...
Tiling Dodecagon
There are 5 ways to tile a regular dodecagon (12-sided polygon) of side length 1 with regular polygons of side length 1. Let T(n) be the number of ways to tile a regular dodecagon of side length n...
Quad-Free Words
A word w over an alphabet Sigma_k = {0, 1,..., k-1} is quad-free (avoids 4th powers) if it contains no factor of the form xxxx where x is a nonempty string. Count q(n, k) = |{w in Sigma_k^n: w is q...
Prime Guessing
This problem involves information-theoretic prime identification. The central quantity is: H = ceil(log_2 pi(N))
Balanced Sculptures
This problem involves polyomino enumeration with balance constraints. The central quantity is: B(n) = |{P: |P|=n, P balanced}|
Drifting Digits
Consider the reverse-and-add process: given a positive integer n, compute n + rev(n) where rev(n) denotes the integer obtained by reversing the base-10 digits of n. Iterate until a palindrome is re...
Recursive Bracelets
This problem concerns the enumeration of equivalence classes of bead colorings on a cycle under the action of the dihedral group, i.e., counting bracelets. The central formula is the necklace count...
Forbidden Subgraphs
This problem concerns Turan-type extremal graph theory: determining the maximum number of edges in a graph on n vertices that avoids a specified complete subgraph K_r. The extremal number is ex(n,...
Maximal Coprime Subsets
Given a set {1, 2,..., N}, find the maximum-size subset S such that every pair of distinct elements is coprime: max |S| subject to gcd(a, b) = 1 forall a!= b in S. The problem asks for a specific q...
Quadratic Residue Sequences
This problem involves patterns in the Legendre symbol sequence and character sums over finite fields. The central object is: ((n)/(p)) = n^((p-1)/2) mod p, the Legendre symbol, which encodes whethe...
Triplet Tricks
Beginning with three numbers a, b, c, at each step one may perform one of three operations: Replace a with 2(b + c) - a Replace b with 2(c + a) - b Replace c with 2(a + b) - c Define f(a, b, c) as...
XOR-Equation A
The XOR-product of x and y, denoted x x y, is carry-less multiplication in base 2 (equivalently, polynomial multiplication over GF(2)). For example, 7 x 3 = 9 since 111_2 x 11_2 = 1001_2. Consider...
XOR-Equation B
Using the same XOR-product x (carry-less multiplication in base 2) as Problem 877, consider the equation: (a x a) + (2 x a x b) + (b x b) = k. Define G(N, m) as the number of solutions (a, b, k) sa...
Touch-screen Password
A touch-screen password consists of a sequence of two or more distinct spots on a rectangular grid, subject to the following rules: 1. The user touches the first spot, then traces straight-line seg...
Cyclic Polyhedra
A cyclic polyhedron has all vertices on a sphere. This problem studies the enumeration of combinatorially distinct convex polyhedra on n vertices, governed by Euler's polyhedral formula and Steinit...
Divisor Graph Coloring
Define the divisibility graph G_n on vertex set {1, 2,..., n} where i and j are connected by an edge if one divides the other (and i!= j). Determine the chromatic number chi(G_n).
Matchstick Equations
Each digit 0-9 can be formed using matchsticks with the following costs: | Digit | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| | Cost | 6 | 2 | 5 | 5 | 4 |...
Remarkable Representations
For a finite group G, a representation is a homomorphism rho: G -> GL(V) for some vector space V. The dimension dim rho = dim V. The fundamental theorem of representation theory relates dimensions...
Lattice Walks with Barriers
Count the number of lattice paths from (0,0) to (m,n) using unit steps right (1,0) and up (0,1), subject to barrier constraints (e.g., the path must not cross certain lines). The solution uses the...
Modular Fibonacci Products
The Fibonacci sequence F_1 = 1, F_2 = 1, F_(n+2) = F_(n+1) + F_n. Compute: P(n, m) = prod_(k=1)^n F_k mod m for large n using the Pisano period (periodicity of Fibonacci mod m).
Coprime Permutations
A permutation sigma of {1, 2,..., n} is called coprime if gcd(i, sigma(i)) = 1 for all i in {1, 2,..., n}. Let P(n) be the number of coprime permutations of {1, 2,..., n}. For example, P(4) = 2 as...
Chained Radicals
Define the infinite nested radical for a >= 0: R(a) = sqrta + sqrta + sqrt(a +...) Determine R(a) in closed form and study variants with different nested radical chains.
Multidimensional Sieve
The Mobius function mu(n) and Mobius inversion extend to multiple dimensions. Given an arithmetic function f(n_1,..., n_k), compute its Mobius inversion efficiently.
Reversal Sort
A prefix reversal of a permutation pi reverses the first k elements. The pancake number P(n) is the maximum over all permutations of S_n of the minimum number of prefix reversals needed to sort. De...
Birthday Paradox Variants
In the classical birthday problem, n people each have a birthday uniformly distributed among N days. The probability that at least two share a birthday is: P(n, N) = 1 - prod_(k=0)^(n-1)(1 - (k)/(N...
Pentagon Tilings
Study the enumeration of pentagonal tilings via Euler's pentagonal number theorem. The generalized pentagonal numbers omega_k = k(3k-1)/2 for k in Z govern the expansion of the Euler function prod_...
Recursive Digit Factorial
Define f(n) = sum_(d in digits(n)) d! for any positive integer n. A factorion is a number n satisfying f(n) = n. Determine all factorions in base 10 and characterize the cycle structure of the func...
Steiner Systems
A Steiner system S(t, k, v) is a collection of k -element subsets (called blocks) of a v -element set V such that every t -element subset of V is contained in exactly one block. Determine necessary...
Summation of Summations
Define the m -fold iterated partial sum of a sequence (a_1, a_2,..., a_n) by S^((m))_n = sum_(i_1=1)^n sum_(i_2=1)^(i_1)... sum_(i_m=1)^i_(m-1) a_(i_m). Find a closed-form expression for S^((m))_n...
Arithmetic Derivative
The arithmetic derivative n' is defined on nonneg integers by: 1. 0' = 0, 1' = 0. 2. p' = 1 for every prime p. 3. (ab)' = a'b + ab' (Leibniz product rule). Compute sum_(n=1)^N n' and study the stru...
Divisible Ranges
A contiguous range of positive integers is called a divisible range if all the integers in the range can be arranged in a row such that the n-th term is a multiple of n. For example, the range [6.....
Base-b Palindromes
A number n is a palindrome in base b if its base- b representation reads the same forwards and backwards. Let P_b(N) count the number of positive integers <= N that are palindromic in base b. Given...
Product Partition Function
A multiplicative partition (or factorization) of n is a way to write n as an ordered or unordered product of integers greater than 1. Let f(n) denote the number of unordered multiplicative partitio...
Tree Enumeration
The number of labeled trees on n vertices is given by Cayley's formula: t(n) = n^(n-2). We study this formula, its proofs, and efficient computation. Given N, compute sum_(n=2)^N n^(n-2) mod p.
Sum of Remainders
Define S(n) as the sum of all remainders when n is divided by each positive integer up to n: S(n) = sum_(k=1)^n (n mod k) = sum_(k=1)^n (n - kfloor((n)/(k))) Compute S(N) for large N efficiently.
Digital Root Patterns
Let d(n) denote the digital root of n (the single digit obtained by repeatedly summing digits). Define S(N) = sum_(k=1)^N k * d(k). Find S(10^6) mod 10^9+7.
Permutation Cycles
Let C(n) be the number of permutations of {1,2,...,n} whose longest cycle has length exactly floor(n/2). Find C(20) mod 10^9+7. Since floor(20/2) = 10, we seek permutations of 20 elements whose max...
Matrix Permanent Modulo a Prime
Let A be the n x n matrix with A_ij = (i * j) mod n, where i, j in {1, 2,..., n}. Find perm(A) mod 10^9+7 for n = 12.
Integer Partition Asymptotics
Let p(n) denote the number of integer partitions of n. Find p(200) mod 10^9+7. A partition of n is a multiset of positive integers summing to n. For example, p(5) = 7: the partitions are 5, 4+1, 3+...
Lattice Point Visibility
A lattice point (a,b) with 1 <= a, b <= N is visible from the origin if gcd(a,b) = 1. Let V(N) be the count of visible points. Find V(10^6) mod 10^9+7.
Fibonacci Modular Properties
Let F_n denote the n -th Fibonacci number with F_1 = F_2 = 1. Find sum_(k=1)^(10^7) F_k mod 10^9+7.
Minimum Path Sum in Triangle
Given a triangle of N = 1000 rows where row i (0-indexed) has entry T(i,j) = ((i+1)(j+1) * 37 + 13) mod 100 for 0 <= j <= i, find the minimum path sum from top to bottom, where each step goes to an...
Coprime Chains
A coprime chain of length k is a strictly increasing sequence a_1 < a_2 <... < a_k where gcd(a_i, a_(i+1)) = 1 for all consecutive pairs, with all a_i in {2, 3,..., 100}. Find the length of the lon...
Random Walk Return Probability
In a symmetric random walk on Z, starting at 0, each step goes +1 or -1 with equal probability 1/2. Let R(2n) be the probability of being at position 0 after exactly 2n steps. Find R(20) as a reduc...
Prime Constellation Counting
A twin prime pair is (p, p+2) where both p and p+2 are prime. Find the number of twin prime pairs with p < 10^7.
Geometric Series Truncation
Let S(r, n) = sum_(k=0)^n r^k for integer r >= 2. Find sum_(r=2)^100 S(r, r) mod (10^9+7).
Polynomial Roots over Finite Fields
Let p = 997 (a prime). For the polynomial f(x) = x^3 + 2x + 1 over F_p, find the number of roots, i.e., |{x in F_p: f(x) equiv 0 (mod p)}|.
Balanced Ternary Representation
In balanced ternary, digits are {-1, 0, 1} (written as T, 0, 1). Every integer has a unique balanced ternary representation. Find the sum of all positive integers n <= 10^6 whose balanced ternary r...
Convex Lattice Polygons
Let P(A) be the number of convex lattice polygons (vertices at integer coordinates) with area exactly A that contain the origin in their interior. Find P(10).
Digit Power Sum Sequences
Define f(n) = sum_(d in digits(n)) d^5. Starting from any n, the sequence n, f(n), f(f(n)),... eventually enters a cycle. Find the sum of all starting values n <= 10^6 that eventually reach 1.
Graph Isomorphism Counting
Find the number of non-isomorphic simple graphs on 7 vertices.
Modular Square Roots
For a prime p = 10^9 + 7, find the number of quadratic residues modulo p in the range [1, p-1].
Farey Sequence Properties
The Farey sequence F_n consists of all reduced fractions a/b with 0 <= a <= b <= n, arranged in ascending order. Find |F_1000|, the number of terms in F_1000.
Multiplicative Persistence
The multiplicative persistence of n is the number of times you must multiply the digits of n until reaching a single digit. Find the sum of all n < 10^7 with multiplicative persistence exactly 4.
Stern-Brocot Mediant
In the Stern-Brocot tree, the mediant of a/b and c/d is (a+c)/(b+d). Starting from 0/1 and 1/0, find the depth at which 355/113 first appears.
Divisor Chain Lengths
A divisor chain starting from n is a sequence n = a_1 > a_2 >... > a_k = 1 where each a_(i+1) | a_i. The length of such a chain is k - 1. Let L(n) denote the maximum chain length. Compute sum_(n=1)...
Elliptic Curve Point Counting
For the elliptic curve E: y^2 = x^3 + x + 1 over F_p with p = 1009, find |E(F_p)|, the number of points including the point at infinity.
Combinatorial Game Values
In the game of Nim with heaps of sizes 1, 2,..., n, the Sprague--Grundy value is G(n) = 1 + 2 +... + n (XOR sum). Find the number of n <= 10^6 for which G(n) = 0 (i.e., the second player wins).
Random Graph Connectivity
In the Erdos--Renyi model G(n,p), each of the C(n, 2) possible edges exists independently with probability p. For n = 100, find the smallest p (to 6 decimal places) such that the probability of the...
Continued Fraction Convergents
The continued fraction expansion of sqrt(2) is [1; 2, 2, 2,...]. Let p_n/q_n denote the n -th convergent. Find p_100 + q_100 mod 10^9+7.
Binomial Coefficient Divisibility
Find the number of entries in Pascal's triangle (rows 0 through N = 1000) that are not divisible by the prime p = 2.
Totient Sum Optimization
Find sum_(k=1)^N varphi(k) (mod 10^9+7) for N = 10^7.
Catalan Number Variants
The n -th Catalan number is C_n = (1)/(n+1)C(2n, n). Find sum_(k=0)^1000 C_k (mod 10^9+7).
Prime Gap Distribution
Let g(p) denote the gap to the next prime: g(p) = p' - p, where p' is the smallest prime exceeding p. Find sum_(p <= 10^7, p prime) g(p)^2.
Quadratic Residue Patterns
For a prime p, define R(p) = sum_(a=1)^(p-1) ((a)/(p))((a+1)/(p)), where ((*)/(p)) is the Legendre symbol. Find sum_(p <= 10^5, p prime) R(p).
Sum of Radical Expressions
For a positive integer n, define R(n) = sum_(d | n) rad(d), where rad(d) is the product of the distinct prime factors of d (with rad(1) = 1). Find sum_(n=1)^(10^7) R(n) mod (10^9 + 7).
Triangular Number Intersections
Let T_n = n(n+1)/2 be the n -th triangular number. Find the number of ordered pairs (a, b) with 1 <= a < b <= 10^6 such that T_a + T_b is also a triangular number.
Digit Factorial Chains
Define f(n) as the sum of factorials of the digits of n. Starting from any n, repeatedly applying f eventually enters a cycle. Let L(n) be the number of distinct values visited before entering a cy...
Primitive Root Sequences
For a prime p, let g(p) be the smallest primitive root modulo p. Define S(N) = sum_(p <= N, p prime) g(p). Find S(10^7).
Lattice Paths with Obstacles
On a 50 x 50 grid, obstacles are placed at all lattice points (x, y) where x + y is a perfect square and gcd(x, y) > 1. Starting from (0, 0) and moving only right (+1, 0) or up (0, +1), find the nu...
Modular Fibonacci Matrix
Define the Fibonacci sequence F_0 = 0, F_1 = 1, F_n = F_(n-1) + F_(n-2). Find M = sum_(k=1)^10^12 k * F_k (mod 10^9 + 7).
Pandigital Prime Search
A number is k -pandigital if it uses each digit from 1 to k exactly once. Find the largest k -pandigital prime (for any k from 1 to 9).
Circle Lattice Points
Let C(r) be the number of lattice points (x, y) in Z^2 with x^2 + y^2 <= r^2. Define D(N) = sum_(r=1)^N C(r). Find D(10^5) mod (10^9 + 7).
Goldbach Partition Counting
For an even number n >= 4, let G(n) be the number of ways to write n = p + q where p <= q are both prime. Find sum_(n=4, n even)^(10^6) G(n).
Power Tower Modular Arithmetic
Define a power tower T(a, n) recursively: T(a, 1) = a and T(a, n) = a^(T(a, n-1)) for n >= 2. Find T(2, 100) mod (10^9 + 7).
Binary Palindrome Sums
A binary palindrome is a positive integer whose binary representation (with no leading zeros) is a palindrome. Find the sum of all binary palindromes less than 2^30.
Polygonal Number Chains
The k -th s -gonal number is P(s,k) = k((s-2)k-(s-4))/2. Find the longest chain where consecutive terms share a value with different (s,k) pairs, 3 <= s <= 8, values up to 10^4.
Dirichlet Series Evaluation
Define D(s) = sum_(n=1)^N (mu(n))/(n^s) where mu is the Mobius function. Find floor(D(2) * 10^12) for N = 10^7.
Random Permutation Inversions
An inversion in a permutation sigma of {1,...,n} is a pair (i,j) with i<j and sigma(i)>sigma(j). Let E(n) be the expected number of inversions in a uniformly random permutation of size n, and let V...
Smooth Number Sieve
A positive integer n is B -smooth if all its prime factors are <= B. Let Psi(x,B) count B -smooth numbers up to x. Find Psi(10^10, 100).
Hypergeometric Sums
Evaluate S = sum_(k=0)^1000 C(2000, k)^2 mod 10^9+7.
Nim with Restricted Moves
In a game of Nim with a single pile of n stones, a player may remove 1, 2, or 4 stones on each turn. The player who takes the last stone wins. Let W(N) = #{n <= N: first player wins}. Find W(10^9).
Counting Squarefree Numbers in Range
A positive integer is squarefree if no perfect square other than 1 divides it. Let Q(n) be the count of squarefree numbers up to n. Find Q(10^12).
Sum of Primitive Roots
For a prime p, the sum of all primitive roots modulo p is mu(p-1) (mod p). Find sum_(p <= 10^6, p prime) (sum of primitive roots mod p) (mod 10^9+7).
Chromatic Polynomial of Grid Graphs
The chromatic polynomial P(G, k) counts the number of proper k -colorings of graph G. For the 3 x n grid graph G_(3,n), find P(G_(3,10), 4) mod 10^9+7.
Euler Product Approximation
The Euler product for the Riemann zeta function is zeta(s) = prod_(p prime) (1 - p^(-s))^(-1). Let E(s, N) = prod_(p <= N) (1 - p^(-s))^(-1). Find floor(E(3, 10^6) x 10^15).
Integer Points on Ellipses
Find the number of integer solutions (x, y) to 3x^2 + 5y^2 <= 10^6.
Sorting Network Verification
A sorting network on n wires consists of comparators (i,j) that swap wires i and j if they are out of order. By the 0-1 principle, a network sorts all inputs iff it sorts all 2^n binary inputs. For...
Prime Counting Function
Let pi(x) denote the number of primes not exceeding x. Compute sum_(k=1)^(10^4) pi(k^2).
Fibonacci Entry Points
For a positive integer m, the Fibonacci entry point (or rank of apparition) alpha(m) is the smallest positive k such that m | F_k. Find sum_(m=1)^(10^5) alpha(m).
Random Matrix Determinant
Consider all 3 x 3 matrices with entries from {-1, 0, 1}. Let S be the sum of the absolute values of the determinants over all such matrices. Find S.
Diophantine Approximation
For irrational alpha, the best rational approximations are given by its continued fraction convergents. Let p_k/q_k be the k -th convergent of sqrt(2). Find sum_(k=0)^50 (p_k^2 - 2q_k^2).
Subset Sum Counting
Given the set A = {1, 2, 4, 8, 16,..., 2^19} (powers of 2 from 2^0 to 2^19), find the number of subsets of A whose elements sum to exactly 500000.
Sequence Alignment Score
In bioinformatics, the edit distance between two strings measures the minimum number of insertions, deletions, and substitutions to transform one into the other. Let s_1 be the first 100 decimal di...
Modular Combinatorics
Find sum_(k=0)^(10^6) C(10^6, k) * k^3 (mod 10^9+7).
Repunit Divisibility
A repunit R_n is a number consisting of n ones: R_n = underbrace11ldots1_n = (10^n - 1)/(9). Find the sum of all n <= 1000 such that R_n is divisible by n.
Taxicab Numbers
The n -th taxicab number Ta(n) is the smallest number expressible as the sum of two positive cubes in n distinct ways. Find Ta(2) + Ta(3) (mod 10^9+7).
Palindromic Primes in Bases
A number is called multi-palindromic if it is a palindrome in at least two different bases from 2 to 16. Find the count of multi-palindromic primes below 10^6.
Generalized Pentagonal Numbers
The generalized pentagonal numbers are omega_k = k(3k-1)/2 for k = 0, +/- 1, +/- 2,..., yielding 0, 1, 2, 5, 7, 12, 15, 22, 26,.... Find the sum of all generalized pentagonal numbers below 10^7.
Erdos-Straus Conjecture Instances
The Erdos-Straus conjecture states that for every integer n >= 2, (4)/(n) = (1)/(x) + (1)/(y) + (1)/(z) has a solution in positive integers. For each n from 2 to 10^6, find the solution (x,y,z) min...
Abundant Number Chains
Define s(n) = sigma(n) - n (sum of proper divisors). An abundant chain of length k starting at n is a sequence n, s(n), s(s(n)),... where each term is abundant (s(term) > term) for k consecutive st...
Pisano Period Computation
The Pisano period pi(m) is the period of the Fibonacci sequence modulo m. Find sum_(m=2)^1000 pi(m).
Fraction Tree Traversal
The Stern-Brocot tree contains every positive rational number exactly once in lowest terms. Starting from (1)/(1) at the root, perform a breadth-first traversal and collect fractions. Find the sum...
Additive Prime Counting
An additive prime is a prime whose digit sum is also prime. Find the count of additive primes below 10^6.
Collatz Stopping Time Statistics
The Collatz stopping time t(n) is the number of steps to reach 1 from n using the rule: if even, n -> n/2; if odd, n -> 3n + 1. Find sum_(n=1)^(10^6) t(n).
Gaussian Integer Primes
Let Z[i] = {a + bi: a, b in Z} denote the ring of Gaussian integers. Count the number of Gaussian primes a + bi satisfying 0 <= a <= 500 and 0 <= b <= 500 (i.e., those lying in the closed first-qua...
Stern Sequence Properties
The Stern diatomic sequence {s(n)}_(n >= 0) is defined by: s(0) = 0, s(1) = 1, s(2n) = s(n), s(2n+1) = s(n) + s(n+1) (n >= 1). Compute sum_(n=1)^2^20 s(n).
Lucky Number Sieve
The lucky numbers are generated by the following sieve process. Begin with the sequence of odd positive integers: 1, 3, 5, 7, 9, 11, 13, 15,... The first element greater than 1 is 3; remove every 3...
Mobius Function Partial Sums
The Mertens function is defined as M(n) = sum_(k=1)^n mu(k), where mu is the Mobius function. Compute sum_(n=1)^(10^5) |M(n)|.
Zeckendorf Representation Uniqueness
By Zeckendorf's theorem, every positive integer n has a unique representation as a sum of non-consecutive Fibonacci numbers. Let z(n) denote the number of Fibonacci summands in this representation....
Perfect Power Detection
A perfect power is an integer of the form a^b where a >= 1 and b >= 2. Find the number of distinct perfect powers in {1, 2,..., 10^18}.
Dedekind Sum Computation
The Dedekind sum is defined for coprime integers h, k with k > 0 by: s(h,k) = sum_(r=1)^(k-1) (((r)/(k))) (((hr)/(k))) where the sawtooth function is ((x)) = x - floor(x) - tfrac12 for x not in Z,...
Bernoulli Number Modular
The Bernoulli numbers B_n satisfy the recurrence sum_(k=0)^n C(n+1, k) B_k = 0 for n >= 1, with B_0 = 1. Write B_n = p_n / q_n in lowest terms (with q_n > 0). Compute sum_(n=0)^200 (|p_n| + q_n) (m...
Josephus Problem Variant
In the Josephus problem, n people stand in a circle and every k -th person is eliminated. Let J(n,k) be the 1-indexed position of the last survivor. Find sum_(n=1)^10000 J(n, 3).
Multiplicative Order Statistics
The multiplicative order ord_n(2) is the smallest positive k such that 2^k equiv 1 (mod n). Find sum_(n=2, gcd(2,n)=1)^10000 ord_n(2).
Thue-Morse Sequence Sums
The Thue-Morse sequence t(n) = popcount(n) mod 2. Let T(N) = sum_(n=0)^(N-1) (-1)^(t(n)) * n. Find T(2^20).
Cantor Set Measure
After n iterations of the Cantor set construction, the remaining measure is (2/3)^n. Define S(n) = floor(10^18 * (2/3)^n). Find sum_(n=0)^100 S(n) mod (10^9 + 7).
Digit Permutation Primes
A digit permutation prime group is a set of primes that are all permutations of the same digits. Find the number of such groups among primes below 10^6 where the group size is at least 4.
Stirling Number Asymptotics
The Bell number B_n = sum_(k=0)^n S(n,k) counts the number of partitions of {1,..., n}. Find B_1000 mod (10^9+7).
Graph Coloring Polynomial
The chromatic polynomial P(G, k) counts proper k -colorings of graph G. For the Petersen graph, find P(G, 4) mod (10^9+7).
Partition Rank Statistics
The rank of a partition is (largest part) - (number of parts). Let R(n) = sum_(lambda vdash n) rank(lambda). Find sum_(n=1)^100 R(n) mod (10^9+7).
Cyclotomic Polynomial Evaluation
The n -th cyclotomic polynomial Phi_n(x) is defined as the minimal polynomial over Q whose roots are the primitive n -th roots of unity. Compute: S = sum_(n=1)^500 Phi_n(2) (mod 10^9 + 7)
Gaussian Elimination Mod p
For p = 2 and n = 10, find the number of invertible 10 x 10 binary matrices, modulo 10^9 + 7.
No Project Euler entries fit the current search and filter combination.