Problem Analysis #25

I need to find which values of f(n) are actually possible given g(n)=15.

Let me think about the structure. Write n = 3^a · m where m is coprime to 3. Divisors not divisible by 3 are divisors of m, each congruent to 1 or 2 mod 3.

Factor m using primes p ≡ 1 mod 3 and primes q ≡ 2 mod 3. Divisors divisible by 3 are ≡ 0 mod 3, so f and g only count divisors coprime to 3.

For a divisor d of m: d mod 3 depends on the product of prime factors. Primes ≡ 1 contribute factor 1; primes ≡ 2 contribute factor 2 mod 3. So d ≡ 2^k mod 3 where k = total exponent count of primes ≡ 2 mod 3 in d.

So d ≡ 1 if k even, d ≡ 2 if k odd.

Let the primes ≡ 1 mod 3 have exponents giving total divisor count A (product of (e_i+1)). Let primes ≡ 2 mod 3 be q_1^{b_1}...q_r^{b_r}.

For the part from primes ≡ 2, count divisors with even total exponent (E) and odd total exponent (O).

Then f(n) = A·E, g(n) = A·O.

So f(n)/g(n) = E/O. With g(n)=15, f(n) = 15·E/O.

I need to find possible ratios E/O for products of (b_i+1) structure.

For a single prime q^b: divisors q^0...q^b, even exponents count = ⌈(b+1)/2⌉, odd = ⌊(b+1)/2⌋.

• E_1 = ceil((b+1)/2), O_1 = floor((b+1)/2).

For multiple primes, even/odd total exponent: this is a parity convolution. Let me track (E, O) for combined.

Combining two factors: total E = E1·E2 + O1·O2, total O = E1·O2 + O1·E2.

For each prime power, (E_i, O_i):

• b even: E = (b+2)/2... let me just compute. b+1 divisors. If b even, b+1 odd, even-exponent count = (b/2+1), odd = b/2. So E-O = 1.
• b odd: b+1 even, E = (b+1)/2, O=(b+1)/2, E-O=0, E=O.

Key invariant: E-O. Combining: (E1-O1)(E2-O2) = (E_total - O_total).

Check: E_total - O_total = E1E2+O1O2 - E1O2 - O1E2 = (E1-O1)(E2-O2). Yes!

So E - O = ∏(E_i - O_i). If any prime has odd exponent (E_i=O_i, difference 0), then E=O total, giving f=g=15 → f=15.

If all primes ≡2 have even exponents, each E_i-O_i=1, so E-O=1.

Now g(n) = A·O = 15. f(n) = A·E.

Case 1: E=O. Then A·O=15, f=A·E=15. ✓ (f=15)

Case 2: E-O=1 (all even exponents). Then with total divisors from these primes = E+O. We have g = A·O = 15, f = A·E = A·(O+1) = 15 + A.

So f = 15 + A where A divides... we need A·O=15 with O being the odd-exponent count.

Need to find valid (A, O, E) with E=O+1, E+O = total divisors T (product of (b_i+1)), and the structure E-O=1.

For single prime q^b, b even: E = b/2+1, O=b/2. Need O = b/2, E=O+1. Total = b+1 = odd. For multiple primes all even exponents: E-O=1 still, E = (T+1)/2, O=(T-1)/2 where T = ∏(b_i+1) (all odd, product odd).

So O = (T-1)/2, and A·O = 15.

f = 15 + A. So I need A·(T-1)/2 = 15, i.e., A(T-1) = 30.

A = product of (e_i+1) for primes ≡1 mod 3, can be any positive integer ≥1 (taking enough such primes/powers). T-1 must be even (T odd, so T-1 even).

A·(T-1)=30, T-1 even, A≥1, T≥1 (T odd so T-1∈{0,2,4,...}).

• T-1=2 (T=3): A=15 → f=15+15=30 ✓
• T-1=6 (T=7): A=5 → f=15+5=20 ✓
• T-1=10 (T=11): A=3 → f=15+3=18 ✓
• T-1=30 (T=31): A=1 → f=15+1=16 ✓

Also T-1=0 means no primes≡2, but then O=0, g=0≠15. Invalid.

So possible f from case 2: 30, 20, 18, 16. Plus case 1 gives 15.

Need T realizable as odd product of (b_i+1): T=3,7,11,31 all odd. T=3 (one prime b=2), T=7(b=6), T=11(b=10), T=31(b=30). All valid. A=15,5,3,1 realizable.

So all five values {15,16,18,20,30} are possible.

Sum = 15+16+18+20+30 = 99.

\boxed{99}