# Generalized FiveThirtyEight Sequences

## 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 ith number in the sequence determines how many 3s there are before the ith 2 and following any previous 2s. So since the sequence starts with a 3 the sequence must begin 3 3 3 2 and since there are three 3s 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 ns show up before the ith k and following any previous ks.

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 ns to ks 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.

• – Martin Ender Dec 9 '17 at 23:11
• I recommend allowing a pair of integers as a ratio, needing answerers to separate the numbers with / or : just adds an unnecessary complication to the challenge. – Erik the Outgolfer Dec 10 '17 at 9:24
• @EriktheOutgolfer a decimal number is allowed too – dylnan Dec 10 '17 at 13:29
• Is a standard float exact enough for the decimal output? – Reinstate Monica -- notmaynard Dec 10 '17 at 14:48
• @iamnotmaynard I’m not strict about the float format so yes I think so – dylnan Dec 10 '17 at 15:06

# Husk, 16 bytes

¤/#ωȯ↑⁰J¹C∞²N¹²


Try it online!

Takes inputs in the same order as the test cases. Outputs a rational number. I feel like this has too many superscripts, but I don't know how to get rid of them...

## Explanation

¤/#ωȯ↑⁰J¹C∞²N¹²  Inputs are n, k, i.
N    Starting with the natural numbers [1,2,3..
ωȯ             do this until a fixed point is reached:
Argument is a list s.
∞²       Take the infinite list [n,n,n..
C         and split it to the lengths in s.
J¹           Join the resulting blocks with k.
↑⁰             Take the first i elements.
Call the result x.
¤             ¹²  For each of n and k,
#               count their number of occurrences in x
/                and perform exact division on the results.


# Python 3, 949289 87 bytes

def g(n,k,i):o,t=[n],0;exec('o+=[n]*o[t]+[k];t+=1;'*i);return-1-i/(o[1:i+1].count(n)-i)


Try it online!

# Credits

• Reduced from 94 to 92 bytes: Colera Su.
• Reduced from 92 to 89 bytes: dylnan.
• Reduced from 89 to 87 bytes: ovs.
• Shouldn't it be .count(n)? – Colera Su Dec 10 '17 at 3:46
• @ColeraSu Thanks. Don't know how I missed that, fixed. – Neil Dec 10 '17 at 3:47
• – Colera Su Dec 10 '17 at 3:52
• @ColeraSu Thanks, updated. I'll try to start using exec's. That's pretty cool. – Neil Dec 10 '17 at 3:54
• 89 bytes – dylnan Dec 10 '17 at 3:56

# Jelly, 22 bytes

³ẋÐ€;€⁴Ẏḣ⁵
ẋ;ÇÐLLƙ÷/


Try it online!

Full program. Takes arguments n, k, i.

There's a bug that makes this need to be unnecessarily longer by 1 byte.

• Used some of your tricks - nice. Wondering about what the correct fix for the bug should really be... – Jonathan Allan Dec 10 '17 at 13:02
• @JonathanAllan What struck me is this line, although not sure why putting a  makes it work. Oh, and where your answer differs is that I forgot to implement a golf I found in another language >_> – Erik the Outgolfer Dec 10 '17 at 13:13

# Jelly,  25  16 bytes

-9 bytes ~50% attributable to Erik the Outgolfer's Jelly answer (1. using the new-ish key quick ƙ even with a bug in the interpreter currently costing a byte; 2. using a mapped repetition to avoid counting and indexing into the current sequence.) Go give him some credit!

³ẋÐ€j⁴ṁ⁵µÐLLƙ÷/


A full program taking three arguments: n, k, i which prints the result.

Try it online!

### How?

³ẋÐ€j⁴ṁ⁵µÐLLƙ÷/ - Main link
ÐL      - apply the monadic chain to the left repeatedly until no change occurs:
³                -   program's 1st argument, n
Ð€             -   map across the current sequence (initially just n)
ẋ               -     repeat (the first run give triangle of n i.e. [[n],[n,n],...,[n]*n]
⁴           -     program's 2nd argument, k
j            -     join
⁵         -     program's 3rd argument, i
ṁ          -     mould like (repeat the list to fill, or cut it, to length i)
ƙ    - keyed application, map over groups of identical items:
   - (this has an arity of 2, make it monadic by repeating the argument)
L     -   length -> [numberOfNs, numberOfKs]
/ - reduce with:
÷  -   division -> [numberOfNs / numberOfKs]
- implicit print (a single item list just prints its content)


example run with inputs n=2, k=3, i=30:

Start the "loop until no change", ÐL
Note: Initial left argument, n=2, implicitly range-ified by Ð€ to become [1,2]
1. mapped repeat of n: [[2],[2,2]]
join with k: [2,3,2,2]
mould like i: [2,3,2,2,2,3,2,2,2,3,2,2,2,3,2,2,2,3,2,2,2,3,2,2,2,3,2,2,2,3]

2. mapped repeat of n: [[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2]]
join with k: [2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2]
mould like i: [2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2]
^different to previous result

3. mapped repeat of n: [[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2]]
join with k: [2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2]
mould like i: [2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2]
^different to previous result

4. mapped repeat of n: [[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2]]
join with k: [2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2]
mould like i: [2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2]
^different to previous result

5. mapped repeat of n: [[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2]]
join with k: [2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2]
mould like i: [2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2]
all the same as the previous result; stop loop and yield this.

length applied to equal elements: [length([2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]), length([3,3,3,3,3,3,3,3,3])]
= [21,9]
reduce by division              = [21/9] = [2.3333333333333335]
implicit print                  2.3333333333333335


# Mathematica, 85 bytes

(s={#};Do[s=Join[s,#~Table~s[[t]],{#2}],{t,#3}];Last@@Ratios@Tally@s[[#+3;;#3+#+2]])&


Try it online!

# APL (Dyalog Unicode), 126 70 bytes

k n i←⎕
j←⍴v←⍬
:While j<i
v,←k,⍨n⍴⍨{v≢⍬:j⊃v⋄n}j+←1
:End
÷/+/¨n k⍷¨⊂j⍴v


Try it online!

Well, thanks to @Adám for obliterating 56 bytes out of this answer.

⎕PP←5 is not added to the byte count because it's only used to limit the Print Precision to 5 digits.

∇f and ∇ are not added to the byte count because they're not part of the code, only delimiters for the tradfn.

### How it Works:

k n i←⎕                   ⍝ Take input (←⎕) for k, n and i.
j←⍴v←⍬                    ⍝ Assign (←) an empty vector (⍬) to v, then assign its shape (⍴, which is 0) to j.
:While j<i                ⍝ while j<i, do:
v,←k,⍨n⍴⍨{v≢⍬:j⊃v⋄n}j+←1 ⍝ this:
j+←1 ⍝ increment j (+←1)
{v≢⍬:     }     ⍝ if (:) v does not match (≢) ⍬
j⊃v        ⍝ return the jth element of v (v[j])
⋄n      ⍝ else (⋄) return n
n⍴⍨                 ⍝ shape (⍴) n as the result (repeats n result times)
k,⍨                    ⍝ append (,⍨) k
v,←                       ⍝ append to (,←) v
:End                      ⍝ End while loop
÷/+/¨n k⍷¨⊂j⍴v            ⍝ then:
j⍴v            ⍝ shape (⍴) v as j (truncates v to j elements)
⊂               ⍝ enclose the resulting vector
¨                ⍝ for each element
⍷                 ⍝ find (returns a boolean vector)
n k                  ⍝ n and k (⍷ will return a boolean vector for each)
+/¨                     ⍝ cumulative sum of each vector (returns the number of times n and k appear in v)
÷/                        ⍝ divide them and implicitly return the result.


# R, 88 bytes

function(n,k,i){s=rep(n,n);for(j in 1:i){s=c(s,k,rep(n,s[j]))};z=sum(s[1:i]==n);z/(i-z)}


Try it online!

• you can get rid of the braces around the for loop body as there's only one statement. – Giuseppe Dec 13 '17 at 21:47

# Swift, 152 bytes

func f(n:Int,k:Int,i:Int){var a=[0];(1...i).map{a+=(0..<(a.count>$0 ?a[$0]:n)).map{_ in n}+[k]};let m=a[1...i].filter{n==$0}.count;print("\(m)/\(i-m)")}  Will it be shorter than Java? ## Explanation func f(n:Int,k:Int,i:Int){ var a=[0] // Initialize the array (the zero is to // define the type of the array and will be // ignored by the code) (1...i).map{ // Repeat i times (more than enough): a+=(0..<(a.count>$0 ?a[$0]:n)).map{_ in n} // Add the right amount of n:s to the array +[k] // Add k to the array } // End repeat let m=a[1...i].filter{n==$0}.count           // Count the amount of n:s in the first
//  i elements of the array
print("\(m)/\(i-m)")                         // Print the result
}


# Ruby, 7771 70 bytes

->n,k,i{r=[n]
i.times{|c|r+=[n]*r[c]+[k]}
1r*(j=r[1,i].count n)/(i-j)}


Try it online!

Returns a Rational, which both operates as a number and stringifies to the exact reduced fraction.

# Pyth, 24 bytes

AEtcH/e.u<sm+*d]QGNH]Q)G


Test suite.

Fixed point of [n] under certain function of array.

# Zephyr, 284 bytes

input n as Integer
input k as Integer
input m as Integer
set s to Array(m)
for i from 1 to n
set s[i]to n
next
set s[i]to k
set N to n
set K to 1
for a from 2 to m
for b from 1 to s[a]
inc i
if i<=m
set s[i]to n
inc N
end if
next
inc i
if i<=m
set s[i]to k
inc K
end if
next
print N/K


Takes the three numbers from stdin on three separate lines. Outputs an exact ratio such as 104/11 or 63.

### Ungolfed

input n as Integer
input k as Integer
input maxIndex as Integer

set sequence to Array(maxIndex)
for i from 1 to n
set sequence[i] to n
next
set sequence[i] to k

set nCount to n
set kCount to 1

for a from 2 to maxIndex
for b from 1 to sequence[a]
inc i
if i <= maxIndex
set sequence[i] to n
inc nCount
end if
next
inc i
if i <= maxIndex
set sequence[i] to k
inc kCount
end if
next

print nCount / kCount
`