Computation Workshop Solution Checker

Recursively Defined Function

The function \(f\) is defined on positive integers by \(f(p)=1\) for all prime numbers \(p\), and \(f(xy) = xf(y) + yf(x)\) for all positive integers \(x\) and \(y\). We are interested in finding integers \(n\) such that \(n=f(n)\).

Part A Determine the smallest \(n>2023\) such that \(f(n)=n\).
Part B Determine the smallest \(n>1000000\) such that \(f(n)=n\).

Identical Chairs

Suppose there are a row of \(n\) chairs. Along come \(k\) identical people who want to sit in these chairs. Let \(S(n,k)\) denote the number of ways for these people to sit in these chairs, such that between any two people there will be at least \(2\) empty chairs. So for example \(S(5,1)=5\) because the person can sit in any of the five chairs, but \(S(5,2)=3\) because there are 3 ways to choose which two chairs they occupy.

Part A Determine \(S(100,3)\).
Part B Determine the remainder when \(S(1000,100)\) is divided by \(10^9+7\).