18
\$\begingroup\$

You should have heard about the Fibonacci Numbers, often called the Fibonacci Sequence. In this sequence the first two terms are 0 and 1, and every number after the first two is the sum of the two preceding ones. In other words, F(n) = F(n-1) + F(n-2).

Here are the first 20 Fibonacci numbers:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

Task:

Given an integer x, compute the arithmetic mean (the average) of the prime Fibonacci Numbers up to the x number of the Fibonacci Sequence.

Rules:

  • the Fibonacci sequence starts with 0 and 1 for this challenge
  • 3 < x < 40, because higher values of x might cause some huge execution time or overflows and smaller values have no output
  • 1 is NOT prime, since it only has 1 divisor
  • the arithmetic mean should include decimals, if it's the case, or should be displayed as an exact fraction
  • you are only allowed to take x as input and the code needed to take the input does not count (e.g: if you need something like x = input(), you should not take it into consideration when counting the bytes)

Examples:

Ex. 1: For x=10, the output is 5.75, because the 10th Fibonacci number is 55 and the prime Fibonacci numbers up to 55 are 2, 3, 5, 13, their average being 5.75

Following the explanation from example 1, other examples are:

Ex. 2: For x=15, the output is 57.5

Ex. 3: For x=20, the output is 277.428571428571, or any other close approximation. In this case 277.4286, for instance, is an accepted value

Ex. 4: For x=11, the output is 22.4

Ex. 5: For x=30, the output is 60536.4444444444, or any other close approximation, such as 60536.444


Leaderboard:

var QUESTION_ID=112025,OVERRIDE_USER=59487;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>


To change the leader, submit a shorter valid solution. Your code should be as short as possible, since this is , so the shortest answer in bytes wins. Good luck!

\$\endgroup\$
  • \$\begingroup\$ Can the result be returned as an exact fraction instead of a rounded decimal? \$\endgroup\$ – Martin Ender Mar 4 '17 at 18:07
  • \$\begingroup\$ Yes of course, as long as it is the correct value. Edited the question :)) \$\endgroup\$ – Mr. Xcoder Mar 4 '17 at 18:07
  • \$\begingroup\$ If the answer is given as a fraction, does the fraction have to be reduced? \$\endgroup\$ – DLosc Mar 5 '17 at 6:02
  • \$\begingroup\$ That's up to you. You can reduce it if you want, but I don't think that's necessary. \$\endgroup\$ – Mr. Xcoder Mar 5 '17 at 6:51
  • \$\begingroup\$ Please update accepted answer. \$\endgroup\$ – Erik the Outgolfer Mar 5 '17 at 11:02

17 Answers 17

5
\$\begingroup\$

Actually, 10 bytes

Code:

R♂F;Mr♂P∩æ

Explanation:

R            # On the input, create the range [1 .. input].
 ♂F          # Map the nth Fibonacci command over it.
   ;M        # Duplicate and get the maximum of the list.
     r       # Create the range [0 .. maximum - 1].
      ♂P     # Map the nth prime operator over each element (zero-indexed).
        ∩    # Intersection of both.
         æ   # Get the mean and implicitly display.

Uses the CP-437 encoding. Try it online!

\$\endgroup\$
  • \$\begingroup\$ Wow, done such a job in just 10 bytes. Impressive! \$\endgroup\$ – Mr. Xcoder Mar 5 '17 at 12:42
12
\$\begingroup\$

Python 2, 71 bytes

s=2.;a=b=c=1
exec"p=2**a%a==2;c+=p;s+=a*p;a,b=b,a+b;"*input()
print s/c

Try it online!

Python doesn't have useful arithmetic built-ins for this, so we do things by hand. The code iterates through Fibonacci numbers via a,b=b,a+b starting from a=b=1.

The Fermat primality test with base 2 is used to identify primes as a where 2^a == 2 (mod a). Though this only checks for probable primes, none of the false positives are within the first 40 Fibonacci numbers.

The current sum s and count c of primes are updated each time a prime is encountered, and their ratio (the mean) is printed at the end. Because the prime check misses a=2 and it's guaranteed to be in the input range, the sum starts at 2 and the count starts at 1 to compensate.

\$\endgroup\$
8
\$\begingroup\$

Jelly, 11 bytes

