15
\$\begingroup\$

Consider three number sequences, A, B and C:

  • A: A sequence based on recurrence relations, f(n) = f(n-1)+f(n-2), starting with f(1) = 3, f(2) = 4. So, the sequence begins like this: 3 4 7 11 18 29 47 76 ...
  • B: The composite numbers, that is all integers that aren't primes (or 1): 4 6 8 9 10 12 14 15 16 ...
  • C: The digits of Pi: 3 1 4 1 5 9 2 6 5 ...

Given a positive integer N < 50, either as function argument or STDIN, return the decimal value of the fraction A(N)/B(N) with C(N) digits after the decimal point. Normal rules for rounding applies (round up if the N+1'th digit is 5 or higher). If the Nth digit of pi is zero, an integer should be printed. scientific notation / Standard form is accepted for numbers higher than 1000.

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

Some examples:

N = 1: 0.750
N = 2: 0.7
N = 3: 0.8750
N = 4: 1.2
N = 6: 2.416666667
N = 10: 11.056
N = 20: 764.8750

Of course, standard code golf rules applies.

The function must terminate in less than two minutes on any modern laptop.

\$\endgroup\$
  • \$\begingroup\$ When you say C(n) digits, do we have to include trailing 0's? \$\endgroup\$ – Maltysen Sep 3 '15 at 19:19
  • \$\begingroup\$ To which input does the time limit apply? \$\endgroup\$ – Dennis Sep 3 '15 at 19:33
  • \$\begingroup\$ @Dennis, do you mean to which N? If so, up to N = 49. Or something else? \$\endgroup\$ – Stewie Griffin Sep 3 '15 at 19:36
  • \$\begingroup\$ JavaScript has a limited floating point accuracy of 16. Past that you'll start getting inaccurate results. Is this okay? \$\endgroup\$ – Downgoat Sep 3 '15 at 22:08
  • 1
    \$\begingroup\$ @vihan My solution (unpublished ATM) stores the first 49 digits of pi in a string. And you don't need any more than 9 digits of accuracy in the result, if you're worried about that. \$\endgroup\$ – ETHproductions Sep 3 '15 at 23:26
9
\$\begingroup\$

Pyth, 60 57 58 bytes

.[K`.Rchu,eGsGQjT7e.ftPZQ)Je/u+/*GHhyHy^TQr^T3ZZT\0+xK\.hJ

Test harness

It's pretty straightforward - calculate pi, the fibonacci series and the composites, round to C(n) digits, pad to C(n) digits plus the location of the decimal point digits, done.

A(n): hu,eGsGQjT7

B(n): e.ftPZQ)

C(n): e/u+/*GHhyHy^TQr99ZZT

60 -> 57: Cleaned up the n = 1 special case in the pi calculation.

57 -> 58: Wasn't using high enough precsion for pi for the entire input range - increased 99 iterations to 1000 iterations.

Note on rounding: This uses Python's "nearest even" rounding system, rather than the OP specified "towards infinity" system. However, the difference only matters if the digits immediately following the rounding point are 5000..., e.g. 1.25 rounded to 1 digit. I checked the input range, and this never happens, so the correct result is alway returned.

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

PowerShell, 420 Bytes (ayyyyyyyy) 378 Bytes

param($n);[int[]]$p="03141592653589793238462643383279502884197169399375"-Split'';$a=@(0,3,4);for($i=3;$i-lt50;$i++){$a+=$a[$i-1]+$a[$i-2]};$c=[char[]]"00001010111010111010111011111010111110111010111011111011111010111110111";$b=@(0);for($i=4;$i-le70;$i++){if($c[$i]-eq'1'){$b+=$i}};[double]$r=$a[$n]/$b[$n];$q=$p[$n+1];$s="";(0..($q-1))|%{$s+="0"};([math]::Round($r,$q,[MidpointRounding]::AwayFromZero)).ToString("0.$s")

Thanks to isaacg for saving 41 bytes, for calculating how the question does rounding. Means I didn't have to include the horrendous [MidpointRounding]::AwayFromZero and didn't need to explicitly cast as a [double].

This one was great fun!

Expanded:

# Take input N
param($n)

# First digits of pi, stored as integer array
[int[]]$p="03141592653589793238462643383279502884197169399375"-Split''

# Fibonacci sequence A(N)
$a=@(0,3,4)
for($i=3;$i-lt50;$i++){
  $a+=$a[$i-1]+$a[$i-2]
}

# Zero-indexed bitmask for if the n-th integer is composite (1) or not (0)
$c=[char[]]"00001010111010111010111011111010111110111010111011111011111010111110111"

# Populate B(N) as an array using the $c mask
$b=@(0)
for($i=4;$i-le70;$i++){
  if($c[$i]-eq'1'){
    $b+=$i
  }
}

# Calculation Time!
$r=(a($n))/$b[$n]

# A small golf, as $p[$n+1] gets used a couple times
$q=$p[$n+1]

# Need to generate a string of zeroes for padding
$s=""
(0..($q-1))|%{$s+="0"}

# Round the number, then send it to a string so we get the necessary number of zeroes
([math]::Round($r,$q)).ToString("0.$s")

Recursion in PowerShell is ... slow, shall we say, so we have to build A(N) the other direction and store it into an array, then index it.


OLD

Also, holy cow, did the output requirements kill this. PowerShell defaults to rounding-to-nearest a/k/a banker's rounding, which necessitates utilizing the extraordinarily verbose [MidpointRounding]::AwayFromZero to switch rounding styles. On top of that, we then needing to pad trailing zeroes, if any. Those two requirements combined to turn the last couple of lines from 20 Bytes [math]::Round($r,$q) to 102 Bytes (from the $s="" to +$s)) ... wow.

\$\endgroup\$
  • \$\begingroup\$ Great description/commenting! 32 chars for [MidpointRounding]::AwayFromZero alone is almost too good/bad to be true... =) \$\endgroup\$ – Stewie Griffin Sep 4 '15 at 18:17
  • 1
    \$\begingroup\$ See my note on rounding in my answer. PowerShell default rounding should be fine. \$\endgroup\$ – isaacg Sep 4 '15 at 18:31
1
\$\begingroup\$

Javascript (ES6), 302 bytes

One word: Unfinished.

x=>{a=[0,3,4],b=[0],c='03141592653589793238462643383279502884197169399375';for(i=1;i<x;a[i+2]=a[i]+a[++i]);for(i=1,p=[];++i<70;v=p.every(x=>i%x),(v?p:b).push(i));r=''+Math.round(a[x]/b[x]*(l=Math.pow(10,c[x])))/l;if(x==33)return r;r.indexOf`.`<0&&(r+='.');while(!r[r.indexOf`.`+ +c[x]])r+='0';return r}

The first 49 digits of pi are stored in a string, and the other two sequences are auto-generated. This has been golfed about halfway; I'm (almost) sure I could squeeze another 50 bytes out of it.

Works for all the test cases, and should work for the rest. Crashes on anything more than 49 or less than 0 (it should never encounter these situations anyway). I especially like its result for 0:

NaN.
\$\endgroup\$
  • \$\begingroup\$ Why is this unfinished? \$\endgroup\$ – Beta Decay Sep 6 '15 at 9:16
  • \$\begingroup\$ @BetaDecay I meant I haven't finished golfing it yet. I will as soon as I have the time. \$\endgroup\$ – ETHproductions Sep 8 '15 at 1:45
1
\$\begingroup\$

Octave, 276 236 Bytes

First of all I thought it would be cool to make use of some unlimited accuracy in these mathematical tools (and to refresh some knowledge about it) so I started writing some algorithms and then ended finally found out that the pi value is not so accurate that I will have to use the array again. So again, no great success:

function c(A)p="3141592653589793238462643383279502884197169399375";f=ones (1,50);f(1)=3;f(2)=4;for i=3:53f(i)=f(i-1)+f(i-2);end
i=0;x=1;while i<A
x++;for j=2:x/2
if mod(x,j)==0 i++;break;end end end
printf(["%." p(A) "f\n"],f(A)/x);end

Still quite readable, isn't it?

Usage

copy-paste function into octave, call function c with argument of required value:

>>> c(1)
0.750
>>> c(49)
407880480.04348

Optimizations:

  • Substitute endif, endfor and similar with end which works the same way
  • decreasing variable i by one save one byte
  • remove num2str(str2num(p(A))) nonsense :)
\$\endgroup\$
  • \$\begingroup\$ I like that you posted a Octave solution (I'm a MATLAB guy myself!). Note that this code is Octave only, not MATLAB. MATLAB uses end, not endif, so many bytes saved. If you also happen to have the symbolic toolbox for MATLAB, you can use vpa to get enough decimal points for pi: vpa(sym(pi),49). I don't have it at this laptop, so I'm not sure if the sym is necessary there, but should save quite some bytes anyways =) And readable is not necessarily a good thing in code golf =) \$\endgroup\$ – Stewie Griffin Sep 5 '15 at 22:47
  • \$\begingroup\$ x++ is also not a MATLAB command. I didn't know there were such large differences between the two... IMO, it shouldn't be. I think all code written in Octave should be portable to MATLAB (but not necessarily the other way around as MATLAB has more options). \$\endgroup\$ – Stewie Griffin Sep 5 '15 at 22:54
  • \$\begingroup\$ Approved your edit. I don't have matlab around here so I was unable to test it. I was searching for solution to get more pi decimals in octave, but nothing was shorter than just array, unfortunately. But ommiting while from endwhile and similar works fine, so I'm updating the answer with few less characters :) \$\endgroup\$ – Jakuje Sep 6 '15 at 7:32

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.