17
\$\begingroup\$

Generate the nth Narayana-Zidek-Capell number given an input n. Fewest bytes win.

f(1)=1, f(n) is the sum of the previous floor(n/2) Narayana-Zidek-Capell terms.

Test Cases:

f(1)=1

f(9)=42

f(14)=1308

f(15)=2605

f(23)=664299
\$\endgroup\$
  • 12
    \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! This is a nice first challenge. Though it's ultimately up to you, typically we recommend waiting at least a week to accept an answer. Having an accepted answer early on can send a signal to other users that the challenge is more or less over, which discourages them from participating. \$\endgroup\$ – Alex A. Jul 11 '16 at 20:27

16 Answers 16

6
\$\begingroup\$

Jelly, 11 10 bytes

HĊrµṖ߀Sȯ1

Try it online!

Takes n as argument and prints the result.

Explanation

H              divide input by 2
 Ċ             round up to get first n to recurse
  r            inclusive range from that to n
   µ           (chain separator)
    Ṗ          remove n itself from the range
     ߀        call self recursively on each value in the range
       S       sum results
        ȯ1     if sum was zero, return one
\$\endgroup\$
7
\$\begingroup\$

Ruby, 34 32 bytes

This uses a formula from the OEIS page for the Narayana-Zidek-Cappell numbers.

Edit: Got rid of parentheses using operator precedence with thanks to feersum and Neil.

f=->x{x<4?1:2*f[x-1]-x%2*f[x/2]}
\$\endgroup\$
  • \$\begingroup\$ Surely you don't need parentheses for x%2? \$\endgroup\$ – feersum Jul 11 '16 at 13:43
  • \$\begingroup\$ Well, not if you put x%2* at least. \$\endgroup\$ – Neil Jul 11 '16 at 13:48
  • \$\begingroup\$ @feersum and Neil Thank you both \$\endgroup\$ – Sherlock9 Jul 11 '16 at 13:50
  • \$\begingroup\$ Previous question edits suggested that the formula was x<2?... this makes it much clearer thanks! \$\endgroup\$ – Neil Jul 11 '16 at 13:50
6
\$\begingroup\$

Python 2, 48 42 38 36 bytes

Algorithm taken from the OEIS page. n<3 may be changed to n<4 with no effect. Returns the nth number, where n is a positive integer.

a=lambda n:n<3or 2*a(n-1)-n%2*a(n/2)

Try it online

\$\endgroup\$
5
\$\begingroup\$

05AB1E, 16 bytes

An iterative solution as 05AB1E doesn't have functions.

X¸sGDN>;ï£Os‚˜}¬

X¸               # initialize a list with 1
  sG          }  # input-1 number of times do
    D            # duplicate current list
     N>;ï£       # take n/2 elements from the list
          O      # sum those elements
           s‚˜   # add at the start of the list
               ¬ # get the first element and implicitly print

Try it online

\$\endgroup\$
5
\$\begingroup\$

C, 38

A translation of the OEIS algorithm. There's just not enough C code around here!

f(n){return n<3?:2*f(n-1)-n%2*f(n/2);}
\$\endgroup\$
  • \$\begingroup\$ How does n<3?:(...) work? \$\endgroup\$ – LegionMammal978 Jul 11 '16 at 22:16
  • 2
    \$\begingroup\$ It's a GCC extension (seems to work in clang too) that evaluates to the conditional itself if the middle expression is missing. See the relevant GCC page and this SO question for more details. \$\endgroup\$ – owacoder Jul 12 '16 at 1:51
4
\$\begingroup\$

Python 3, 67 bytes