ÆḞ€ÆPÐfµS÷L

Try it online!

How it works

ÆḞ€ÆPÐfµS÷L  Main link. Argument: n (integer)

ÆḞ€          Map the Fibonacci atom over [1, ..., n].
   ÆPÐf      Filter by primality.
       µ     Begin a new chain. Argument: A (array of Fibonacci primes)
        S    Yield the sum of A.
          L  Yield the length of A.
         ÷   Compute the quotient.
\$\endgroup\$
  • 11
    \$\begingroup\$ A solid 2 of 3 on math built-ins. Fibonacci, check. Primality, check. Arithmetic mean, nope. \$\endgroup\$ – xnor Mar 4 '17 at 18:06
  • \$\begingroup\$ I have changed the accepted answer, because a shorter one was posted. \$\endgroup\$ – Mr. Xcoder Mar 5 '17 at 12:33
7
\$\begingroup\$

Mathematica, 38 bytes

Mean@Select[Fibonacci@Range@#,PrimeQ]&

(* or *)

Mean@Select[Fibonacci~Array~#,PrimeQ]&

Explanation

Mean@Select[Fibonacci@Range@#,PrimeQ]&  
                                     &  (* For input # *)
                      Range@#           (* List {1, 2, 3, ... #} *)
            Fibonacci@                  (* Find the corresponding fibonacci numbers *)
     Select[                 ,PrimeQ]   (* Select the prime terms *)
Mean@                                   (* Take the Mean *)
\$\endgroup\$
  • 2
    \$\begingroup\$ I think you want # and not #-1: the OP says that 55 is the 10th Fibonacci number, so their list must be 0-indexed (as is the best convention). Compare your output for inputs 10 and 11 with the OP. Fortunately this actually saves you three bytes! \$\endgroup\$ – Greg Martin Mar 4 '17 at 19:49
  • \$\begingroup\$ You can drop the & and replace # with x (question says that input taking code is not scored) \$\endgroup\$ – CalculatorFeline Jul 5 '17 at 17:03
6
\$\begingroup\$

Perl 6, 51 bytes

{sum($/=[grep *.is-prime,(0,1,*+*...*)[0..$_]])/$/}

Try it

Expanded:

{
  sum(
    $/ = [                # store as an Array in $/

      grep
        *.is-prime,       # find the primes
        (
          0, 1, *+* ... * # Fibonacci sequence
        )[ 0 .. $_ ]      # grab the indicated values in the sequence

    ]
  )

  /

  $/   # use the Array as a number (elems)
}
\$\endgroup\$
5
\$\begingroup\$

MATL, 16 bytes

lOi:"yy+]vtZp)Ym

Try it online!

Explanation

lO     % Push 1, then 0. This way the generated numbers with indices 1, 2, 3, ...
       % will be 1, 1, 2, ... as required
i      % Input n
:"     % Do the following n times
  yy   %   Duplicate top two numbers
  +    %   Add
]      % End
v      % Concatenate all numbers into a column vector
t      % Duplicate
Zp     % Vector of logical values: true for prime numbers, false otherwise
)      % Apply that vector as an index. This keeps only prime numbers
Ym     % Mean. Implicitly display
\$\endgroup\$
4
\$\begingroup\$

Octave, 75 71 bytes

@(n)mean((t=fix(((1+(s=5^.5)).^(x=1:n)-(1-s).^x)/s./2.^x))(isprime(t)))

Anonymous function that uses Binet's formula. Input and output are in the form of function arguments.

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ +1 for the interesting use of Binet's formula, combined with the built-in isprime which is perfect for this challenge. \$\endgroup\$ – Mr. Xcoder Mar 4 '17 at 18:38
4
\$\begingroup\$

Maxima, 49 bytes

f(n):=mean(sublist(makelist(fib(x),x,n),primep));
\$\endgroup\$
4
\$\begingroup\$

Prolog (SWI), 269 264 254 218 bytes

  • Thanks to Fatalize for saving 37 bytes!
  • Thanks to Emigna for saving 9 bytes!

I'm fairly certain that I could golf some more bytes down.

X/X:-X<3.
N/R:-A is N-1,B is N-2,A/C,B/D,R is C+D.
2^0^0.
C^S^E:-G is C-1,G/M,G^Q^R,(p(M)->S=M+Q,E is R+1;S=Q,E is R).
a(X,S):-X^R^Q,S is R/Q.
p(N):-N*(N-1).
p(2).
p(3).
N*2:-N mod 2=\=0.
N*C:-N mod C=\=0,D is C-1,N*D.

Run it as a(15, R). for x = 15, R is the output variable.

Try it online!


A more readable version:

fibonacci(1, 1) :- !.
fibonacci(2, 2) :- !.

fibonacci(N, R) :-
  N0 is N - 1,
  N1 is N - 2,
  fibonacci(N0, R1),
  fibonacci(N1, R2),
  R is R1 + R2.

listed(2, 0, 0) :- !.

listed(C, S, Successes) :-
  C0 is C - 1,
  fibonacci(C0, Result),
  listed(C0, S0, S1),
  (
    is_prime(Result)
    ->
      S = Result + S0, Successes is S1 + 1
    ; S = S0, Successes is S1
  ).

f(X, S) :-
  listed(X, R, Q),
  S is R / Q.

is_prime(Num) :- is_prime(Num, Num - 1).

is_prime(2).
is_prime(3).

is_prime(Num, 2) :- Num mod 2 =\= 0, !.

is_prime(Num, C) :-
  Num mod C =\= 0,
  C0 is C - 1,
  is_prime(Num, C0).
\$\endgroup\$
  • 1
    \$\begingroup\$ Golfing in SWI Prolog is golden (and very hard), so nice work! \$\endgroup\$ – Mr. Xcoder Mar 4 '17 at 19:30
  • \$\begingroup\$ I'm pretty sure things like N*C:- is allowed for head declarations in PPCG, which can save you some bytes. \$\endgroup\$ – Fatalize Mar 6 '17 at 7:32
  • \$\begingroup\$ @Fatalize I just learned this programming language about a week ago, so I'm not sure what you mean :p. Do you mean to substitute p(N,C):- with N*C:-? \$\endgroup\$ – Adnan Mar 6 '17 at 20:40
  • \$\begingroup\$ @Adnan Exactly! \$\endgroup\$ – Fatalize Mar 7 '17 at 7:14
  • \$\begingroup\$ @Fatalize Oohhh, that's really neat! Thanks :). \$\endgroup\$ – Adnan Mar 8 '17 at 10:06
3
\$\begingroup\$

Röda, 98 94 93 bytes

f n{z=0;i=1;j=1;s=0;seq 2,n-1|{|_|c=i+j;i=j;j=c;seq 2,c-1|{z+=1;s+=c}if[c%p>0]()for p}_[s/z]}

It's a function that returns the result as a floating point number.

Ungolfed version:

function f(n) {
    i = 1
    j = 1
    sum = 0
    num = 0
    seq(2, n-1) | for _ do
        /* calculate next fibonacci number: */
        c = i+j
        i = j
        j = c
        /* if it's prime: */
        {
            num += 1
            sum += c
        /* primality test: */
        } if [c%p > 0]() for p in [seq(2, c-1)]
    done
    return sum/num
}
\$\endgroup\$
  • \$\begingroup\$ Can you do c%p>0 instead of c%p!=0? \$\endgroup\$ – Cows quack Mar 5 '17 at 18:06
  • \$\begingroup\$ @KritixiLithos Yes! Thank you. \$\endgroup\$ – fergusq Mar 5 '17 at 18:09
3
\$\begingroup\$

05AB1E, 13 bytes

!ÅF¹£DpÏDOsg/

Try it online! or as a Test suite

Explanation

!ÅF             # get a list of fibonacci numbers up to fac(input)
   ¹£           # take the first input elements of that list
     D          # duplicate
      p         # isprime on the copy
       Ï        # keep the fibonacci numbers which are true in the isprime list
        D       # duplicate the list of fibonacci primes
         O      # sum the list
          s     # swap the other copy to the top of the stack
           g    # get its length
            /   # divide sum by length
\$\endgroup\$
2
\$\begingroup\$

Pyke, 11 bytes

S.b#_P)'sl/

Try it online!

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

dc, 129 bytes

?sa0sb1sd0ss0sz[[lF1+sF]sqlelG!=q]si[ls+sslz1+sz]sw[lddlb+dsdrsbdsG2se0sF[lGdle%0=ile1+dse<p]dspxlF0=wla1-dsa1<c]dscxEkls1-lz1-/p

A Fibonacci number generator and primality checker all in one. Nice.

Try it online!

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

Japt, 14 bytes

ò@MgXÃfj
x /Ul

Test it


Explanation

Implicit input of integer U.
30

ò

Generate an array of integers from 0 to U inclusive.
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]

@   Ã

Pass each integer through a function.

MgX

Get the Xth Fibonacci number, where X is the current element.

[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040]

fj

Filter (f) the array to those elements that return truthy when checked for primality (j). Implicitly assign the resulting array to variable U.
[2,3,5,13,89,233,1597,28657,514229]

x

Reduce the array by summing.
544828

/Ul

Divide the result by the array's length (l) and implicitly output the result.
60536.444444444445

\$\endgroup\$
  • \$\begingroup\$ Wow, I love new answers to old questions. Also close to the other golfing languages, so +1. \$\endgroup\$ – Mr. Xcoder Jul 5 '17 at 17:02
1
\$\begingroup\$

perl, 91 bytes

$b=1;map{($a,$b)=($b,$a+$b),$p=("x"x$b)!~/^(.|(..+)\2+)$/,$s+=$b*$p,$c+=$p}2..$x;print$s/$c

Cuold have been 8 bytes shorter if the modulo pseudoprime test worked as well in perl as in the python answer:

$b=1;$s=2;map{($a,$b)=($b,$a+$b),$p=2**$b%$b==2,$s+=$b*$p,$c+=$p}2..$x;print$s/++$c

...but this gives wrong answer for input > 16 in perl.

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

Axiom, 104 bytes

g(n)==(y:=x:=r:=0;repeat(x>n=>break;j:=fibonacci(x);x:=x+1;if prime?(j)then(r:=r+j;y:=y+1));y=0=>-1;r/y)

ungolfed, test code and results

f(n)==
  y:=x:=r:=0
  repeat
     x>n=>break
     j:=fibonacci(x)
     x:=x+1
     if prime?(j) then(r:=r+j;y:=y+1)
  y=0=>-1
  r/y

(3) -> [[i,g(i)::Float] for i in [1,2,3,10,15,20,11,30,50]]
   Compiling function g with type PositiveInteger -> Fraction Integer
   (3)
   [[1.0,- 1.0], [2.0,- 1.0], [3.0,2.0], [10.0,5.75], [15.0,57.5],
    [20.0,277.4285714285 7142857], [11.0,22.4], [30.0,60536.4444444444 44444],
    [50.0,309568576.1818181818 2]]

i try to duplicate the matematica, octave etc languages entry, if one not count the mean() function, to implement it would be here 62 bytes so good too

mean(a:List Float):Any== 
    i:=1; s:=0.0
    repeat  
       if~index?(i,a)then break
       s:=s+a.i
       i:=i+1
    i=1=>[]
    s/(i-1)

--62 bytes
f(x:NNI):Any==mean(select(prime?,[fibonacci(i)for i in 1..x]))
\$\endgroup\$
1
\$\begingroup\$

JavaScript ES6, 137 136 118 113 bytes

m=

n=>(a=[],(f=x=>a[x]=x<2?x:f(--x)+f(--x))(n),eval((a=a.filter(x=>eval("for(y=x;x%--y;);y==1"))).join`+`)/a.length)

console.log(m(10))
console.log(m(15))
console.log(m(20))
console.log(m(11))
console.log(m(30))


History

118 bytes

n=>(a=[0,1,1],(f=x=>a[--x]=a[x]||f(x)+f(--x))(n),eval((a=a.filter(x=>eval("for(y=x;x%--y;);y==1"))).join`+`)/a.length)

136 bytes

n=>(a=[0,1,1],(f=x=>a[--x]=a[x]||f(x)+f(--x))(n),eval((a=a.filter(x=>x>1&&!Array(x).fill().some((i,j)=>j>1&&!(x%j)))).join`+`)/a.length)

137 bytes

n=>(a=[0,1,1],(f=x=>a[--x]=a[x]||f(x)+f(--x))(n),eval((a=a.filter(x=>{d=x;while(--d>1)if(!(x%d))return 0;return x>1})).join`+`)/a.length)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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