18
\$\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
Improve this question
\$\endgroup\$
1
  • 13
    \$\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.
    Commented Jul 11, 2016 at 20:27

16 Answers 16

Reset to default
7
\$\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
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Stumbled across this old answer. I found a couple of saves. Firstly the trailing 1 is redundant since the argument will be one in the case it is used. Secondly, we can take the second "half" of the range from zero to n to get the same list of numbers as HĊrµṖ gets us which is ḶŒHṪ - TIO \$\endgroup\$
    – Jonathan Allan
    Commented Nov 29, 2023 at 22:19
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]}
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Surely you don't need parentheses for x%2? \$\endgroup\$
    – feersum
    Commented Jul 11, 2016 at 13:43
  • \$\begingroup\$ Well, not if you put x%2* at least. \$\endgroup\$
    – Neil
    Commented Jul 11, 2016 at 13:48
  • \$\begingroup\$ @feersum and Neil Thank you both \$\endgroup\$
    – Sherlock9
    Commented Jul 11, 2016 at 13:50
  • \$\begingroup\$ Previous question edits suggested that the formula was x<2?... this makes it much clearer thanks! \$\endgroup\$
    – Neil
    Commented Jul 11, 2016 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

Improve this answer
\$\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

Improve this answer
\$\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);}
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ How does n<3?:(...) work? \$\endgroup\$
    – LegionMammal978
    Commented Jul 11, 2016 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
    Commented Jul 12, 2016 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

Improve this answer
\$\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.

Improve this answer
\$\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.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ There's no built in? \$\endgroup\$
    – Insane
    Commented Jul 11, 2016 at 21:31
  • \$\begingroup\$ @Insane No, there's no built-in. \$\endgroup\$
    – LegionMammal978
    Commented Jul 11, 2016 at 22:02
  • \$\begingroup\$ Simply amazing! \$\endgroup\$
    – Insane
    Commented Jul 11, 2016 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.

Improve this answer
\$\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));}
Improve this answer
\$\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

Improve this 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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ O(n) notices? Huh? \$\endgroup\$
    – cat
    Commented Jul 11, 2016 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
    Commented Jul 11, 2016 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.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\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
    Commented Jul 31, 2016 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
Improve this answer
\$\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
Improve this answer
\$\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.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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