Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a positive integer n output the integers a and b (forming reduced fraction a/b) such that:

Formula a/b = product of k=1 to n: (p_k^2 - 1) / (p_k^2 + 1)

Where pk is the k th prime number (with p1 = 2).

Examples:

1   -> 3, 5
2   -> 12, 25
3   -> 144, 325
4   -> 3456, 8125
5   -> 41472, 99125
15  -> 4506715396450638759507001344, 11179755611058498955501765625
420 -> very long

Probabilistic prime checks are allowed, and it's ok if your answer fails due to limitations in your language's integer type.


Shortest code in bytes wins.

share|improve this question
    
Can we also output 3.0 instead of 3? – Adnan Mar 23 at 16:00
2  
@AandN I guess... Make sure your program is correct for all inputs though, and does not suffer from floating point errors for big inputs. – orlp Mar 23 at 16:06
    
Can we output a and b as a rational type? – Alex A. Mar 24 at 0:31
2  
@AlexA. Only if the output clearly shows both integers. – orlp Mar 24 at 0:48
1  
@SamYonnou Those already exist, but abusing native number types to trivialize a problem is one of the loopholes that are forbidden by default. – Dennis Mar 25 at 3:46

13 Answers 13

Mathematica, 32 bytes

1##&@@(1-2/(Prime@Range@#^2+1))&

An unnamed function that takes integer input and returns the actual fraction.

This uses the fact that (p2-1)/(p2+1) = 1-2/(p2+1). The code is then golfed thanks to the fact that Mathematica threads all basic arithmetic over lists. So we first create a list {1, 2, ..., n}, then retrieve all those primes and plug that list into the above expression. This gives us a list of all the factors. Finally, we multiply everything together by applying Times to the list, which can be golfed to 1##&.

Alternatively, we can use Array for the same byte count:

1##&@@(1-2/(Prime~Array~#^2+1))&
share|improve this answer
    
1-2=1, right? – CalculatorFeline Mar 23 at 18:07
    
@CatsAreFluffy Yeah (-1 actually), but 1-2/x ≠ -1/x. ;) – Martin Ender Mar 23 at 18:08
    
@Range@±~Array~ – CalculatorFeline Mar 23 at 18:37

Python 2, 106 bytes

from fractions import*
n=input()
F=k=P=1
while n:b=P%k>0;n-=b;F*=1-Fraction(2*b,k*k+1);P*=k*k;k+=1
print F

The first and fourth lines hurt so much... it just turned out that using Fraction was better than multiplying separately and using gcd, even in Python 3.5+ where gcd resides in math.

Prime generation adapted from @xnor's answer here, which uses Wilson's theorem.

share|improve this answer

M, 9 bytes

RÆN²‘İḤCP

Try it online!

Trivia

Meet M!

M is a fork of Jelly, aimed at mathematical challenges. The core difference between Jelly and M is that M uses infinite precision for all internal calculations, representing results symbolically. Once M is more mature, Jelly will gradually become more multi-purpose and less math-oriented.

M is very much work in progress (full of bugs, and not really that different from Jelly right now), but it works like a charm for this challenge and I just couldn't resist.

How it works

RÆN²‘İḤCP  Main link. Argument: n

R          Range; yield [1, ..., n].
 ÆN        Compute the kth primes for each k in that range.
   ²‘      Square and increment each prime p.
     İ     Invert; turn p² + 1 into the fraction 1 / (p² + 1).
      Ḥ    Double; yield 2 / (p² + 1).
       C   Complement; yield 1 - 2 / (p² + 1).
        P  Product; multiply all generated differences.
share|improve this answer
    
Is ÆN the only M-specific operator? Also Melly – CalculatorFeline Apr 11 at 16:54
    
None of these operators are specific to M. The difference is that M calculates a fraction, while Jelly calculates a floating point number. – Dennis Apr 11 at 16:55

Ruby, 122 77 65 bytes

Thanks to Sherlock for shaving off 10 bytes.

require'prime'
->n{Prime.take(n).map{|x|1-2r/(x*x+1)}.reduce(:*)}

Defines an anonymous function that takes a number and returns a Rational.

share|improve this answer

Jelly, 14 13 bytes

RÆN²µ’ż‘Pµ÷g/

Try it online! Thanks to @Dennis for -1 byte.

R                       Range [1..n]
 ÆN                     Nth prime
   ²                    Square
    µ                   Start new monadic chain
     ’ż‘                Turn each p^2 into [p^2-1, p^2+1]
        P               Product
         µ              Start new monadic chain
          ÷             Divide by...
           g/           Reduce GCD
share|improve this answer

Pyth, 26 25

/RiFN=N*MCm,tdhd^R2.fP_ZQ