def f(n):
 x=1,
 for i in range(n):x+=sum(x[-i//2:]),
 print(x[-1])

A function that takes input via argument and prints to STDOUT. This is a direct implementation of the definition.

How it works

def f(n):               Function with input target term index n
 x=1,                   Initialise term list x as tuple (1)
 for i in range(n):...  For all term indices in [0,n-1]...
 x[-i//2:]              ..yield the previous floor(i/2) terms...
 x+=sum(...)            ...and append their sum to x
 print(x[-1])           Print the last term in x, which is the nth term

Try it on Ideone

\$\endgroup\$
3
\$\begingroup\$

Pyth, 12 bytes

L|syM>/b2Ub1

Try it online. Test suite.

Defines a function y(n) that returns the nth Narayana-Zidek-Capell-number.

\$\endgroup\$
3
\$\begingroup\$

Mathematica, 38 bytes

If[#<4,1,2#0[#-1]-#~Mod~2#0[(#-1)/2]]&

Anonymous function. Takes 𝑛 as input and returns 𝑓(𝑛) as output. Based off of the Ruby solution.

\$\endgroup\$
  • \$\begingroup\$ There's no built in? \$\endgroup\$ – Insane Jul 11 '16 at 21:31
  • \$\begingroup\$ @Insane No, there's no built-in. \$\endgroup\$ – LegionMammal978 Jul 11 '16 at 22:02
  • \$\begingroup\$ Simply amazing! \$\endgroup\$ – Insane Jul 11 '16 at 22:07
2
\$\begingroup\$

Haskell, 34 bytes

f 1=1
f n=sum$f<$>[n-div n 2..n-1]

Usage example: f 14 -> 1308.

A direct implementation of the definition.

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

Java, 63 Bytes

int z(int n){return n<3?1:n%2>0?(2*z(n-1)-z(n/2)):(2*z(n-1));}
\$\endgroup\$
1
\$\begingroup\$

Go, 63 bytes

func f(i int) int{if(i<4){return 1};return 2*f(i-1)-i%2*f(i/2)}

Pretty much a direct port from the C answer

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

PHP, 81 bytes

This is a full program without recursion. A recursive function can be defined in 52 bytes (it might be possible to beat that) but that's just a pretty boring port of sherlock9's answer (and it errors if you ask for f(100) or more) so I'm putting up this longer and more interesting version

<?php for($i=$argv[1];$j=$i;$i--)for(;--$j*2>=$i;)$a[$j]+=$a[$i]?:1;echo$a[1]?:1;

Causes many (O[n]) notices but that's fine.

\$\endgroup\$
  • \$\begingroup\$ O(n) notices? Huh? \$\endgroup\$ – cat Jul 11 '16 at 16:25
  • \$\begingroup\$ notices are a non critical error type that don't stop execution and are commonly silenced in production environments. whenever you try to get the value of an undeclared variable or an undefined offset in an array you get a notice. This program tries to get the value of O[n] undefined offsets (and a couple of undeclared variables too) so you get O[n] notices. \$\endgroup\$ – user55641 Jul 11 '16 at 16:32
0
\$\begingroup\$

R, 55 bytes

x[1]=1;for(i in 2:10){x[i]=sum(x[i-1:floor(i/2)])};x[9]

Change 10 in the for loop and x[9] to get whichever index the user wants.

\$\endgroup\$
  • \$\begingroup\$ Here's a recursive version that is 54 bytes long: f=function(n)ifelse(n<4,1,2*f(n-1)-n%%2*f(floor(n/2))) \$\endgroup\$ – DSkoog Jul 31 '16 at 0:17
0
\$\begingroup\$

JavaScript, 54 52

f=n=>Math.round(n<3?1:2*f(n-1)-n%2*f(parseInt(n/2)))

Based on the C answer.

  • Saved 2 bytes by using parseInt instead of Math.floor
\$\endgroup\$
0
\$\begingroup\$

Maple, 46 44 bytes

`if`(n<4,1,2*f(n-1)-(n mod 2)*f(floor(n/2)))

Usage:

> f:=n->`if`(n<4,1,2*f(n-1)-(n mod 2)*f(floor(n/2)));
> seq( f(i), i = 1..10 );
  1, 1, 1, 2, 3, 6, 11, 22, 42, 84
\$\endgroup\$
0
\$\begingroup\$

R, 63 bytes

f=function(n,a=0)if(n<2)1 else{for(i in n-1:(n%/%2))a=a+f(i);a}

a=0 is added as a default because it saves me two curly brackets. Function recursively calls itself as needed.

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