13
\$\begingroup\$

This is a math problem which takes quite many things into question, making it rather challenging, and as you might have guessed, it's a code golf, so it should be as short as possible as well.

The input, n, is any integer number (should at least support integers, but needn't be limited to). The output is the average of:

  • n
  • The square of n
  • The closest prime number to n
  • The closest number to n in the Fibonacci sequence

Shortly, the program should print to the standard output channel the result of (n+(n*n)+closestPrime(n)+closestFib(n))/4.

You don't have to care about possible overflows etc. Normal floating point precision is also ok.

The way the input is given is completely up to you. Shortest program (in characters) wins, as always with code golfs.

In the case a tie occurs when you are looking for the closest, choose one of the following:

  1. Go up
  2. Go down
  3. Choose one randomly
\$\endgroup\$
  • \$\begingroup\$ Define "closest". How are ties broken? \$\endgroup\$ – Peter Taylor Apr 6 '11 at 18:53
  • \$\begingroup\$ @Peter Taylor: Move up, down, or choose one randomly. \$\endgroup\$ – Anto Apr 6 '11 at 18:55
  • \$\begingroup\$ Give some sample input/output to verify the solutions. \$\endgroup\$ – fR0DDY Apr 7 '11 at 3:26
  • \$\begingroup\$ When you say “mustn't be limited to”, what else must be supported? Or did you mean “needn't be limited to”? \$\endgroup\$ – Timwi Apr 10 '11 at 2:05
  • \$\begingroup\$ @Timwi! "needn't", sorry, will fix it \$\endgroup\$ – Anto Apr 10 '11 at 6:22
10
\$\begingroup\$

Python 160 Chars

p=lambda n:any(n%x<1for x in range(2,n))
N=input()
a=0;b=1
while b<N:a,b=b,a+b
c=d=N
while p(c)and p(d):c-=1;d+=1
print (N+N*N+[b,a][2*N-a-b<0]+[c,d][p(c)])/4.0

A little explanation about the closestFib part:

When the while loop ends a is smaller than N and b is either equal to or greater than N. Now the [b,a][2*N-a-b<0] part. Look at it as [b,a][(N-a)-(b-N)]. (N-a) is the difference between N and a and similarly (b-N) the difference between b and N. If the difference between these two is less than 0 it means a is closer to N and vice-versa.

\$\endgroup\$
  • \$\begingroup\$ Could you add an explanation of why is this working? \$\endgroup\$ – Quixotic Apr 9 '11 at 12:00
  • \$\begingroup\$ @Debanjan Anything specific, you wan't to know? I thought everything was self explanatary. :) \$\endgroup\$ – fR0DDY Apr 9 '11 at 15:54
  • \$\begingroup\$ Just the bit of nearest fib part [b,a][2*N-a-b<0] :) \$\endgroup\$ – Quixotic Apr 9 '11 at 20:02
7
\$\begingroup\$

GolfScript, 59 characters

