# Unnecessary Fluff

• Take a list of positive integers and a positive integer $$\m\$$ as input.
• Only keep the prime values from the list.
• Define $$\f(n) = F_{n^2 + 1}\$$ (the $$\n^2+1\$$-th element in the Fibonacci sequence, starting from $$\F_0=0, F_1=1\$$), $$\g(n) = \underbrace{f(f(\cdots f(n)\cdots))}_{m\text{ applications of }f}\$$, and $$\h(n) = \begin{cases}h(g(n) \mod n) + 1&n\neq0\\0&n=0\end{cases}\$$.
• Apply $$\h\$$ to each element on the list.
• Return the median (you can assume the input contained an odd number of primes).

## Test cases

[2,7,11,10,14,4,9], 1 -> 2
[2,7,11,5,13,10,14,4,9], 1 -> 2
[5,5,11,5,13,93,94,95,9], 1 -> 3
[5,7,11], 2 -> 2
[5,5,11], 2 -> 1
[5,43,67], 2 -> 3
[5,43,67], 2 -> 3
[977], 2 -> 5
[719, 727, 733, 739, 743], 2 -> 4
[967], 10 -> 4
[977], 10 -> 3
[5], 10 -> 1


Standard loopholes are forbidden. You can use any reasonable I/O format.

This is code golf, so the shortest answer in each language wins.

• How are you defining Fibonacci?
– Tbw
Jan 5 at 4:47
• @Tbw I'm using $F_0 = 0, F_1 = 1, F_{n+2} = F_n + F_{n+1}$, but I just noticed that my code doesn't do that - let me fix the test cases. Jan 5 at 4:58
• @Tbw What do you mean? It depends on $m$. $f(100)$, or $f(f(3))$ should fit in the memory, but not much after that - to compute larger values you can use modular arithmetic to directly compute $g(n)\mod n$ (although you don't have to do that - your code only has to theoretically be correct). Jan 5 at 5:06
• @NickKennedy $h$ is recursive, $h(0)$ is the base case. Jan 5 at 8:26
• @KevinCruijssen The modulus is the argument of $h$, not the original $n$, so $h(1) = h(\text{something}\mod 1)+1 = h(0)+1 = 1$. Jan 5 at 8:28

# 05AB1E, 28 bytes

DpÏε"ÐĀiIFn>Åf}s%®.V>"©.V}Åm


Times out for the $$\m\geq2\$$ test cases, but works in theory.

Explanation:

DpÏ          # Only keep the primes of the first (implicit) input-list
ε         # Map over each prime:
"..."    #  Define recursive string h explained below
©   #  Store this string in variable ® (without popping)
.V #  Execute it as 05AB1E code, with the current prime as argument
}Åm       # After the map: Pop and push its median
# (which is output implicitly as result)

Ð            # Triplicate the current value
Āi          # Pop one, and if it's NOT 0:
IF        #  Loop the second input-integer m amount of times:
n>      #   Square the current value, and then increase it by 1
Åf    #   Pop and push the 0-based Fibonacci number
}s       #  After the loop: swap so a copy of the triplicated number is at the top
%      #  Modulo
®.V   #  Then do a recursive call to ®
>  #  And increase it by 1
# (implicit else:)
#  (implicitly use the triplicated 0)


# Jelly, 20 bytes

²‘ÆḞƊ⁴¡%⁸ßẸ¡‘
ẒƇÇ€Æṁ


Try it online!

A full program taking the list of integers as the first argument and $$\m\$$ as the second. Prints the result to STDOUT. The TIO link includes a footer that evaluates the first three examples. Times out where $$\m \ge 2\$$.

## Alternative approach Jelly, 36 bytes