Try it here or run the Test Suite.

1 byte saved thanks to Jakube!

Pretty naive implementation of the specifications. Uses the spiffy "new" (I have no idea when this was added, but I've never seen it before) P<neg> which returns whether the positive value of a negative number is prime or not. Some of the mapping, etc can probably be golfed...

share|improve this answer

PARI/GP, 33 bytes

n->prod(i=1,n,1-2/(prime(i)^2+1))

Alternate version (46 bytes):

n->t=1;forprime(p=2,prime(n),t*=1-2/(p^2+1));t

Non-competing version giving the floating-point (t_REAL) result (38 bytes):

n->prodeuler(p=2,prime(n),1-2/(p^2+1))
share|improve this answer

Julia, 59 42 bytes

n->prod(1-big(2).//-~primes(2n^2)[1:n].^2)

This is an anonymous function that accepts an integer and returns a Rational with BigInt numerator and denominator.

We begin by generating the list of prime numbers less than 2n2 and selecting the first n elements. This works because the nth prime is always less than n2 for all n > 1. (See here.)

For each p of the n primes selected, we square p using elementwise power (.^2), and construct the rational 2 / (p + 1), where 2 is first converted to a BigInt to ensure sufficient precision. We subtract this from 1, take the product of the resulting array of rationals, and return the resulting rational.

Example usage:

julia> f = n->prod(1-big(2).//-~primes(2n^2)[1:n].^2)
(anonymous function)

julia> f(15)
4506715396450638759507001344//11179755611058498955501765625

Saved 17 thanks to Sp3000!

share|improve this answer

Convex, 28 bytes

Convex is a new language that I am developing that is heavily based on CJam and Golfscript. The interpreter and IDE can be found here. Input is an integer into the command line arguments. Indexes are one-based. Uses the CP-1252 encoding.

,:)_{µ²1-}%×\{µ²1+}%׶_:Ðf/p

You may or may not consider this answer to be competing since I was working on a few features that this program uses before the challenge was posted, but the commit was made once I saw this challenge go out.

share|improve this answer

MATL, 18 bytes

:Yq2^tqpwQpZd1Mhw/

Try it online!

Fails for large inputs because only integers up to 2^52 can be accurately represented internally.

Explanation

:     % implicitly take input n. Generate range [1,...,n]
Yq    % first n prime numbers
2^    % square
tqp   % duplicate. Subtract 1. Product
wQp   % swap. Add 1. Product
Zd    % gcd of both products
1M    % push the two products again
h     % concatenate horizontally
w/    % swap. Divide by previously computed gcd. Implicitly display
share|improve this answer

Mathematica, 45 bytes

Times@@Array[(Prime@#^2-1)/(Prime@#^2+1)&,#]&

Primes? Fractions? Mathematica.

share|improve this answer

Haskell, 53 bytes

Anonymous function, 53 characters:

(scanl(*)1[1-2%(p*p+1)|p<-nubBy(((>1).).gcd)[2..]]!!)

Try it here (note: in standard GHCi you need first to make sure Data.Ratio and Data.List are imported):

λ (scanl(*)1[1-2%(p*p+1)|p<-nubBy(((>1).).gcd)[2..]]!!) 5
41472 % 99125
:: Integral a => Ratio a

Haskell's list indexing !! is 0-based. (___!!) is an operator section, forming an anonymous function so that (xs !!) n == xs !! n.

It's four bytes less to generate the whole sequence:

λ mapM_ print $ take 10 $     -- just for a nicer output
    scanl(*)1[1-2%(n*n+1)|n<-[2..],all((>0).rem n)[2..n-1]]
1 % 1
3 % 5
12 % 25
144 % 325
3456 % 8125
41472 % 99125
3483648 % 8425625
501645312 % 1221715625
18059231232 % 44226105625
4767637045248 % 11719917990625
:: IO ()
share|improve this answer

Seriously, 25 bytes

,r`PªD;⌐k`M┬`π`Mi│g;)@\)\

Outputs a\nb (\n is a newline). Large inputs will take a long time (and might fail due to running out of memory) because prime generation is pretty slow.

Try it online!

Explanation:

,r`PªD;⌐k`M┬`π`Mi│g;)@\)\
,r                         push range(input)
  `PªD;⌐k`M                map:
   P                         k'th prime
    ª                        square
     D                       decrement
      ;                      dupe
       ⌐                     add 2 (results in P_k + 1)
        k                    push to list
           ┬               transpose
            `π`M           map product
                i│         flatten, duplicate stack
                  g;)      push two copies of gcd, move one to bottom of stack
                     @\    reduce denominator
                       )\  reduce numerator
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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