~:N..*.,2>{:P{(.P\%}do(!},{{N-.*}$0=}:C~[1.{.@+.N<}do]C+++4/

This script does not fulfill some of the requirements:

  • It only works correctly for inputs n >= 2, otherwise it crashes.
  • The output is truncated to an integer.
  • Terrible performance for any moderately large n

A brief walkthrough of the code:

  1. ~:N..* The input is stored in N, and we push both n and the square n*n right away.
  2. .,2> We will generate a list of primes by filtering the array [2..n*n]. We use our previous calculation of n*n as a (very bad!) upper bound for finding a prime that is larger than n.
  3. {:P{(.P\%}do(!}, Our previous array is filtered by trial division. Each integer P is tested against every integer [P-1..1].
  4. {{N-.*}$0=}:C~ Sorts the previous array based on the distance to n, and grabs the first element. Now we have the closest prime.
  5. [1.{.@+.N<}do]C We generate Fibonnacis until we get one greater than n. Fortunately, this algorithm naturally keeps track of the previous Fibonnaci, so we throw them both in an array and use our earlier distance sort. Now we have the closest Fibonnaci.
  6. +++4/ Average. Note that GolfScript doesn't have support for floats, so the result is truncated.

GolfScript, 81 characters

Here is a variant that fulfills all of the requirements.

~:N..*2N*,3,|2,^{:P{(.P\%}do(!},{{N-.*}$0=}:C~[0.1{.@+.N<}do]C+++100:E*4/.E/'.'@E%

To ensure proper behavior for n<2, I avoid 2< (crashes when the array is small), and instead use 3,|2,^. This makes sure the prime candidate array is just [2] when n < 2. I changed the upper bound for the next prime from n*n to 2*n (Bertrand's postulate). Also, 0 is considered a Fibonnaci number. The result is calculated in fixed point math at the end. Interestingly, it seems like the result is always in fourths (0, .25, .5, .75), so I hope 2 decimal places of precision is sufficient.

My first crack at using GolfScript, I'm sure there is room for improvement!

\$\endgroup\$
  • 7
    \$\begingroup\$ You know, when dividing by 4 it's not terribly surprising you get fourths ;-) \$\endgroup\$ – Joey Apr 7 '11 at 12:46
  • \$\begingroup\$ ...indeed! +1 ;) \$\endgroup\$ – Mike Welsh Apr 7 '11 at 21:29
3
\$\begingroup\$

JavaScript, 190

function n(n)
{z=i(n)?n:0
for(x=y=n;!z;x--,y++)z=i(x)?x:i(y)?y:0
for(a=b=1;b<n;c=a+b,a=b,b=c);
return(n+n*n+(2*n-a-b<0?a:b)+z)/4}
function i(n)
{for(j=2;j<n;j++)
if(!(n%j))return 0
return 1}

[257]

function n(n)
{return(n+n*n+p(n)+f(n))/4}
function p(n)
{if(i(n))return n
for(a=b=n;;a--,b++){if(i(a))return a
if(i(b))return b}}
function i(n)
{for(j=2;j<n;j++)
if(!(n%j))return 0
return 1}
function f(n)
{for(a=b=1;b<n;c=a+b,a=b,b=c);
return 2*n-a-b<0?a:b}

Uncompressed:

function closest( a, b, c )
{
  return 2*a-b-c < 0 ? b : c;
}

function closestPrime( n )
{
  a=b=n;
  if (isPrime( n ) ) return n;
  while ( true )
  {
    a-=1;
    b+=1;
    if (isPrime(a))return a;
    if (isPrime(b))return b;
  }
}

function isPrime( n )
{
  for (i=2;i<n;i++)
  {
    if ( !( n % i ) ) return false;
  }
  return true;
}

function closestFib( n )
{
  for(fib1=0,fib2=1;fib2<n;fib3=fib1+fib2,fib1=fib2,fib2=fib3);
  return closest( n, fib1, fib2 );
}

function navg(n)
{
  n2 = n*n;
  np = closestPrime( n );
  nf = closestFib( n );
  return ( n + n2 + np + nf ) / 4;
}
\$\endgroup\$
  • \$\begingroup\$ For your closest prime function: I'm thinking you can save space if you use just a=0 and increment positively. Instead of checking isPrime for a and b, just check isPrime(n+a) and isPrime(n-a). You could probably mash it all into one crazy ternary statement, but I'm terrible with javascript. \$\endgroup\$ – Mr. Llama Mar 14 '12 at 20:00
  • \$\begingroup\$ The following seems to work pretty well: function closestPrime(n,o){return isPrime(n+o)?n+o:isPrime(n-o)?n-o:closestPrime(n,o+1);}. Call it as closestPrime(n,0) and it'll work itself out. Shorten as needed. \$\endgroup\$ – Mr. Llama Mar 14 '12 at 20:08
1
\$\begingroup\$

Mathematica, 70 69 bytes

One byte saved thanks to Sp3000 (sometimes built-ins aren't the best way to go).

((n=#)+#^2+(f=#&@@#@Range@Max[1,2n]~Nearest~n&)@Prime+f@Fibonacci)/4&

This defines an unnamed function taking an integer and producing the exact mean as a rational number. In the case of ties, the smaller prime/Fibonacci number is chosen.

This is very inefficient for large inputs, because it actually generates the first 2n primes and Fibonacci numbers before picking the closest.

\$\endgroup\$
  • \$\begingroup\$ #&@@# .. Huh? \$\endgroup\$ – seequ Apr 19 '15 at 15:08
  • \$\begingroup\$ @Sieg Starting from the right: # is the argument of a pure function (of f). This case, it's actually a function itself, since f is applied to Prime and Fibonacci. So that #@Range@... applies the given function to each integer in the range. Then #&@@ is just a golfed way to extract the first element of a list. It works by applying #& to the list, which is a function which merely returns its first argument. \$\endgroup\$ – Martin Ender Apr 19 '15 at 15:25
0
\$\begingroup\$

Q, 119

Not the most efficient.

{%[;4]x+(x*x)+((*:)a(&)b=min b:abs x-a:{x,sum -2#x}/[x-2;1 1])+(*:)d(&)e=min e:x-d:(&)1={(min x mod 2_(!)x)}each(!)x+2}
\$\endgroup\$
0
\$\begingroup\$

MATLAB 88 Chars

C=@(F)(F(abs(F-n)==min(abs(F-n))));(n+n^2+C(primes(n*2))+C(round(1.618.^(1:n)/2.236)))/4

n is your integer

Works with non integers, as far as I've tested it works with very large numbers as well, runs pretty damn quickly too.

\$\endgroup\$
0
\$\begingroup\$

Scala 299

object F extends App{type I=Int
def f(n:I,b:I=1,a:I=1):I=if(a>=n)if(a-n>n-b)b else a else f(n,a,b+a)
def p(n:I)=(2 to n-1).exists(n%_==0)
def i(n:I,v:I):Int=if(!p(n+v))n+v else i(n+v,v)
val a=readInt
println(({val p=Seq(-1,1).map(i(math.max(a,3),_))
if(a-p(0)>p(1)-a)p(1)else p(0)}+f(a)+a+a*a)/4.0)}

Test and invocation:

a  a² nP(a) nF  ∑   /4.0 
------------------------
-2  4   2   1   5   1.25
-1  1   2   1   3   0.75
0   0   2   1   3   0.75
1   1   2   1   5   1.25
2   4   2   2   10  2.5
3   9   2   3   17  4.25
4   16  3   5   28  7.0
5   25  3   5   38  9.5

The question talks about any Integer but the problem isn't that interesting for values below 0. However - how do we start? At 0? At 1? And what is the next prime for 11? 11 itself?

The idea to allow the next bigger or lower in case of a tie is bad, because it makes comparing needless difficult. If your results differ, they can have chosen the other fib, the other prime, the other fib and the other prime, or yours are wrong, or the result of the other person is wrong, or it is a combination: different choice, but wrong although, maybe both wrong.

\$\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.