ẒƇµØ.;S$%ḊɗƬLƊ⁹Ð¡ḊU²‘%ÆḞʋƒ%µ¹Ð¿)ẈÆṁ’  Try it online! A dyadic link taking the list of integers as its left argument and $$\m\$$ as its right, and returning the result. Works for all of the examples in under two seconds total. Full explanation to follow, but in brief: 1. For a given integer $$\n\$$: 1. Generate $$\\pi(n)\$$, $$\\pi(\pi(n))\$$, $$\\pi(\pi(\pi(n)))\$$ … so we have $$\m\$$ levels of this. Here $$\\pi(n)\$$ is the Pisano period which is the period of the Fibonacci sequence $$\\mod n\$$. 2. Reverse these. So for example where $$\n = 977\$$ and $$\m = 5\$$, we have a list of [120, 120, 120, 984, 652]. 3. Starting with $$\n\$$, reduce using each member of the list with the following dyadic function: $$\ F((x ^ 2 + 1) \bmod y) \$$ where $$\F(z)\$$ is the zth Fibonacci sequence member. 4. Take the result of this reduction $$\ \bmod n\$$ 2. If the result is non-zero, repeat the above using the result as the new $$\n\$$. 3. Count how many steps it takes to get to zero. 4. Repeat for all of the other prime integers, and take the median. ### Line by line explanation ẒƇµØ.;S$%ḊɗƬLƊ⁹Ð¡ḊU²‘%ÆḞʋƒ%µ¹Ð¿)ẈÆṁ’­⁡​‎‎⁪⁡⁪⁠⁪⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁪‏‏​⁡⁠⁡‌⁢​‎‎⁪⁡⁪⁠⁪⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁤⁪‏‏​⁡⁠⁡‌⁣​‎‎⁪⁡⁪⁠⁪⁢⁣⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁣⁪‏‏​⁡⁠⁡‌⁤​‎⁪⁪⁠‎⁪⁡⁪⁠⁪⁤⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁡⁪‏‏​⁡⁠⁡‌⁢⁡​‎‎⁪⁡⁪⁠⁪⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁤⁪‏‏​⁡⁠⁡‌⁢⁢​‎‎⁪⁡⁪⁠⁪⁢⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁪‏‏​⁡⁠⁡‌⁢⁣​‎⁪⁪⁠‎⁪⁡⁪⁠⁪⁣⁡⁪‏‏​⁡⁠⁡‌⁢⁤​‎⁪⁪⁠‎⁪⁡⁪⁠⁪⁣⁢⁪‏‏​⁡⁠⁡‌⁣⁡​‎‎⁪⁡⁪⁠⁪⁤⁡⁪‏‏​⁡⁠⁡‌⁣⁢​‎‎⁪⁡⁪⁠⁪⁢⁡⁢⁪‏‏​⁡⁠⁡‌⁣⁣​‎‎⁪⁡⁪⁠⁪⁢⁡⁣⁪‏‏​⁡⁠⁡‌⁣⁤​‎‎⁪⁡⁪⁠⁪⁢⁣⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁣⁢⁪‏‏​⁡⁠⁡‌⁤⁡​‎‎⁪⁡⁪⁠⁪⁢⁡⁤⁪‏‏​⁡⁠⁡‌⁤⁢​‎‎⁪⁡⁪⁠⁪⁢⁢⁡⁪‏‏​⁡⁠⁡‌⁤⁣​‎‎⁪⁡⁪⁠⁪⁢⁢⁢⁪‏‏​⁡⁠⁡‌⁤⁤​‎‎⁪⁡⁪⁠⁪⁢⁢⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁢⁤⁪‏‏​⁡⁠⁡‌⁢⁡⁡​‎‎⁪⁡⁪⁠⁪⁢⁣⁣⁪‏‏​⁡⁠⁡‌⁢⁡⁢​‎‎⁪⁡⁪⁠⁪⁣⁡⁡⁪‏‏​⁡⁠⁡‌⁢⁡⁣​‎‎⁪⁡⁪⁠⁪⁣⁡⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁡⁣⁪‏‏​⁡⁠⁡‌⁢⁡⁤​‎‎⁪⁡⁪⁠⁪⁣⁡⁤⁪‏‏​⁡⁠⁡‌­
ẒƇ                                    # ‎⁡Keep primes
µ                            )      # ‎⁢Start a new monadic chain and apply it to each of the primes:
µ¹Ð¿       # ‎⁣- Repeat until zero, collecting up intermediate results:
Ɗ⁹Ð¡                     # ‎⁤  - Do the following the number of times indicated by the link’s right argument, collecting up intermediate results (argument starts as one of the primes):
Ø.     ɗƬ                          # ‎⁢⁡    - Do the following starting with [0, 1] and with the current value of n as the right argument until no new values are seen (I.e. we’ve reached [0, 1] again):
;S$# ‎⁢⁢ - Concatenate the sum to the end % # ‎⁢⁣ - Mod n Ḋ # ‎⁢⁤ - Remove first value L # ‎⁣⁡ - Length (which will be Pisano period) Ḋ # ‎⁣⁢ - Remove first value U # ‎⁣⁣ - Reverse order ʋƒ # ‎⁣⁤ - Reduce this list using the following, and starting with the current n ² # ‎⁤⁡ - Squared ‘ # ‎⁤⁢ - Increment by 1 % # ‎⁤⁣ - Mod the current Pisano period ÆḞ # ‎⁤⁤ - Fibonacci number % # ‎⁢⁡⁡ - Mod n Ẉ # ‎⁢⁡⁢Lengths Æṁ # ‎⁢⁡⁣Median ’ # ‎⁢⁡⁤Decrement by 1 💎  Created with the help of Luminespire. # Raku, 107 bytes ->\v,\m{v.grep(&is-prime).map(->\n{n&&&?BLOCK(([o] &{(0,1,*+*...*)[$^n**2+1]} xx m)(n)%n)+1}).sort[*div 2]}


