Adapted from this FiveThirtyEight riddle.
Background
Examine the following infinite sequence:
3 3 3 2 3 3 3 2 3 3 3 2 3 3 2 3 3 3 2 ...
Let's say the sequence is 1-indexed. The i
th number in the sequence determines how many 3
s there are before the i
th 2
and following any previous 2
s. So since the sequence starts with a 3
the sequence must begin 3 3 3 2
and since there are three 3
s at the beginning of the sequence the subsequence 3 3 3 2
must repeat itself three times. After that you reach 3 3 2
because the fourth number in the sequence is 2
.
The FiveThirtyEight riddle asks for the limit of the ratios of threes to twos (which I won't spoil here) but you can also ask what the cumulative ratio is after index i
. For example the ratio at i=4
is 3/1 = 3
and at i=15
it's 11/4 = 2.75
.
Let's get general
Given numbers n
and k
we can make a similar sequence that starts with n
and just like the original sequence described the number at index i
determines how many n
s show up before the i
th k
and following any previous k
s.
Examples:
n=2, k=5
gives the sequence 2 2 5 2 2 5 2 2 2 2 2 5 2 2 5 ...
n=3, k=0
gives 3 3 3 0 3 3 3 0 3 3 3 0 0 3 3 3 0 ...
n=1, k=3
gives 1 3 1 1 1 3 1 3 1 3 1 3 1 1 1 3 1 ...
The Challenge
Write a function/program and with it do the following. Take as input:
- a positive integer
n
- a nonnegative integer
k ≠ n
- a positive integer
i > n
The first two inputs n
and k
determine a sequence as described above and i
is an index. I am using 1-indexing in the examples but you have the freedom to use 0- or 1-indexing. If 0-indexed then the restriction on i
is i ≥ n
.
With the three numbers output the ratio of n
s to k
s in the sequence up to and including the number at the index i
. The format of the output can either be a decimal value with at least 5 digits of precision or an exact value as a ratio like 3524/837
or 3524:837
.
In decimal form, the last digit can be rounded however you like. Trailing zeros and whitespace are allowed.
In either of the string forms the two numbers need to be normalized so that they are coprime. For example if the ratio was 22/4, 11/2
and 11:2
are acceptable but 22/4
is not.
Examples
n k i output
2 4 15 2.75 or 11/4
6 0 666 5.1101 or 557:109
50 89 64 63 or 63:1
3 2 1000 2.7453 or 733/267
9 12 345 9.4545 or 104/11
This is code golf per language, so shortest code in each language is the winner.
/
or:
just adds an unnecessary complication to the challenge. \$\endgroup\$