The Frequency Ruler of a Spectrum App

A phone app shows the spectrum of what its microphone hears. It records n samples at fs samples per second and computes their DFT. Bin k counts waves that make k whole cycles during the recording, and the recording lasts n / fs seconds, so bin k stands for the frequency

f_k = k * fs / n    hertz

The spacing between neighbouring bins, fs / n, is the frequency resolution: two tones closer than that fall into the same bin. It is one over the recording time, so only a longer recording sharpens it. The bins that mean something for a real signal run from k = 0 (the offset) up to k = n // 2, at or just below the Nyquist frequency fs / 2; the bins above mirror them.

Write bin_ruler(fs, n, f) that returns a tuple:

1. the resolution fs / n in hertz,
2. the list of the frequencies f_k of the bins k = 0, 1, ..., n // 2,
3. the bin number k in that range whose frequency is closest to the frequency f (the tests never have an exact tie).

Examples

Input:  fs = 50, n = 10, f = 12
Output: (5.0, [0.0, 5.0, 10.0, 15.0, 20.0, 25.0], 2)
Explanation: ten samples last 0.2 s, so the bins are 5 Hz apart. 12 Hz is 2 Hz from bin 2
and 3 Hz from bin 3.

Input:  fs = 1000, n = 7, f = 500
Output: (142.85714285714286, [0.0, 142.85714285714286, 285.7142857142857, 428.57142857142856], 3)
Explanation: with an odd n the last useful bin, n // 2 = 3, lies below fs / 2.

Constraints

• 0 <= f <= fs / 2
• answers are compared with a tolerance of 1e-6

Goals

• Convert a bin number k into a frequency k * fs / N in hertz
• Read the frequency resolution fs / N as one over the recording time
• Find the bin that best represents a given frequency