Attempt This Online!

• .grep(&is-prime) filters the prime numbers (&is-prime is a built-in function)
• (0, 1, * + * ... *) constructs the Fibonacci sequence
• &?BLOCK is a compile-time variable referring to the current block, so we can recurse with even anonymous functions
• o is the function composition operator; [o] says "reduce with o", so we can compose m functions with it
• [* div 2] as an array subscript passes the array length to * there, effectively getting the middle element without hussle (div is doing floor division)

# R, 241 bytes

\(x,m,~=sapply,&=c,f=for,-=sum)median(x[x~\(z)2>-!z%%(2:z)]~\(n){while(n){p=n
f(i,1:m,{x=1&1
j=2
while(-((x=x[2]&-x%%p[1])>0:1))j=j+1
p=j&p})
f(i,1:m,n<-if((n=(n^2+1)%%p[i])<2,n,{x=0:1
f(l,2:n,x<-x[2]&-x%%p[i+1])
x[2]}))
F=F+1}
F})


Attempt This Online!

A function taking the vector of integers as its first argument and $$\m\$$ as its second. Returns an integer.

This uses the same methodology described in my second Jelly answer, but uses no built-ins for checking primes or the Fibonacci sequence.

# Wolfram Language(Mathematica), 132 bytes

132 bytes, it can be golfed much more.

g[0,n_]:=n
g[m_,n_]:=g[m-1,Fibonacci[n*n+1]]
h[m_,0]=0
h[m_,n_]:=h[m,g[m,n]~Mod~n]+1
F[l_,m_]:=Median[Map[h[m,#]&,Select[l,PrimeQ]]]


Try it online!

# Python 3, 252 bytes

from statistics import*
f=lambda n:f(n-1)+f(n-2)if n>1else n
g=lambda m,n:g(m-1,f(n*n+1))if m>0else n
h=lambda m,n:h(m,g(m,n)%n)+1if n>0else 0
F=lambda l,m:median(map(lambda n:h(m,n),filter(lambda n:0not in map(lambda m:n%(m+2),range(n-2))and n!=1,l)))


Try it online!