10
\$\begingroup\$

Following the great advice (what do you mean it's not advice?!) on Adding unnecessary fluff we can devise the following task:

  • 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.

\$\endgroup\$
14
  • 1
    \$\begingroup\$ How are you defining Fibonacci? \$\endgroup\$
    – Tbw
    Jan 5 at 4:47
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Jan 5 at 4:58
  • 1
    \$\begingroup\$ @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). \$\endgroup\$ Jan 5 at 5:06
  • 1
    \$\begingroup\$ @NickKennedy \$h\$ is recursive, \$h(0)\$ is the base case. \$\endgroup\$ Jan 5 at 8:26
  • 1
    \$\begingroup\$ @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\$. \$\endgroup\$ Jan 5 at 8:28

6 Answers 6

4
\$\begingroup\$

05AB1E, 28 bytes

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

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

Try it online or verify all m=1 test cases.

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)
\$\endgroup\$
0
4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.